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$
  • $\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 '18 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 '18 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 '18 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 '18 at 18:03
  • $\begingroup$ Is $s$ a variable or a given parameter? $\endgroup$ – Rodrigo de Azevedo Feb 27 '18 at 7:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.