0/1 polytopes with quadratic Chvátal rank

DOI10.1007/978-3-642-36694-9_30MaRDI QIDQ4911536zbMATH OpenOpenAlexFDO

Authors Thomas Rothvoß, Laura Sanità

Publication date 19 March 2013

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.4753

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Abstract: For a polytope P, the Chvatal closure P' is obtained by simultaneously strengthening all feasible inequalities cx <= b (with integral c) to cx <= floor(b). The number of iterations of this procedure that are needed until the integral hull of P is reached is called the Chvatal rank. If P is a subset of [0,1]^n, then it is known that O(n^2 log n) iterations always suffice (Eisenbrand and Schulz (1999)) and at least (1+1/e-o(1))n iterations are sometimes needed (Pokutta and Stauffer (2011)), leaving a huge gap between lower and upper bounds. We prove that there is a polytope contained in the 0/1 cube that has Chvatal rank Omega(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 Chvatal rank to simultaneous Diophantine approximations w.r.t. the L1-norm of the normal vector defining P.

Recommendations

• \(0/1\) polytopes with quadratic Chvátal rank
• On the Chvátal rank of polytopes in the 0/1 cube
• On the rank of mixed 0,1 polyhedra.
• scientific article; zbMATH DE number 1342126
• Bounds on the Chvatal rank of polytopes in the 0/1-cube

Cited in

(16)

• Bounds on the Chvatal rank of polytopes in the 0/1-cube
• Aggregation-based cutting-planes for packing and covering integer programs
• On some polytopes contained in the 0,1 hypercube that have a small Chvátal rank
• On the Chvátal rank of polytopes in the 0/1 cube
• Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II
• On the rational polytopes with Chvátal rank 1
• Complexity of branch-and-bound and cutting planes in mixed-integer optimization
• On some polytopes contained in the 0,1 hypercube that have a small Chvátal rank
• Characterizing polytopes in the 0/1-cube with bounded Chvátal-Gomory rank
• \(0/1\) polytopes with quadratic Chvátal rank
• High Degree Sum of Squares Proofs, Bienstock--Zuckerberg Hierarchy, and Chvátal--Gomory Cuts
• Complexity of optimizing over the integers
• Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II
• Reducing the Chvátal rank through binarization
• On the power and limitations of branch and cut
• Reverse split rank

This page was built for publication: 0/1 polytopes with quadratic Chvátal rank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4911536)