Divide and conquer: Towards faster pseudo-boolean solving

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

Abstract

The last 20 years have seen dramatic improvements in the performance of algorithms for Boolean satisfiability-so-called SAT solvers-and today conflict-driven clause learning (CDCL) solvers are routinely used in a wide range of application areas. One serious short-coming of CDCL, however, is that the underlying method of reasoning is quite weak. A tantalizing solution is to instead use stronger pseudo-Boolean (PB) reasoning, but so far the promise of exponential gains in performance has failed to materialize-the increased theoretical strength seems hard to harness algorithmically, and in many applications CDCL-based methods are still superior. We propose a modified approach to pseudo-Boolean solving based on division instead of the saturation rule used in [Chai and Kuehlmann'05] and other PB solvers. In addition to resulting in a stronger conflict analysis, this also improves performance by keeping integer coefficient sizes down, and yields a very competitive solver as shown by the results in the Pseudo-Boolean Competitions 2015 and 2016.

Detaljer

Författare
Externa organisationer
  • KTH Royal Institute of Technology
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)
Originalspråkengelska
Titel på värdpublikationProceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018
RedaktörerJerome Lang
FörlagInternational Joint Conferences on Artificial Intelligence
Sidor1291-1299
Antal sidor9
ISBN (elektroniskt)9780999241127
StatusPublished - 2018
PublikationskategoriForskning
Peer review utfördJa
Externt publiceradJa
Evenemang27th International Joint Conference on Artificial Intelligence, IJCAI 2018 - Stockholm, Sverige
Varaktighet: 2018 jul 132018 jul 19

Publikationsserier

NamnIJCAI International Joint Conference on Artificial Intelligence
Volym2018-July
ISSN (tryckt)1045-0823

Konferens

Konferens27th International Joint Conference on Artificial Intelligence, IJCAI 2018
LandSverige
OrtStockholm
Period2018/07/132018/07/19