論文の概要: Advancing Stochastic 3-SAT Solvers by Dissipating Oversatisfied Constraints

• arxiv url: http://arxiv.org/abs/2506.15774v1
• Date: Wed, 18 Jun 2025 18:00:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-23 19:00:04.781023
• Title: Advancing Stochastic 3-SAT Solvers by Dissipating Oversatisfied Constraints
• Title（参考訳）: 充足制約の分散による確率的3SAT解法の改善
• Authors: J. Schwardt, J. C. Budich,
• Abstract要約: NP完全満足度問題 3-SAT の局所探索を導入,ベンチマークする。 私たちの建設は、WalkSATのような確立した従来のアプローチが、地元のミニマで立ち往生する傾向にあるという決定的な観察に基づいています。 我々は,N=15000までの様々な問題サイズを持つ3SATインスタンスをランダムに生成したサンプルを用いて,アルゴリズムを解析・ベンチマークする。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce and benchmark a stochastic local search heuristic for the NP-complete satisfiability problem 3-SAT that drastically outperforms existing solvers in the notoriously difficult realm of critically hard instances. Our construction is based on the crucial observation that well established previous approaches such as WalkSAT are prone to get stuck in local minima that are distinguished from true solutions by a larger number of oversatisfied combinatorial constraints. To address this issue, the proposed algorithm, coined DOCSAT, dissipates oversatisfied constraints (DOC), i.e. reduces their unfavorable abundance so as to render them critical. We analyze and benchmark our algorithm on a randomly generated sample of hard but satisfiable 3-SAT instances with varying problem sizes up to N=15000. Quite remarkably, we find that DOCSAT outperforms both WalkSAT and other well known algorithms including the complete solver Kissat, even when comparing its ability to solve the hardest quintile of the sample to the average performance of its competitors. The essence of DOCSAT may be seen as a way of harnessing statistical structure beyond the primary cost function of a combinatorial problem to avoid or escape local minima traps in stochastic local search, which opens avenues for generalization to other optimization problems.
• Abstract（参考訳）: 本稿では,NP完全満足度問題 3-SAT に対する確率的局所探索ヒューリスティックを導入,ベンチマークする。 我々の構成は、WalkSATのような確立済みのアプローチが、多くの過剰な組合せ制約によって真の解と区別される局所的なミニマで立ち往生する傾向にあるという決定的な観察に基づいている。 この問題に対処するため、提案アルゴリズムはDOCSATと呼ばれ、過剰な制約(DOC)を解消する。 我々は,N=15000までの様々な問題サイズを持つ3SATインスタンスをランダムに生成したサンプルを用いて,アルゴリズムを解析・ベンチマークする。 DOCSATはWalkSATと完全解法Kissatを含む他のよく知られたアルゴリズムよりも優れており、たとえサンプルの最も難解なクインタイルを競合他社の平均的な性能と比較した場合であっても、非常に優れています。 DOCSATの本質は、確率的局所探索において局所的なミニマトラップを回避または回避するために、組合せ問題の主要なコスト関数を超えて統計構造を利用する方法とみなすことができ、他の最適化問題への一般化の道を開くことができる。

関連論文リスト

• Noise to the Rescue: Escaping Local Minima in Neurosymbolic Local Search [50.24983453990065]
  結合と解離を min と max で表す Godel 論理に BP を適用することは SAT 問題解決のための局所探索アルゴリズムと等価であることを示す。 本稿では,モデルのロジットに雑音を付加し,局所最適化から逃れるゴデルトリックを提案する。
  論文  参考訳（メタデータ） (2025-03-03T18:42:13Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。 赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
  論文  参考訳（メタデータ） (2024-06-21T05:57:08Z)
• Rethinking the Soft Conflict Pseudo Boolean Constraint on MaxSAT Local Search Solvers [20.866863965121013]
  MaxSATは、有名なNP完全満足度問題(SAT)の最適化版である。 そこで我々は,SPB-MaxSATと呼ばれる局所探索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-01-19T09:59:02Z)
• Using deep learning to construct stochastic local search SAT solvers with performance bounds [0.0]
  グラフニューラルネットワークを用いてオーラクルを訓練し、2つのSLSソルバ上で、様々な難易度を持つランダムSATインスタンス上でそれらを評価する。 GNNベースのオラクルへのアクセスは,両者のパフォーマンスを著しく向上させることがわかった。
  論文  参考訳（メタデータ） (2023-09-20T16:27:52Z)
• Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT [55.78588835407174]
  振幅増幅アルゴリズムは、可変代入を満たすために非構造化探索に適用することができる。 Quantum Approximate Optimization Algorithm (QAOA)は、ノイズのある中間量子デバイスのための3SATを解くための有望な候補である。 振幅増幅によるQAOAの変種を導入し、3SATの成功確率を改善する。
  論文  参考訳（メタデータ） (2023-03-02T11:52:39Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。 これらの問題に対する新規で簡単な最適化法を開発した。 結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2021-09-23T17:38:24Z)
• Incomplete MaxSAT Approaches for Combinatorial Testing [0.0]
  本稿では,最小長の制約付き混合被覆アレイを構築するためのSAT(Satifiability)に基づくアプローチを提案する。 この問題はシステム障害検出のためのコンビネータテストの中心である。
  論文  参考訳（メタデータ） (2021-05-26T14:00:56Z)
• On Continuous Local BDD-Based Search for Hybrid SAT Solving [40.252804008544985]
  CLSに必要な勾配を効率的に計算するための新しいアルゴリズムを提案する。 多くのベンチマークインスタンスに適用することにより、多用途CLSソルバであるGradSATの機能と限界について検討する。 実験結果から,GradSATは既存のSATおよびMaxSATソルバのポートフォリオに追加され,ブール適合性および最適化問題の解決に有用であることが示唆された。
  論文  参考訳（メタデータ） (2020-12-14T22:36:20Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。 最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。 提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
  論文  参考訳（メタデータ） (2020-06-08T09:25:47Z)

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

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