On computing small variable disjunction branch-and-bound trees

DOI10.1007/S10107-023-01968-YMaRDI QIDQ6589747zbMATH OpenFDO

Authors Max Gläser, Marc E. Pfetsch

Publication date 20 August 2024

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S10107-023-01968-Y

zbMATH Keywords

counting problembinary programbranch-and-bound proof

Mathematics Subject Classification ID

Integer programming (90C10)

Recommendations

• On the complexity of finding shortest variable disjunction branch-and-bound proofs
• Lower bounds on the size of general branch-and-bound trees
• Compressing branch-and-bound trees
• Estimating the Size of Branch-and-Bound Trees

Cites work

• scientific article; zbMATH DE number 7561762 (Why is no real title available?)
• scientific article; zbMATH DE number 7124428 (Why is no real title available?)
• scientific article; zbMATH DE number 7788373 (Why is no real title available?)
• 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
• 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
• Lower bounds on the size of general branch-and-bound trees
• On Approximation Algorithms for # P
• On Interpolation and Automatization for Frege Systems
• On the complexity of k-SAT
• On the complexity of finding shortest variable disjunction branch-and-bound proofs
• PP is as Hard as the Polynomial-Time Hierarchy
• Proof Complexity
• Resolution Is Not Automatizable Unless W[P] Is Tractable
• Stabbing planes
• The Complexity of Enumeration and Reliability Problems
• The complexity of computing the permanent
• The complexity of the Kth largest subset problem and related problems
• Trivial integer programs unsolvable by branch-and-bound

This page was built for publication: On computing small variable disjunction branch-and-bound trees

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