Journal
THEORY AND APPLICATIONS OF SATISFIABILITY TESTING, SAT 2021
Volume 12831, Issue -, Pages 64-81Publisher
SPRINGER INTERNATIONAL PUBLISHING AG
DOI: 10.1007/978-3-030-80223-3_6
Keywords
CDCL; Local search; Application benchmarks
Funding
- Beijing Academy of Artificial Intelligence (BAAI)
- Youth Innovation Promotion Association, Chinese Academy of Sciences [2017150]
Ask authors/readers for more resources
The study proposes deeper cooperation techniques by enhancing the performance of three typical CDCL solvers, particularly on satisfiable instances. These techniques significantly improve the solver's capabilities and lead to successful outcomes in various benchmarks.
Modern SAT solvers are based on a paradigm named conflict driven clause learning (CDCL), while local search is an important alternative. Although there have been attempts combining these two methods, this work proposes deeper cooperation techniques. First, we relax the CDCL framework by extending promising branches to complete assignments and calling a local search solver to search for a model nearby. More importantly, the local search assignments and the conflict frequency of variables in local search are exploited in the phase selection and branching heuristics of CDCL. We use our techniques to improve three typical CDCL solvers (glucose, MapleLCMDistChronoBT and Kissat). Experiments on benchmarks from the Main tracks of SAT Competitions 2017-2020 and a real world benchmark of spectrum allocation show that the techniques bring significant improvements, particularly on satisfiable instances. For example, the integration of our techniques allow the three CDCL solvers to solve 62, 67 and 10 more instances in the benchmark of SAT Competition 2020. A resulting solver won the Main Track SAT category in SAT Competition 2020 and also performs very well on the spectrum allocation benchmark. As far as we know, this is the first work that meets the standard of the challenge Demonstrate the successful combination of stochastic search and systematic search techniques, by the creation of a new algorithm that outperforms the best previous examples of both approaches. [35] on standard application benchmarks.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available