Optimization Online


On the Rank of Cutting-Plane Proof Systems

Sebastian Pokutta(sebastian.pokutta***at***isye.gatech.edu)
Andreas S. Schulz(schulz***at***mit.edu)

Abstract: We introduce a natural abstraction of propositional proof systems that are based on cut- ting planes. This leads to a new class of proof systems that includes many well-known meth- ods, such as Gomory-Chvátal cuts, lift-and-project cuts, Sherali-Adams cuts, or split cuts. The rank of a proof system corresponds to the number of rounds that is needed to show the nonexistence of integral solutions. We exhibit a family of polytopes without integral points contained in the n-dimensional 0/1-cube that has rank Ω(n/ log n) for every proof system in our class. In fact, we show that whenever some cutting-plane based proof system has (maximal) rank n on a particular family of instances, then any cutting-plane proof system in our class has rank Ω(n/ log n) for this family. This shows that the rank complexity of worst-case instances is intrinsic to the problem; it does not depend on specific cutting-plane proof systems, except for log factors. We also construct a new cutting-plane proof system that has worst-case rank O(n/ log n) for any polytope without integral points, implying that our universal lower bound is essentially tight.

Keywords: Integer programming, propositional proof systems, cutting planes, Gomory-Chvátal cuts, Lovász-Schrijver cuts, lift-and-project cuts, split cuts

Category 1: Integer Programming (Cutting Plane Approaches )

Category 2: Integer Programming (0-1 Programming )

Category 3: Combinatorial Optimization (Polyhedra )


Download: [PDF]

Entry Submitted: 02/20/2013
Entry Accepted: 02/20/2013
Entry Last Modified: 02/20/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society