On Continuous Optimization for Constraint Satisfaction Problems
This work addresses the challenge of efficiently solving CSPs for researchers and practitioners in mathematics, physics, and computer science, representing an incremental extension of existing methods.
The paper tackles the problem of solving general constraint satisfaction problems (CSPs) by extending continuous local search techniques from Boolean SAT to finite-domain CSPs, resulting in a scalable framework called FourierCSP that achieves competitive performance on benchmarks.
Constraint satisfaction problems (CSPs) are fundamental in mathematics, physics, and theoretical computer science. While conflict-driven clause learning Boolean Satisfiability (SAT) solvers have achieved remarkable success and become the mainstream approach for Boolean satisfiability, recent advances show that modern continuous local search (CLS) solvers can achieve highly competitive results on certain classes of SAT problems. Motivated by these advances, we extend the CLS framework from Boolean SAT to general CSP with finite-domain variables and expressive constraints. We present FourierCSP, a continuous optimization framework that generalizes the Walsh-Fourier transform to CSP, allowing for transforming versatile constraints to compact multilinear polynomials, thereby avoiding the need for auxiliary variables and memory-intensive encodings. Our approach leverages efficient evaluation and differentiation of the objective via circuit-output probability and employs a projected gradient optimization method with theoretical guarantees. Empirical results on benchmark suites demonstrate that FourierCSP is scalable and competitive, significantly broadening the class of problems that can be efficiently solved by CLS techniques.