2
$\begingroup$

I am formulating a MILP in which there is a continuous variable x and a binary variable $y$.

In the program formulation there are the following constraints: $Ay\leq x \leq By$ (with $0\leq A\leq B$). The idea is that $y=0$ if and only if $x=0$ and $y=1$ if and only if $x>0$ (this is used in other constraints).

However it may happen that $A=0$, in which case $y$ is not constrained to be $0$ when $x=0$. I've thus reformulated the left-hand-side constraint as $Ay\leq x$ if $A > 0$ and $0.1y\leq x$ otherwise. The $0.1$ factor is however arbitrary and has been chosen because in implementations it produced better results than other candidates (such as $10^{-2}$ and lower).

Still I'm afraid that this factor might depend on the scale of other parameters in the program, and I wondered whether there is a more robust way to implement $(x=0) \Rightarrow (y=0)$.

$\endgroup$
2
  • $\begingroup$ I think that there is a little error in your third sentence. It should be $y=1$ if and only if $x=0$. Can you please check that? $\endgroup$
    – PeterD
    Mar 22, 2022 at 13:51
  • $\begingroup$ @Pedrinho if $y=1$ then $Ay\leq x$ implies $x>0$, and on the contrary if $x\leq By$ then $x>0$ implies $y=1$. So its $y=1$ if and only if $x=1$ $\endgroup$
    – Meth
    Mar 22, 2022 at 13:53

1 Answer 1

5
$\begingroup$

Equivalently, you want to enforce the contrapositive $y = 1 \implies x > 0$. The standard approach is to introduce a small constant tolerance $\epsilon > 0$ and enforce $y = 1 \implies x \ge \epsilon$ via big-M constraint $$\epsilon - x \le M(1-y).$$ With $M = \epsilon - 0$, the constraint reduces to $\epsilon y \le x$, as you had obtained. Alternatively, you can use an indicator constraint, but you will still need $\epsilon$.

$\endgroup$
6
  • $\begingroup$ I don't understand the role of $M$ here, since $x$ in nonnegative. $M=1$ yields $y\leq x + 1-\epsilon$ with also yields $x=0 \Rightarrow y=0$. Might question would be why is $y\leq x + 1-\epsilon$ better than $\epsilon y \leq x$ ? $\endgroup$
    – Meth
    Mar 22, 2022 at 15:04
  • $\begingroup$ PS: Numerical simulations also seem to be sensitive to the choice of $\epsilon$ for this additive formulation constraint, $0.1$ and $0.01$ seem to produce the desirable outcome but not $0.001$. $\endgroup$
    – Meth
    Mar 22, 2022 at 15:22
  • 1
    $\begingroup$ The choice of $\epsilon$ in Rob's formulation is indeed subject to what else is going on in the model (so, as you put it, dependent on other parameters), and sadly that is largely unavoidable. $\endgroup$
    – prubin
    Mar 22, 2022 at 16:03
  • 1
    $\begingroup$ Smaller $M$ is better. You want it to be an upper bound on the LHS when $y=0$. Because $0$ is a lower bound on $x$, take $M=\epsilon-0=\epsilon$. $\endgroup$
    – RobPratt
    Mar 22, 2022 at 16:09
  • $\begingroup$ Okay so your answer is that my initial formulation was correct? Sorry I got confused. $\endgroup$
    – Meth
    Mar 22, 2022 at 17:21

Your Answer

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

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