Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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$

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).

Optimal Formulation

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?

share|improve this question
    
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
add comment

2 Answers 2

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.

share|improve this answer
    
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
2  
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ɛffE Dec 5 '12 at 21:50
1  
@GiorgioCamerani: I did need to say positive - I've updated my answer. –  Colin McQuillan Dec 5 '12 at 22:43
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.