TL;DR
This paper investigates the effectiveness of various heuristics in Conflict-Driven Clause Learning (CDCL) SAT solvers by using theoretically constructed benchmarks with known properties. The authors found that while many heuristics are crucial for performance, their interactions are complex, and theoretical insights can explain observed solver behavior, opening avenues for further research into CDCL's underlying mechanisms.
What Problem Does This Paper Address?
Boolean Satisfiability (SAT) solvers, particularly those based on Conflict-Driven Clause Learning (CDCL), have become incredibly powerful, capable of solving problems with millions of variables. However, a deep understanding of why these solvers are so effective, especially the interplay of their numerous sophisticated heuristics, remains elusive. Traditional approaches of using real-world benchmarks are hampered by their limited size and diversity, making it difficult to draw statistically significant conclusions about heuristic performance. This paper aims to bridge this gap by using theoretically designed benchmarks that are scalable, extremal with respect to complexity-theoretic properties, and possess short resolution proofs, allowing for a systematic study of CDCL heuristics and their impact on proof search efficiency.
Methods
The core of this research involves an instrumented CDCL solver built upon Glucose, a state-of-the-art SAT solver. This instrumented solver allows for fine-grained control over various heuristic parameters, including:
- Restart Policy: Investigating adaptive restarts (Glucose), fixed-interval Luby restarts, and disabling restarts entirely.
- Variable Decisions: Comparing VSIDS (Variable State Independent Decaying Sum) with different decay factors and the Learning Rate Based Branching (LRB) heuristic.
- Phase Selection: Examining standard phase saving, dynamic phases, and fixed phases.
- Clause Erasure: Analyzing different policies for removing learned clauses, from aggressive (MiniSat-like) to more generous (Glucose-like) and no erasure.
- Clause Assessment: Evaluating heuristics like Literal Block Distance (LBD) and activity-based assessment for identifying important clauses.
- Learning Scheme: Comparing 1UIP (Unique Implication Point) clause learning with last-decision UIP learning.
- Preprocessing: Assessing the impact of standard preprocessing steps.
The authors employed a combination of quantitative analysis (PAR scores, timeouts) and qualitative analysis (heatmaps) to understand the interactions between these heuristics and the theoretical properties of the benchmarks.
Datasets
The paper introduces and utilizes 9 families of crafted theoretical benchmarks. These benchmarks are derived from formulas with asymptotically proven extremal properties in proof complexity. While these formulas are sometimes scaled down for practical experiments (losing some asymptotic guarantees), they retain their character as challenging instances. A key feature of these benchmarks is that they are designed to have short resolution proofs, meaning that CDCL performance on them primarily reflects the efficiency of the proof search itself.
Key Insights and Ideas
- Restarts are Crucial: Frequent restarts appear essential for CDCL solvers to harness the full power of resolution, particularly for formulas that are hard for restricted proof systems but easy for general resolution.
- Learned Clauses are Critical: Solvers critically need to store learned clauses to move beyond tree-like DPLL-style search to general resolution proofs, significantly boosting reasoning power.
- Clause Erasure Trade-offs: While aggressive clause erasure can be detrimental to proof search quality, it can be important for performance on certain challenging formulas where unit propagation becomes a bottleneck.
- VSIDS Decay Factor Matters: The choice of decay factor in VSIDS can be critically important, with different values being optimal for different benchmark families, potentially correlating with whether tree-like or DAG-like proofs are more suitable.
- Phase Saving is Under-understood but Vital: Standard phase saving is empirically essential for good performance on many benchmarks, though its theoretical underpinnings are unclear.
- LBD for Clause Assessment is Effective: The Literal Block Distance (LBD) heuristic for clause assessment consistently shows improvement, suggesting it helps in identifying important clauses to retain.
Key Results
The paper reports on extensive experiments involving over 650 solver configurations, requiring hundreds of years of computation time. Key findings include:
- Adaptive restarts generally outperform fixed-interval restarts, but can sometimes perform poorly when they are incorrectly triggered.
- The LRB heuristic for variable decisions did not consistently outperform VSIDS with a high decay factor.
- For partial ordering principle formulas, a high VSIDS decay factor makes them nearly impossible to solve, while a lower factor makes them easy, highlighting the sensitivity to this parameter.
- Clause erasure policies significantly impact performance, with MiniSat's aggressive approach sometimes suffering, while Glucose's more generous approach combined with LBD assessment generally performs well.
- The paper provides empirical evidence for time-space trade-offs in practice for certain theoretical benchmark families, a novel observation.
Limitations and Future Work
The authors acknowledge several limitations:
- Correlation vs. Causation: While theoretical insights inform interpretation, correlation does not imply causation.
- Scaled-Down Benchmarks: The use of scaled-down theoretical benchmarks means asymptotic properties may not strictly hold.
- Unsatisfiable Instances Only: The study exclusively focuses on unsatisfiable instances due to the nature of proof complexity, which might not fully represent performance on satisfiable problems.
- Combinatorial Explosion: The vast number of possible heuristic combinations makes a full exploration infeasible.
Future work directions include:
- Investigating the precise timing of restarts and exploring combinations of adaptive and fixed-interval restarts.
- Developing adaptive methods for determining the optimal VSIDS decay factor.
- Further theoretical and empirical study of phase saving.
- Exploring whether removing "junk clauses" can ever be beneficial for proof search quality.
- Investigating the observed phenomenon where clique formulas require restarts to be switched off.
Summary updated