0
$\begingroup$

How can I convert a XOR statement into linear constraints for integer programming ?

The expression is $(x_1 \geq 1)$ XOR $(x_2 \geq 1)$ where $x_1$ and $x_2$ are integer. It means that if $x_1 \geq 1$ then $x_2 = 0$ and vice versa.

I started to linearize the statement by : $(x_1 \geq 1)$ XOR $(x_2 \geq 1) = (x_1 \geq 1 \quad and \quad x_2 \leq 0) or (x_1 \leq 0 \quad and \quad x_2 \geq 1)$ but I don't know how to continue, I would like to follow the Big M mothod but I'm going around in circles...

I need it to resolve this kind of linear program where if $x_1\geq 0$ then $x_2=0$ and vice versa :

\begin{equation} \begin{aligned} \min \quad & a_1x_1 + a_2x_2 + a_3x_3\\ \textrm{s.t.} \quad & x_1 + x_2 + x_3 = 200\\ &x_1 \leq 100\\ &x_2 \leq 100\\ &x_3 \leq 100\\ &x_1 \geq 1 \quad xor \quad x_2 \geq 1 \\ &x_i \in N, \quad i \in \{1, 2, 3 \} \\ &a_i \in R, \quad i \in \{1, 2, 3 \} \\ \end{aligned} \end{equation}

Thanks a lot ! :)

$\endgroup$

1 Answer 1

1
$\begingroup$

For binary variables you could just write $x_1 = 1 - x_2$, but I see that in your case $x_1,x_2 \in \{1,2,3\}$. You can still use the same trick once you force a boolean variable $y_i$ to be 1 if and only if $x_i \ge 1$:

$$ \begin{align*} 3 y_1 &\ge x_1 \\ y_1 &\le x_1 \\[6pt] 3 y_2 &\ge x_2 \\ y_2 &\le x_2 \\[6pt] y_1 &= 1-y_2 \\[6pt] y_1, y_2 &\in \{0,1\} \end{align*} $$

$\endgroup$
0

Your Answer

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

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