# 0-1 Linear Programming: computing the Optimal Formulation

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:

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?

-
This seems to be NP-hard to do exactly, by reduction from subset sum. Given binary integers $v_1,\dots,v_n$, to test whether there is a subset summing to $s$, we can test whether there is a point on the hyperplane $v_1x_1+\dots+v_1x_n= s$. Are you interested in approximations? –  Colin McQuillan Dec 4 '12 at 15:03
@ColinMcQuillan: The question was meant for an exact solution, however I'm certainly interested also in approximations. Why don't you turn your comment into an answer? –  Giorgio Camerani Dec 4 '12 at 15:09
@ColinMcQuillan: Also, your hyperplane is defined by using an equality, while mine is defined by using an inequality. Are you sure that this makes no difference in terms of hardness? I didn't check that yet, thus I'm just asking. –  Giorgio Camerani Dec 4 '12 at 15:14
I'm a little confused about all the restrictions on $O$. If you're looking for information about the convex hull of $S_c$ then there are lots of results in the operations research literature about the 0-1 knapsack polytope. In terms of approximate formulations, see this. –  Austin Buchanan Dec 10 '13 at 5:00

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.

-
Maybe I'm overlooking something macroscopic here, but I have 2 questions: 1) When you say "Given binary integers" what do you mean by binary? $v_1, ..., v_n$ belong to $\mathbb{R}$. Maybe you mean encoded in binary? Or maybe you wanted to say positive? 2) Why throwing out all the integers larger than $s$? They may contribute to the solution. For example: $v_1 = -3, v_2 = 7, v_3 = -5, s = 2$ if you throw away $v_2$ you lose the only solution $\{v_2, v_3\}$. –  Giorgio Camerani Dec 5 '12 at 21:04
I think what Colin means is that if the constraint coefficients $a_i$ are rational numbers, in their usual binary representation, then your problem appears to NP-hard. (Mixing real numbers and NP-hardness is always tricky.) –  JɛﬀE Dec 5 '12 at 21:50
@GiorgioCamerani: I did need to say positive - I've updated my answer. –  Colin McQuillan Dec 5 '12 at 22:43

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.

-