8
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the helpful suggestions! Can you elaborate on how SOS constraints are helpful/useful in this particular situation? $\endgroup$ – D.W. Dec 10 '16 at 1:21
  • $\begingroup$ I added an example with indicator constraints. For SOS it is more complicated and you have to introduce additional variables, so you may end up not gaining much by using them. I think the only aspect to be careful about here are the numerical issues that can arise using the formulations proposed by others, and how to alleviate them. If you have access to a solver with indicator constraints, then try it that way as the solver can branch on them directly, or dynamically modify the big-M value. $\endgroup$ – Septimus G Dec 10 '16 at 2:51

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.