How can we handle \[y = x_1 \oplus x_2 \oplus \cdots \oplus x_n\] in a linear MIP model? Here \(\oplus\) indicates thexoroperation.

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

## No comments:

## Post a Comment