A different notion of Duality for Binary Integer Programming

122 Views Asked by At

Let $M$ be a convex subset of the unit hypercube embedded in $\mathbb{R}^n$ as

$$ 0 \le x_1 ... x_n \le 1 $$

With the property that $M$ is the convex hull of its vertices, and all of its vertices are integer points lying on the corners of the unit hypercube.

It is easy then to define a notion of a "binary dual" of $M$, $M'$ where $M'$ is a convex hull of all the vertices of the hypercube that are not in $M$.

A concrete example, Given:

$$M: x -y =0, 0 \le y \le 1 $$

As such a $M$ in $\mathbb{R}^2$ we can find its binary dual to be:

$$ M': x +y =1, 0 \le x \le 1 $$

Which can be verified by drawing the two structures out and checking that $M'$ has vertices strictly where $M$ does not.

So that leads to a natural question, given the $H$ representation of $M$ (so it arrives as a collection of inequalities) which you are told is the convex hull of its binary integer vertices, how does one efficiently compute $M'$ (as a collection of inequalities)?