TL;DR
This paper introduces novel techniques for deeper integration of two powerful SAT solving paradigms: Conflict-Driven Clause Learning (CDCL) and local search. By allowing CDCL to leverage local search for exploring promising branches and using local search insights to guide CDCL's heuristics, they achieve significant performance improvements, particularly on satisfiable instances, and meet a long-standing challenge in SAT research.
What Problem Does This Paper Address?
The Satisfiability (SAT) problem, a fundamental challenge in computer science, asks whether a given logical formula can be satisfied. Two dominant approaches to solving SAT are Conflict-Driven Clause Learning (CDCL), a systematic search method, and local search, an incomplete but often faster method for finding solutions. While hybrid approaches combining these have existed, they often treat each other as black boxes. This paper aims to bridge this gap by proposing a deeper cooperation where local search actively assists CDCL, going beyond simple invocation. The goal is to harness the strengths of both systematic and stochastic search to outperform existing state-of-the-art solvers.
Methods
The authors propose three key techniques for integrating local search into CDCL:
- Relaxed CDCL with Local Search Exploration: When CDCL encounters a promising branch (defined by certain criteria related to assignment depth and lack of conflicts), it extends this branch to a complete assignment. This complete assignment is then handed over to a local search solver. If local search fails to find a solution within a time limit, CDCL resumes its search from where it left off. This allows CDCL to explore potentially fruitful areas of the search space more thoroughly.
- Local Search Rephasing: Insights from local search are used to improve CDCL's branching heuristics. Specifically, assignments generated by local search are used to "rephase" (i.e., reset the preferred assignment value for) variables when CDCL restarts. This helps guide the systematic search with information gathered from the local search exploration.
- Branching with Conflict Frequency: The frequency with which variables appear in unsatisfied clauses during local search is used to enhance CDCL's branching heuristics. This "conflict frequency" metric is incorporated into the activity scores of variables in heuristics like VSIDS or used to adjust learning rates in LRB, aiming to prioritize variables that are problematic in the local search context.
Datasets
The experiments were conducted on:
- Benchmarks from the main tracks of the SAT Competitions from 2017 to 2020.
- A real-world benchmark suite of 10000 instances from spectrum repacking.
Key Insights and Ideas
- Deeper Cooperation is Key: Simply calling local search from CDCL isn't enough; integrating local search insights into CDCL's core mechanisms (like branching heuristics and variable rephasing) yields substantial gains.
- Satisfiable Instances Benefit Most: The techniques are particularly effective for finding solutions to satisfiable instances, where local search excels.
- Meeting a Grand Challenge: The work claims to meet Selman's 7th challenge: demonstrating a successful combination of stochastic and systematic search that outperforms the best of each approach on application benchmarks.
- Local Search as a "Guide": Local search, when integrated deeply, acts not just as a solver but as a source of intelligence to guide the more systematic CDCL search.
Key Results
The proposed techniques significantly improved the performance of three state-of-the-art CDCL solvers (glucose, MapleLCMDistChronoBT-DL, and Kissat_sat).
- For the SAT Competition 2020 benchmark, the enhanced glucose solver solved 62 additional instances, and the enhanced Maple-DL solver solved 67 additional instances.
- On the spectrum repacking benchmark, the enhanced Maple solver solved the most instances (8977 total).
- The hybrid solvers solved a notable number of instances that neither the base CDCL solver nor the local search solver could solve independently, demonstrating the synergy of the techniques.
- While improvements are significant for satisfiable instances, there's a slight degradation (solving 2-3 fewer instances) on unsatisfiable instances, which is a common trade-off in such hybrid approaches.
Limitations and Future Work
- Degradation on Unsatisfiable Instances: The techniques show a slight decrease in performance on unsatisfiable instances.
- Future Work: The paper suggests further exploration of how to best leverage local search insights for improving CDCL, particularly for unsatisfiable instances. The authors also mention that the integration of these techniques is a significant step towards addressing broader challenges in combining different AI search paradigms.
Summary updated