A New Variable Ordering for In-processing Bounded Variable Elimination in SAT Solvers

Shuolin Li, Chu-Min Li, Mao Luo, Jordi Coll, Djamal Habet, Felip ManyàIJCAI 2023 · DOI

TL;DR

This paper introduces a novel variable ordering strategy called ESA (Elimination Scheduled by Activity) for in-processing Bounded Variable Elimination (BVE) in SAT solvers. By prioritizing variables with lower "activity" (less involvement in recent conflicts), ESA effectively protects more critical variables, leading to significant improvements in the number of solved instances across various state-of-the-art SAT solvers.

What Problem Does This Paper Address?

Modern SAT solvers, particularly those employing Conflict-Driven Clause Learning (CDCL), rely on various techniques to simplify the Boolean formulas they process. Bounded Variable Elimination (BVE) is one such technique, aiming to reduce the formula's complexity by removing variables and their associated clauses. However, BVE has a critical drawback: the order in which variables are eliminated significantly impacts the solver's performance. A poorly chosen order can lead to an explosion in the number of clauses or, worse, eliminate variables that are crucial for the CDCL search, thereby hindering its effectiveness. Furthermore, eliminating a variable also discards all learned clauses containing it, representing a loss of valuable search progress. This paper addresses the challenge of finding an optimal variable ordering for in-processing BVE that maximizes simplification benefits while minimizing the loss of search progress and protecting essential variables.

Methods

The core contribution of this paper is the ESA (Elimination Scheduled by Activity) variable ordering. The principle behind ESA is that variables frequently involved in recent conflicts (i.e., "high activity" variables) are crucial for the CDCL search. Eliminating low-activity variables first, while protecting high-activity ones, is hypothesized to be beneficial.

Here's how it works:

  • Activity Measurement: Variable activity is measured by their participation in recent conflicts. This is often implicitly captured by the decision heuristics used in SAT solvers.
  • ESA Ordering: Variables are sorted in increasing order of their activity. This means variables that have been less involved in recent conflicts are prioritized for elimination.
  • In-processing BVE: ESA is integrated into the in-processing BVE mechanism of CDCL solvers. This means BVE is applied periodically during the SAT solving process, not just as a pre-processing step.
  • Implementation: ESA was implemented in several state-of-the-art SAT solvers, including Cadical and three Kissat-based solvers (Kissat_MAB, Kissat_MAB_HyWalk, and Kissat_Inc). The paper details how ESA is integrated with the specific decision heuristics (VSIDS, CHB, VMTF) of these solvers.

Datasets

The paper evaluates the proposed ESA ordering on a comprehensive benchmark set consisting of all 5675 instances from the Application, Crafted, and Main tracks of the SAT Competitions up to 2022. This includes instances from the Anniversary track of the SAT Competition 2022, augmented with additional instances from the Main track.

Key Insights and Ideas

  • Activity as a Proxy for Importance: The paper posits that variables frequently involved in conflicts are critical for the CDCL search. Protecting these variables from elimination is key.
  • Low Activity First: By eliminating low-activity variables first, ESA indirectly "reinforces" high-activity variables by potentially increasing the number of clauses they appear in, making them less likely to be eliminated themselves.
  • Soft Protection: ESA offers a "soft" protection for high-activity variables, meaning they are not strictly forbidden from elimination but are less likely to be chosen if lower-activity variables also meet the BVE criteria.
  • Decision Heuristics as Activity Indicators: The paper highlights that existing decision heuristics in SAT solvers already quantify variable activity, making them suitable for deriving the ESA ordering.
  • Robustness Across Solvers: ESA demonstrates effectiveness across different solver architectures and decision heuristics, suggesting its general applicability.

Key Results

  • Improved Performance: Solvers equipped with ESA consistently solved more instances than their baseline counterparts across the benchmark set. For example, Cadical_ESA solved more instances than Cadical, and KM_ESA won the Anniversary track of the SAT Competition 2022.
  • Quantitative Gains: Table 1 shows that Cadical_ESA solved 8 more instances than Cadical, and Kissat_MAB_ESA solved 19 more instances than Kissat_MAB. The PAR2 scores (a measure of average solving time) also improved for ESA-equipped solvers.
  • Reduced Learnt Clause Loss: Figure 2 (right) indicates that ESA leads to fewer lost learnt clauses per eliminated variable in the first BVE, suggesting better preservation of search progress.
  • Effective Variable Elimination: Figure 3 shows that while KM_ESA might eliminate fewer variables in the first BVE, it eliminates a comparable or greater number of variables across all BVE calls, indicating a more strategic elimination process.

Limitations and Future Work

  • VMTF Score Unsuitability: The paper found that using the VMTF decision heuristic's score directly for ESA ordering in Kissat_MAB_ESAfull did not yield improvements, suggesting that not all decision heuristics are equally suitable for reflecting variable activity relevant to BVE. Future work could explore better ways to adapt decision heuristic scores or develop new ones for BVE.
  • Instance-Dependent Thresholds: The paper notes that the effectiveness of BVE is influenced by bounds like clauseNbGrowthLimit and resolventLengthLimit. The current threshold for protecting high-activity variables is "soft" and might benefit from being instance-dependent, which is suggested as future research.
  • Broader Application: The principle of protecting high-activity variables could be extended to other CDCL techniques, such as clause deletion heuristics, which also involve removing parts of the search progress. This is identified as a promising avenue for future work.

Summary updated

BibTeX
@inproceedings{li2023new,
  author = {Shuolin Li and Chu-Min Li and Mao Luo and Jordi Coll and Djamal Habet and Felip Manyà},
  title = {{A New Variable Ordering for In-processing Bounded Variable Elimination in SAT Solvers}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/220},
}
Figure