Express XOR with multiple inputs in zero-one integer linear programming (ILP)

Question

In the below post, it is explained how to express xor of two variables as linear inequalities.

Express boolean logic operations in zero-one integer linear programming (ILP)

Naturally, the xor of multiple variables can be expressed using a sequence of multiple 2-input xors but my question whether there is a smarter way to do it?

Answer 1

Here is another way you could try. To express $y=x_1 \oplus x_2 \oplus \dots \oplus x_n$ (the exclusive-or of $x_1,\dots,x_n$), try the following constraints:

$$y = x_1 + x_2 + \dots + x_n - 2t$$ $$0 \le y \le 1$$

where $y$ and $t$ are constrained to be integers.

There are no guarantees this will work better than a sequence of 2-input xors or a tree of 2-input xors. Generally, the only way to discover what will work best with an ILP solver is to try each of the operations and see how fast the ILP solver runs.

Caution: If your problem has a lot of XORs, integer linear programming might not be the best tool for the job. A SAT solver might be more effective. See also CryptoMiniSat, which is a SAT solver optimized to deal well with XORs.