Formulation of a constraint in a MIP for an element in different Sets

Question

I have an element e $\in E$ with $E$ the set containing all elements e and $e \in Y_i$ with $Y_i \subseteq E$. Each set $Y_i$ has different attributes.

$G_j$ is a set of sets and the following holds: $ Y_i\in\ G_j $ and $\cup_j G_j = E$

Example:

$e=5$ and sets $Y_2$={5,2,7}; $Y_{40}$={5,100,7}; ...; $Y_t$={300,400,2,5} are in $G_1$ so:

$ G_1=\{Y_2, Y_{40},..., Y_t\}$

1. In the end, I want to write a sum over a decision variable, that sums all variables found in the different sets for a particular element e.

   This should look likes this -> $\sum\limits^{G_1}_{Y_i \ni e}x_e(Y_i)$ or $\sum\limits^{G_j}_{Y_i}x_{e,Y_i} \; \forall e \in E: e \in Y_i:Y_i \in G_j$

2. I want a sum over all elements within a set $Y_i$

   This should look like this -> $\sum \limits^{Y_i}_e x_{e,Y_i} \; \forall\ Y_i \in G_j: e\in Y_i $

x is a binary decision variable.

With my knowledge, I do not see how a solver could work like this.

I could have used indices for the attributes found in the sets $Y_i$. This way I would avoid using $Y_i$ as an index. That though would probably add too many unnecessary decision variables that would be set to zero, since not for all elements exists these combinations of attributes.

Is there a way to formulate such a thing?

Answer 1

Update: So, for all $j$ indexing the larger set of sets, let $M_j$ be the set of indices $i$ within $G_j$, meaning $G_j=\cup_{i\in M_j}Y_i$ (e.g., $M_1=\{2,40,\ldots,t\}$). Now define the (binary) decision variable $x_{e,i}$ (to avoid using $Y_i$). This variable only exists $\forall e\in E, i\in M_j:e\in Y_i$. You could further pre-compute $Y(e) = \{i: e\in Y_i\}$ (set of i's such that $e\in Y_i$). With the notation in place:

1. $$\sum_{i\in Y(e)}{x_{e,i}} \quad \forall e \in E$$
2. $$\sum_{e\in Y_i}{x_{e,i}} \quad \forall j=1,2,\ldots;i\in M_j$$

Old:

Let $g \in G_1$ be any of those sets $Y_i$ you listed, and first define the union $U_1 = \displaystyle\cup_{g\in G}{g}$. Now you are sure all elements contained in the sets of $G_1$ are there. Now, if you want to "write a sum over a decision variable, that sums all variables found in the different sets", it would be $\displaystyle\sum_{e\in U_1}x_e$.

Answer 2

I tried to understand your question and ended up with the following:

You want to count the number of $Y_i$ sets in each set of sets $G_j$ which include the variable $e$. If it is the right way to translate your problem, my suggestion is to define binary variables with two indices like $x_{ij}$ with the following definition:

$x_{ij}=\left\{ \begin{array}{ll} 1 & \text{if $e \in Y_i$ & $Y_i \in G_j$ }\\ 0 & \text{if $e \notin Y_i$ || $Y_i \notin G_j$} \end{array} \right. $

then you can easily sum over the binary variables $x_{ij}$.