Skip to Main content Skip to Navigation
New interface
Conference papers

Combining Clause Learning and Branch and Bound for MaxSAT (Extended Abstract)

Abstract : Branch and Bound (BnB) has been successfully used to solve many combinatorial optimization problems. However, BnB MaxSAT solvers perform poorly when solving real-world and academic optimization problems. They are only competitive for random and some crafted instances. Thus, it is a prevailing opinion in the community that BnB is not really useful for practical MaxSAT solving. We refute this opinion by presenting a new BnB MaxSAT solver, called MaxCDCL, which combines clause learning and an efficient bounding procedure. MaxCDCL is among the top 5 out of a total of 15 exact solvers that participated in the 2020 MaxSAT Evaluation, solving several instances that other solvers cannot solve. Furthermore, MaxCDCL solves the highest number of instances from different MaxSAT Evaluations when combined with the best existing solvers.
Document type :
Conference papers
Complete list of metadata

https://hal-amu.archives-ouvertes.fr/hal-03775319
Contributor : Jordi Coll Connect in order to contact the contributor
Submitted on : Monday, September 12, 2022 - 2:30:48 PM
Last modification on : Tuesday, September 13, 2022 - 3:51:39 AM

File

0739.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03775319, version 1

Collections

Citation

Chu-Min Li, Zhenxing Xu, Jordi Coll, Felip Manyà, Djamal Habet, et al.. Combining Clause Learning and Branch and Bound for MaxSAT (Extended Abstract). 31ST INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE (IJCAI 2022), Jul 2022, Vienne, Austria. ⟨hal-03775319⟩

Share

Metrics

Record views

36

Files downloads

2