Linear programming, Checking a constraint based on condition

Question

I have a constraint $X \ge Y$ in a Linear programming formulation, where both $X$ and $Y$ are binary. I want to check this constraint on a condition like:

if (Y==1)
 then check the constraint
else
 Don't care about the constraint

How to do it.

• adrianN: Check page 7
• drzbir: You do it by introducing a large number, say $M,ドル and writ $X+(1-Y)M\geqslant Y$.
• drzbir: If $Y=1$ then $X$ must be greater than or equal to 1ドル$ and since $X$ is binary, then you must have that $X=1$. So there is no need to introduce a large number $M$. You can simply write $X\geqslant Y$. In case $Y=1,ドル you get $X=1$ and in case $Y=0,ドル you have no restriction on $X$.
• D.W.: I don't think this is a duplicate of cs.stackexchange.com/q/67459/755. That other question asks about if Y==1: X=1 else: X=0. That's a different situation. The solution listed for the other question doesn't solve this question.

Answer 1

If $X$ and $Y$ are zero-or-one (binary) integer variables, then this is encoded as

$$X \ge Y.$$

Why does this work? If $Y=1,ドル then this enforces the constraint $X \ge Y,ドル as you wanted. If $Y=0,ドル this enforces the constraint $X \ge 0,ドル i.e., it doesn't impose any rstrictions on $X,ドル which is also as you wanted.

In general, conditional constraints can be handled using the techniques found on page 7 of AIMMS Modeling Guide - Integer Programming Tricks, which is a helpful tutorial on how to encode constraints in integer programming. Thanks to @adrianN for pointing to that resource.

You can also take a look at https://cs.stackexchange.com/a/12118/755 and at Formulating Integer Linear Programs: A Rogues' Gallery for other techniques and practice problems.