ツーステージグラフスパージファシケーションを用いた巡回セールスマン問題における機械学習

arXiv:2604.20236v1 発表タイプ：new 要約：高性能な TSP ソルバーである LKH は、すべてのエッジに対してではなく、スパージファシケーションされた候補グラフ内で探索を行います。グラフのスパージファシケーションは困難であり、エッジを過剰に保持するとソルバーは時間を浪費し、逆に過剰に削除すると最適ルートに属するエッジが失われます。二大ヒューリスティック手法である $\ ext{α-Nearest}$ と POPMUSIC は高品質な候補グラフを生成しますが、単一のヒューリスティック手法はすべてのインスタンスサイズと分布においてスパースかつ信頼性のあるものはありません。機械学習手法はより良いスパージファシケーションモデルを学習する可能性があります。ただし、既存のアプローチは完全グラフに作用しており、これは高価であると同時に主にユークリッド距離に制限されています。この問題を解決するために、本研究では二つのステージを有するグラフスパージファシケーションアプローチを提案します：第 1 ステージは $\\text{α-Nearest}$ と POPMUSIC の併用法を用いて再現性を最大化し、第 2 ステージは単一のモデルを用いて密度を削減します。私たちは 4 つの TSPLIB 距離タイプ、5 つの空間分布、および 50 から 500 までの問題サイズで実験を行いました。二ステージアプローチは候補グラフの密度を大幅に削減し、高いカバレッジを維持するとともに、距離タイプや分布を跨る汎用性を示し、ユークリッド距離に制限された最近のニューラルスパージファシケーション手法を凌駕し、単一ステージのヒューリスティックが劣化傾向にありつつある大規模スケールにおいてさらに価値を高める傾向を示しました。

arXiv:2604.20236v1 Announce Type: new Abstract: High-performance TSP solvers like LKH search within a sparsified candidate graph rather than over all possible edges. Graph sparsification is non-trivial: keep too many edges and the solver wastes time; cut too many and it loses edges that belong to the optimal tour. The two leading heuristic methods, $\alpha$-Nearest and POPMUSIC, produce high-quality candidate graphs, but no single heuristic is both sparse and reliable across all instance sizes and distributions. Machine learning methods can potentially learn better sparsification models. However, existing approaches operate on the complete graph, which is expensive and mostly restricted to Euclidean distances. To address this issue, we propose a two-stage graph sparsification approach: Stage~1 takes the union of $\alpha$-Nearest and POPMUSIC to maximise recall; Stage~2 trains a single model to reduce density. We conducted experiments across four TSPLIB distance types, five spatial distributions, and problem sizes from 50 to 500. The two-stage approach substantially reduces candidate-graph density while retaining high coverage, generalises across distance types and distributions, outperforms recent neural sparsification methods that are restricted to Euclidean distances, and becomes increasingly valuable at larger scales where single-stage heuristics degrade.