Search papers, labs, and topics across Lattice.
This study introduces GNNAS-TSP, a Graph Neural Network-based framework for Automated Algorithm Selection (AS) tailored to the Traveling Salesman Problem (TSP), which learns instance representations directly from raw graph data. By framing AS as a joint cost-prediction and ranking task, the framework evaluates various cost-based and rank-based learning objectives across a portfolio of TSP solvers. The results demonstrate significant improvements in solution cost over the Single Best Solver (SBS) under both 10 and 60-second computational budgets, highlighting the effectiveness of GNNAS-TSP in leveraging solver performance variation.
GNNAS-TSP achieves substantial cost reductions in TSP solutions, outperforming traditional single-solver approaches by adapting to instance-specific characteristics.
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.
