<p>Via <a href="http://pubsonline.informs.org/doi/abs/10.1287/opre.18.5.940" rel="nofollow">Rubin</a>:</p>

<p>There is a sequence of polytopes $\{ P_k\}_k$ each defined by two variables and one constraint (plus two nonnegativity constraints) such that the integer hull of $P_k$ has $k+3$ vertices and $k+3$ facets. </p>

<p>$P_k=\{ (x,y)\in \mathbb{R}^2_+ ~|~f_{2k} x + f_{2k+1}y \le f^2_{2k+1}-1\}$</p>

<p>Here, $f_j$ is the $j$-th Fibonacci number.</p>

<p>This shows that the number of facets of the integer hull $P_I$ cannot be bounded above in terms of the number variables and constraints of $P$.</p>

<p>Schrijver provides a nice collection of these kind of results in his <em>Theory of Linear and Integer Programming</em>.</p>

CC BY-SA 3.0
2014-04-11T21:40:43.323Z
2014-04-11T21:45:44.887Z
2014-04-11T21:45:44.887Z
Austin Buchanan
<p>I am interested in the upper bound of the number of inequalities to describe the integer hull of a polyhedron. That is, given an integer programming problem with n inequalities which construct a polyhedron P, we often adding some inequalities to get the integer hull P_I of P. Then what is the maximum number of inequalities needed to describe this P_I? I have known that there are some conclusions on this topic but I don't what they are. I need some paper about it. Please tell me if you know it.</p>

CC BY-SA 3.0
2014-04-12T00:59:55.500Z
If there is no such bound on general integer programming problem, how about 0-1 integer programming? Is there any bound on the number of inequalities to define the Integer hull of 0-1 integer programming problem?
THULeiZhixian
<reference-request><integer-programming>
Paper about the upper bound of the number of inequalities to describe the Integer hull of a polyhedron
THULeiZhixian
# Paper about the upper bound of the number of inequalities to describe the Integer hull of a polyhedron

(Asked by: username_0 on 2014-04-11)

I am interested in the upper bound of the number of inequalities to describe the integer hull of a polyhedron. That is, given an integer programming problem with n inequalities which construct a polyhedron P, we often adding some inequalities to get the integer hull P\_I of P. Then what is the maximum number of inequalities needed to describe this P\_I? I have known that there are some conclusions on this topic but I don't what they are. I need some paper about it. Please tell me if you know it.

**Tags:** reference-request, integer-programming

> **Comments:**
> **username_0**: If there is no such bound on general integer programming problem, how about 0-1 integer programming? Is there any bound on the number of inequalities to define the Integer hull of 0-1 integer programming problem?  

---

## 1 answers

### Answer by username_1 on 2014-04-11. Score: 3

Via [Rubin](http://pubsonline.informs.org/doi/abs/10.1287/opre.18.5.940):

There is a sequence of polytopes $\{ P\_k\}\_k$ each defined by two variables and one constraint (plus two nonnegativity constraints) such that the integer hull of $P\_k$ has $k+3$ vertices and $k+3$ facets.

$P\_k=\{ (x,y)\in \mathbb{R}^2\_+ ~|~f\_{2k} x + f\_{2k+1}y \le f^2\_{2k+1}-1\}$

Here, $f\_j$ is the $j$-th Fibonacci number.

This shows that the number of facets of the integer hull $P\_I$ cannot be bounded above in terms of the number variables and constraints of $P$.

Schrijver provides a nice collection of these kind of results in his *Theory of Linear and Integer Programming*.


---

