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 workflow involves:
- MRBDD Construction: Constraints are converted into a shared BDD structure to optimize memory.
- Continuous Relaxation: The Boolean problem is treated as a maximization task on a continuous cube.
- 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.
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