1
$\begingroup$

I'm trying to solve an integer linear program (ILP) in which a constraint of the following kind must be met:

$x_1 \oplus x_2 \oplus \cdots \oplus x_n = 1$

where $\oplus$ is the binary xor operator.

The answer to this question shows how to represent $y = x_1 \oplus x_2$ with linear inequalities. In an answer to this question there is an attempt to generalize the representation to more than two inputs, but the two answers seem to be inconsistent, since the latter doesn't even use inequalities.

So, the question is: how can I represent $y = x_1 \oplus x_2 \oplus \cdots \oplus x_n$ as set of linear inequalities?

$\endgroup$
1
$\begingroup$

Introducing another integer variable $t$, you can express the condition $x_1 \oplus x_2 \oplus \cdots \oplus x_n = 1$ as in the following canonical form. $$x_1 + x_2 + \dots + x_n - 2t \le 1$$ $$- x_1 - x_2 - \dots - x_n + 2t \le -1$$ $$(x_1, x_2, \cdots, x_n) \le (1,1,\cdots,1)$$ $$(x_1, x_2, \cdots, x_n, t) \ge \mathbf 0$$ $$(x_1, x_2, \cdots, x_n, t) \in \Bbb Z^{n+1}$$ You can also replace the first two inequalities by the following equality. $$x_1 + x_2 + \dots + x_n - 2t = 1$$ In other words, you can actually eliminate one of $x_1, x_2, \cdots, x_n$ by replacing it with $t$.

Note $t$ is an integer not bounded from above. However, you can also bounded it by the following inequality, which is implied by the existing inequalities.

$$0\le t\le \lceil \frac{n}2\rceil-1$$


The idea is that $x_1 \oplus x_2 \oplus \cdots \oplus x_n = 1$ if and only if the number of $x_i$'s that are 1 is odd. This answer is essentially the same as the answer you mentioned.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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