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
- 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
- XOR as linear inequalities, https://yetanothermathprogrammingconsultant.blogspot.com/2016/02/xor-as-linear-inequalities.html
- A variant of the Lights Out game, https://yetanothermathprogrammingconsultant.blogspot.com/2016/01/a-variant-of-lights-out-game.html
I was trying to model these in a nice problem, where a set of lamps are turned on and off by a set of switches. Each switch commands a given subset of lamps and a lamp is commanded by several switches of course. Then, a lamp is on iff an odd number of its switches are activated, and the goal is to maximize the number of lamps that are switched on. I have used the formulation on very large instance (1000 lights and 300 switches) but as we might expect, the linear relaxation provides poor bounds. It's better to solve linear systems over the field GF(2).
ReplyDeleteNote also that these could be generalized into "modulo p" constraints, by replacing 2 with p.
ReplyDelete