論文の概要: A Study of Parallel Continuous Local Search

• arxiv url: http://arxiv.org/abs/2606.06656v2
• Date: Mon, 08 Jun 2026 15:19:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-09 14:42:05.061172
• Title: A Study of Parallel Continuous Local Search
• Title（参考訳）: 並列連続局所探索に関する研究
• Authors: Cody J Christopher, Charles Gretton,
• Abstract要約: 連続局所探索は対称擬似ブール制約による満足度問題に対する解法である。 CLSは、ハイブリダイズされた設定におけるサブソルバとして有望であり、部分的な割り当てを迅速に完了することを示す。 本研究は,最近のアクセラレータハードウェアにおけるSATにおけるLCSの実用的利用を示唆するものである。
• 参考スコア（独自算出の注目度）: 0.6353525052246608
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study parallel Continuous Local Search (CLS) as a solution approach for Boolean satisfiability problems with symmetric pseudo-Boolean (PB) constraints. Here, the $n$-variable PB-satisfiability problem is relaxed to a continuous optimisation problem with a differentiable objective function on an $n$-dimensional hypercube. For satisfiable instances, the global minimisers of this optimisation problem correspond to satisfying assignments of the SAT problem at hand. We present several novel findings via empirical experiments: (i) redundant constraints can inhibit rather than accelerate convergence; (ii) CLS shows promise as a sub-solver in hybridised settings, quickly completing partial assignments; and (iii) local search rapidly converges to a stable distribution of solution quality (i.e., degree of satisfaction), due to saddle-dense objectives where additional solver steps yield diminishing returns. Our findings inform practical uses of CLS for SAT on modern accelerator hardware.
• Abstract（参考訳）: 並列連続局所探索(CLS)を対称擬似ブール制約を用いたブール適合性問題に対する解法として検討した。 ここで、$n$-variable PB-satisfiability 問題は、$n$-dimensional ハイパーキューブ上の微分可能な目的関数を持つ連続最適化問題に緩和される。 満足のいく例では、この最適化問題の大域的最小化は、手元にあるSAT問題の割り当てを満たすことに対応する。 実験を通して,いくつかの新しい知見を提示する。 一 余分な制約は、収束を加速させるよりはむしろ抑制することができる。 (二)CLSは、ハイブリダイズされた設定におけるサブソルバとして約束を示し、迅速に部分割り当てを完了させる。 三 局所探索は、解法を加味して利得が減少するサドル密度目標により、解の質(すなわち満足度)の安定分布に急速に収束する。 本研究は,最近のアクセラレータハードウェアにおけるSATにおけるLCSの実用的利用を示唆するものである。

関連論文リスト

• On Continuous Optimization for Constraint Satisfaction Problems [33.35208489737497]
  制約満足度問題(Constraint satisfaction problem, CSP)は、数学、物理学、理論計算機科学において基本的な問題である。 近年の進歩により、最近の連続局所探索(CSP)解法は、SAT問題の特定のクラスにおいて高い競争力を発揮することが示されている。 本稿では,Walsh-Fourier変換をCSPに変換する連続最適化フレームワークを提案する。
  論文  参考訳（メタデータ） (2025-10-06T04:30:07Z)
• 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)
• 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)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling [86.85697555068168]
  2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。 特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。 PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
  論文  参考訳（メタデータ） (2021-05-05T03:36:00Z)
• On Continuous Local BDD-Based Search for Hybrid SAT Solving [40.252804008544985]
  CLSに必要な勾配を効率的に計算するための新しいアルゴリズムを提案する。 多くのベンチマークインスタンスに適用することにより、多用途CLSソルバであるGradSATの機能と限界について検討する。 実験結果から,GradSATは既存のSATおよびMaxSATソルバのポートフォリオに追加され,ブール適合性および最適化問題の解決に有用であることが示唆された。
  論文  参考訳（メタデータ） (2020-12-14T22:36:20Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)

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

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