論文の概要: Reinforcement Learning for Node Selection in Branch-and-Bound
- arxiv url: http://arxiv.org/abs/2310.00112v1
- Date: Fri, 29 Sep 2023 19:55:56 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-05 06:31:27.141270
- Title: Reinforcement Learning for Node Selection in Branch-and-Bound
- Title(参考訳): 分岐境界におけるノード選択のための強化学習
- Authors: Alexander Mattick and Christopher Mutschler
- Abstract要約: 現在の最先端セレクタは手作りのアンサンブルを使用して、ナイーブなサブノードセレクタと、個々のノードデータに依存する学習ノードセレクタを自動的に切り替える。
本稿では,木全体の状態を考慮した強化学習(RL)を用いた2次元シミュレーション手法を提案する。
- 参考スコア(独自算出の注目度): 58.740509566888676
- 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 bi-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 TSP
instances. Experiments on several benchmarks show significant improvements in
optimality gap reductions and per-node efficiency under strict time
constraints.
- Abstract(参考訳): ブランチとバウンドにおける大きな課題は、検索ツリー内の最適なノードを特定することにある。
現在の最先端セレクタは手作りのアンサンブルを使用して、ナイーブなサブノードセレクタと、個々のノードデータに依存する学習ノードセレクタを自動的に切り替える。
本稿では,孤立ノードではなく,木の状態全体を考慮しながら強化学習(rl)を用いた新しい二重シミュレーション手法を提案する。
これを実現するために,モデルの根元から'to-be-selected'の葉への経路に基づいて確率分布を生成するグラフニューラルネットワークを訓練する。
ノード選択を確率分布としてモデル化することで、本質的なノード品質とノード評価コストの両方をキャプチャする最先端RL技術を用いてモデルを訓練することができる。
提案手法は,特殊設計の合成TSPインスタンスでのみ訓練されているにもかかわらず,多種多様な複雑な問題集合に対して高品質なノード選択ポリシーを誘導する。
いくつかのベンチマーク実験では、厳密な時間制約下での最適ギャップ低減とノード単位の効率が大幅に改善されている。
関連論文リスト
- Efficient Link Prediction via GNN Layers Induced by Negative Sampling [92.05291395292537]
リンク予測のためのグラフニューラルネットワーク(GNN)は、緩やかに2つの広いカテゴリに分けられる。
まず、Emphnode-wiseアーキテクチャは各ノードの個別の埋め込みをプリコンパイルし、後に単純なデコーダで結合して予測を行う。
第二に、エンフェッジワイド法は、ペアワイド関係の表現を強化するために、エッジ固有のサブグラフ埋め込みの形成に依存している。
論文 参考訳(メタデータ) (2023-10-14T07:02:54Z) - Determinate Node Selection for Semi-supervised Classification Oriented
Graph Convolutional Networks [21.086299227526684]
本稿では,ラベル付きノードを決定論的に選択する効率的な手法として,決定ノード選択(DNS)アルゴリズムを提案する。
DNSアルゴリズムは、典型的なノードと発散ノードの2つのカテゴリを識別する。
我々は, DNSアルゴリズムの導入により, モデルの平均精度が著しく向上し, 標準偏差が著しく低下することが実証された。
論文 参考訳(メタデータ) (2023-01-11T10:02:14Z) - 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) - NODE-SELECT: A Graph Neural Network Based On A Selective Propagation
Technique [0.48489389711734543]
NODE-SELECTは、最適な共有フィットノードのみが情報を伝達できるサブセット層を使用する効率的なグラフニューラルネットワークです。
提案手法であるNODE-SELECTは,各層に並列に積み重ねる選択機構を持つことで,拡散するノイズを低減し,実世界グラフに見られる制限共有の概念を適応させることができる。
論文 参考訳(メタデータ) (2021-02-17T05:51:11Z) - Growing Deep Forests Efficiently with Soft Routing and Learned
Connectivity [79.83903179393164]
この論文は、いくつかの重要な側面で深い森林のアイデアをさらに拡張します。
我々は、ノードがハードバイナリ決定ではなく、確率的ルーティング決定、すなわちソフトルーティングを行う確率的ツリーを採用する。
MNISTデータセットの実験は、私たちの力のある深部森林が[1]、[3]よりも優れたまたは匹敵するパフォーマンスを達成できることを示しています。
論文 参考訳(メタデータ) (2020-12-29T18:05:05Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。