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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Check page 7 $\endgroup$
    – adrianN
    Dec 19, 2016 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, 2016 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, 2016 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, 2016 at 15:39

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.