5

Somehow I don't get it right.

I would like to model the following conditional:

If $A\le B$ then $Y=1$ otherwise $Y=0$
where $A, B$ are reals and $Y$ is binary.

I can model as follows:

$Y \cdot A \le B$ and linearise this, but then I get into trouble when $A = 0$;

In this case $Y$ can be anything but I want it to be $1$.

Adi Shavit
  • 195
  • 5
Clement
  • 2,252
  • 7
  • 13

2 Answers2

7

If $A\in[\underline{A},\overline{A}]$ and $B\in[\underline{B},\overline{B}]$, the following big-M constraints enforce $Y=1\implies A \le B$ and $Y=0\implies B \le A$, respectively: \begin{align} A - B &\le (\overline{A}-\underline{B})(1-Y)\\ B - A &\le (\overline{B}-\underline{A}) Y\\ \end{align} To disambiguate the $A=B$ case, you could introduce $\epsilon$ in the second constraint, as follows: $$B - A + \epsilon \le (\overline{B}-\underline{A}+\epsilon) Y$$

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • But the opposite is not necessarily true. I mean, A≤B does not imply Y=1.

    I had a look here:
    https://yalmip.github.io/tutorial/logicprogramming/

    they propose a solution to the problem

    IF f(x) <= 0 THEN a else not a, a is binary

    which matches my problem when setting f(x) to A-B and a to Y

     – Clement Mar 01 '20 at 17:07
  • My suggestion about $\epsilon$ takes care of that case. – RobPratt Mar 01 '20 at 18:31
  • Hello Rob Thanks for waisting your time with me. Could you please have a look in the link, I did provide? Somehow I don't get it right there: They speak about a function g(x) but they mean f(x) I suppose: Further they write
    Z1= 1 -> f(x) <= 0, a = 1 Z2=1 -> f(x) >= 0, a = 0 Is this correct? In my application I get an infeasibility, but it surely is my mistake. Does the case f(x) = 0 generate any problems? By the way my function is x1 - x2, and both are positive reals, the are supposed to model the start time of jobs.     – Clement Mar 01 '20 at 18:52
  • That link has lots of errors. The place you referenced does not disambiguate $f(x)=0$ and is unnecessarily complicated. You need only one binary variable. Look instead at the section "If a then f(x)<0," which is equivalent to its contrapositive "If f(x) >= 0 then not a." It uses $\epsilon$, just like I suggested. – RobPratt Mar 01 '20 at 18:56
  • Can you give me a hint for the magnitude of epsilon? Should it be very close to zero e.g. 1E-8 or significantly distinct from Zero e.g. 0.001? – Clement Mar 02 '20 at 14:53
  • The magnitude of epsilon really depends on the application. For your case, how far apart should two start times be to consider them to be different? – RobPratt Mar 02 '20 at 15:24
  • Here it is, where it becomes tricky. If the tasks are performed on the same unit, the second task can start after the first one has finished. So, the difference is at least the duration of the first task. But if the tasks are performed on different units, then the difference can be 0 and in my case this will occur very often. . – Clement Mar 02 '20 at 20:04
  • It sounds like you might want an additional binary variable to capture this distinction. Maybe you should start a new question about your specific business problem. – RobPratt Mar 02 '20 at 21:29
  • Hi Rob

    Thank you again. I will see how far I can come without additional help und if needed, I will do as you propose.

     – Clement Mar 03 '20 at 07:50
1

If $A$ is continuous, this logical constraint cannot be represented by a finite set of linear inequalities (see old work by Bob Jeroslow). What you can do is to relax a little.

Saying $A\le B \implies Y=1$ is the same as imposing $Y=0 \implies A > B$. If you can allow this to become $A \ge B+\epsilon$ then the constraint becomes $A \ge M\cdot Y + (B+\epsilon) (1-Y)$ where $M$ is a lower bound of $A$ ($A$ is always $\ge$).

Of course if $A$ is known, e.g., to be integer, than you can choose $\epsilon = 1$ without loss of generality.

RobPratt
  • 32,006
  • 1
  • 44
  • 84
Fabio Schoen
  • 151
  • 3