Tuesday, February 1, 2011

Binary Exclusive Or

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$
000
011
101
110

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.

3 comments:

  1. This is a neat problem. i tried this alternative route by "fitting to the truth table":

    z = (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.

    ReplyDelete
  2. sorry, a boo-boo. constraint 4 would be:
    w >= x + y -1

    ReplyDelete
  3. Just what I was looking for! Thanks!

    ReplyDelete

If this is your first time commenting on the blog, please read the Ground Rules for Comments. In particular, if you want to ask an operations research-related question not relevant to this post, consider asking it on OR-Exchange.