On the complexity of finding shortest variable disjunction branch-and-bound proofs

DOI10.1007/978-3-031-06901-7_22MaRDI QIDQ2164707zbMATH OpenOpenAlexFDO

Authors Max Gläser, Marc E. Pfetsch

Publication date 16 August 2022

Full work available at URL https://doi.org/10.1007/978-3-031-06901-7_22

zbMATH Keywords

binary programbranch-and-bound proofcounting problem

Mathematics Subject Classification ID

Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• Lower bounds on the size of general branch-and-bound trees
• Bounds on the size of branch-and-bound proofs for integer knapsacks
• Basis reduction and the complexity of branch-and-bound
• Branch-and-bound solves random binary IPs in poly(n)-time
• Complexity of branch-and-bound and cutting planes in mixed-integer optimization

Cites work

• An abstract model for branching and its application to mixed integer programming
• Automating resolution is NP-hard
• Branching rules revisited
• Cloud branching
• Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II
• Computational Complexity
• Estimating the Efficiency of Backtrack Programs
• Estimating the Size of Branch-and-Bound Trees
• scientific article; zbMATH DE number 7561762 (Why is no real title available?)
• Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. 6th international conference, CPAIOR 2009, Pittsburgh, PA, USA, May 27--31, 2009. Proceedings
• NP is as easy as detecting unique solutions
• On Approximation Algorithms for # P
• On Interpolation and Automatization for Frege Systems
• On the complexity of k-SAT
• On the complexity of cutting-plane proofs
• PP is as Hard as the Polynomial-Time Hierarchy
• Proof Complexity
• Resolution Is Not Automatizable Unless W[P] Is Tractable
• The complexity of computing the permanent
• The Complexity of Enumeration and Reliability Problems
• Trivial integer programs unsolvable by branch-and-bound

Cited in

(6)

• Lower bounds on the size of general branch-and-bound trees
• Early estimates of the size of branch-and-bound trees
• Variable Elimination in Binary CSPs
• Compressing branch-and-bound trees
• On computing small variable disjunction branch-and-bound trees
• Compressing branch-and-bound trees

This page was built for publication: On the complexity of finding shortest variable disjunction branch-and-bound proofs

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