# 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{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}

Thanks a lot ! :)

## 1 Answer

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*}