Exponential Lower Bounds on the Lengths of Some Classes of Branch-and-Cut Proofs
From MaRDI portal
Publication:5704244
DOI10.1287/moor.1050.0151zbMath1082.90143MaRDI QIDQ5704244
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
68Q25: Analysis of algorithms and problem complexity
90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C60: Abstract computational complexity for mathematical programming problems
90C09: Boolean programming
Related Items
The Complexity of Propositional Proofs, Towards NP-P via proof complexity and search, 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, Theoretical challenges towards cutting-plane selection