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

arXiv: https://arxiv.org/abs/2607.18632 · HTML: https://mlsanity.com/paper/2607.18632/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 39 references that are in the map.
- First posted on arXiv 21 Jul 2026.

## Builds on (most cited first, 19 of 19)

- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Temporal Graph Networks for Deep Learning on Dynamic Graphs](https://mlsanity.com/paper/2006.10637/) (2020)
- [Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification](https://mlsanity.com/paper/2009.03509/) (2020)
- [EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs](https://mlsanity.com/paper/1902.10191/) (2019)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Automated Algorithm Selection: Survey and Perspectives](https://mlsanity.com/paper/1811.11597/) (2018)
- [Graph Neural Network Guided Local Search for the Traveling Salesperson Problem](https://mlsanity.com/paper/2110.05291/) (2021)
- [ASlib: A Benchmark Library for Algorithm Selection](https://mlsanity.com/paper/1506.02465/) (2015)
- [DualOpt: A Dual Divide-and-Optimize Algorithm for the Large-scale Traveling Salesman Problem](https://mlsanity.com/paper/2501.08565/) (2025)
- [A case study of algorithm selection for the traveling thief problem](https://mlsanity.com/paper/1609.00462/) (2016)
- [Revisit the Algorithm Selection Problem for TSP with Spatial Information Enhanced Graph Neural Networks](https://mlsanity.com/paper/2302.04035/) (2023)
- [GNNAS-Dock: Budget Aware Algorithm Selection with Graph Neural Networks for Molecular Docking](https://mlsanity.com/paper/2411.12597/) (2024)
- [GELD: A Unified Neural Model for Efficiently Solving Traveling Salesman Problems Across Different Scales](https://mlsanity.com/paper/2506.06634/) (2025)
- [MC-GNNAS-Dock: Multi-criteria GNN-based Algorithm Selection for Molecular Docking](https://mlsanity.com/paper/2509.26377/) (2025)
- [Cascaded Large-Scale TSP Solving with Unified Neural Guidance: Bridging Local and Population-based Search](https://mlsanity.com/paper/2501.14285/) (2025)
- [ViTSP: A Vision Language Models Guided Framework for Solving Large-Scale Traveling Salesman Problems](https://mlsanity.com/paper/2509.23465/) (2025)
- [Molecular Embedding-Based Algorithm Selection in Protein-Ligand Docking](https://mlsanity.com/paper/2512.02328/) (2025)
- [Beyond Numerical Features: CNN-Driven Algorithm Selection via Contour Plots for Continuous Black-Box Optimization](https://mlsanity.com/paper/2605.20797/) (2026)

## Abstract (arXiv)

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.