# In an integer program, how I can force a binary variable to equal 1 if some condition holds?

Suppose we have a binary or continuous variable $$x$$, a binary variable $$y$$, and a constant $$b$$, and we want to enforce a relationship like

If $$x \gtreqless b$$, then $$y = 1$$.

How can we write this using one or more linear constraints?

If $$x$$ is binary: Then the "if" condition really means either "$$x = 0$$" or "$$x=1$$".

To enforce "if $$x=0$$ then $$y=1$$": use $$y \ge 1-x.$$ To enforce "if $$x=1$$ then $$y=1$$": use $$y \ge x.$$

If you want to require that $$y=1$$ if and only if the condition holds, then replace the $$\ge$$s above with $$=$$s.

If $$x$$ is continuous: In this case, numerical inaccuracy might produce errors, so be prepared for $$y$$ to be set incorrectly if $$x$$ is close to but on the “wrong” side of $$b$$. To avoid this, you can increase or decrease $$b$$ a little bit to provide some buffer.

To enforce "if $$x < b$$ then $$y=1$$": $$b - x \le My,$$ where $$M$$ is a large constant. The logic is that if $$b - x > 0$$, then $$y$$ must equal 1, and otherwise it may equal 0.

To enforce "if $$x > b$$ then $$y=1$$": $$x - b \le My,$$ with similar logic as above.

To enforce "if $$x = b$$ then $$y=1$$": This one is tricky. I'm not sure my approach is the easiest. (Anyone have a better solution?) We really can't check for $$x=b$$, but we can check for $$b-\delta \le x \le b+\delta$$ for some small $$\delta > 0$$. To do this, we introduce two new binary decision variables.

Let $$z_1$$ be a binary variable that equals 1 if $$x > b - \delta$$, equals 0 if $$x < b - \delta$$, and could equal either if $$x = b - \delta$$. Enforce this definition by adding the following constraints: \begin{alignat}{2} Mz_1 & \ge x - b + \delta\tag1 \\ M(1-z_1) & \ge b - x - \delta\tag2 \end{alignat} The logic is:

• If $$x > b - \delta$$, then (1) forces $$z_1=1$$ and (2) has no effect.
• If $$x < b - \delta$$, then (2) forces $$z_1=0$$ and (1) has no effect.
• If $$x = b - \delta$$, then (1) and (2) have no effect; $$z_1$$ could equal either 0 or 1.

Next, introduce a second binary variable $$z_2$$, which equals 1 if $$x < b + \delta$$, equals 0 if $$x > b + \delta$$, and could equal either if $$x = b + \delta$$. Introduce the following constraints: \begin{alignat}{2} Mz_2 & \ge b - x + \delta\tag3 \\ M(1-z_2) & \ge x - b - \delta\tag4 \end{alignat} The logic is similar:

• If $$x < b + \delta$$, then (3) forces $$z_2=1$$ and (4) has no effect.
• If $$x > b + \delta$$, then (4) forces $$z_2=0$$ and (3) has no effect.
• If $$x = b + \delta$$, then (3) and (4) have no effect; $$z_2$$ could equal either 0 or 1.

From constraints (1)-(4), we can say that if $$z_1=z_2=1$$, then $$b - \delta \le x \le b + \delta$$. Therefore, we can enforce "if $$b - \delta \le x \le b + \delta$$ then $$y=1$$" using: $$y \ge z_1 + z_2 - 1.$$

Note: If your model is relatively large, i.e., it takes a non-negligible amount of time to solve, then you need to be careful with big-$$M$$-type formulations. In particular, you want $$M$$ to be as small as possible while still enforcing the logic of the constraints above.

• In the first part where $x$ is binary, what if I have 2 or more binary variable that leads to the decision of $y$ like $x$ and $z$ when $x=1 \wedge z = 1$ then $y = 1$
– ooo
Jan 28 '20 at 21:22
• Then you'd have to formulate separate constraints in which you enforce the definition of $y$ and then use $y$ as described above. Jan 29 '20 at 14:33
• I didn't get it.
– ooo
Jan 29 '20 at 19:38
• Lets say I have 4 binary variable $a,b,c,d$ if all $a,b,c,d = 1$ the $x = 1$ else $x =0$, then can I write $x \ge 3 - a+b+c+d$
– ooo
Jan 30 '20 at 13:57
• @LarrySnyder610: how small could we set $\delta$ to? Jun 4 '20 at 17:39

Rather than linearising the logical constraint, I would try the logical constraints built in a solver. Gurobi and SCIP both have indicator constraints.

My colleague works with these a lot and he’s finding the indicator constraints in Gurobi perform worse than big-M. He’s in contact with the Gurobi developers so I might be able to get more info if there’s interest.

• I've never tried those; that's a good suggestion. More info would certainly be welcome (maybe in a new Q&A). May 31 '19 at 15:36

To model $$x=b \implies y=1$$, where $$L \le x \le U$$, you can do the following: \begin{align} L y^- + b y + (b+\delta)y^+ \le x &\le (b-\delta) y^- + b y + U y^+\\ y^- + y + y^+ &= 1 \\ y^-, y, y^+ &\in \{0,1\} \end{align} In fact, this formulation also enforces the converse $$y=1 \implies x=b$$.

• If we assume $L=b-\delta$ and $U=b+\delta$, then the first constraint is essentially: $L y^- + b y + Uy^+ \le x \le L y^- + b y + U y^+$ or $x = L y^- + b y + U y^+$.
– EhsanK
Jan 17 '20 at 1:40
• True, but the idea here is that $\delta>0$ is small, so those assumptions on $L$ and $U$ would imply that $x$ is essentially constant. The more useful setting would be when $L\ll b\ll U$. Jan 17 '20 at 1:48