Guiding CDCL SAT Search via Random Exploration amid Conflict Depression

Md. Solimul Chowdhury, Martin Müller, Jia-Huai YouAAAI 2020 · OpenReview

Abstract

The efficiency of Conflict Driven Clause Learning (CDCL) SAT solving depends crucially on finding conflicts at a fast rate. State-of-the-art CDCL branching heuristics such as VSIDS, CHB and LRB conform to this goal. We take a closer look at the way in which conflicts are generated over the course of a CDCL SAT search. Our study of the VSIDS branching heuristic shows that conflicts are typically generated in short bursts, followed by what we call a conflict depression phase in which the search fails to generate any conflicts in a span of decisions. The lack of conflict indicates that the variables that are currently ranked highest by the branching heuristic fail to generate conflicts. Based on this analysis, we propose an exploration strategy, called expSAT, which randomly samples variable selection sequences in order to learn an updated heuristic from the generated conflicts. The goal is to escape from conflict depressions expeditiously. The branching heuristic deployed in expSAT combines these updates with the standard VSIDS activity scores. An extensive empirical evaluation with four state-of-the-art CDCL SAT solvers demonstrates good-to-strong performance gains with the expSAT approach.

Introduction

Modern SAT solvers rely on the Conflict-Driven Clause Learning (CDCL) framework, where performance is driven by the rapid discovery of conflicts. When a solver encounters a contradiction, it learns a new clause to prune the search space. However, empirical observation reveals that conflict generation is not a steady process. Instead, it occurs in intense bursts separated by long "Conflict Depression" (CD) phases. During these depressions, standard branching heuristics like VSIDS often rely on outdated conflict data, leading to a high volume of decisions that fail to produce new learning, effectively wasting CPU resources.

The expSAT Methodology

To address the inefficiency of CD phases, we propose expSAT, a strategy that proactively "kicks" the solver out of depressions through targeted exploration.

Detection and Exploration

The solver monitors the ratio of decisions to conflicts. When consecutive decisions without a conflict exceed a threshold, a "substantial CD phase" is declared. At this point, the solver initiates an exploration episode consisting of multiple short random walks.

The expSAT exploration strategy uses random walks and steps to probe the search space for new conflicts.

In each walk, the solver selects unassigned variables at random and performs Unit Propagation (UP). If a conflict is encountered during these probes, the variables involved are assigned an "exploration score," with higher credit given to variables closer to the conflict via an exponential decay factor.

Heuristic Integration

These exploration scores are integrated with standard VSIDS activity scores. This hybrid approach allows the solver to prioritize variables that demonstrated immediate utility during the random probes, effectively guiding the search toward more productive, conflict-rich regions of the search tree. An adaptive variant, expSAT-ad, further tunes exploration parameters based on the quality of learned "glue" clauses.

Experimental Results

The expSAT extension was evaluated using 750 instances from the SAT Competitions (2017-2018) and 52 hard cryptographic benchmarks from SATCoin.

Performance comparison showing the number of additional instances solved by expSAT-enhanced solvers compared to their baselines over time.

As shown in the performance analysis, the expSAT variants consistently outperformed their respective baselines. On the SAT Competition benchmarks, the best variant solved 16 additional instances and achieved a lower PAR-2 score. The gains were even more pronounced in the cryptographic domain; for instance, one solver increased its solved count from 13 to 29 instances. Notably, the overhead for random exploration was minimal, representing only 3.94% of total runtime while significantly reducing the duration of conflict depression phases.

Conclusion

By identifying and mitigating conflict depression phases, expSAT provides a robust mechanism for improving CDCL SAT solver efficiency. Future work includes extending this exploration strategy to other heuristics like LRB or CHB and investigating its application to polarity selection. Predictive modeling to anticipate the onset of CD phases also remains a promising avenue for further optimization.

Summary updated

Abstract

The efficiency of Conflict Driven Clause Learning (CDCL) SAT solving depends crucially on finding conflicts at a fast rate. State-of-the-art CDCL branching heuristics such as VSIDS, CHB and LRB conform to this goal. We take a closer look at the way in which conflicts are generated over the course of a CDCL SAT search. Our study of the VSIDS branching heuristic shows that conflicts are typically generated in short bursts, followed by what we call a conflict depression phase in which the search fails to generate any conflicts in a span of decisions. The lack of conflict indicates that the variables that are currently ranked highest by the branching heuristic fail to generate conflicts. Based on this analysis, we propose an exploration strategy, called expSAT, which randomly samples variable selection sequences in order to learn an updated heuristic from the generated conflicts. The goal is to escape from conflict depressions expeditiously. The branching heuristic deployed in expSAT combines these updates with the standard VSIDS activity scores. An extensive empirical evaluation with four state-of-the-art CDCL SAT solvers demonstrates good-to-strong performance gains with the expSAT approach.
BibTeX
@inproceedings{chowdhury2020guiding,
  author = {Md. Solimul Chowdhury and Martin Müller and Jia-Huai You},
  title = {{Guiding CDCL SAT Search via Random Exploration amid Conflict Depression}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=RPesmIcOnh},
}

Loading related content...

Figure