I have a formulation of linear inequality constraints (A1, ..., An) from which I need exactly one to be true:
A1 xor A2 xor ... xor An
and I'd like to transform the above into a typical and-related set of constraints (B1, ..., Bm)
B1 and B2 and ... and Bm
in order to provide it as input to a linear programming solver.
How can I perform this transformation, or at least find a feasible solution to a set of xor-related constraints?
Note that the set where a condition of the type $B_1 \text{ and } B_2 \text{ and } \ldots \text{ and } B_m$ is true, is always a convex polyhedron. This is not the case for $\oplus$-related constraints, the set where these are true is in general not even convex (Think of $(x_1 \ge 0) \oplus (x_2 \ge 0)$). What you can do is, solve the $n$ problems with constraints (1) $B_1 \text{ and } \neg B_2 \text{ and } \cdots \text{ and } \neg B_n$, (2) $\neg B_1 \text { and } B_2 \text{ and } \cdots \text{ and } \neg B_n$, $\ldots$ ($n$) $\neg B_1 \text{ and } \neg B_2 \text{ and } \cdots \text{ and } B_n$ seperately.