14
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Dec 4, 2012 at 15:03
  • $\begingroup$ @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? $\endgroup$ Dec 4, 2012 at 15:09
  • $\begingroup$ @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. $\endgroup$ Dec 4, 2012 at 15:14
  • $\begingroup$ 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. $\endgroup$ Dec 10, 2013 at 5:00

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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\}$. $\endgroup$ Dec 5, 2012 at 21:04
  • 2
    $\begingroup$ 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.) $\endgroup$
    – Jeffε
    Dec 5, 2012 at 21:50
  • 1
    $\begingroup$ @GiorgioCamerani: I did need to say positive - I've updated my answer. $\endgroup$ Dec 5, 2012 at 22:43
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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