Branch and Bound for Boolean Optimization and the Generation of Optimality Certificates

DOI10.1007/978-3-642-02777-2_42MaRDI QIDQ3637179zbMATH OpenOpenAlexFDO

Authors Javier Larrosa, Robert Nieuwenhuis, Albert Oliveras, Enric Rodríguez-Carbonell

Publication date 7 July 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02777-2_42

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• A framework for certified Boolean branch-and-bound optimization
• Complexity results on DPLL and resolution
• optsat: A Tool for Solving SAT Related Optimization Problems
• A tight bound for the boolean quadratic optimization problem and its use in a branch and bound algorithm¹
• On the complexity of choosing the branching literal in DPLL

Cites work

• A logical approach to efficient Max-SAT solving
• A Simple and Flexible Way of Computing Small Unsatisfiable Cores in SAT Modulo Theories
• Efficient Generation of Unsatisfiability Proofs and Cores in SAT
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability
• On SAT Modulo Theories and Optimization Problems
• Radio link frequency assignment
• Satisfiability-based algorithms for Boolean optimization
• SATLIB: An online resource for research on SAT
• Solving SAT and SAT modulo theories, from an abstract Davis-Putnam-Logemann-Loveland procedure to \(\operatorname{DPLL}(T)\)

Cited in

(3)

• A framework for certified Boolean branch-and-bound optimization
• Reducing chaos in SAT-like search: finding solutions close to a given one
• Boolean Methods of Optimization over Independence Systems

Describes a project that uses

Uses Software

• SATLIB
• MaxSolver
• GLPK

This page was built for publication: Branch and Bound for Boolean Optimization and the Generation of Optimality Certificates

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