Exponential Lower Bounds on the Lengths of Some Classes of Branch-and-Cut Proofs

DOI10.1287/moor.1050.0151zbMath1082.90143OpenAlexW2113462655MaRDI QIDQ5704244

Sanjeeb Dash

Publication date: 11 November 2005

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/84fa4ebbcec964624274a3648751b65e5fb09848

zbMATH Keywords

cutting planesbranch-and-cut proofs, proof complexitycutting-plane proofs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Abstract computational complexity for mathematical programming problems (90C60) Boolean programming (90C09)

Related Items (10)

Theoretical challenges towards cutting-plane selection ⋮ Towards NP-P via proof complexity and search ⋮ Complexity of optimizing over the integers ⋮ Lower bounds on the size of general branch-and-bound trees ⋮ Complexity of branch-and-bound and cutting planes in mixed-integer optimization ⋮ Cutting planes cannot approximate some integer programs ⋮ On the empirical time complexity of finding optimal solutions vs proving optimality for Euclidean TSP instances ⋮ On the complexity of cutting-plane proofs using split cuts ⋮ The Complexity of Propositional Proofs ⋮ Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II

This page was built for publication: Exponential Lower Bounds on the Lengths of Some Classes of Branch-and-Cut Proofs