On Continuous Optimization for Constraint Satisfaction Problems

• URL: http://arxiv.org/abs/2510.04480v1
• Date: Mon, 06 Oct 2025 04:30:07 GMT
• Title: On Continuous Optimization for Constraint Satisfaction Problems
• Abstract summary: Constraint satisfaction problems (CSPs) are fundamental in mathematics, physics, and theoretical computer science.<n>Recent advances show that modern continuous local search (CSP) solvers can achieve highly competitive results on certain classes of SAT problems.<n>We present a continuous optimization framework that generalizes the Walsh-Fourier transform to CSP, allowing for transforming versatile constraints to compact multi-intensives.
• Score: 33.35208489737497
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Pure and mixed Dicke state ansatz for equality and inequality constraints in variational quantum eigensolver [0.0]
  Combinatorial optimization can be addressed with quantum computing through variational quantum algorithms.<n>A central challenge is to design an ansatz expressive enough to explore the feasible subspace of the Hilbert space where the optimal solution lies.<n>We propose the first feasibility-preserving mixed Dicke state ansatz for Hamming weight constrained optimization.
  arXiv  Detail & Related papers  (2026-06-07T08:10:09Z)
• A Study of Parallel Continuous Local Search [0.6353525052246608]
  Continuous Local Search is a solution approach for satisfiability problems with symmetric pseudo-Boolean constraints.<n>We show that CLS shows promise as a sub-solver in hybridised settings, quickly completing partial assignments.<n>Our findings inform practical uses of CLS for SAT on modern accelerator hardware.
  arXiv  Detail & Related papers  (2026-06-04T19:03:32Z)
• A Complex-Valued Continuous-Variable Quantum Approximation Optimization Algorithm (CCV-QAOA) [3.6704226968275253]
  Continuous-variable quantum systems offer a natural framework for continuous optimization through their infinite spaces.<n>We propose the Complex ContinuousVariable Quantum Approximate Optimization Algorithm (CCV-QAOA), a framework that efficiently solves complex complex optimization problems.
  arXiv  Detail & Related papers  (2026-04-23T08:18:17Z)
• Variational Quantum Algorithm for Constrained Combinatorial Optimization Problems [0.7024739861125416]
  Penalty-based variational quantum algorithms suffer from a fundamental limitation: inefficient sampling in vast infeasible regions.<n>We introduce an alternative VQA whose core innovation lies in a strategically designed loss function.<n>Our design requires adding only an efficient validation oracle module to the penalty-based circuit, resulting in a circuit complexity significantly lower than that of ansatz-based approaches.
  arXiv  Detail & Related papers  (2026-03-06T02:37:05Z)
• Continual Quantum Architecture Search with Tensor-Train Encoding: Theory and Applications to Signal Processing [68.35481158940401]
  CL-QAS is a continual quantum architecture search framework.<n>It mitigates challenges of costly encoding amplitude and forgetting in variational quantum circuits.<n>It achieves controllable robustness expressivity, sample-efficient generalization, and smooth convergence without barren plateaus.
  arXiv  Detail & Related papers  (2026-01-10T02:36:03Z)
• Cutting Slack: Quantum Optimization with Slack-Free Methods for Combinatorial Benchmarks [4.266376725904727]
  Constraint handling remains a key bottleneck in quantum optimization.<n>We investigate a suite of Lagrangian-based optimization techniques for solving constrained problems on quantum simulators and hardware.<n>Our results highlight the flexibility of Lagrangian formulations as a scalable alternative to QUBO penalization.
  arXiv  Detail & Related papers  (2025-07-16T11:39:47Z)
• Adaptive Graph Shrinking for Quantum Optimization of Constrained Combinatorial Problems [4.266376725904727]
  We propose a hybrid classical--quantum framework based on graph shrinking to reduce the number of variables and constraints in QUBO formulations of optimization problems.<n>Our approach improves solution feasibility, reduces repair complexity, and enhances quantum optimization quality on hardware-limited instances.
  arXiv  Detail & Related papers  (2025-06-17T07:11:48Z)
• An Expansion-Based Approach for Quantified Integer Programming [0.0]
  Quantified Programming (QIP) bridges multiple domains by extending Quantified Boolean Formulas (QBF)<n>QIP provides a versatile framework for addressing complex decision-making scenarios.<n>We introduce an expansion-based approach for QIP using Counterexample-Guided Abstraction Refinement (CEGAR)
  arXiv  Detail & Related papers  (2025-06-04T21:14:14Z)
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems [3.757262277494307]
  This paper proposes a novel combination of constraint encoding methods for the Quantum Approximate Optimization Ansatz.<n>One-hot constraints are enforced through $XY$-mixers that restrict the search space to the feasible sub-space naturally.<n>Since $XY$-mixers restrict the search space, specific state vector entries are always zero and can be omitted from the simulation, saving valuable memory and computing resources.
  arXiv  Detail & Related papers  (2025-06-03T17:46:53Z)
• Thinking Out of the Box: Hybrid SAT Solving by Unconstrained Continuous Optimization [25.30924681709063]
  We propose unconstrained continuous optimization for hybrid SAT solving by penalty terms.<n>Our results highlight the potential of combining continuous optimization and machine-learning-based methods for effective hybrid SAT solving.
  arXiv  Detail & Related papers  (2025-05-31T18:58:33Z)
• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  This paper examines a crucial subset of problems where both the objective and constraint functions are weakly convex.<n>Existing methods often face limitations, including slow convergence rates or reliance on double-loop designs.<n>We introduce a novel single-loop penalty-based algorithm to overcome these challenges.
  arXiv  Detail & Related papers  (2025-04-21T17:15:48Z)
• Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling [0.0]
  This study proposes a different approach that integrates gradient-based update through continuous relaxation, combined with Quasi-Quantum Annealing (QQA) Numerical experiments demonstrate that our method is a competitive general-purpose solver, achieving performance comparable to iSCO and learning-based solvers.
  arXiv  Detail & Related papers  (2024-09-02T12:55:27Z)
• A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints [66.61399765513383]
  We develop a BLOCC algorithm to tackle BiLevel Optimization problems with Coupled Constraints. We demonstrate its effectiveness on two well-known real-world applications.
  arXiv  Detail & Related papers  (2024-06-14T15:59:36Z)
• No-Regret Constrained Bayesian Optimization of Noisy and Expensive Hybrid Models using Differentiable Quantile Function Approximations [0.0]
  Constrained Upper Quantile Bound (CUQB) is a conceptually simple, deterministic approach that avoids constraint approximations. We show that CUQB significantly outperforms traditional Bayesian optimization in both constrained and unconstrained cases.
  arXiv  Detail & Related papers  (2023-05-05T19:57:36Z)
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
  We propose a sequential quadratic programming algorithm (TR-StoSQP) to solve nonlinear optimization problems with objectives and deterministic equality constraints. The algorithm adaptively selects the trust-region radius and, compared to the existing line-search StoSQP schemes, allows us to utilize indefinite Hessian matrices.
  arXiv  Detail & Related papers  (2022-11-29T05:52:17Z)
• Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
  In this paper, we develop a simple yet efficient approach for the problem of comparing uncertain quantities. We recast inner optimization in the Lagrangian as a learning problem for surrogate approximation, which bypasses apparent intractability. The proposed light-SD demonstrates superior performance on several representative problems ranging from finance to supply chain management.
  arXiv  Detail & Related papers  (2022-11-14T21:54:31Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.