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