On Continuous Local BDD-Based Search for Hybrid SAT Solving

Anastasios Kyrillidis, Moshe Y. Vardi, Zhiwei Zhang

Introduction

Modern Boolean Satisfiability (SAT) solving has traditionally relied on discrete local search or conflict-driven clause learning (CDCL). While these methods are highly optimized for Conjunctive Normal Form (CNF) formulas, they often struggle with "hybrid" constraints—such as XOR gates or Pseudo-Boolean (PB) constraints—which are common in cryptography and optimization. This paper introduces GradSAT, a solver that transforms SAT problems into continuous optimization challenges using Binary Decision Diagrams (BDDs) to efficiently navigate the search space.

The Challenge of Hybrid Constraints

Discrete solvers typically require hybrid constraints to be encoded into CNF, which can lead to a significant "blow-up" in the number of variables and clauses. Continuous Local Search (CLS) offers an alternative by mapping Boolean variables to the real-number interval $[-1, 1]$. However, previous CLS attempts, such as FourierSAT, were hindered by the high computational cost of calculating gradients and limited expressiveness.

The GradSAT Approach: Efficient Gradients via BDDs

GradSAT addresses these limitations by representing Boolean constraints as Multi-Rooted Binary Decision Diagrams (MRBDDs). The core innovation is a message-passing algorithm (similar to belief propagation) that computes the gradient for all variables simultaneously. By performing a top-down and bottom-up pass through the BDD, GradSAT achieves gradient computation that is as computationally cheap as a single function evaluation.

The GradSAT algorithm incorporates dynamic weighting to escape local optima.

The GradSAT workflow involves:

  1. MRBDD Construction: Constraints are converted into a shared BDD structure to optimize memory.
  2. Continuous Relaxation: The Boolean problem is treated as a maximization task on a continuous cube.
  3. Dynamic Weighting: To avoid getting trapped in local optima, the algorithm increases the weights of unsatisfied constraints, a heuristic known as "breakout."

Experimental Evaluation

The researchers evaluated GradSAT against state-of-the-art solvers, including CDCL, discrete local search, and specialized PB solvers. Benchmarks included hybrid random sets (CNF+XOR, PB constraints) and MaxSAT competition tracks.

GradSAT demonstrates competitive performance on hybrid benchmarks compared to traditional discrete solvers.

Key results include:

  • Efficiency: GradSAT achieved a gradient computation speedup of up to 15.5x over FourierSAT.
  • Hybrid Solving: On PB and cardinality benchmarks, GradSAT solved 732 instances, outperforming most general-purpose discrete solvers and trailing only specialized tools like RoundingSAT.
  • Optimization: In MaxSAT tasks, GradSAT consistently found higher-quality solutions than previous continuous methods.

Conclusion and Future Work

GradSAT demonstrates that continuous local search, when powered by efficient BDD-based gradient computation, is a viable and powerful addition to the SAT solving portfolio. While it faces challenges with highly "shattered" solution spaces (like pure XOR problems) and massive industrial instances, future work on stochastic gradient descent and improved variable ordering for BDDs promises to further scale this approach.

Summary updated

Abstract

We explore the potential of continuous local search (CLS) in SAT solving by proposing a novel approach for finding a solution of a hybrid system of Boolean constraints. The algorithm is based on CLS combined with belief propagation on binary decision diagrams (BDDs). Our framework accepts all Boolean constraints that admit compact BDDs, including symmetric Boolean constraints and small-coefficient pseudo-Boolean constraints as interesting families. We propose a novel algorithm for efficiently computing the gradient needed by CLS. We study the capabilities and limitations of our versatile CLS solver, GradSAT, by applying it on many benchmark instances. The experimental results indicate that GradSAT can be a useful addition to the portfolio of existing SAT and MaxSAT solvers for solving Boolean satisfiability and optimization problems.
BibTeX
@inproceedings{kyrillidis2021continuous,
  author = {Anastasios Kyrillidis and Moshe Y. Vardi and Zhiwei Zhang},
  title = {{On Continuous Local BDD-Based Search for Hybrid SAT Solving}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=A40vxBBclVS},
}
Figure