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

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?

• In your example, e seems to be contained in all Y_i's. I would assume that some Y_i does not contain this element e. Also, can you explain a little bit more on "an additional parameter would be needed that would state whether a combination is impossible or not"? Jul 6, 2019 at 19:36
• @QianZhang e is contained in all sets within G1. Of course, there are other sets in which e is not contained, e.g. , $Y_1 = \{1,2,3\}$. $Y_1$ is though not in $G_1$ Jul 6, 2019 at 19:41
• @MarcoLübbecke I am trying to sum all $x_e$ found in $Y_i \in G_1$ with that I mean. $x_{e}(Y_{2}) + x_{e}(Y_{40}) + ... + x_{e}(Y_{t})$. I do not want to use the different sets as an index, since this way I will get for some combination zero variables. Jul 7, 2019 at 2:18
• @MarcoLübbecke Yes $x_e$ is a binary variable as stated above. I do know that element e belongs to the sets in group $G_1$. Another element, let us call it b belongs to the sets within group $G_2$ and so on. So yes, I do know that $x_e$ belongs to a set $Y_i \in G_1$, $x_b$ belongs to a set $Y_j \in G_2$... Jul 7, 2019 at 11:12
• @Georgios as I understand it, you would do it the way you don't want to do it, you will use the set as an index, and this is not bad, because you define the variable/set pairs only for those existing combinations. No need to worry about "zero valued variables", you simply don't define them. I may read your question wrong, but you seem to be on the right track already. Maybe you can give it a try an post your experience again here. Jul 7, 2019 at 12:50

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$$.

• You are definitely right for all elements. My goal is though to sum only for a particular element e. Jul 7, 2019 at 19:51

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}$$.

• @Georgios Please let me know if my understanding is not correct. Jul 7, 2019 at 19:59
• I believe that you are describing constant information, the set membership of a variable is a parameter, no need for variables. Apart from that, you definition exactly describes this parameter. Jul 8, 2019 at 9:39
• @OguzToragay Maybe my formulation was not clear enough. Your explanation goes to the direction I want but is not quite what I am looking for. I want to select for an element e all the decision variables x that are found in different sets $Y_i$. The decision variable does not have to be 1 the way you defined it. I think I will just have to add the set $Y_i$ as an index to the decision variable -> $x_{e,Y_i}$. Jul 8, 2019 at 11:23
• @Georgios You are right, sorry for any inconvenience. Jul 8, 2019 at 16:41
• @Marco Lübbecke, thanks for the comment and correction. Jul 8, 2019 at 16:42