Reproduce “Graph Neural Network-based Algorithm Selection for the Traveling Salesman Problem: A Systematic Study of Cost and Rank Losses under Distinct Budget Regimes” on OpenResearch

About this paper

Zhaoxuan Li, Jiale Yang, Yifei Lu, Mustafa Misir

A Graph Neural Network-based Algorithm Selection (GNNAS-TSP) framework predicts per-solver costs for the Traveling Salesman Problem directly from graph data, eliminating manual feature engineering. It achieved a statistically significant improvement in normalized solution cost over a Single Best Solver baseline, closing 73.28% of the SBS-to-VBS gap under a 10-second budget and 65.82% under a 60-second budget.

Key insights

• Graph Neural Networks can effectively learn implicit, rich instance representations for algorithm selection directly from graph structures, bypassing the need for manual feature engineering in TSP.
• Hybrid loss functions, combining cost and rank-based objectives, yield superior algorithm selection performance compared to purely cost-based or rank-based alternatives.
• Solver performance exhibits structured heterogeneity across TSP instances and computational budgets, which GNNAS-TSP successfully exploits to dynamically select complementary solvers.

Summary by alphaXiv.