On the Chvatal rank of polytopes in the 0/1 cube

Given a polytope P subset of or equal to R-n, the Chvatal-Gomory procedure computes iteratively the integer hull P-I of P. The Chvatal rank of P is th e minimal number of iterations needed to obtain P-I. It is always finite, b ut already the Chvatal rank of polytopes in R-2 can be arbitrarily large. I n this paper, we study polytopes in the 0/1 cube, which are of particular i nterest in combinatorial optimization. We show that the Chvatal rank of any polytope P subset of or equal to [0, 1](n) is O(n(3) log n) and prove the linear upper and lower bound n for the case P boolean AND Z(n) = 0. (C) 199 9 Elsevier Science B.V. All rights reserved.