XOR Statement in integer programming 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 &amp; a_1x_1 + a_2x_2 + a_3x_3\\
\textrm{s.t.} \quad &amp; x_1 + x_2 + x_3 = 200\\
  &amp;x_1 \leq 100\\
  &amp;x_2 \leq 100\\
  &amp;x_3 \leq 100\\
  &amp;x_1 \geq 1 \quad xor \quad x_2 \geq 1 \\
  &amp;x_i \in N, \quad i \in \{1, 2, 3 \}   \\
  &amp;a_i \in R, \quad i \in \{1, 2, 3 \}   \\
\end{aligned}
\end{equation}
Thanks a lot ! :)
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 &amp;\ge x_1 \\
y_1 &amp;\le x_1 \\[6pt]
3 y_2 &amp;\ge x_2 \\
y_2 &amp;\le x_2 \\[6pt]
y_1 &amp;= 1-y_2 \\[6pt]
y_1, y_2 &amp;\in \{0,1\}
\end{align*}
$$