用傅里叶变换让连续优化解更复杂的约束问题，无需额外变量。
FourierCSP: Differentiable Constraint Satisfaction Problem Solving by Walsh-Fourier Expansion
- 将沃尔什-傅里叶展开用于约束问题，把复杂约束转为紧凑多项式
- 在多个基准上表现良好，支持大规模有限域约束求解
- 适合想做神经符号系统融合的研究者
约束满足问题（CSP）在数学、物理和理论计算机科学中具有基础地位。近年来，连续局部搜索（CLS）求解器在某些布尔可满足性（SAT）问题上表现出色。受此启发，我们拓展了CLS框架，从布尔SAT推广到具有限域变量和丰富约束形式的通用CSP。提出FourierCSP，一种基于沃尔什-傅里叶展开的连续优化框架，能将多样化约束转化为紧凑的多重线性多项式，避免引入辅助变量和内存密集型编码。采用具有收敛保证的投影子梯度与镜像下降算法，并将其结合以加速梯度优化。在基准测试集上的实验表明，FourierCSP具备可扩展性和竞争力，显著拓宽了可由可微分CLS技术高效求解的问题类别，为端到端神经符号集成铺平道路。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。