5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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"? $\endgroup$ – Qian Zhang Jul 6 '19 at 19:36
  • $\begingroup$ @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$ $\endgroup$ – Georgios Jul 6 '19 at 19:41
  • 1
    $\begingroup$ @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. $\endgroup$ – Georgios Jul 7 '19 at 2:18
  • 1
    $\begingroup$ @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$... $\endgroup$ – Georgios Jul 7 '19 at 11:12
  • 1
    $\begingroup$ @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. $\endgroup$ – Marco Lübbecke Jul 7 '19 at 12:50
5
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ You are definitely right for all elements. My goal is though to sum only for a particular element e. $\endgroup$ – Georgios Jul 7 '19 at 19:51
1
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ @Georgios Please let me know if my understanding is not correct. $\endgroup$ – Oguz Toragay Jul 7 '19 at 19:59
  • 1
    $\begingroup$ 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. $\endgroup$ – Marco Lübbecke Jul 8 '19 at 9:39
  • 1
    $\begingroup$ @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}$. $\endgroup$ – Georgios Jul 8 '19 at 11:23
  • $\begingroup$ @Georgios You are right, sorry for any inconvenience. $\endgroup$ – Oguz Toragay Jul 8 '19 at 16:41
  • 1
    $\begingroup$ @Marco Lübbecke, thanks for the comment and correction. $\endgroup$ – Oguz Toragay Jul 8 '19 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.