論文の概要: Learning to Rank the Initial Branching Order of SAT Solvers

• arxiv url: http://arxiv.org/abs/2603.07176v1
• Date: Sat, 07 Mar 2026 12:35:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-10 15:13:13.99207
• Title: Learning to Rank the Initial Branching Order of SAT Solvers
• Title（参考訳）: SATソルバーの初期分岐順序をランク付けする学習
• Authors: Arvid Eriksson, Gabriel Poesia, Roman Bresson, Karl Henrik Johansson, David Broman,
• Abstract要約: SAT問題を解く前に、学習に基づくアプローチを用いて、優れた分岐順序を予測する。 既存のCDCL SATソルバでは、優れた初期分岐を提供することで、大きな利益が得られることを示す。 また、そのような初期分岐順序を抽出可能な方法で見つけるための3つのラベリング手法も提供する。
• 参考スコア（独自算出の注目度）: 12.097954536315386
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Finding good branching orders is key to solving SAT problems efficiently, but finding such branching orders is a difficult problem. Using a learning based approach to predict a good branching order before solving, therefore, has potential. In this paper, we investigate predicting branching orders using graph neural networks as a preprocessing step to conflict-driven clause learning (CDCL) SAT solvers. We show that there are significant gains to be made in existing CDCL SAT solvers by providing a good initial branching. Further, we provide three labeling methods to find such initial branching orders in a tractable way. Finally, we train a graph neural network to predict these branching orders and show through our evaluations that a GNN-initialized ordering yields significant speedups on random 3-CNF and pseudo-industrial benchmarks, with generalization capabilities to instances much larger than the training set. However, we also find that the predictions fail at speeding up more difficult and industrial instances. We attribute this to the solver's dynamic heuristics, which rapidly overwrite the provided initialization, and to the complexity of these instances, making GNN prediction hard.
• Abstract（参考訳）: SAT問題を効率的に解くためには、優れた分岐順序を見つけることが重要であるが、そのような分岐順序を見つけることは難しい問題である。 学習に基づくアプローチを使用して、解決する前に優れた分岐順序を予測する。 本稿では、競合駆動節学習(CDCL)SATソルバの前処理ステップとしてグラフニューラルネットワークを用いた分岐順序の予測について検討する。 既存のCDCL SATソルバでは、優れた初期分岐を提供することで、大きな利益が得られることを示す。 さらに,これらの初期分岐順序を抽出可能な方法で検索する3つのラベリング手法を提案する。 最後に、これらの分岐順序を予測するためにグラフニューラルネットワークをトレーニングし、GNN初期化順序付けにより、ランダムな3CNFと擬似産業ベンチマークにおいて、トレーニングセットよりもはるかに大きなインスタンスに一般化機能を持たせ、かなりのスピードアップが得られることを示す。 しかし、予測はより困難で工業的なインスタンスをスピードアップするのに失敗する。 これは、提供された初期化を素早く上書きする解法の動的ヒューリスティックスと、これらのインスタンスの複雑さのため、GNN予測を困難にしている。

関連論文リスト

• Faster Predictive Coding Networks via Better Initialization [52.419343840654186]
  本稿では,従来のトレーニングサンプルの反復的進捗を抑えることを目的とした,予測符号化ネットワークのための新しい手法を提案する。 本実験は,教師なし設定と教師なし設定の両方において,収束速度と最終テスト損失が大幅に改善されたことを示す。
  論文  参考訳（メタデータ） (2026-01-28T08:52:19Z)
• On the Bias of Next-Token Predictors Toward Systematically Inefficient Reasoning: A Shortest-Path Case Study [4.798155648915794]
  大規模言語モデルにおける推論を改善するための2つの重要な要因について検討する。 我々は、カスタムトークン化器を用いて、質問-トレース-回答三重項に対してデコーダのみの変換器を訓練する。 同じトレーニングの予算で、非効率なトレースで訓練されたモデルは、目に見えないグラフよりも一般化される。
  論文  参考訳（メタデータ） (2025-07-07T18:00:06Z)
• Learning from Algorithm Feedback: One-Shot SAT Solver Guidance with GNNs [2.722939308105689]
  この研究は、グラフニューラルネットワーク(GNN)を用いたSATソルバ分岐をガイドするパラダイムとして、RLAF(Reinforcement Learning from Algorithm Feedback)を導入している。 RLAFを訓練したポリシーは、多様なSAT問題分布にまたがる様々なベースソルバの平均解時間を著しく削減し、場合によっては2倍以上のスピードアップを達成する。
  論文  参考訳（メタデータ） (2025-05-21T22:07:08Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  ニューラルネットワーク推論タスクのOOD一般化について検討する。 目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
  論文  参考訳（メタデータ） (2022-11-01T18:33:20Z)
• A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking [124.21408098724551]
  グラフニューラルネットワーク(GNN)の大規模グラフトレーニングは、非常に難しい問題である 本稿では,既存の問題に対処するため,EnGCNという新たなアンサンブルトレーニング手法を提案する。 提案手法は,大規模データセット上でのSOTA(State-of-the-art)の性能向上を実現している。
  論文  参考訳（メタデータ） (2022-10-14T03:43:05Z)
• Discovering Non-monotonic Autoregressive Orderings with Variational Inference [67.27561153666211]
  我々は、訓練データから高品質な生成順序を純粋に検出する、教師なし並列化可能な学習装置を開発した。 エンコーダを非因果的注意を持つトランスフォーマーとして実装し、1つのフォワードパスで置換を出力する。 言語モデリングタスクにおける経験的結果から,我々の手法は文脈認識であり,一定の順序と競合する,あるいはより優れた順序を見つけることができる。
  論文  参考訳（メタデータ） (2021-10-27T16:08:09Z)
• Learning to Hash with Graph Neural Networks for Recommender Systems [103.82479899868191]
  グラフ表現学習は、大規模に高品質な候補探索をサポートすることに多くの注目を集めている。 ユーザ・イテム相互作用ネットワークにおけるオブジェクトの埋め込みベクトルの学習の有効性にもかかわらず、連続的な埋め込み空間におけるユーザの好みを推測する計算コストは膨大である。 連続的かつ離散的なコードとを協調的に学習するための,単純かつ効果的な離散表現学習フレームワークを提案する。
  論文  参考訳（メタデータ） (2020-03-04T06:59:56Z)

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

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