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:$O$ contains exactly $n$ points.Such $n$ points are linearly independent.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 Given $c$, is it possible to compute $O$ efficiently?  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/2012MotivationThe 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?
0-1 Linear Programming: computing the Optimal Formulation
reference request;co.combinatorics;optimization;linear programming;convex optimization