# Restriction for greater than constraint in linear programming

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

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

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?

• 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. Feb 26, 2018 at 13:22
• Do you have an upper bound on the maximum possible value of $y$? Is $s$ a constant or a variable?
– D.W.
Feb 26, 2018 at 17:47
• Related but different (I don't think it answers your question): cs.stackexchange.com/q/67163/755
– D.W.
Feb 26, 2018 at 17:50
• @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?
– D.W.
Feb 26, 2018 at 18:03
• 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. Feb 27, 2018 at 7:42