# Paper about the upper bound of the number of inequalities to describe the Integer hull of a polyhedron

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.

• 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 Apr 12 '14 at 0:59

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