Deep Cooperation of CDCL and Local Search for SAT (Extended Abstract)

Deep Cooperation of CDCL and Local Search for SAT (Extended Abstract)

Shaowei Cai, Xindi Zhang

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
Sister Conferences Best Papers. Pages 5274-5278. https://doi.org/10.24963/ijcai.2022/734

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. 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.'' (AAAI 1997) on standard application benchmarks.
Keywords:
Artificial Intelligence: General