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

DOI10.1007/978-3-031-06901-7_22zbMath1497.90137OpenAlexW4285295970MaRDI QIDQ2164707

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

counting problembinary programbranch-and-bound proof

Mathematics Subject Classification ID

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

Related Items

Compressing branch-and-bound trees

Cites Work

• Unnamed Item
• On the complexity of cutting-plane proofs
• The complexity of computing the permanent
• 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
• An abstract model for branching and its application to mixed integer programming
• Branching rules revisited
• Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II
• PP is as Hard as the Polynomial-Time Hierarchy
• Resolution Is Not Automatizable Unless W[P Is Tractable]
• On Approximation Algorithms for # P
• The Complexity of Enumeration and Reliability Problems
• Estimating the Efficiency of Backtrack Programs
• On Interpolation and Automatization for Frege Systems
• Proof Complexity
• Trivial integer programs unsolvable by branch-and-bound
• Cloud Branching
• Estimating the Size of Branch-and-Bound Trees
• Automating Resolution is NP-Hard
• Computational Complexity
• On the complexity of \(k\)-SAT