Seeking practical CDCL insights from theoretical SAT benchmarks

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Over the last decades Boolean satisfiability (SAT) solvers based on conflict-driven clause learning (CDCL) have developed to the point where they can handle formulas with millions of variables. Yet a deeper understanding of how these solvers can be so successful has remained elusive. In this work we shed light on CDCL performance by using theoretical benchmarks, which have the attractive features of being a) scalable, b) extremal with respect to different proof search parameters, and c) theoretically easy in the sense of having short proofs in the resolution proof system underlying CDCL. This allows for a systematic study of solver heuristics and how efficiently they search for proofs. We report results from extensive experiments on a wide range of benchmarks. Our findings include several examples where theory predicts and explains CDCL behaviour, but also raise a number of intriguing questions for further study.

Original languageEnglish
Title of host publicationProceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018
EditorsJerome Lang
Number of pages9
PublisherInternational Joint Conferences on Artificial Intelligence
Publication date2018
Pages1300-1308
ISBN (Electronic)9780999241127
DOIs
Publication statusPublished - 2018
Externally publishedYes
Event27th International Joint Conference on Artificial Intelligence, IJCAI 2018 - Stockholm, Sweden
Duration: 13 Jul 201819 Jul 2018

Conference

Conference27th International Joint Conference on Artificial Intelligence, IJCAI 2018
LandSweden
ByStockholm
Periode13/07/201819/07/2018
SponsorInternational Joint Conferences on Artifical Intelligence (IJCAI)
SeriesIJCAI International Joint Conference on Artificial Intelligence
Volume2018-July
ISSN1045-0823

ID: 251867360