## Sunday, December 23, 2018

### Linearizing multiple XOR operations

I have never encountered this in a model. but nevertheless this is an interesting question.

How can we handle $y = x_1 \oplus x_2 \oplus \cdots \oplus x_n$ in a linear MIP model? Here $$\oplus$$ indicates the xor operation.

Well, when we look at $$x_1 \oplus x_2 \oplus \cdots \oplus x_n$$ we can see that this is identical to $$\sum x_i$$ being odd. A small example illustrates that:

Checking if an expression is odd can be done by seeing if it can not be expressed as $$2z$$ where $$z$$ is an integer variable. So combining this, we can do:

Linearization of $$y = x_1 \oplus x_2 \oplus \cdots \oplus x_n$$
\begin{align} & \color{DarkRed}y = \sum_i \color{DarkRed}x_i - 2 \color{DarkRed}z \\ & \color{DarkRed}y, \color{DarkRed} x_i \in\{0,1\} \\ & \color{DarkRed}z \in \{0,1,2,\dots\} \end{align}

If we want, we can relax $$y$$ to be continuous between 0 and 1. An upper bound on z can be
$z \le \left \lfloor{ \frac{n}{2} }\right \rfloor$.

#### References

1. Express XOR with multiple inputs in zero-one integer linear programming (ILP), https://cs.stackexchange.com/questions/40737/express-xor-with-multiple-inputs-in-zero-one-integer-linear-programming-ilp
2. XOR as linear inequalities, https://yetanothermathprogrammingconsultant.blogspot.com/2016/02/xor-as-linear-inequalities.html
3. A variant of the Lights Out game, https://yetanothermathprogrammingconsultant.blogspot.com/2016/01/a-variant-of-lights-out-game.html