29
$\begingroup$

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?

$\endgroup$
1

3 Answers 3

31
$\begingroup$

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.

$\endgroup$
5
  • $\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
12
$\begingroup$

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.

$\endgroup$
1
  • 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
6
$\begingroup$

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

$\endgroup$
2
  • $\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