0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Can you clarify your goals? What do you mean by "smarter"? What's wrong with using a sequence of 2-input xors? Have you tried that with your particular problem? Was there some problem with it? We normally expect you to flesh out your question by telling us what you're looking for, how you will evaluate answers, and what you've tried. $\endgroup$ – D.W. Mar 25 '15 at 20:32
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.