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.
Thanks! You help me a lot!
ReplyDeleteDear colleagues,
ReplyDeleterecently we understood how to represent any boolean function f(x) as system of linear inequalities in the following sense.
Let B^n={(x_1,x_2, ..., x_n): x_k={0,1}} be is a set of n-dimensional unit cube's vertices, i.e. the set of all 0-1 arguments of some boolean function f:B^n -> {0,1}. Then there exist a system of a number of linear inequalities of n+1 variables (x,y):
S(x,y)={a_i + l_i(x) + b_i*y >= 0: i={1:m}} such that for any x\in B^n, f(x)=y if and only if S(x,y) holds.
It is important that we do not need to assume that y is a discrete, 0-1, variable! For any 0-1 vector x, corresponding y value will be either 0, or 1.
And I can explicitly produce the system S(x,y) for any function f(x) given either by formula or in tabular form.
Can any body tell me any reference on this subject?
I can not believe that it a "fresh result" in math. programming ... But my rather intensive search over literature did not bring any similar assertion...
what about detecting equality or not (xor) between 2 consecutive integer variables? not only binary. thanks
ReplyDelete