On Continuous Optimization for Constraint Satisfaction Problems

Yunuo Cen, Zixuan Wang, Jintao Zhang, Zhiwei Zhang, Xuanyao FongarXiv 2025 · DOI · arXiv

Introduction

Constraint Satisfaction Problems (CSPs) are fundamental to numerous industrial applications, ranging from airline scheduling to hardware verification. Traditionally, these problems are solved using discrete combinatorial search methods like backtracking and constraint propagation. However, the discrete nature of CSPs makes them incompatible with modern gradient-based deep learning frameworks. FOURIERCSP addresses this gap by transforming discrete constraints into differentiable multilinear polynomials using Walsh-Fourier expansion, enabling the use of continuous optimization techniques on GPUs.

The FOURIERCSP Framework

The core of the FOURIERCSP approach is the Walsh-Fourier Expansion (WFE). By representing discrete constraints as compact multilinear polynomials, the framework "smooths" the search space. Variables are represented on a probability simplex, allowing for a continuous transition between discrete states. A key theoretical insight is that for these multilinear objectives, local minima cannot exist in the interior of the search space; they must lie on the boundaries, ensuring that the continuous search naturally converges toward valid discrete assignments.

Optimization with Hybrid Descent

To navigate the resulting non-convex landscape, the authors introduce Hybrid Descent (HD). This method combines the strengths of Projected Gradient Descent (PGD), which is computationally efficient, and Mirror Descent (MD), which better respects the geometry of the probability simplex.

Figure 2: Performance comparison of PGD, MD, and HD across iterations and time to reach local and global minima.

As shown in Figure 2, Hybrid Descent consistently outperforms standalone PGD or MD in terms of both iterations and total running time to reach global minima. The framework also incorporates acceleration techniques like FISTA to further enhance convergence speed.

Experimental Evaluation and Results

FOURIERCSP was evaluated on benchmarks including random hybrid constraints, task scheduling, and graph coloring. By leveraging JAX for GPU acceleration, the framework achieves massive parallelism, particularly for problems with symmetric constraint patterns.

Figure 6: Running time comparison on a benchmark suite, demonstrating the efficiency of Hybrid Descent and its variants compared to standard PGD.

The results demonstrate significant performance gains. On task scheduling benchmarks, a portfolio version of FOURIERCSP achieved speedups of over 130x compared to industrial solvers like OR-Tools CP-SAT and Gurobi. Figure 6 highlights the dramatic reduction in running time achieved by the proposed optimization strategies compared to standard PGD baselines, where variants like HD and KL (a form of Mirror Descent) solve instances in seconds compared to hundreds of seconds for PGD.

Conclusion and Future Work

FOURIERCSP provides a robust bridge between discrete symbolic reasoning and continuous gradient-based optimization. While the computational complexity of evaluating the full Walsh-Fourier expansion remains a challenge for very dense constraints, the use of Decision Diagrams (MDDs) is proposed as a future direction to maintain efficiency. This work paves the way for integrated neurosymbolic AI systems where deep learning and hard logical constraints can be optimized in a unified differentiable space.

Summary updated

BibTeX
@misc{cen2025continuous,
  author = {Yunuo Cen and Zixuan Wang and Jintao Zhang and Zhiwei Zhang and Xuanyao Fong},
  title = {{On Continuous Optimization for Constraint Satisfaction Problems}},
  year = {2025},
  eprint = {2510.04480},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.04480},
}
Figure