DiverSAT: A Novel and Effective Local Search Algorithm for Diverse SAT Problem

Jiaxin Liang, Junping Zhou, Minghao YinAAAI 2025 · DOI

TL;DR

This paper introduces DiverSAT, a novel local search algorithm designed to find a set of diverse satisfying assignments (models) for Boolean Satisfiability Problems (SAT). Unlike traditional SAT solvers that aim for a single solution, DiverSAT tackles the challenge of generating multiple, distinct solutions, which is crucial for real-world applications like intelligent planning and software testing.

What Problem Does This Paper Address?

The Boolean Satisfiability Problem (SAT) is a fundamental problem in computer science with applications across many fields. While standard SAT solvers focus on finding any single satisfying assignment (a "model") for a given logical formula, many real-world scenarios require not just one solution, but a collection of diverse solutions. This is because a single solution might not capture all the nuances or uncertainties of a complex problem. For instance, in intelligent planning, diverse solutions allow for more robust decision-making in dynamic environments. Similarly, in software testing, diverse models can improve fault detection.

Existing SAT solvers, even when run multiple times, tend to produce similar or identical solutions. This limitation motivates the "Diverse SAT problem," which aims to find a set of k distinct models for a given formula, maximizing the sum of pairwise distances between them. While some prior work has explored related problems like finding solutions with a minimum distance or sampling multiple solutions, dedicated algorithms for the Diverse SAT problem are scarce, with Nadel's DiversekSet being a notable early attempt. However, these existing methods often struggle with solution quality. This paper addresses this gap by proposing an effective local search algorithm, DiverSAT, specifically designed to generate high-quality, diverse sets of SAT solutions.

Methods

DiverSAT employs a local search strategy that iteratively refines a set of k diverse models. The algorithm operates in two main phases:

  • Initialization Phase: This phase aims to generate an initial set of k diverse candidate models. Instead of random generation, DiverSAT uses a novel algorithm called GSMD (Generate a Single Model with Diversity). GSMD incorporates three key heuristics:
  • Variable Decision Heuristic: This heuristic prioritizes variables based on a combination of their order in previous solutions and their activity score (VSIDS), aiming to explore different solution subspaces.
  • Polarity Selection Heuristic: This heuristic guides the assignment of a variable's truth value based on its prevalence in the current set of diverse models, encouraging assignments that increase dissimilarity.
  • SCCA (Strengthening Configuration Checking with Aspiration) Heuristic: This is a greedy heuristic that helps ensure diversity during the local search within GSMD. It's a variant of CCA, but it also considers the flipping preference of variables to maintain diversity.
  • Optimization Phase: Once an initial set of diverse models is established, DiverSAT enters an optimization phase to further improve the diversity of the solution set. This phase involves:
  • Scoring Function: A novel scoring function is introduced to evaluate the diversity contribution of each model within the solution set, measuring its uniqueness relative to others.
  • Model Replacement: The algorithm iteratively replaces the model with the lowest score (least diverse) with a newly generated diverse model from GSMD, provided it improves the overall diversity.
  • Adaptive Perturbation Mechanism: To escape local optima and prevent stagnation, an adaptive perturbation mechanism is employed. If diversity doesn't improve significantly over a set number of iterations, the algorithm replaces a model closest to the newly generated one, rather than the worst-scoring one, to encourage exploration.

Datasets

The paper evaluates DiverSAT on two types of benchmarks:

  • Semiformal Hardware Verification Benchmarks: A collection of 66 instances previously used for testing Diverse SAT solvers (from Nadel, 2011).
  • SAT Application Benchmarks: A large set of 2670 instances sourced from SATLIB. These were filtered to include only instances with more than 100 models, as required by the experimental setup for generating k diverse solutions.

Key Insights and Ideas

  • Diversity is Crucial for Real-World Problems: The paper strongly emphasizes that for many practical applications, a single SAT solution is insufficient, and a diverse set of solutions is highly desirable.
  • Local Search Can Be Adapted for Diversity: By carefully designing heuristics and scoring functions, local search, traditionally used for finding single solutions, can be effectively adapted to the Diverse SAT problem.
  • Heuristics for Diversity Generation: The proposed variable decision and polarity selection heuristics are key to generating initial diverse models, moving beyond simple randomization.
  • Maintaining Diversity is a Challenge: The paper highlights the difficulty of ensuring diversity, as standard SAT solvers tend to converge to similar solutions. The SCCA heuristic and the adaptive perturbation mechanism are designed to combat this.
  • Scoring Models for Diversity Contribution: The novel scoring function is crucial for identifying and replacing the least diverse models in the solution set, directly optimizing for the diversity objective.

Key Results

  • Superior Diversity Quality: DiverSAT consistently achieved higher diversity quality (measured by DQ(S)) compared to two competitive solvers, DiversekSet and randAllSAT, across various problem types and for different values of k (10, 50, 100).
  • Scalability: DiverSAT demonstrated good scalability, particularly on large-scale problems like bmc and hardware, achieving significantly better solutions than the competitors.
  • Runtime Trade-off: While DiverSAT generally consumed more time than the other solvers, the increase in runtime was often justified by the substantial improvement in solution diversity. Ablation studies showed that the core strategies did not drastically increase runtime.
  • Effectiveness of Components: Ablation studies indicated that both the initialization heuristics (variable decision, polarity selection, SCCA) and the adaptive perturbation mechanism contribute significantly to DiverSAT's performance, with each having unique strengths that complement each other.

Limitations and Future Work

  • Runtime: While DiverSAT achieves better diversity, it sometimes incurs a higher runtime compared to other methods. The paper suggests future work could focus on improving convergence speed.
  • Parameter Tuning: The performance of DiverSAT relies on carefully tuned parameters (e.g., pr, λ₁, λ₂, m, r, max_step, max_cnt). Further research could explore more adaptive or automated parameter tuning strategies.
  • Future Directions: The authors suggest future work will focus on developing clearer directions for model generation and achieving faster convergence to better solutions. Exploring more sophisticated techniques for model generation and diversity assessment could also be fruitful.

Summary updated

BibTeX
@inproceedings{liang2025diversat,
  author = {Jiaxin Liang and Junping Zhou and Minghao Yin},
  title = {{DiverSAT: A Novel and Effective Local Search Algorithm for Diverse SAT Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i11.33228},
}
Figure