Combining multiple binary variable combinations in sum statement

226 Views Asked by At

I have a question regarding how to formulate a constraint of an MILP.

I have 2 platforms p and v(p) which are neighbours. Depending on the state of both of these platforms a specific value is chosen. P and v(p) can either be 1 or 0. I can easily write it like that:

p*v(p)*a + (p-1)*v(p)b + p(v(p)-1)c + (p-1)(v(p)-1)*d

For only these two, i could just write my constraint down like that. But if I add a third variable, this becomes hard.

How can I write this expression as a sum statement?

1

There are 1 best solutions below

0
On

You can do this by adding variables and constraints. Suppose that your original three binary variables are $x_1,x_2,x_3$. Add a variable for each of the seven possible combinations other than $x_1=x_2=x_3=0.$ Let's call them $y_1, y_2, y_3, y_{1,2}, y_{1,3}, y_{2,3}, y_{1,2,3}.$ The value of your expression will be $a_1 y_1 + \dots + a_{1,2,3} y_{1,2,3}$, where each $a$ parameter is the expression value for the combination of $x$ values reflected in the corresponding $y$ variable.

Now we need constraints to define $y$ in terms of $x$. All the $y$ variables can either be continuous with domain $[0,1]$ or binary. The single subscript variable $y_1$ should be 1 iff $x_1 = 1$ and $x_2 = x_3 = 0,$ which we get via the following constraints: $$y_1 \le x_1\\ y_1 \le 1 - x_2\\y_1 \le 1-x_3 \\ y_1 \ge x_1 - x_2 - x_3.$$ The double subscript variable $y_{1,2}$ should be 1 iff $x_1 = 1 = x_2$ and $x_3=0$, for which we have the following constraints: $$y_{1,2} \le x_1 \\ y_{1,2} \le x_2 \\ y_{1,2} \le 1-x_3 \\ y_{1,2} \ge x_1 + x_2 - x_3 - 1.$$ For the other combinations, just permute the subscripts. Variable $y_{1,2,3}$ should be 1 iff all three $x$ variables are 1, which leads to these constraints: $$y_{1,2,3} \le x_1\\y_{1,2,3} \le x_2 \\y_{1,2,3} \le x_3 \\y_{1,2,3} \ge x_1 + x_2 + x_3 - 2.$$