Integer linear constraint(s) for y= x1 XOR x2 [closed]

Question

Is there any way to convert $y=x_1~ \text{XOR} ~x_2$ to linear constraints? It means we write some linear relations with:

if $x_1=x_2 =0$ or $x_1=x_2=1$ $\to$ $y=0$, else, $y=1$?

Answer 1

You can derive the desired constraints somewhat automatically via conjunctive normal form as follows: $$(\lnot x_1 \land \lnot x_2) \implies \lnot y \\ \lnot (\lnot x_1 \land \lnot x_2) \lor \lnot y \\ (x_1 \lor x_2) \lor \lnot y \\ x_1 + x_2 + (1-y)\ge 1\\ x_1 + x_2 -y \ge 0 $$ The other three constraints are similar.

Answer 2

Under the constraints $x_1,x_2,y\in\{0,1\}$, the equality $y=x_1\oplus x_2$ is equivalent to $$\begin{cases} y \geq x_1 - x_2, \\ y \geq x_2 - x_1, \\ y \leq x_1 + x_2, \\ y \leq 2 - x_1 - x_2. \end{cases}$$

Answer 3

If we consider the cube $0 \le x_1, x_2, y \le 1$ then the eight possible Boolean assignments to $x_1, x_2, y$ are the vertices of the cube. We can mark an assignment $x_1 = a, x_2 = b, y = c$ as illegal with the constraint $$\begin{pmatrix}x_1 - \tfrac12 \\ x_2 - \tfrac12 \\ y - \tfrac12\end{pmatrix} \cdot \begin{pmatrix}a - \tfrac12 \\ b - \tfrac12 \\ c - \tfrac12\end{pmatrix} < \begin{pmatrix}a - \tfrac12 \\ b - \tfrac12 \\ c - \tfrac12\end{pmatrix} \cdot \begin{pmatrix}a - \tfrac12 \\ b - \tfrac12 \\ c - \tfrac12\end{pmatrix}$$

which can be expressed as a linear constraint with integer coefficients via suitable scaling. The xor constraint can be written as four of these linear constraints.