1
$\begingroup$

I have a model that considers real values and that uses a binary variable $x$. In this model, the following conditions should apply:

\begin{equation} x= \begin{cases} 0, & \text{if}\ y > s \\ 1, & \text{otherwise}~(y \le s) \end{cases} \end{equation}

with $y \ge 0$ and $s \ge 0$.

First I tried these two restrictions:

$$ (s - y) - M x \le 0\\ (y - s) - M (1-x) \le 0 $$

where $M$ is a very large constant.

Unfortunately, if $y = s$ the binary variable can be either $1$ or $0$. It is also not possible to enforce one value by the objective function. To fix this problem, I added an very small value $\epsilon$ to the first restriction:

$(s - y) + \epsilon - M x \le 0$

This solution works, but is there a way I can model that without the $\epsilon$ value?

Improve this question
$\endgroup$
6
  • $\begingroup$ Assuming your objective is to minimize some function $f(z)$ you could minimize $f(z, x) = f(z) + (1-x)$ instead. Numerically, this should be better, however, you have to deal with some offset in your objective value. $\endgroup$
    – ttnick
    Feb 26, 2018 at 13:22
  • $\begingroup$ Do you have an upper bound on the maximum possible value of $y$? Is $s$ a constant or a variable? $\endgroup$
    – D.W. ♦
    Feb 26, 2018 at 17:47
  • $\begingroup$ Related but different (I don't think it answers your question): cs.stackexchange.com/q/67163/755 $\endgroup$
    – D.W. ♦
    Feb 26, 2018 at 17:50
  • $\begingroup$ @PHPNick, Clever idea. However, I think it has two limitations. 1. If the objective function already depends on $x$, this isn't applicable (it might change the solution). 2. If there are multiple instances of this pattern (multiple $x_i$'s and $y_i$'s), then I don't think this necessarily works (consider e.g., the case of constraints between the $x_i$'s). Do you see any way to deal with those situations? $\endgroup$
    – D.W. ♦
    Feb 26, 2018 at 18:03
  • 1
    $\begingroup$ Thanks for the helpful responses so far. Unfortunately the link you posted D.W. doesnt solve my problem. In your response im still left with the strict inequality $x_1 > x_2 - My$. The second post also offers a solution with an offset A, that i wanted to avoid. s and y are both variables. For y i have an upper bound, but this upper bound could be 0 if thats a problem. $\endgroup$
    – locomania
    Feb 27, 2018 at 7:42

0

Reset to default

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.