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

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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