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/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?