2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

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