  


On the Rank of CuttingPlane Proof Systems
Sebastian Pokutta(sebastian.pokuttaisye.gatech.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 wellknown meth ods, such as GomoryChvátal cuts, liftandproject cuts, SheraliAdams 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 ndimensional 0/1cube that has rank Ω(n/ log n) for every proof system in our class. In fact, we show that whenever some cuttingplane based proof system has (maximal) rank n on a particular family of instances, then any cuttingplane proof system in our class has rank Ω(n/ log n) for this family. This shows that the rank complexity of worstcase instances is intrinsic to the problem; it does not depend on specific cuttingplane proof systems, except for log factors. We also construct a new cuttingplane proof system that has worstcase 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, GomoryChvátal cuts, LovászSchrijver cuts, liftandproject cuts, split cuts Category 1: Integer Programming (Cutting Plane Approaches ) Category 2: Integer Programming (01 Programming ) Category 3: Combinatorial Optimization (Polyhedra ) Citation: Download: [PDF] Entry Submitted: 02/20/2013 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  