3

I am trying to use a binary variable based on an inequality. The value of binary variable $q $ is 1 or 0 based on the following equation.

[ $q $ = \begin{cases} 0,& \text{if } b \geq \pi ,\\ 1, & \text{otherwise} \end{cases}

Here, b and $\pi$ are real numbers. Sample value b = 20 , $\pi$ = 30.

I have tried to represent this by:

\begin{equation} q \geq \dfrac { (\pi - b )} {M} \end{equation}

\begin{equation} q \leq 1 + \dfrac { (\pi - b )} {M} \end{equation}

By using these two equations I am able to cover the cases for when $b > \pi $ and when $b < \pi $. Unfortunately I am unable to set $q$ as 0 when $b=q$ without violating other conditions.

Danish Shaikh
  • 33
  • 3
  • Cross-posted: https://math.stackexchange.com/questions/4473882/disjunctive-constraint-logical-constraints-using-binary-variable-to-replace-a – RobPratt Jun 16 '22 at 19:00

1 Answers1

2

The usual approach to this requires that $b$ be bounded, say $L \le b \le U$ for some constants $L$ and $U.$ You can come close to what you want with the following: $$b \ge \pi (1-q) + L q$$ $$b \le \pi q + U (1-q).$$ If $b > \pi,$ the second constraint forces $q=0.$ If $b < \pi,$ the first constraint forces $q=1.$ The tricky part comes when $b=\pi,$ in which case $q$ can be either 0 or 1. Because you cannot enforce a strict inequality in a MIP model, if you can't accept the ambiguity when $b=\pi$ then you can change the second constraint to $$b \le (\pi - \epsilon) q + U (1-q),$$ where $\epsilon > 0$ is a small constant. Now $$b\ge \pi \implies q=0,$$ $$b \le \pi-\epsilon \implies q = 1,$$ and $\pi - \epsilon < b < \pi$ is forbidden.

prubin
  • 39,078
  • 3
  • 37
  • 104
  • Thank You for your response. This solved the problem. The Lower Bound must be greater than both b and \pi to work , and the Upper Bound must be higher than both to work. Am I right? – Danish Shaikh Jun 16 '22 at 12:37
  • I assume you meant "less" rather than "greater" for the lower bound, in which case you are right, with the following qualification. If $L > \pi$ or $U < \pi,$ $q$ is a constant and can be eliminated from the model. – prubin Jun 16 '22 at 15:15
  • yes , thank you for the response. What if both b and $\pi$ are decision variables , is there any way to remove the non-linearity to model the binary variable q? i.e. model the binary variable q in a linear fashion to represent the inequality b $\geq \pi$ ? – Danish Shaikh Jun 17 '22 at 14:19
  • 1
    You can linearize the product $\pi q$ with additional constraints. This is a FAQ on this forum. See, for instance, the accepted answer to https://or.stackexchange.com/questions/6028/mixed-integer-optimization-with-bilinear-constraint. – prubin Jun 17 '22 at 15:06
  • Thank you for your quick reply Professor , I was able to solve it :) You have been a great help ! – Danish Shaikh Jun 17 '22 at 22:42