1
$\begingroup$

Consider a variable c from the domain {-1,0,1}. I have the following constraint:
IF $c = 1 \Rightarrow x = 1 $ ELSE $x = 0$ How do I linearize this constraint?

$\endgroup$
3
  • $\begingroup$ As a quick fix, I think you can do x >= c, x <= c+1, x - c <= 0, assuming x is a binary variable, of course. $\endgroup$ Commented Mar 17, 2023 at 12:59
  • 1
    $\begingroup$ @J.Dionisio What you proposed forces $x=c$. $\endgroup$
    – RobPratt
    Commented Mar 17, 2023 at 13:13
  • $\begingroup$ @RobPratt Ah, of course. Sorry! $\endgroup$ Commented Mar 17, 2023 at 14:21

1 Answer 1

6
$\begingroup$

It might help to consider the contrapositives: \begin{align} x=0 &\implies c\le 0 \\ x=1 &\implies c\ge 1 \end{align} Both of these are indicator constraints, which you can linearize via big-M: \begin{align} c &\le 1x \\ -c+1 &\le 2(1-x) \end{align} Simplifying yields $$2x-1 \le c \le x,$$ which you could have also derived via $$-1(1-x)+1x \le c \le 0(1-x)+1x.$$

$\endgroup$
6
  • $\begingroup$ Thanks, I need to change my other constraints a bit to implement this, but it is possible. $\endgroup$
    – Waldo
    Commented Mar 17, 2023 at 17:08
  • $\begingroup$ @RobPratt, is it possible to relax the domain of $c$ (despite of being $c$ real or integer) to make the problem readable? (e.g. $c \in \{-1..1\}$) $\endgroup$
    – A.Omidi
    Commented Mar 18, 2023 at 7:36
  • $\begingroup$ @A.Omidi The constraints I proposed enforce $c\in[-1,0]\cup\{1\}$. $\endgroup$
    – RobPratt
    Commented Mar 18, 2023 at 13:52
  • $\begingroup$ @RobPratt, sorry for the late answer, and thanks for the clarification. Would you please, does it make any mistake to use $c \in \{-1..1\}$? As if $c$ is being integer the domain falls in {-1,0,1} and again if $c$ is being real, the questioner limited it to be {-1,0,1}. $\endgroup$
    – A.Omidi
    Commented Mar 19, 2023 at 10:39
  • $\begingroup$ @A.Omidi I don’t understand your question. The question specifies that $c\in\{-1,0,1\}$. If you relax integrality of $c$, my constraints would allow fractional values with $-1<c<0$. I think the notation $\{-1..1\}$ is ambiguous and would instead recommend using $\{-1,0,1\}$ for the finite set and $[-1,1]$ for the closed interval. $\endgroup$
    – RobPratt
    Commented Mar 19, 2023 at 14:26

Your Answer

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