論文の概要: NeuroPrim: An Attention-based Model for Solving NP-hard Spanning Tree
Problems
- arxiv url: http://arxiv.org/abs/2210.12453v1
- Date: Sat, 22 Oct 2022 13:49:29 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-25 18:14:37.659075
- 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要約: 特別な制約のある樹木の問題は、給水、輸送、電気通信といった現実のシナリオに広く適用されている。
近年,ルーティング問題を解決するために,エンドツーエンドのディープニューラルネットワーク(DNN)への関心が高まっている。
本稿では,ニューラルネットワークとプリムアルゴリズムを組み合わせた新しいフレームワークであるNeuroPrimを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Spanning tree problems with special constraints are widely applied in
real-life scenarios, such as water supply, transportation and
telecommunications, which often require complex algorithm design and
exponential time to solve. In recent years, there has been a surge of interest
in end-to-end Deep Neural Networks (DNNs) to solve routing problems. However,
as the output of such methods is a sequence of vertices, it is difficult to
apply them to combinatorial optimization problems where the solution set
consists of a edges sets, such as various spanning tree problems. In this
paper, we propose NeuroPrim, a novel framework combining neural networks and
the Prim algorithm, which is trained by REINFORCE with the POMO baseline to
learn metrics for selecting edges for different spanning tree problems. We
apply it to three difficult problems on Euclidean spaces, namely
Degree-constrained Minimum Spanning Tree Problem (DCMSTP), Minimum Routing Cost
Spanning Tree Problem (MRCSTP) and Steiner Tree Problem in Graphs (STPG).
Experimental results show that our model is able to outperform some of the
heuristics and obtain extremely small gaps of less than $0.1\%$ for simple
problems such as DCMST with degree constraint $3$ and special cases of STPG up
to 100 vertices. In addition, we find no significant degradation on problem
instances as large as 1000, which demonstrates its strong generalization
ability.
- Abstract（参考訳）: 特別な制約を伴う木の問題にまたがる問題は、水供給、輸送、電気通信など、複雑なアルゴリズム設計と指数時間を必要とする現実のシナリオに広く適用されている。
近年,ルーティング問題を解決するために,エンドツーエンドのディープニューラルネットワーク(DNN)への関心が高まっている。
しかし、そのような手法の出力は頂点の列であるため、様々なスパンディングツリー問題のような解集合が辺集合からなる組合せ最適化問題に適用することは困難である。
本稿では,ニューラルネットワークとプリムアルゴリズムを組み合わせた新しいフレームワークであるNeuroPrimを提案する。
ユークリッド空間上の3つの難しい問題、すなわち、DCMSTP(Degree Constrained Minimum Spanning Tree Problem)、MRCSTP(Minimum Routing Cost Spanning Tree Problem)、STPG(Steiner Tree Problem in Graphs)に適用する。
実験結果から,DCMSTの次数制約が3ドル,STPGの特殊ケースが100バーチカンに制限されたような単純な問題に対して,本モデルがヒューリスティックスの一部を上回り,0.1 %未満の極めて小さなギャップを得ることができた。
さらに,1000以上の問題事例において,その強力な一般化能力を示す有意な劣化は見つからない。
関連論文リスト
- An Unsupervised Learning Framework Combined with Heuristics for the Maximum Minimal Cut Problem [5.092968949752308]
本研究は,MMCPの最大値と非教師なし学習フレームワークを提案する。
重要な観察は、それぞれの溶液が少なくとも1本の枝木に対応することである。
フレームワークを評価し、特定のアプリケーションを提供するために、広範な実験を行います。
論文 参考訳（メタデータ） (2024-08-16T02:07:34Z) - Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。
GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。
我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
論文 参考訳（メタデータ） (2024-06-05T22:52:27Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。