3
$\begingroup$

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

$\endgroup$
2
  • $\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
    Jul 29 at 7:29
  • $\begingroup$ Related: or.stackexchange.com/a/2632/123 $\endgroup$
    – TheSimpliFire
    Jul 29 at 7:34
5
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

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

Your Answer

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

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