0/1 Polytopes with Quadratic Chvátal Rank

Thomas Rothvoß () and Laura Sanità ()
Additional contact information
Thomas Rothvoß: University of Washington, Seattle, 98105
Laura Sanità: University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada

Operations Research, 2017, vol. 65, issue 1, 212-220

Abstract: For a polytope P , the Chvátal closure P ′ ⊆ P is obtained by simultaneously strengthening all feasible inequalities cx ⩽ β (with integral c ) to cx ⩽ ⌊ β ⌋. The number of iterations of this procedure that are needed until the integral hull of P is reached is called the Chvátal rank. If P ⊆ [0, 1] n , then it is known that O ( n 2 log n ) iterations always suffice and at least (1 + 1/ e − o (1)) n iterations are sometimes needed, leaving a huge gap between lower and upper bounds. We prove that there is a polytope contained in the 0/1 cube that has Chvátal rank Ω( n 2 ), closing the gap up to a logarithmic factor. In fact, even a superlinear lower bound was mentioned as an open problem by several authors. Our choice of P is the convex hull of a semi-random Knapsack polytope and a single fractional vertex. The main technical ingredient is linking the Chvátal rank to simultaneous Diophantine approximations w.r.t. the ‖·‖ 1 -norm of the normal vector defining P .

Keywords: integer programming; Chvátal-gomory cuts (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.287/opre.2016.1549 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:65:y:2018:i:1:p:212-220

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().