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?


3 Answers 3


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.

  • $\begingroup$ 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$ $\endgroup$
    – ooo
    Jan 28, 2020 at 21:22
  • $\begingroup$ Then you'd have to formulate separate constraints in which you enforce the definition of $y$ and then use $y$ as described above. $\endgroup$ Jan 29, 2020 at 14:33
  • $\begingroup$ I didn't get it. $\endgroup$
    – ooo
    Jan 29, 2020 at 19:38
  • $\begingroup$ 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$ $\endgroup$
    – ooo
    Jan 30, 2020 at 13:57
  • $\begingroup$ @LarrySnyder610: how small could we set $\delta$ to? $\endgroup$
    – Betty
    Jun 4, 2020 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.

  • 1
    $\begingroup$ I've never tried those; that's a good suggestion. More info would certainly be welcome (maybe in a new Q&A). $\endgroup$ May 31, 2019 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$.

  • $\begingroup$ 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^+$. $\endgroup$
    – EhsanK
    Jan 17, 2020 at 1:40
  • $\begingroup$ 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$. $\endgroup$
    – RobPratt
    Jan 17, 2020 at 1:48

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.