Parallel CLS shows promise for SAT solving with PB constraints
Redundant constraints can slow convergence, but CLS excels as a hybrid sub-solver.
A new arXiv paper by Cody J Christopher and Charles Gretton investigates the use of parallel Continuous Local Search (CLS) for solving Boolean satisfiability (SAT) problems with symmetric pseudo-Boolean (PB) constraints. The approach relaxes the n-variable PB-satisfiability problem into a continuous optimization task with a differentiable objective function on an n-dimensional hypercube. For satisfiable instances, global minimizers of this function correspond directly to satisfying assignments of the original SAT problem.
Through empirical experiments, the researchers made three key observations. First, redundant constraints — which one might expect to accelerate convergence — actually inhibited progress and slowed the solver down. Second, CLS showed strong potential as a sub-solver in hybridized settings, quickly completing partial assignments that could then be handed off to other solvers. Third, the local search process rapidly converged to a stable distribution of solution quality (degree of satisfaction) because the objective function is saddle-dense, meaning additional solver steps yield diminishing returns. These findings provide practical guidance for deploying CLS on modern accelerator hardware for SAT and related problems.
- Redundant constraints can slow CLS convergence, contradicting common intuition.
- CLS serves as an effective sub-solver in hybrid SAT solvers, completing partial assignments quickly.
- Saddle-dense objectives cause rapid convergence to a stable solution quality with diminishing returns from further steps.
Why It Matters
Improves SAT solving efficiency for AI and logic problems, especially on modern parallel hardware.