On the rank of cutting-plane proof systems

DOI10.1007/978-3-642-13036-6_34MaRDI QIDQ3569838zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(22)

• Input Proofs and Rank One Cutting Planes
• 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
• On the complexity of cutting-plane proofs
• Rank Lower Bounds for the Sherali-Adams Operator
• Stabbing planes
• Cutting planes cannot approximate some integer programs
• Rank bounds and integrality gaps for cutting planes procedures
• Design and verify: A new scheme for generating cutting-planes
• 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
• On the complexity of cutting-plane proofs using split cuts
• Design and verify: a new scheme for generating cutting-planes
• On the Chvátal rank of the pigeonhole principle
• Random half-integral polytopes
• Tight rank lower bounds for the Sherali-Adams proof system

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)