<p>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$.</p>

<p>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.</p>

CC BY-SA 3.0
2012-12-05T21:04:38.533Z
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
CC BY-SA 3.0
2012-12-05T21:50:31.487Z
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.)
Jeffε
CC BY-SA 3.0
2012-12-05T22:43:11.143Z
@GiorgioCamerani: I did need to say positive - I've updated my answer.
Colin McQuillan
CC BY-SA 3.0
2012-12-04T15:24:33.007Z
2012-12-05T22:41:25.450Z
2012-12-05T22:41:25.450Z
Colin McQuillan
<p>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.</p>

<p>There is all theory on the generation of valid inequalities. A good starting point would be shrijver's book theory of integer programming. </p>

CC BY-SA 3.0
2012-12-24T15:43:28.370Z
2012-12-24T15:43:28.370Z
AJ Student
<p>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}$.</p>

<p>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$.</p>

<p>Assume that $|S_c| \geq n$. Now, let $O$ be a subset of $S_c$ such that all the following three statements hold:</p>

<ol>
<li>$O$ contains exactly $n$ points.</li>
<li>Such $n$ points are linearly independent.</li>
<li>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$.</li>
</ol>

<blockquote>
  <p><strong>Questions</strong>  </p>
  
  <ol>
  <li>Given $c$, is it possible to compute $O$ efficiently?  </li>
  <li>Which is the best known algorithm to compute it?</li>
  </ol>
</blockquote>

<p>$\ $</p>

<p><strong>Example with</strong> $n = 3$  </p>

<p><img src="https://i.sstatic.net/snbXL.png" alt="Example with n = 3"></p>

<p>$S_{\lnot c} = \{ ( 1, 0, 1 ) \}$, $O = \{ ( 0, 0, 1 ), ( 1, 1, 1 ), ( 1, 0, 0 ) \}$.</p>

<p>$\ $</p>

<p><strong>Update 05/12/2012</strong></p>

<blockquote>
  <p><strong>Motivation</strong></p>
  
  <p>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$.  </p>
  
  <p>The optimal constraint $c^*$ is the one that leads to the optimal polytope $P^*$.</p>
  
  <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).</p>
</blockquote>

<p><img src="https://i.sstatic.net/e29WJ.png" alt="Optimal Formulation"></p>

<p>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:</p>

<blockquote>
  <p><strong>Additional Question</strong>  </p>
  
  <p>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?</p>
</blockquote>

CC BY-SA 3.0
2012-12-04T15:03:03.610Z
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
CC BY-SA 3.0
2012-12-04T15:09:34.980Z
@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
CC BY-SA 3.0
2012-12-04T15:14:41.143Z
@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
CC BY-SA 3.0
2013-12-10T05:00:12.377Z
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](http://www.sciencedirect.com/science/article/pii/S0167637707001162).
Austin Buchanan
<reference-request><co.combinatorics><optimization><linear-programming><convex-optimization>
0-1 Linear Programming: computing the Optimal Formulation
Giorgio Camerani
# 0-1 Linear Programming: computing the Optimal Formulation

(Asked by: username_0 on 2012-12-04)

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](https://i.sstatic.net/snbXL.png)

$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](https://i.sstatic.net/e29WJ.png)

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?

**Tags:** reference-request, co.combinatorics, optimization, linear-programming, convex-optimization
> **Comments:**
> **username_1**: 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?  
> **username_0**: @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?  
> **username_0**: @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.  
> **username_2**: 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](http://www.sciencedirect.com/science/article/pii/S0167637707001162).  

---

## 2 answers

### Answer by username_1 on 2012-12-04. Score: 6

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.

> **Comments:**
> **username_0**: 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\}$.  
> **username_3**: 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.)  
> **username_1**: @GiorgioCamerani: I did need to say positive - I've updated my answer.  

---

### Answer by username_4 on 2012-12-24. Score: 2

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.


---

