Casting the truth value of an inequality to a boolean

Question

The problem I am trying to solve is very similar to this one or this other one, except that I would not necessarily want to limit it to integer variables (but it could be a start if nothing else is possible).

I have an expression $d = x_1 - x_2 - w_2$, where:

$0 \le x_1 \le W - w_1$
$0 \le x_2 \le W - w_2$
$W > 0$
$0 \le w_1 \le W$
$0 \le w_2 \le W$

I want to define a binary (boolean) variable $b$ such that:

$d \ge 0 \implies b = 1$
$d < 0 \implies b = 0$

It seemed to me that this solution or this other one should work, but then I am not sure how I would encode a constraint like $U b - d > 0$ in a linear program, given that I can only use $\le$ or $\ge$.
Should I use $\ge$ with a small $\epsilon$ added to the right hand side?

Then I am also struggling with the upper and lower bounds, but first I would like to understand if this approach is valid at all.

EDIT based on Rob Pratt's reply, trying* to write out a method by which I could have figured this out.

(trying* = as in: if I am writing any nonsense, please do let me know)

First for the case where $d$ is an integer, which implies that $d < 0$ can be replaced by $d \le -1$.

Suppose the two constraints I need are linear functions of $d$ and $b$.

$(1) Ad + Bb + C \ge 0$
$(2) A'd + B'b + C' \ge 0$

If I set $b = 0$ for the first constraint, I want it to reduce to $d \le -1$. Thus:

$(1) Ad + C \ge 0$
$d \le -1 \iff -d - 1 \ge 0$
$\implies A=C=-1$

If I set $b = 1$ for the second constraint, I want it to reduce to $d \ge 0$. Thus:

$(2) A'd + B' + C' \ge 0$
$d \ge 0$
$\implies A' = 1, B' + C' = 0$

So we now have:

$(1) -d + Bb -1 \ge 0$
$(2) d + B'b - B' \ge 0$

These two constraints need to remain true in the complementary cases of $b$, i.e. the first one when $b=1$:

$(1) -d + B -1 \ge 0$
$d \le B -1$

which is always true if $B-1$ is an upper bound $U$ for $d$, i.e. $B = U+1$.

And the second one when $b=0$:

$(2) d - B' \ge 0$
$d \ge B'$

which is always true if $B'$ is a lower bound $L$ for $d$.

Overall, after substitution and some rearrangement of signs:

$(1) d - (U+1)b +1 \le 0$
$(2) d - L(1- b) \ge 0$

Checking this in Excel seems to work:

Repeating the same procedure for the case where $d$ is continuous, the only change being that $d < 0$ is replaced by $d \le -\epsilon$, with $\epsilon$ being a very small real positive value.
The second constraint is not affected.

If I set $b = 0$ for the first constraint, I want it to reduce to $d \le -\epsilon$. Thus:

$(1) Ad + C \ge 0$
$d \le -\epsilon \iff -d - \epsilon \ge 0$
$\implies A=-1, C=-\epsilon$

So we now have:

$(1) -d + Bb -\epsilon \ge 0$
$(2) d + B'b - B' \ge 0$

These two constraints need to remain true in the complementary cases of $b$, i.e. the first one when $b=1$:

$(1) -d + B -\epsilon \ge 0$
$d \le B -\epsilon$

which is always true if $B-\epsilon$ is an upper bound $U$ for $d$, i.e. $B = U+\epsilon$.

Overall:

$(1) d - (U+\epsilon)b +\epsilon \le 0$
$(2) d - L(1- b) \ge 0$

which seems equivalent to Rob Pratt's answer, and also seems to work with some numerical values in Excel:

Perhaps one more thing that I need to figure out is why $L$ needs to be negative for the second constraint to work correctly.
Of course I understand that if $L$ is positive, the condition $d < 0$ can never be true; still, something does not convince me about it.

Answer 1

Equivalently, you want to enforce the contrapositives \begin{align} b=0 &\implies d<0 \\ b=1 &\implies d\ge 0 \end{align} For $d<0$, rewrite as $d\le -\epsilon$ for some positive constant tolerance $\epsilon$. If $d$ is an integer variable, you can take $\epsilon=1$. Some solvers support such “indicator constraints” directly. Otherwise, you can use a big-M formulation as follows, where $\underline{d}$ and $\bar{d}$ are constant lower and upper bounds on $d$, respectively: \begin{align} d + \epsilon &\le (\bar{d} + \epsilon) b \tag1\label1\\ -d &\le (-\underline{d})(1-b) \tag2\label2 \end{align}

• If $b=0$, then \eqref{1} enforces $d \le -\epsilon$ and \eqref{2} enforces the redundant $d \ge \underline{d}$.
• If $b=1$, then \eqref{2} enforces $d \ge 0$ and \eqref{1} enforces the redundant $d \le \bar{d}$.