Sunday, February 21, 2016

xor as linear inequalities

I came across a question about using an xor condition in a MIP model. Here is a summary of the answer.

Expressing $$z=x\cdot y$$ (or $$z=x\text{ and }y$$ ) where $$x,y,z \in \{0,1\}$$ as a set of linear constraints is well-known:

and:     \begin{align} &z \le x \\ &z \le y \\ &z \ge x+y-1 \end{align} $$\>\>\>\Longleftrightarrow\>\>\>$$
 $$z$$ $$x$$ $$y$$ $$0$$ $$0$$ $$0$$ $$0$$ $$0$$ $$1$$ $$0$$ $$1$$ $$0$$ $$1$$ $$1$$ $$1$$
The relation $$z=x\text{ xor }y$$ is slightly more complicated. The xor (exclusive-or) condition can also be written as $$z = x<>y$$, i.e. $$z$$ is 1 if $$x$$ and $$y$$ are different (and $$z$$ is zero if they are the same). This we can write as the following set of linear inequalities:
xor:     \begin{align} & z \le x+y\\ & z \ge x-y \\ & z \ge y-x \\ & z \le 2 -x - y \end{align} $$\>\>\>\Longleftrightarrow\>\>\>$$
 $$z$$ $$x$$ $$y$$ $$0$$ $$0$$ $$0$$ $$1$$ $$0$$ $$1$$ $$1$$ $$1$$ $$0$$ $$0$$ $$1$$ $$1$$
To be complete $$z=x\text{ or }y$$ can be written as:
or:     \begin{align} & z \le x+y\\ & z \ge x \\ & z \ge y \end{align} $$\>\>\>\Longleftrightarrow\>\>\>$$
 $$z$$ $$x$$ $$y$$ $$0$$ $$0$$ $$0$$ $$1$$ $$0$$ $$1$$ $$1$$ $$1$$ $$0$$ $$1$$ $$1$$ $$1$$
In all of this we assumed $$x,y$$ and $$z$$ are binary variables.