# Write in ILP: If $x$ within range then $s=1$, else $0$

How can write the following function in LP:

$$s= \begin{cases} 1 & 1 \leq x \leq C \\ 0 & \text{otherwise} \end{cases}$$ where $$x$$ takes only non-negative integers and $$C$$ is some large constant integer.

I've tried using big M, and came up with conditions for $$s=1$$. \begin{align} x-M \cdot (1-s) &\leq C\\ x+M \cdot (1-s) &\geq 1 \\ \end{align} But I wonder how to force $$s=0$$ when $$x=0$$ or $$x\ge C+1$$.

• Do you want $s\in A \Rightarrow x \in B$ or $x \in B \Rightarrow s \in A$ (where $A$ and $B$ are the set of values for variables $s$ and $x$)? Jul 29 at 7:29
• Related: or.stackexchange.com/a/2632/123 Jul 29 at 7:34

Use three binary variables $$r,s,t$$ for the three intervals and impose linear constraints: $$r+s+t = 1 \\ 0r+1s+(C+1)t \le x \le 0r+Cs+Mt$$ Then \begin{align} r = 1 &\implies x = 0 \\ s = 1 &\implies 1 \le x \le C \\ t = 1 &\implies C + 1 \le x \le M \\ \end{align}
If you prefer, treat $$r$$ as a slack variable and instead impose linear constraints: $$s+t\le 1 \\ 1s+(C+1)t \le x \le Cs+Mt$$
In addition to $$s$$, add a binary variable $$u$$ and the constraint $$s + u \le 1$$. The remaining constraints would be \begin{align*} x & \le1+M(s+u)\\ x & \ge s\\ x & \ge Cu\\ x & \le C+Mu. \end{align*} If $$s=0=u$$ this reduces to $$x\le 1$$. If $$s=1$$, $$u=0$$ and the constraints reduce to $$1\le x\le C$$. Finally, if $$u=1$$, $$s=0$$ and the constraints become $$C\le x\le 1+M$$.
As always, there are boundary issues, meaning that $$s$$ is ambiguous when $$x=1$$ and when $$x=C$$. The only way to remove the ambiguity requires that you make values of $$x$$ slightly less than 1 or slightly greater than $$C$$ infeasible.
• Because $x$ is integer here, you can use $\epsilon = 1$ to avoid ambiguity. Jul 29 at 20:27
• @RobPratt Good catch -- I saw the part about $x$ integer and promptly forgot it. Jul 30 at 17:05