Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.04480 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910002792366080 |
|---|---|
| author | Cen, Yunuo Wang, Zixuan Zhang, Jintao Zhang, Zhiwei Fong, Xuanyao |
| author_facet | Cen, Yunuo Wang, Zixuan Zhang, Jintao Zhang, Zhiwei Fong, Xuanyao |
| contents | The Constraint-satisfaction problem (CSP) is fundamental in mathematics, physics, and theoretical computer science. Continuous local search (CLS) solvers, as recent advancements, can achieve highly competitive results on certain classes of Boolean satisfiability (SAT) problems. Motivated by these advances, we extend the CLS framework from Boolean SAT to general CSP with finite-domain variables and expressive constraint formulations. 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. We employ projected subgradient and mirror descent algorithms with provable convergence guarantees, and further combine them to accelerate gradient-based optimization. Empirical results on benchmark suites demonstrate that FourierCSP is scalable and competitive, significantly broadening the class of problems that can be efficiently solved by differentiable CLS techniques and paving the way toward end-to-end neurosymbolic integration. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_04480 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | FourierCSP: Differentiable Constraint Satisfaction Problem Solving by Walsh-Fourier Expansion Cen, Yunuo Wang, Zixuan Zhang, Jintao Zhang, Zhiwei Fong, Xuanyao Artificial Intelligence The Constraint-satisfaction problem (CSP) is fundamental in mathematics, physics, and theoretical computer science. Continuous local search (CLS) solvers, as recent advancements, can achieve highly competitive results on certain classes of Boolean satisfiability (SAT) problems. Motivated by these advances, we extend the CLS framework from Boolean SAT to general CSP with finite-domain variables and expressive constraint formulations. 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. We employ projected subgradient and mirror descent algorithms with provable convergence guarantees, and further combine them to accelerate gradient-based optimization. Empirical results on benchmark suites demonstrate that FourierCSP is scalable and competitive, significantly broadening the class of problems that can be efficiently solved by differentiable CLS techniques and paving the way toward end-to-end neurosymbolic integration. |
| title | FourierCSP: Differentiable Constraint Satisfaction Problem Solving by Walsh-Fourier Expansion |
| topic | Artificial Intelligence |
| url | https://arxiv.org/abs/2510.04480 |