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

This paper addresses the challenge of Automated Algorithm Selection (AS) for the Traveling Salesman Problem (TSP). Because no single algorithm is universally optimal for all TSP instances, the authors seek to build a model that can automatically predict which solver from a predefined portfolio will perform best on a given instance. Unlike traditional approaches that rely on manual feature engineering, this study proposes a Graph Neural Network (GNN)-based framework to learn instance representations directly from raw graph data.

The authors introduce GNNAS-TSP, a framework that uses a Residual Gated Graph Convolutional Network (ResGatedGCN) to process TSP instances. The model takes node coordinates as input and outputs predicted performance scores for five distinct solvers: Chained Lin-Kernighan, Edge Assembly Crossover, Lin-Kernighan-Helsgaun, Multiagent Optimization System, and Concorde. The framework is trained using various loss functions, including cost-based (MSE, MAE, Huber) and rank-based (RankNet, ListNet, LambdaRank) objectives, to evaluate which approach best identifies the optimal solver under fixed computational budgets of 10 and 60 seconds.

The empirical results demonstrate that GNNAS-TSP successfully improves upon the Single Best Solver (SBS) in normalized solution cost. The model is particularly effective under the 10-second budget, where it achieves statistically significant cost improvements. By comparing different loss functions, the study shows that the framework can effectively leverage both cost-prediction and ranking information to guide the selection process. The findings suggest that GNN-based meta-solving is a robust strategy for TSP when there is meaningful variation in solver performance across instances.

This research bridges the gap between deep learning-based representation learning and classical combinatorial optimization. By automating the selection process without the need for expert-designed features, GNNAS-TSP provides a scalable and flexible tool for practitioners. It demonstrates that GNNs are well-suited for capturing the structural nuances of TSP instances, offering a pathway to improve solver efficiency in practical applications like logistics and circuit design.