Divide and conquer: Towards faster pseudo-boolean solving
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
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.
Originalsprog | Engelsk |
---|---|
Titel | Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018 |
Redaktører | Jerome Lang |
Antal sider | 9 |
Forlag | International Joint Conferences on Artificial Intelligence |
Publikationsdato | 2018 |
Sider | 1291-1299 |
ISBN (Elektronisk) | 9780999241127 |
DOI | |
Status | Udgivet - 2018 |
Eksternt udgivet | Ja |
Begivenhed | 27th International Joint Conference on Artificial Intelligence, IJCAI 2018 - Stockholm, Sverige Varighed: 13 jul. 2018 → 19 jul. 2018 |
Konference
Konference | 27th International Joint Conference on Artificial Intelligence, IJCAI 2018 |
---|---|
Land | Sverige |
By | Stockholm |
Periode | 13/07/2018 → 19/07/2018 |
Sponsor | International Joint Conferences on Artifical Intelligence (IJCAI) |
Navn | IJCAI International Joint Conference on Artificial Intelligence |
---|---|
Vol/bind | 2018-July |
ISSN | 1045-0823 |
ID: 251867419