Integer Programming Conditional Constraints

Question

I have a set of integer $\{0,1\}$ variables $x_1$,$y_1$,$x_2$,$y_2$,$x_3$,$y_3$,$x_4$,$y_4$

I want a conditional constraint such that if any of the $x$ variables is equal to 1, I want the sum of the subsequent $y$ variables to be $2$.

For example

The objective function is just the sum of all the variables. There are additional constraints such as: $x_1+x_2+x_3+x_4=2$ and $y_1+y_2+y_3+y_4=2$.

The solution here would be: $1 0 1 0 0 1 0 1$

Kuifje · Accepted Answer · 2015-11-20 17:35:05Z

1

Such constraints are called disjunctive constraints. You can proceed as follows (for your constraint 1.):

$$ y_2+y_3+y_4\le2+(1-x_1)\quad y_2+y_3+y_4\ge2-2(1-x_1), $$

This way, if $x_1=1$, you have

$$ y_2+y_3+y_4\le2 \quad y_2+y_3+y_4\ge2, $$

which is equivalent to $y_2+y_3+y_4=2$. And if $x_1=0$, you have

$$ y_2+y_3+y_4\le2+1=3\quad y_2+y_3+y_4\ge2-2=0, $$

which will always be satisfied since variables are boolean.

answered Nov 20, 2015 at 14:38

Kuifje

9,8622 gold badges18 silver badges39 bronze badges

user1234 · Accepted Answer · 2015-11-22 08:55:22Z

0

I have figured out the answer to this. The constraints:

can also be formulated as:

Hence the constraints can be written as such:

Where $M$ is a very large integer.

answered Nov 22, 2015 at 8:55

user1234

711 silver badge9 bronze badges

2 Answers 2