2
$\begingroup$

I have $ x \in \{0,1\}$ and $y \geq 0$ and I want to model that $x=1$ iff $y>0$, is this possible while keeping the constraint linear? Thanks.

One part of the implication is easy $ y \leq Mx$. The other part I can approximate as $ \epsilon x \leq y $. Where $\epsilon$ is small and $M$ is big. But this doesn't work if $y$ is very small.

$\endgroup$
  • $\begingroup$ Your constraint handles $y>0\implies x=1$. To handle the reverse case, you want $x=1$ to be less optimal than $x=0$ when $y=0$. You can handle this by adjusting the objective function by $-Mx$ (in the case of maximisation), as it will force $x=0$ unless it is required to be positive at the optimal solution. $\endgroup$ – Daryl Apr 13 at 12:04
  • $\begingroup$ thanks, there's no other way? $\endgroup$ – lucmobz Apr 13 at 12:08
  • $\begingroup$ As you’ve observed, trying to put an upper bound on $x$ changes the range of values available for $y$. I don’t have all of my literature available to check at the moment, but the method I described is my usual approach when the remainder of the problem is linear. $\endgroup$ – Daryl Apr 13 at 12:15
1
$\begingroup$

In practice, if $y$ is computed (as opposed to a parameter that is read in and never changed), the chances are high that you will get a nonzero value (possibly even negative) when it should be zero, due to rounding error. Constraints aside, you probably should set a tolerance value $\epsilon > 0$, small but not too small, and round $y$ to $0$ any time $|y|<\epsilon$. That will let you proceed as you proposed in your question.

$\endgroup$
0
$\begingroup$

Your constraint handles y>0⟹x=1. To handle the reverse case, you want x=1 to be less optimal than x=0 when y=0. You can handle this by adjusting the objective function by −Mx (in the case of maximisation), as it will force x=0 unless it is required to be positive at the optimal solution. – Daryl

$\endgroup$

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.