hide
Free keywords:
-
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$.
