論文の概要: NeuroPrim: An Attention-based Model for Solving NP-hard Spanning Tree
Problems
- arxiv url: http://arxiv.org/abs/2210.12453v2
- Date: Sat, 10 Jun 2023 16:21:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-14 02:20:32.497536
- Title: NeuroPrim: An Attention-based Model for Solving NP-hard Spanning Tree
Problems
- Title（参考訳）: NeuroPrim:NP-hardスパンニングツリー問題の解決のための注意に基づくモデル
- Authors: Yuchen Shi, Congying Han, Tiande Guo
- Abstract要約: 我々は,グラフ上の一般的な最適化問題に対して,決定過程(MDP)を定義することによって,様々な木にまたがる問題を解く新しいフレームワークであるNeuroPrimを提案する。
この枠組みをユークリッド空間上の3つの難しい問題に適用する: Degree-constrained Minimum Spanning Tree (DCMST) 問題、最小コストスパンニングツリー (MRCST) 問題、ルーティンググラフ (STP) におけるスタイナーツリー問題。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Spanning tree problems with specialized constraints can be difficult to solve
in real-world scenarios, often requiring intricate algorithmic design and
exponential time. Recently, there has been growing interest in end-to-end deep
neural networks for solving routing problems. However, such methods typically
produce sequences of vertices, which makes it difficult to apply them to
general combinatorial optimization problems where the solution set consists of
edges, as in various spanning tree problems. In this paper, we propose
NeuroPrim, a novel framework for solving various spanning tree problems by
defining a Markov Decision Process (MDP) for general combinatorial optimization
problems on graphs. Our approach reduces the action and state space using
Prim's algorithm and trains the resulting model using REINFORCE. We apply our
framework to three difficult problems on Euclidean space: the
Degree-constrained Minimum Spanning Tree (DCMST) problem, the Minimum Routing
Cost Spanning Tree (MRCST) problem, and the Steiner Tree Problem in graphs
(STP). Experimental results on literature instances demonstrate that our model
outperforms strong heuristics and achieves small optimality gaps of up to 250
vertices. Additionally, we find that our model has strong generalization
ability, with no significant degradation observed on problem instances as large
as 1000. Our results suggest that our framework can be effective for solving a
wide range of combinatorial optimization problems beyond spanning tree
problems.
- Abstract（参考訳）: 特定の制約でツリー問題をスパンニングすることは現実のシナリオでは解決が困難であり、しばしば複雑なアルゴリズム設計と指数時間を必要とする。
近年、ルーティング問題を解決するためのエンドツーエンドのディープニューラルネットワークへの関心が高まっている。
しかし、そのような方法は一般に頂点の列を生成するため、様々なスパンディングツリー問題のように解集合がエッジからなる一般組合せ最適化問題に適用するのが困難である。
本稿では,グラフ上の一般組合せ最適化問題に対するマルコフ決定過程(mdp)を定義することにより,様々なスパンディングツリー問題を解決するための新しい枠組みであるneuroprimを提案する。
提案手法は,Primのアルゴリズムを用いて動作と状態空間を削減し,REINFORCEを用いて結果モデルを訓練する。
この枠組みをユークリッド空間上の3つの難しい問題に適用する: Degree-constrained Minimum Spanning Tree (DCMST) 問題、最小ルーティングコストSpanning Tree (MRCST) 問題、グラフにおけるSteiner Tree Problem (STP) 問題。
文献実験の結果,モデルが強いヒューリスティックを上回り,最大250頂点の小さな最適ギャップを達成することが示された。
さらに,本モデルには強い一般化能力が備わっており,1000以上の問題事例では有意な劣化はみられなかった。
以上の結果から,本フレームワークは木にまたがるより広範な組合せ最適化問題の解決に有効であることが示唆された。
関連論文リスト
- Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。
GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。
我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
論文 参考訳（メタデータ） (2024-06-05T22:52:27Z) - Query-decision Regression between Shortest Path and Minimum Steiner Tree [20.092639310758145]
本稿では,最短経路問題とSteiner木問題に焦点をあてる。
我々は、スコアリングモデルを構築するための実現可能な仮説空間の設計に関する理論的知見を提供する。
実験により,そのような問題を統計的に有意な程度に解決できることが示唆された。
論文 参考訳（メタデータ） (2024-02-03T17:05:01Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Neural Algorithmic Reasoning for Combinatorial Optimisation [20.36694807847833]
ニューラル推論の最近の進歩を活用して,CO問題の学習を改善することを提案する。
私たちは、COインスタンスでトレーニングする前に、関連するアルゴリズムでニューラルネットワークを事前トレーニングすることを提案します。
以上の結果から,この学習装置を用いることで,非アルゴリズム的情報深層学習モデルよりも優れた性能が得られることが示された。
論文 参考訳（メタデータ） (2023-05-18T13:59:02Z) - Learning to Prune Instances of Steiner Tree Problem in Graphs [0.47138177023764655]
ノードの集合が与えられるグラフ上のスタイナー木問題を考える。
目的は、追加ノードを含むすべてのノードを含むツリーのサブグラフを見つけることである。
論文 参考訳（メタデータ） (2022-08-25T10:31:00Z) - Neural Improvement Heuristics for Graph Combinatorial Optimization
Problems [49.85111302670361]
本稿では,ノード,エッジ,あるいはその両方に情報をエンコードするグラフベースの問題を扱う新しいニューラル改善(NI)モデルを提案する。
提案モデルは,各地区の操作の選択を誘導する丘登頂に基づくアルゴリズムの基本的な構成要素として機能する。
論文 参考訳（メタデータ） (2022-06-01T10:35:29Z) - Learning to Solve Combinatorial Graph Partitioning Problems via
Efficient Exploration [72.15369769265398]
実験により、ECORDは最大カット問題に対するRLアルゴリズムのための新しいSOTAを実現する。
最も近い競合と比較して、ECORDは最適性ギャップを最大73%削減する。
論文 参考訳（メタデータ） (2022-05-27T17:13:10Z) - What's Wrong with Deep Learning in Tree Search for Combinatorial
Optimization [8.879790406465556]
本稿では、NP-hard Maximum Independent Set問題に対するオープンソースのベンチマークスイートについて、その重み付けと非重み付けの両変種について述べる。
また,Li らによる木探索アルゴリズム (NeurIPS 2018) の詳細な解析を行い,小型および大規模合成および実世界のグラフ上で様々な構成を検証した。
木探索で用いられるグラフ畳み込みネットワークは,解構造の有意な表現を学ばず,実際にランダムな値に置き換えることができることを示す。
論文 参考訳（メタデータ） (2022-01-25T17:37:34Z) - Combinatorial Optimization with Physics-Inspired Graph Neural Networks [0.0]
最適化問題の解法としてグラフニューラルネットワークを用いる方法を示す。
ニューラルネットワークは、既存の解法よりも優れているか、あるいは優れていることが分かりました。
論文 参考訳（メタデータ） (2021-07-02T16:54:35Z) - A Bi-Level Framework for Learning to Solve Combinatorial Optimization on
Graphs [91.07247251502564]
本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。
このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
論文 参考訳（メタデータ） (2021-06-09T09:18:18Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。