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.

  • $\begingroup$ 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? $\endgroup$ – THULeiZhixian Apr 12 '14 at 0:59

Via Rubin:

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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