0
$\begingroup$

I would like to represent the following constraint as MILP constraint where $x \in [a, b]$ with fixed $a, b \in \mathbb{R}$ and $y \in \lbrace 0, 1 \rbrace$.
$(x = 0 \wedge y = 1) \vee (x \neq 0 \wedge y = 0)$
A simple approach is to write the above constraint as
$(x \leq 0 \wedge x \geq 0 \wedge y \leq 1 \wedge y \geq 1) \vee (x < 0 \wedge y \leq 0 \wedge y \geq 0) \vee (x > 0 \wedge y \leq 0 \wedge y \geq 0)$
To avoid strict inequalities we can reformulate for a sufficiently small $\epsilon > 0$ as follows
$(x \leq 0 \wedge x \geq 0 \wedge y \leq 1 \wedge y \geq 1) \vee (x \leq -\epsilon \wedge y \leq 0 \wedge y \geq 0) \vee (x \geq \epsilon \wedge y \leq 0 \wedge y \geq 0)$
Now for each conjunction we introduce one binary variable, i.e. $b_1, b_2, b_3 \in \lbrace 0, 1 \rbrace$ and we apply big-M. The first conjunction turns into
$x \leq 0 + M (1 - b_1)$
$x \geq 0 - M (1 - b_1)$
$y \leq 1 + M (1 - b_1)$
$y \geq 1 - M (1 - b_1)$
Similarly for the other conjunctions. Adding the constraint $b_1 + b_2 + b_3 \geq 1$ completes the translation to MILP.

Having to introduce $\epsilon$ is not nice as it may cause numerical problems with solvers. Is there a MILP formulation of the above constraint that avoids $\epsilon$ and if not why can't there be such a formulation?
Moreover, I wonder if $\epsilon$ can be avoided if quadratic constraints are permitted. Also if not, why does it not help. Thanks for any insights.

$\endgroup$

1 Answer 1

2
$\begingroup$

If you're solving this problem numerically (using floating point numbers), $x > 0$ really means $x \geq \epsilon$ where $\epsilon$ is the next representable floating-point number on the number line for the given precision, in the increasing direction.

If you think about it, floating point numbers are essentially a discrete approximation to real numbers, therefore strict inequalities can only be approximated. Therefore in numerical optimization, one cannot directly formulate constraints with $\gt, \lt$ or $\neq$. There is always an $\epsilon$ involved.

As for $\epsilon$ not being numerically nice, in theory yes. But in practice that rarely happens if one is careful to avoid catastrophic cancellations. Also in many applications $\epsilon$ is chosen to be the numerical tolerance (which is usually many orders of magnitude larger than the machine epsilon).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.