論文の概要: Graph Neural Network-based Algorithm Selection for the Traveling Salesman Problem: A Systematic Study of Cost and Rank Losses under Distinct Budget Regimes
- arxiv url: http://arxiv.org/abs/2607.18632v1
- Date: Tue, 21 Jul 2026 02:01:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-22 19:05:05.292274
- Title: Graph Neural Network-based Algorithm Selection for the Traveling Salesman Problem: A Systematic Study of Cost and Rank Losses under Distinct Budget Regimes
- Title（参考訳）: グラフニューラルネットワークを用いたトラベリングセールスマン問題に対するアルゴリズム選択:個別予算法に基づくコストとランク損失の体系的研究
- Abstract要約: 本稿では、生グラフデータから直接TSPインスタンス表現を学習するグラフニューラルネットワーク(GNN)ベースのASフレームワークであるGNNAS-TSPを紹介する。
コストベース(平均二乗誤差(MSE)、平均絶対誤差(MAE)、ランクベース(RankNet、ListNet、LambdaRank)、ハイブリッド学習目標(Chained Lin-Kernighan、Edge Assembly Crossover、Lin-Kernighan-Helsgaun、Multiagent Optimization System、Concorde)を評価した。
10代予算では、ASは実質的かつ統計的に大幅なコスト改善を達成している。
- 参考スコア（独自算出の注目度）: 6.084010809141769
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Automated Algorithm Selection (AS) aims to improve problem-solving performance by selecting, for each problem instance, the most suitable algorithm from a predefined portfolio. This is particularly relevant to the Traveling Salesman Problem (TSP), where solver performance is strongly instance-dependent. We introduce GNNAS-TSP, a Graph Neural Network (GNN)-based AS framework that learns TSP instance representations directly from raw graph data, avoiding manual feature engineering. GNNAS-TSP formulates AS as a joint cost-prediction and ranking task. We evaluate cost-based (mean squared error (MSE), mean absolute error (MAE), and Huber), rank-based (RankNet, ListNet, and LambdaRank), and hybrid learning objectives for a portfolio comprising Chained Lin-Kernighan, Edge Assembly Crossover, Lin-Kernighan-Helsgaun, Multiagent Optimization System, and Concorde. Experiments use fixed computational budgets of 10 and 60 seconds. On the held-out test set, the selected configurations improve on the Single Best Solver (SBS) in normalized solution cost at both budgets. For the 10s budget, AS achieves substantial and statistically significant cost improvement over SBS. Overall, the results suggest that GNNAS-TSP is a useful meta-solving strategy when exploitable variation exists across solver performance.
- Abstract（参考訳）: 自動アルゴリズム選択(AS)は、各問題インスタンスに対して、あらかじめ定義されたポートフォリオから最も適切なアルゴリズムを選択することにより、問題解決性能を向上させることを目的としている。
これは特にトラベリングセールスマン問題(TSP)に関係しており、ソルバのパフォーマンスはインスタンスに依存している。
本稿では,グラフニューラルネットワーク(GNN)ベースのASフレームワークであるGNNAS-TSPを紹介する。
GNNAS-TSPは、ASを共同コスト予測とランキングタスクとして定式化する。
コストベース(平均二乗誤差(MSE)、平均絶対誤差(MAE)、ランクベース(RankNet、ListNet、LambdaRank)、ハイブリッド学習目標(Chained Lin-Kernighan、Edge Assembly Crossover、Lin-Kernighan-Helsgaun、Multiagent Optimization System、Concorde)を評価した。
実験では10秒から60秒の固定的な計算予算を使用する。
ホールドアウトテストセットでは、選択された構成は、両方の予算で正規化されたソリューションコストでSBS(Single Best Solver)を改善する。
10代予算では、ASはSBSよりも実質的で統計的に重要なコスト改善を達成している。
以上の結果から, GNNAS-TSPは, 解法性能に悪用可能な変動が存在する場合に, メタ解決戦略として有用であることが示唆された。
関連論文リスト
- RAPNet: Accelerating Algebraic Multigrid with Learned Sparse Corrections [11.742065170002164]
本稿では,粗いグリッド演算子の疎度と収束品質のトレードオフを解消するグラフニューラルネットワーク(GNN)フレームワークであるRAPNetを提案する。
このアプローチの鍵となるのは、小さなサブグラフから学習し、100万ノードドメインへの一般化を可能にするレベルワイドなトレーニング戦略です。
本手法は,PDE離散化およびグラフラプラシアンに基づく古典的非ガレルキン基底線よりも優れていることを示す。
論文 参考訳（メタデータ） (2026-05-26T11:14:59Z) - Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts [19.540758462427878]
最適性と最悪の保証を維持しつつ、正確な代入解決を高速化する学習強化フレームワークを提案する。
グラフベースのモデルのメモリボトルネックを$mathcalO(N2)$で回避する軽量な行独立アーキテクチャであるRowDualNetを紹介します。
論文 参考訳（メタデータ） (2026-05-10T07:15:49Z) - Lighter-X: An Efficient and Plug-and-play Strategy for Graph-based Recommendation through Decoupled Propagation [49.865020394064096]
我々は,既存のGNNベースのレコメンデータアーキテクチャとシームレスに統合可能な,効率的かつモジュール化されたフレームワークである textbfLighter-X を提案する。
提案手法は,基本モデルの理論的保証と経験的性能を保ちながら,パラメータサイズと計算複雑性を大幅に低減する。
実験の結果、Lighter-Xはパラメータが大幅に少ないベースラインモデルに匹敵するパフォーマンスを実現している。
論文 参考訳（メタデータ） (2025-10-11T08:33:08Z) - Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum [78.27945336558987]
分散サーバ(DFL)はクライアント・クライアント・アーキテクチャへの依存をなくす。
非滑らかな正規化はしばしば機械学習タスクに組み込まれる。
本稿では,これらの問題を解決する新しいDNCFLアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-04-17T08:32:25Z) - GDSG: Graph Diffusion-based Solution Generator for Optimization Problems in MEC Networks [109.17835015018532]
グラフ拡散型ソリューション生成(GDSG)法を提案する。
このアプローチは、おそらく最適な解に収束しながら、最適以下のデータセットを扱うように設計されている。
グラフニューラルネットワーク(GNN)を用いたマルチタスク拡散モデルとしてGDSGを構築し,高品質な解の分布を求める。
論文 参考訳（メタデータ） (2024-12-11T11:13:43Z) - Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
本稿では,組合せ最適化(CO)問題を効率よく解くために,GNNのパワーを活用して,QRF-GNNと呼ぶ新しいアルゴリズムを提案する。
QUBO緩和による損失関数の最小化による教師なし学習に依存している。
実験の結果、QRF-GNNは既存の学習ベースアプローチを大幅に上回り、最先端の手法に匹敵することがわかった。
論文 参考訳（メタデータ） (2024-07-23T13:34:35Z) - GNN at the Edge: Cost-Efficient Graph Neural Network Processing over
Distributed Edge Servers [24.109721494781592]
グラフニューラルネットワーク(GNN)はまだ探索中であり、その広範な採用に対する大きな違いを示している。
本稿では,多層ヘテロジニアスエッジネットワーク上での分散GNN処理のコスト最適化について検討する。
提案手法は, 高速収束速度で95.8%以上のコスト削減を行い, デファクトベースラインよりも優れた性能が得られることを示す。
論文 参考訳（メタデータ） (2022-10-31T13:03:16Z) - Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。
最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。
提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
論文 参考訳（メタデータ） (2022-06-14T08:14:14Z) - Towards Optimal VPU Compiler Cost Modeling by using Neural Networks to
Infer Hardware Performances [58.720142291102135]
VPUNN"は低レベルのタスクプロファイリングに基づいてトレーニングされたニューラルネットワークベースのコストモデルである。
これは、IntelのVPUプロセッサのラインにおける最先端のコストモデリングよりも一貫して優れている。
論文 参考訳（メタデータ） (2022-05-09T22:48:39Z) - GLAN: A Graph-based Linear Assignment Network [29.788755291070462]
深層グラフネットワークに基づく学習可能な線形代入問題の解法を提案する。
合成データセットによる実験結果から,本手法は最先端のベースラインよりも優れていることがわかった。
また,提案手法を一般的なマルチオブジェクトトラッキング(MOT)フレームワークに組み込んで,エンド・ツー・エンドでトラッカーをトレーニングする。
論文 参考訳（メタデータ） (2022-01-05T13:18:02Z) - RoMA: Robust Model Adaptation for Offline Model-based Optimization [115.02677045518692]
入力出力クエリの静的データセットからブラックボックス目的関数を最大化する入力を探索する問題を考える。
この問題を解決するための一般的なアプローチは、真の客観的関数を近似するプロキシモデルを維持することである。
ここでの大きな課題は、検索中に逆最適化された入力を避ける方法である。
論文 参考訳（メタデータ） (2021-10-27T05:37:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。