論文の概要: Reinforcement Learning for Node Selection in Branch-and-Bound

• arxiv url: http://arxiv.org/abs/2310.00112v2
• Date: Wed, 5 Jun 2024 12:36:39 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-07 04:16:10.066818
• Title: Reinforcement Learning for Node Selection in Branch-and-Bound
• Title（参考訳）: 分岐境界におけるノード選択のための強化学習
• Authors: Alexander Mattick, Christopher Mutschler,
• Abstract要約: 現在の最先端セレクタは手作りのアンサンブルを使用して、ナイーブなサブノードセレクタと、個々のノードデータに依存する学習ノードセレクタを自動的に切り替える。 孤立ノードではなく木の状態全体を考慮しながら強化学習(RL)を用いる新しいシミュレーション手法を提案する。
• 参考スコア（独自算出の注目度）: 52.2648997215667
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A big challenge in branch and bound lies in identifying the optimal node within the search tree from which to proceed. Current state-of-the-art selectors utilize either hand-crafted ensembles that automatically switch between naive sub-node selectors, or learned node selectors that rely on individual node data. We propose a novel simulation technique that uses reinforcement learning (RL) while considering the entire tree state, rather than just isolated nodes. To achieve this, we train a graph neural network that produces a probability distribution based on the path from the model's root to its "to-be-selected" leaves. Modelling node-selection as a probability distribution allows us to train the model using state-of-the-art RL techniques that capture both intrinsic node-quality and node-evaluation costs. Our method induces a high quality node selection policy on a set of varied and complex problem sets, despite only being trained on specially designed, synthetic travelling salesmen problem (TSP) instances. Using such a fixed pretrained policy shows significant improvements on several benchmarks in optimality gap reductions and per-node efficiency under strict time constraints.
• Abstract（参考訳）: ブランチとバウンドにおける大きな課題は、検索ツリー内の最適なノードを特定することにある。 現在の最先端セレクタは手作りのアンサンブルを使用して、ナイーブなサブノードセレクタと、個々のノードデータに依存する学習ノードセレクタを自動的に切り替える。 孤立ノードではなく木の状態全体を考慮しながら強化学習(RL)を用いる新しいシミュレーション手法を提案する。 これを実現するために、モデル根から「選択すべき」葉への経路に基づいて確率分布を生成するグラフニューラルネットワークを訓練する。 ノード選択を確率分布としてモデル化することで、本質的なノード品質とノード評価コストの両方をキャプチャする最先端のRL技術を用いてモデルを訓練することができる。 提案手法は,TSP(Synthetic Travelling Salesmen problem)インスタンスでのみ訓練されているにもかかわらず,多種多様な複雑な問題集合に対して高品質なノード選択ポリシーを誘導する。 このような固定事前訓練ポリシーを用いることで、厳しい時間制約下での最適性ギャップ削減とノード単位の効率において、いくつかのベンチマークにおいて顕著な改善が示される。

関連論文リスト

• BANGS: Game-Theoretic Node Selection for Graph Self-Training [39.70859692050266]
  グラフ自己学習は、基礎となるグラフニューラルネットワーク(GNN)モデルをトレーニングするために、ラベルなしデータのセットを反復的に選択する半教師付き学習手法である。 本稿では,ノード選択の目的として,条件付き相互情報とラベル戦略を統一する新しいフレームワークであるBANGSを提案する。 我々のアプローチは、ゲーム理論に基づくもので、ある方法でノードを選択し、ノイズのある目的の下でロバスト性に関する理論的保証を提供する。
  論文  参考訳（メタデータ） (2024-10-12T03:31:28Z)
• Efficient Link Prediction via GNN Layers Induced by Negative Sampling [92.05291395292537]
  リンク予測のためのグラフニューラルネットワーク(GNN)は、緩やかに2つの広いカテゴリに分けられる。 まず、Emphnode-wiseアーキテクチャは各ノードの個別の埋め込みをプリコンパイルし、後に単純なデコーダで結合して予測を行う。 第二に、エンフェッジワイド法は、ペアワイド関係の表現を強化するために、エッジ固有のサブグラフ埋め込みの形成に依存している。
  論文  参考訳（メタデータ） (2023-10-14T07:02:54Z)
• Learning to Compare Nodes in Branch and Bound with Graph Neural Networks [5.08128537391027]
  整数プログラミングにおける分岐とバウンドのアプローチは、次の探索のために空間の一部を順序付けする必要がある。 本稿では,この問題に対処する新たなシアムグラフニューラルネットワークモデルを提案し,ノードを属性付き二部グラフとして表現する。 本手法は,ノードがランクに応じて探索される平易なフレームワークのインスタンスを解くことで評価する。
  論文  参考訳（メタデータ） (2022-10-30T19:38:23Z)
• Provably Efficient Reinforcement Learning for Online Adaptive Influence Maximization [53.11458949694947]
  本稿では,リアルタイムフィードバックに基づいてシードノードを逐次活性化する,コンテンツ依存型オンライン影響問題の適応バージョンについて検討する。 提案アルゴリズムは,最適政策を楽観的に改善しつつ,ネットワークモデルの推定を保守し,適応的にシードを選択する。
  論文  参考訳（メタデータ） (2022-06-29T18:17:28Z)
• Neural Structured Prediction for Inductive Node Classification [29.908759584092167]
  本稿では,ラベル付き学習グラフのモデルを学習し,未ラベルの試験グラフ上でノードラベルを推論するために一般化することを目的とした,帰納的環境におけるノード分類について検討する。 本稿では,両者の利点を組み合わせたSPN(Structured Proxy Network)という新しいアプローチを提案する。
  論文  参考訳（メタデータ） (2022-04-15T15:50:27Z)
• Layer Adaptive Node Selection in Bayesian Neural Networks: Statistical Guarantees and Implementation Details [0.5156484100374059]
  スパースディープニューラルネットワークは、大規模研究において予測モデル構築に効率的であることが証明されている。 本稿では,スパイク・アンド・スラブ型ガウス先行法を用いて,訓練中のノード選択を可能にするベイズスパース解を提案する。 本研究は, 先行パラメータのキャラクタリゼーションとともに, 変動的後続一貫性の基本的な結果を確立する。
  論文  参考訳（メタデータ） (2021-08-25T00:48:07Z)
• Pre-Trained Models for Heterogeneous Information Networks [57.78194356302626]
  異種情報ネットワークの特徴を捉えるための自己教師付き事前学習・微調整フレームワークPF-HINを提案する。 PF-HINは4つのデータセットにおいて、各タスクにおける最先端の代替よりも一貫して、大幅に優れています。
  論文  参考訳（メタデータ） (2020-07-07T03:36:28Z)
• Resource Allocation via Graph Neural Networks in Free Space Optical Fronthaul Networks [119.81868223344173]
  本稿では,自由空間光(FSO)フロントホールネットワークにおける最適資源割り当てについて検討する。 我々は、FSOネットワーク構造を利用するために、ポリシーパラメータ化のためのグラフニューラルネットワーク(GNN)を検討する。 本アルゴリズムは,システムモデルに関する知識が不要なモデルフリーでGNNを訓練するために開発された。
  論文  参考訳（メタデータ） (2020-06-26T14:20:48Z)
• Towards Deeper Graph Neural Networks with Differentiable Group Normalization [61.20639338417576]
  グラフニューラルネットワーク(GNN)は、隣接するノードを集約することでノードの表現を学習する。 オーバースムーシングは、レイヤーの数が増えるにつれてGNNのパフォーマンスが制限される重要な問題のひとつです。 2つのオーバースムースなメトリクスと新しいテクニック、すなわち微分可能群正規化(DGN)を導入する。
  論文  参考訳（メタデータ） (2020-06-12T07:18:02Z)

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

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