On the rank of cutting-plane proof systems

DOI10.1007/978-3-642-13036-6_34zbMATH Open1284.03260OpenAlexW2125541192MaRDI QIDQ3569838FDOQ3569838

Authors: Sebastian Pokutta, Andreas S. Schulz 

Publication date: 22 June 2010

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

Full work available at URL: https://doi.org/10.1007/978-3-642-13036-6_34

Recommendations

• Rank bounds and integrality gaps for cutting planes procedures
• On cutting-plane proofs in combinatorial optimization
• Cutting-plane proofs in polynomial space
• On the complexity of cutting-plane proofs
• Bounds on the Chvatal rank of polytopes in the 0/1-cube

zbMATH Keywords

cutting planeslift-and-project cutssplit cutsproof systemsGomory-Chvátal cuts

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Complexity of proofs (03F20)

Cited In (22)

• Rank of random half-integral polytopes. Extended abstract
• Resolution Width and Cutting Plane Rank Are Incomparable
• On cutting-plane proofs in combinatorial optimization
• Theoretical challenges towards cutting-plane selection
• Integer-empty polytopes in the 0/1-cube with maximal Gomory-Chvàtal rank
• Hardness amplification in proof complexity
• Rank Lower Bounds for the Sherali-Adams Operator
• Stabbing planes
• On the complexity of cutting-plane proofs
• Rank bounds and integrality gaps for cutting planes procedures
• Design and verify: A new scheme for generating cutting-planes
• Cutting planes cannot approximate some integer programs
• A short proof for the polyhedrality of the Chvátal-Gomory closure of a compact convex set
• Several notes on the power of Gomory-Chvátal cuts
• Aggregation-based cutting-planes for packing and covering integer programs
• Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators
• Design and verify: a new scheme for generating cutting-planes
• On the complexity of cutting-plane proofs using split cuts
• On the Chvátal rank of the pigeonhole principle
• Random half-integral polytopes
• Tight rank lower bounds for the Sherali-Adams proof system
• Input Proofs and Rank One Cutting Planes

This page was built for publication: On the rank of cutting-plane proof systems

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