Item

Abstract

Gomory's and Chvátal's cutting-plane procedure proves recursively the validity of linear inequalities for the integer hull of a given polyhedron. The number of rounds needed to obtain all valid inequalities is known as the Chvátal rank of the polyhedron. It is well-known that the Chvátal rank can be arbitrarily large, even if the polyhedron is bounded, if it is of dimension $2$, and if its integer hull is a $0/1$-polytope. We prove that the Chvátal rank of polyhedra featured in common relaxations of many combinatorial optimization problems is rather small; in fact, the rank of any polytope contained in the $n$-dimensional $0/1$-cube is at most $3 n^2 \lg n$. This improves upon a recent result of Bockmayr et al.\ \cite{BEHS99} who obtained an upper bound of $\text{O}(n^3 \log n)$. Moreover, we refine this result by showing that the rank of any polytope in the $0/1$-cube that is defined by inequalities with small coefficients is $\text{O}(n)$. The latter observation explains why for most cutting planes derived in polyhedral studies of several popular combinatorial optimization problems only linear growth has been observed (see, e.g., \cite{ChvatalCookHartmann89}); the coefficients of the corresponding inequalities are usually small. Similar results were only known for monotone polyhedra before. Finally, we provide a family of polytopes contained in the $0/1$-cube the Chvátal rank of which is at least $(1+e) n$ for some $e > 0$; the best known lower bound was $n$.