I have an integer linear program with variables $x_1,\dots,x_n$. I have an inequality $a_1 x_1 + \dots + a_n x_n \ge b$ that I care about; it may or may or not hold.

I want to introduce a boolean variable $y$, with the intent that $y=1$ if this inequality holds or $y=0$ if it doesn't. How can I write linear inequalities to constrain $y$ to take this value?

All of $a_1,\dots,a_n,b$ are constants. I know upper and lower bounds for all of the $x_i$'s.

  • $\begingroup$ What about adding this post into the duplicate list of this post? $\endgroup$
    – xskxzr
    Mar 2, 2019 at 5:34
  • $\begingroup$ @xskxzr, good idea! Done. $\endgroup$
    – D.W.
    Mar 2, 2019 at 6:19
  • $\begingroup$ cs.stackexchange.com/q/67163/755 $\endgroup$
    – D.W.
    Mar 16, 2019 at 6:41

1 Answer 1


Add the inequalities

$$\begin{align*} a_1 x_1 + \dots + a_n x_n &\ge b - M (1-y)\\ a_1 x_1 + \dots + a_n x_n &< b + M y, \end{align*}$$

where $M$ is chosen sufficiently large.

Why does this work? If $y=1$, then the first inequality forces $a_1 x_1 + \dots + a_n x_n \ge b$ to hold. If $y=0$, then the second inequality forces $a_1 x_1 + \dots + a_n x_n < b$ to hold, i.e., $a_1 x_1 + \dots + a_n x_n \ge b$ to be false.

How large does $M$ need to be? If the $x_i$'s are zero-or-one variables, then it suffices to take $M$ to be at least $\max(b,a_1+\dots+a_n-b+1)$. In general, if you have upper and lower bounds for each $x_i$, you can derive how large $M$ needs to be.


Your Answer

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

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