Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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