Lately I've been playing with a mixed integer programming model that involves
Hamming distances between binary vectors. This involves what amounts to computing the exclusive or between two binary variables. In a
previous post I made a comment about exclusive or being somewhat tricky to implement, but that was in reference to general linear constraints -- requiring that exactly one of two possible linear equalities/inequalities be satisfied. Fortunately, an
exclusive or between to binary variables is easy.
Let $x$ and $y$ be two binary variables, and let $z=x\oplus y$ be the exclusive disjunction of $x$ and $y$, also declared as a binary variable. The truth table is as follows:
| $x$ | $y$ | $z=x\oplus y$ |
|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
We accomplish this with the following inequalities:\begin{eqnarray*}z\le x + y\\z\le 2 - x - y\\ z\ge x - y\\z \ge y-x.\end{eqnarray*} Verification that this works is left to the reader as an exercise.
This is a neat problem. i tried this alternative route by "fitting to the truth table":
ReplyDeletez = (x-y)^2 = x + y - 2xy
Apply level-1 RLT on the bilinear term xy ~ w to recover the answer.
z = x + y -2w
w <= x
w <= y
w >= 1 - x - y
0 <= w,z,x,y <= 1
x, y binary
the end result is probably equivalent - their performance under fractional x, y doesn't seem different at first glance.
sorry, a boo-boo. constraint 4 would be:
ReplyDeletew >= x + y -1
Just what I was looking for! Thanks!
ReplyDelete