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 wellknown:
and: 
\[\begin{align}
&z \le x \\
&z \le y \\
&z \ge x+y1
\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 (exclusiveor) 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 xy \\
& z \ge yx \\
& 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.
No comments:
Post a Comment