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