Lower bounds for the Chvátal-Gomory rank in the 0/1 cube

Sebastian Pokutta (pokuttamit.edu)
Gautier Stauffer (gautier.stauffermath.u-bordeaux1.fr)

Abstract: 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.

Keywords: Chvátal-Gomory closure, rank, polytopes in 0/1 cube, lower bounds

Category 1: Integer Programming (0-1 Programming )

Category 2: Integer Programming (Cutting Plane Approaches )

Citation:

Download: [PDF]

Entry Submitted: 09/27/2010
Entry Accepted: 09/28/2010
Entry Last Modified: 03/16/2011

Modify/Update this entry