論文の概要: On Continuous Optimization for Constraint Satisfaction Problems

• arxiv url: http://arxiv.org/abs/2510.04480v1
• Date: Mon, 06 Oct 2025 04:30:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-07 16:52:59.679775
• Title: On Continuous Optimization for Constraint Satisfaction Problems
• Title（参考訳）: 制約満足度問題の連続最適化について
• Authors: Yunuo Cen, Zixuan Wang, Jintao Zhang, Zhiwei Zhang, Xuanyao Fong,
• Abstract要約: 制約満足度問題(Constraint satisfaction problem, CSP)は、数学、物理学、理論計算機科学において基本的な問題である。 近年の進歩により、最近の連続局所探索(CSP)解法は、SAT問題の特定のクラスにおいて高い競争力を発揮することが示されている。 本稿では,Walsh-Fourier変換をCSPに変換する連続最適化フレームワークを提案する。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 制約満足度問題(Constraint satisfaction problem, CSP)は、数学、物理学、理論計算機科学において基本的な問題である。 競合駆動型節学習 Boolean Satisfiability (SAT) ソルバは目覚ましい成功を収め、Boolean satisfiability の主流となる一方で、最近の進歩は、現代の連続局所探索 (CLS) ソルバが、SAT問題のある種のクラスにおいて高い競争力を発揮することを示している。 これらの進歩により、我々は CLS フレームワークを Boolean SAT から、有限領域変数と表現的制約を持つ一般 CSP に拡張した。 本稿では,Walsh-Fourier変換をCSPに変換する連続最適化フレームワークであるFourierCSPを提案する。 提案手法は,回路出力確率による目的物の効率的な評価と微分を応用し,理論的保証を伴う勾配最適化手法を用いる。 ベンチマークスイートの実証的な結果は、FourierCSPはスケーラブルで競争力があり、CLS技術によって効率的に解決できる問題のクラスを著しく拡大していることを示している。

関連論文リスト

• Cutting Slack: Quantum Optimization with Slack-Free Methods for Combinatorial Benchmarks [4.266376725904727]
  制約処理は、量子最適化における重要なボトルネックである。 量子シミュレータやハードウェア上での制約問題を解くために,ラグランジアンに基づく一連の最適化手法について検討する。 この結果は,QUBOのペナライゼーションに代わるスケーラブルな代替手段として,ラグランジアン定式化の柔軟性を強調した。
  論文  参考訳（メタデータ） (2025-07-16T11:39:47Z)
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems [3.757262277494307]
  本稿では,量子近似最適化Ansatzのための制約符号化手法の新たな組み合わせを提案する。 ワンホット制約は、検索空間を実現可能なサブ空間に自然に制限する$XY$-mixerによって強制される。 XY$-mixersは検索スペースを制限するため、特定の状態ベクトルエントリは常にゼロであり、シミュレーションから省略することができ、貴重なメモリとコンピューティングリソースを節約できる。
  論文  参考訳（メタデータ） (2025-06-03T17:46:53Z)
• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。 既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。 これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-21T17:15:48Z)
• Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling [0.0]
  本研究では、連続緩和による勾配に基づく更新と準量子アナリング(QQA)を組み合わせた別のアプローチを提案する。 数値実験により,本手法はiSCOと学習型解法に匹敵する性能を有する汎用解法であることが示された。
  論文  参考訳（メタデータ） (2024-09-02T12:55:27Z)
• A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints [66.61399765513383]
  We developed a BLOCC algorithm to tackle BiLevel Optimization problems with Coupled Constraints。 2つのよく知られた実世界のアプリケーションでその効果を実証する。
  論文  参考訳（メタデータ） (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) は、制約近似を避けるための概念的に単純で決定論的アプローチである。 CUQBは制約のある場合と制約のない場合の両方において従来のベイズ最適化よりも著しく優れることを示す。
  論文  参考訳（メタデータ） (2023-05-05T19:57:36Z)
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
  目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。 アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
  論文  参考訳（メタデータ） (2022-11-29T05:52:17Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。