An Effective Learnt Clause Minimization Approach for CDCL SAT Solvers

Mao Luo, Chu-Min Li, Fan Xiao, Felip Manyà, Zhipeng LüIJCAI 2017 · DOI

TL;DR

This paper introduces a novel in-processing technique for CDCL SAT solvers that effectively minimizes redundant literals in learned clauses. By strategically applying Boolean constraint propagation, this approach significantly boosts the performance of leading SAT solvers, enabling them to solve more challenging instances.

What Problem Does This Paper Address?

Modern SAT solvers, particularly those based on Conflict-Driven Clause Learning (CDCL), are powerful tools for solving complex logical problems. A key component of their success is clause learning, where new clauses are generated to represent conflicts encountered during the search. However, these learned clauses often contain "redundant literals" – literals that don't contribute to the clause's logical meaning but can negatively impact performance. These redundant literals can slow down Boolean constraint propagation (BCP), a core mechanism in SAT solvers, and degrade the quality of subsequent learned clauses. While preprocessing techniques to simplify formulas are common, applying similar simplification techniques during the search process (in-processing) to learned clauses has historically been less effective, leading many top solvers to forgo it. This paper aims to bridge this gap by proposing an effective and efficient in-processing method for minimizing learned clauses.

Methods

The core of the proposed approach is an in-processing technique that minimizes redundant literals from learned clauses using Boolean constraint propagation (BCP), specifically unit propagation (UP). The authors carefully address three key questions to ensure effectiveness and efficiency:

  1. When to minimize? Instead of minimizing at every restart, the approach activates minimization based on a condition related to the number of newly learned clauses since the last minimization and the total number of minimizations performed so far. This is inspired by Glucose's clause database reduction strategy.
  2. Which clauses to minimize? Not all learned clauses are minimized. The approach prioritizes clauses with a low Literal Block Distance (LBD). LBD is a measure of clause quality, and clauses with low LBD are considered more relevant and easier to minimize. Clauses are only minimized if they haven't been minimized before.
  3. How to apply UP? The authors define a sort(C) function to order literals within a clause before minimization. They empirically found that processing literals in their original order (roughly the reverse order of their involvement in conflict analysis) is most effective.

The overall process is managed by Algorithm 1 (called at the beginning of each restart) and Algorithm 2 (minimizeL), which iteratively attempts to remove literals from selected clauses using UP. If UP deduces a conflict after asserting a literal, it signifies that the remaining part of the clause is a logical consequence and can potentially replace the original clause. If UP does not deduce a conflict, the literal is added to a new, minimized clause.

Datasets

The authors evaluated their approach on instances from the application and hard combinatorial categories of the 2014 and 2016 SAT competitions. They also used community attachment formulas proposed in [Giráldez-Cru and Levy, 2015] to analyze the impact on community structure.

Key Insights and Ideas

  • In-processing matters: Contrary to the common belief that in-processing clause simplification is less effective than preprocessing, this work demonstrates significant performance gains.
  • LBD is key: Prioritizing clauses with low LBD for minimization is crucial. Minimizing high-LBD clauses is costly and yields little benefit.
  • Strategic activation: Activating minimization based on the number of learned clauses and the history of minimizations (rather than every restart) strikes a good balance between effectiveness and efficiency.
  • Literal ordering is important: The order in which literals are processed during minimization significantly impacts performance, with the original order (derived from conflict analysis) proving most effective.
  • Robustness: The proposed approach is compatible with and complements existing in-processing techniques like recursive clause minimization and binary implication graph simplification.

Key Results

The proposed learnt clause minimization approach was integrated into five leading CDCL SAT solvers (Glucose, TC_Glucose, COMiniSatPS, MapleCOMSPS, and MapleCOMSPS_LRB), creating enhanced versions (e.g., Glucose+, MapleLRB+).

  • Performance Improvement: The enhanced solvers consistently solved a remarkable number of additional instances across various benchmark categories from the 2014 and 2016 SAT competitions. For instance, MapleLRB+ solved 15 more instances than MapleLRB on application categories.
  • Comparison with Prior Work: The approach significantly outperformed the in-processing technique based on binary implication graphs ([Heule et al., 2011]), allowing MapleLRB+ to solve 16 (14) more instances of 2014 (2016) than MapleLRB/noSp.
  • Impact on Clause Structure: The minimization primarily reduces clause size, with a smaller impact on LBD and the number of communities within clauses.
  • Cost-Effectiveness: The approach offers a good trade-off between cost (measured by additional unit propagations) and impact (measured by clause size reduction), leading to overall performance improvements.

Limitations and Future Work

  • Dependency on Solver Implementation: The effectiveness of the liveRestart, liveClause, and sort functions is dependent on the specific implementation details of the underlying SAT solver.
  • Community Structure Impact: While the approach shows some impact on clauses related to community structure, the effect is less pronounced for instances with high modularity, suggesting that minimizing clauses with high community structure might be harder.
  • Future Work: The authors suggest that future SAT solvers will likely incorporate this new in-processing technique. Further exploration into optimizing the liveRestart and liveClause functions for different solver architectures and problem types could be beneficial.

Summary updated

BibTeX
@inproceedings{luo2017effective,
  author = {Mao Luo and Chu-Min Li and Fan Xiao and Felip Manyà and Zhipeng Lü},
  title = {{An Effective Learnt Clause Minimization Approach for CDCL SAT Solvers}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/98},
}
Figure