論文の概要: Learning from Algorithm Feedback: One-Shot SAT Solver Guidance with GNNs

• arxiv url: http://arxiv.org/abs/2505.16053v1
• Date: Wed, 21 May 2025 22:07:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-23 17:12:47.930555
• Title: Learning from Algorithm Feedback: One-Shot SAT Solver Guidance with GNNs
• Title（参考訳）: アルゴリズムフィードバックからの学習:GNNによるワンショットSATソルバガイダンス
• Authors: Jan Tönshoff, Martin Grohe,
• Abstract要約: この研究は、グラフニューラルネットワーク(GNN)を用いたSATソルバ分岐をガイドするパラダイムとして、RLAF(Reinforcement Learning from Algorithm Feedback)を導入している。 RLAFを訓練したポリシーは、多様なSAT問題分布にまたがる様々なベースソルバの平均解時間を著しく削減し、場合によっては2倍以上のスピードアップを達成する。
• 参考スコア（独自算出の注目度）: 2.722939308105689
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Boolean Satisfiability (SAT) solvers are foundational to computer science, yet their performance typically hinges on hand-crafted heuristics. This work introduces Reinforcement Learning from Algorithm Feedback (RLAF) as a paradigm for learning to guide SAT solver branching heuristics with Graph Neural Networks (GNNs). Central to our approach is a novel and generic mechanism for injecting inferred variable weights and polarities into the branching heuristics of existing SAT solvers. In a single forward pass, a GNN assigns these parameters to all variables. Casting this one-shot guidance as a reinforcement learning problem lets us train the GNN with off-the-shelf policy-gradient methods, such as GRPO, directly using the solver's computational cost as the sole reward signal. Extensive evaluations demonstrate that RLAF-trained policies significantly reduce the mean solve times of different base solvers across diverse SAT problem distributions, achieving more than a 2x speedup in some cases, while generalizing effectively to larger and harder problems after training. Notably, these policies consistently outperform expert-supervised approaches based on learning handcrafted weighting heuristics, offering a promising path towards data-driven heuristic design in combinatorial optimization.
• Abstract（参考訳）: Boolean Satisfiability (SAT) はコンピュータ科学の基礎となっているが、その性能は手作りのヒューリスティックにかかっている。 本稿では,アルゴリズムフィードバックによる強化学習(RLAF)を,グラフニューラルネットワーク(GNN)を用いたSATソルバ分岐ヒューリスティックの学習パラダイムとして紹介する。 我々のアプローチの中心は、既存のSATソルバの分岐ヒューリスティックに推論された変動重みと極性を注入するための、新しくて汎用的なメカニズムである。 単一のフォワードパスでは、GNNはこれらのパラメータをすべての変数に割り当てる。 このワンショットガイダンスを強化学習問題として活用することで、GRPOのような市販のポリシー段階の手法でGNNを訓練し、計算コストを唯一の報酬信号として直接利用することができる。 大規模評価の結果, RLAF 学習ポリシーは様々な SAT 問題分布にまたがる基本解法の平均解時間を著しく短縮し, 場合によっては2倍以上の高速化を実現し, 訓練後のより大規模で難しい問題に効果的に一般化できることが示唆された。 特に、これらのポリシーは、手作りの重み付けヒューリスティックの学習に基づく専門家によるアプローチを一貫して上回り、組合せ最適化におけるデータ駆動ヒューリスティック設計への有望な道を提供する。

関連論文リスト

• Assessing and Enhancing Graph Neural Networks for Combinatorial Optimization: Novel Approaches and Application in Maximum Independent Set Problems [0.0]
  Graph Neural Networks (GNNs)は、コンビネーション最適化(CO)問題の解決における研究者の約束を示す。 本研究では,最大独立集合(MIS)問題の解法におけるGNNの有効性について検討した。
  論文  参考訳（メタデータ） (2024-11-06T09:12:31Z)
• Using deep learning to construct stochastic local search SAT solvers with performance bounds [0.0]
  グラフニューラルネットワークを用いてオーラクルを訓練し、2つのSLSソルバ上で、様々な難易度を持つランダムSATインスタンス上でそれらを評価する。 GNNベースのオラクルへのアクセスは,両者のパフォーマンスを著しく向上させることがわかった。
  論文  参考訳（メタデータ） (2023-09-20T16:27:52Z)
• Stochastic Unrolled Federated Learning [85.6993263983062]
  本稿では,UnRolled Federated Learning (SURF)を導入する。 提案手法は,この拡張における2つの課題,すなわち,非学習者へのデータセット全体の供給の必要性と,フェデレート学習の分散的性質に対処する。
  論文  参考訳（メタデータ） (2023-05-24T17:26:22Z)
• Learning To Dive In Branch And Bound [95.13209326119153]
  グラフニューラルネットワークを用いて特定の潜水構造を学習するためのL2Diveを提案する。 我々は、変数の割り当てを予測するために生成モデルを訓練し、線形プログラムの双対性を利用して潜水決定を行う。
  論文  参考訳（メタデータ） (2023-01-24T12:01:45Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  ニューラルネットワーク推論タスクのOOD一般化について検討する。 目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
  論文  参考訳（メタデータ） (2022-11-01T18:33:20Z)
• NeuroBack: Improving CDCL SAT Solving using Graph Neural Networks [13.185943308470286]
  提案的満足度(SAT)は、計画、検証、セキュリティなど、多くの研究分野に影響を与えるNP完全問題である。 グラフニューラルネットワーク(GNN)を用いたCDCL SATソルバの高速化に向けた最近の研究 本稿では,(1)CDCL SATの解法に必要不可欠である変数の位相(すなわち値)を予測すること,(2)SATの解法開始前に1回だけニューラルネットワークに問い合わせること,の2つの知見に基づくNeuroBackという手法を提案する。
  論文  参考訳（メタデータ） (2021-10-26T22:08:22Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。 我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。 いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
  論文  参考訳（メタデータ） (2020-05-05T18:08:23Z)

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

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