Bounds on the Chvátal Rank of Polytopes in the 0/1-Cube*

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 Chvátal rank of the polyhedron is the number of rounds needed to obtain all valid inequalities. It is well known that the Chvátal rank can be arbitrarily large, even if the polyhedron is bounded, if it is 2-dimensional, and if its integer hull is a 0/1-polytope.

We show that the Chvátal rank of polyhedra featured in common relaxations of many combinatorial optimization problems is rather small; in fact, we prove that the rank of every polytope contained in the n-dimensional 0/1-cube is at most n ² (1+log n). Moreover, we also demonstrate that the rank of any polytope in the 0/1-cube whose integer hull is defined by inequalities with constant coefficients is O(n).

Finally, we provide a family of polytopes contained in the 0/1-cube whose Chvátal rank is at least (1 + ε) n, for some ε > 0.

Authors and Affiliations

1. Max-Planck-Institut für Informatik, Stuhlsatzenhausweg 85, D-66123, Saarbrücken, Germany

   Friedrich Eisenbrand

2. M.I.T., Sloan School of Management, 77 Massachusetts Avenue, E53-361, Cambridge, MA, 02139-4307, USA

   Andreas S. Schulz

Corresponding author

Correspondence to Friedrich Eisenbrand.

* An extended abstract of this paper appeared in the Proceedings of the 7th International Conference on Integer Programming and Combinatorial Optimization [20].

Reprints and permissions