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?

$\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

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.