Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
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$.
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.
