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?
$\begingroup$
$\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$– J. DionisioMar 17 at 12:59
-
1$\begingroup$ @J.Dionisio What you proposed forces $x=c$. $\endgroup$– RobPrattMar 17 at 13:13
-
$\begingroup$ @RobPratt Ah, of course. Sorry! $\endgroup$– J. DionisioMar 17 at 14:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
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.$$
-
$\begingroup$ Thanks, I need to change my other constraints a bit to implement this, but it is possible. $\endgroup$– WaldoMar 17 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.OmidiMar 18 at 7:36
-
$\begingroup$ @A.Omidi The constraints I proposed enforce $c\in[-1,0]\cup\{1\}$. $\endgroup$– RobPrattMar 18 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.OmidiMar 19 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$– RobPrattMar 19 at 14:26