0-1 Linear Programming: computing the Optimal Formulation

Question

Consider the $n$ dimensional space $\{0,1\}^n$, and let $c$ be a linear constraint of the form $a_1x_1 + a_2x_2 + a_3x_3 +\ ...\ + a_{n-1}x_{n-1} + a_nx_n \geq k$, where $a_i \in \mathbb{R}$, $x_i \in \{0,1\}$ and $k \in \mathbb{R}$.

Clearly, $c$ has the effect of splitting $\{0,1\}^n$ in two subsets $S_c$ and $S_{\lnot c}$. $S_c$ contains all and only those points satisfying $c$, whereas $S_{\lnot c}$ contains all and only those points falsifying $c$.

Assume that $|S_c| \geq n$. Now, let $O$ be a subset of $S_c$ such that all the following three statements hold:

1. $O$ contains exactly $n$ points.
2. Such $n$ points are linearly independent.
3. Such $n$ points are those at minimum distance from the hyperplane represented by $c$. More precisely, let $d( x, c )$ be the distance of a point $x \in \{0,1\}^n$ from the hyperplane $c$. Then, $\forall B \subseteq S_c$ such that $B$ satisfies 1 and 2 it is the case that $\sum_{x \in B} d(x, c) \geq \sum_{x \in O} d(x, c)$. In other words $O$ is, among all the subsets of $S_c$ satisfying both conditions 1 and 2, the one that minimizes the sum of the distances of its points from the hyperplane $c$.

Questions

1. Given $c$, is it possible to compute $O$ efficiently?
2. Which is the best known algorithm to compute it?

$\ $

Example with $n = 3$

$S_{\lnot c} = \{ ( 1, 0, 1 ) \}$, $O = \{ ( 0, 0, 1 ), ( 1, 1, 1 ), ( 1, 0, 0 ) \}$.

$\ $

Update 05/12/2012

Motivation

The motivation is that using $O$ it should be possible to determine the optimal constraint $c^*$, as it should be the hyperplane defined by the $n$ points in $O$.

The optimal constraint $c^*$ is the one that leads to the optimal polytope $P^*$.

The optimal polytope $P^*$ is the one whose vertices are all and only the integer vertices of the initial polytope $P$ (an integer vertex is a vertex whose coordinates are all integer).

The process can be iterated for each constraint $c$ of a 0-1 $LP$ instance $I$, each time substituting $c$ with its corresponding optimal constraint $c^*$. At the end, this will lead to the optimal polytope $P^*$ of $I$. Then, since the vertices of $P^*$ are all and only the integer vertices of the initial polytope $P$ of $I$, any algorithm for $LP$ can be used to compute the optimal integer solution. I know that being able to compute $P^*$ efficiently would imply $P = NP$, however the following additional question still stands:

Additional Question

Is there any previous work along these lines? Did anyone already investigated the task of computing, given a polytope $P$, its corresponding optimal polytope $P^*$? Which is the best known algorithm to do that?

Answer 1

This seems to be NP-hard to do exactly, by reduction from subset sum. Suppose we had an efficient procedure to compute $O$. Given positive integers $v_1,\dots,v_n$ encoded in binary, we wish to test whether there is a subset summing to $s$. Preprocess by throwing out any integers larger than $s$.

Call the procedure to obtain a small set $O$ of points satisfying $v_1x_1+\dots+v_1x_n\leq s$, satisfying your minimality conditions (the preprocessing ensures $|S_c|\geq n$). This set will certainly contain a point on the hyperplane $v_1x_1+\dots+v_1x_n= s$ if there is one.

Answer 2

Like AJ says, your optimal polytope $P$ is the convex hull of the integer solutions, which can be represented using optimal inequalities, which induce facets of $P$. These inequalities are in a sense optimal because no valid inequalities are tighter.

The problem is that there can be exponentially many facet-defining inequalities needed to describe the convex hull of integer points.

For example, consider the independent set polytope -- the convex hull of independent sets of a graph. You can write an inequality that states that you can select at most one vertex from a maximal clique. Each one of these inequalities induces a facet of the independent set polytope and there can be $O(3^{n/3})$ maximal cliques.

Answer 3

It seems to me you are trying to get to the convex hull of the IP - in essence this is what cut algorithms try to achieve. Although thereotically appealing these methods fare poorly in practice.

There is all theory on the generation of valid inequalities. A good starting point would be shrijver's book theory of integer programming.