1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Check page 7 $\endgroup$ – adrianN Dec 19 '16 at 9:32
  • $\begingroup$ You do it by introducing a large number, say $M$, and writ $X+(1-Y)M\geqslant Y$. $\endgroup$ – drzbir Dec 19 '16 at 13:26
  • $\begingroup$ 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$. $\endgroup$ – drzbir Dec 19 '16 at 15:36
  • $\begingroup$ 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. $\endgroup$ – D.W. Dec 19 '16 at 15:39
2
$\begingroup$

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.

$\endgroup$

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.