Although well studied, important questions on the rank of the Chvátal-Gomory operator when restricting to polytopes contained in the n-dimensional 0/1 cube have not been answered yet. In particular, the question on the maximal rank of the Chvátal-Gomory procedure for this class of polytopes is still open. So far, the best-known upper bound is O(n^2 \log(n)) and the best-known lower bound, which is based on a randomized construction of a family of polytopes, is (1+\epsilon) n, both of which were established in Eisenbrand and Schulz [2003]. The main techniques to prove lower bounds were introduced in Chvátal et al. [1989]. In this paper we revisit one of those techniques and we develop a simpler method to establish lower bounds. We show the power and applicability of this method on classical examples from the literature as well as provide new families of polytopes with high rank. Furthermore, we provide a deterministic family of polytopes achieving a Chvátal-Gomory rank of at least (1+1/e)n - 1 > n and we conclude the paper with showing how to obtain a lower bound on the rank from solely examining the integrality gap.
Article
View Lower bounds for the Chvátal-Gomory rank in the 0/1 cube