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

| improve this answer | |
$\endgroup$
  • $\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$ – anoop Jan 28 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$ – LarrySnyder610 Jan 29 at 14:33
  • $\begingroup$ I didn't get it. $\endgroup$ – anoop Jan 29 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$ – anoop Jan 30 at 13:57
  • $\begingroup$ @LarrySnyder610: how small could we set $\delta$ to? $\endgroup$ – Betty Jun 4 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.

| improve this answer | |
$\endgroup$
  • 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$ – LarrySnyder610 May 31 '19 at 15:36
4
$\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$.

| improve this answer | |
$\endgroup$
  • $\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 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 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.