How can we handle y=x1⊕x2⊕⋯⊕xn in a linear MIP model? Here ⊕ indicates the xor operation.
Well, when we look at x1⊕x2⊕⋯⊕xn we can see that this is identical to ∑xi 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=x1⊕x2⊕⋯⊕xn |
---|
y=∑ixi−2zy,xi∈{0,1}z∈{0,1,2,…} |
If we want, we can relax y to be continuous between 0 and 1. An upper bound on z can be
z≤⌊n2⌋.
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