0/1 Polytopes with Quadratic Chvátal Rank
Operations Research · 2017 · Volume 65 · Issue 1
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
Enable JavaScript for citation tools and additional paper interactions.