5
$\begingroup$

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

Improve this question
$\endgroup$
1
7
$\begingroup$

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

Improve this answer
$\endgroup$
9
  • $\begingroup$ But the opposite is not necessarily true. I mean, A≤B does not imply Y=1. I had a look here: 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 $\endgroup$ – Clement Mar 1 '20 at 17:07
  • $\begingroup$ My suggestion about $\epsilon$ takes care of that case. $\endgroup$ – RobPratt Mar 1 '20 at 18:31
  • $\begingroup$ 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. $\endgroup$ – Clement Mar 1 '20 at 18:52
  • $\begingroup$ 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. $\endgroup$ – RobPratt Mar 1 '20 at 18:56
  • $\begingroup$ 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? $\endgroup$ – Clement Mar 2 '20 at 14:53
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ $B$ is a variable here, so your proposed constraint is nonlinear. $\endgroup$ – RobPratt Mar 11 '20 at 17:57

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.