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

  • $\begingroup$ 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$)? $\endgroup$
    – Kuifje
    Commented Jul 29, 2021 at 7:29
  • $\begingroup$ Related: or.stackexchange.com/a/2632/123 $\endgroup$
    – TheSimpliFire
    Commented Jul 29, 2021 at 7:34

2 Answers 2


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.

  • 1
    $\begingroup$ Because $x$ is integer here, you can use $\epsilon = 1$ to avoid ambiguity. $\endgroup$
    – RobPratt
    Commented Jul 29, 2021 at 20:27
  • $\begingroup$ @RobPratt Good catch -- I saw the part about $x$ integer and promptly forgot it. $\endgroup$
    – prubin
    Commented Jul 30, 2021 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.