Boolean variable true iff equation is satisfied in ILP

Question

Assuming $y$ is a boolean variable in an ILP program (that is $y \in Z$, s.t. $0 <= y <= 1$) and $x_1$, $x_2$ are bounded integer variables between $0$ and $M$. I want to encode the following high level constraint:

$$y = 1 \iff x_1 \le x_2$$

So far I've got this:

$$x_1 \le x_2 + (M+1)y$$

This enforces that whenever $x_1 > x_2$ is true, $y$ must be $1$ or the equation won't hold. However, if $x_1 \le x_2$, nothing is restricting $y$ and thus could either be $0$ or $1$.

What other equation could I add in order to encode the constraint?

Answer 1

You can do this by introducing the two inequalities

$$x_1 \le x_2 + M (1-y)$$

and

$$x_1 > x_2 - M y.$$

The former encodes the requirement $y=1 \implies x_1 \le x_2$ (you can see that if $y=1$, then the $M(1-y)$ term disappears; if $y=0$, then $M(1-y)$ becomes something huge and the inequality is automatically satisfied). The latter encodes the requirement $y=0 \implies x_1 > x_2$ (for similar reasons).

Hopefully this gives you an idea how to handle other kinds of implications as well, should they arise. Basically, multiply by something big, and add it/subtract it somewhere.

Answer 2

You could add a constant $0<A<M$ and then you add this constraint:

$$A-y(A+M)\leqslant x_1-x_2\leqslant M(1-y).$$

If $y=1$ then you are left with

$$-M\leqslant x_1-x_2\leqslant 0,$$ which says that $x_1\leqslant x_2$.

And if $y=0$ then you will be left with

$$A\leqslant x_1-x_2\leqslant M,$$ which says that $x_1>x_2$ (since $0<A<M$).

Answer 3

Look into indicator constraints and SOS constraints. While you can define the target relations linearly as other answers have explained, special constraints can be handled more efficiently by the IP solver.

If you decide to implement the constraints directly as described by the other answer, try to use the smallest M possible, and consider lowering the integrality tolerance if your result is not correct. Also, avoid strict inequalities, they are ambiguous in the context of floating point arithmetic.

Using indicator constraints:

$x_1\le x_2 \leftarrow y=1$

$x_2\ge x_1 +1\leftarrow y=0$

The second constraint is equivalent to $x_2>x_1$ for integers, if you want $x_2\ge x_1$ simply drop the 1.