On the complexity of finding shortest variable disjunction branch-and-bound proofs
From MaRDI portal
Publication:2164707
DOI10.1007/978-3-031-06901-7_22zbMath1497.90137OpenAlexW4285295970MaRDI QIDQ2164707
Publication date: 16 August 2022
Full work available at URL: https://doi.org/10.1007/978-3-031-06901-7_22
Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)
Related Items
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