Source-linked AI summary
Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances
Zhang-Hua Fu, Kai-Bin Qiu, Hongyuan Zha
TL;DR
Existing supervised-learning TSP algorithms have limited generalization across instance sizes and require costly pre-computed high-quality solutions. The paper trains a small supervised model, extends it to large instances through graph sampling, conversion, and heat-map merging, and applies Monte Carlo tree search to the merged maps. Experiments on instances up to 10,000 vertices show clear improvements over existing learning-based TSP algorithms.
Problem
Supervised-learning TSP models may perform poorly on differently sized instances and require many pre-computed optimal or high-quality solutions, limiting their use on large instances.
Method
A small Att-GCRN model builds sub heat maps from sampled, converted subgraphs, which are merged and supplied to Monte Carlo tree search for solution search.
Results
Instances with up to 10,000 cities were tested, and the algorithm clearly outperformed existing learning-based TSP algorithms while obtaining optimal or near-optimal solutions within reasonable time.
Takeaways & Limitations
The approach improves the generalization ability of a small supervised model to TSP instances of arbitrarily large size.
Abstract
from arXiv · showhide
For the traveling salesman problem (TSP), the existing supervised learning based algorithms suffer seriously from the lack of generalization ability. To overcome this drawback, this paper tries to train (in supervised manner) a small-scale model, which could be repetitively used to build heat maps for TSP instances of arbitrarily large size, based on a series of techniques such as graph sampling, graph converting and heat maps merging. Furthermore, the heat maps are fed into a reinforcement learning approach (Monte Carlo tree search), to guide the search of high-quality solutions. Experimental results based on a large number of instances (with up to 10,000 vertices) show that, this new approach clearly outperforms the existing machine learning based TSP algorithms, and significantly improves the generalization ability of the trained model.
Introduction
TSP is an NP-hard optimization problem, while supervised-learning methods struggle to generalize across instance sizes and require costly high-quality solutions. This paper combines a small supervised model with techniques for extending its heat maps and a reinforcement-learning search method.
- Problem: TSP seeks the cheapest tour visiting every city exactly once and returning to the start, but its NP-hardness makes the problem extremely difficult.The problem has applications in transportation, robot routing, biology, and circuit design.
- Existing approaches: Existing machine-learning TSP methods include supervised learning from pre-computed solutions and reinforcement learning through environment interaction.Supervised models can accelerate high-quality solution search, but their fixed-size performance may deteriorate on differently sized instances.
- Limitations: Supervised learning is limited by size-distribution mismatch and the expense of generating many optimal or high-quality training solutions for large instances.These constraints seriously limit supervised learning on large-scale TSP instances.
- Proposed approach: The paper trains a small Att-GCRN model to construct heat maps for m-vertex instances, then repeatedly applies it to sampled subgraphs of larger instances.The subgraphs are converted into standard TSP instances before inference, and their sub heat maps are merged into a complete heat map.
- Proposed approach: Monte Carlo tree search uses the merged heat map to search for high-quality solutions through a hybrid supervised- and reinforcement-learning algorithm.The approach is designed to extend a fixed-size model to arbitrarily large TSP instances without repeatedly training models.
- Results: Instances with up to 10,000 cities were evaluated, and the new algorithm clearly outperformed existing learning-based TSP algorithms while obtaining optimal or near-optimal solutions within reasonable time.The experiments covered a large number of instances and targeted improved generalization of the trained model.
Related works
Prior TSP research includes supervised and reinforcement-learning methods, alongside machine-learning approaches for related routing and TSP variants. Supervised methods learn from pre-computed solutions, whereas reinforcement-learning methods learn through interaction without them.
- Overview: Recent machine-learning TSP algorithms are broadly classified into supervised-learning and reinforcement-learning categories.The related-work review focuses on learning-based methods and omits non-learned methods.
- Supervised learning: Pointer networks use recurrent encoder-decoder architectures and attention to predict distributions over unvisited candidate cities.Other supervised methods train graph neural networks to predict adjacency-matrix heat maps and use beam search to construct feasible tours.
- Reinforcement learning: Reinforcement-learning approaches include actor-critic models, partial-tour construction, and Sinkhorn policy gradients for learning TSP policies.These methods avoid relying on pre-computed solutions during training or search.
- Related problems: Machine-learning methods have also been proposed for decision TSP, multiple TSP, and vehicle-routing problems.The review points to surveys for broader coverage of these related problems.
Methods
The method repeatedly applies a small supervised model to sampled, converted subgraphs, merges their heat maps, and uses MCTS to search large TSP solutions.
- Small-scale supervised model: The pre-trained Att-GCRN accepts TSP instances with fixed size m and produces heat maps over their edges.It is trained offline on 990,000 randomly generated m-vertex instances using Concorde solutions as ground truth.
- Graph sampling: For an arbitrarily large instance, graph sampling extracts overlapping subgraphs containing exactly m vertices.Sampling uses minimally covered vertices as centers and k-nearest neighbors, repeating until coverage reaches a predefined lower bound ω.
- Graph converting and heat-map construction: Each sampled subgraph is converted to match the training distribution before the pre-trained model builds its sub heat map.Coordinates are rescaled within the subgraph so its spatial distribution fits the unit-square training setting.
- Heat-map merging: The sub heat maps are merged into a complete heat map whose edge probabilities estimate membership in the optimal tour.Edges with Pij < 10^-4 are marked unpromising and eliminated to reduce the subsequent search space.
- Reinforcement-learning search: MCTS uses the merged heat map to guide reinforcement-learning search for high-quality TSP solutions.States are complete tours, actions are k-opt transformations, and the search combines small-neighborhood enumeration with targeted sampling in enlarged neighborhoods.
Experiments
Experiments evaluate Att-GCRN+MCTS across standard and much larger TSP instances, comparing it with learning-based and non-learning baselines. The method remains competitive on smaller benchmarks, stays close to optimality through n = 1000, and scales to 10,000 vertices with substantially better learning-based results.
- Experimental setup: Experiments compare Att-GCRN+MCTS with eight learning-based baselines and three non-learning algorithms under separate GPU and CPU setups.Learning-based methods use one GTX 1080 Ti GPU; non-learning methods use an eight-core Intel Xeon Gold 5118 CPU, so non-learning results are indicative rather than strictly uniform.
- Experimental setup: The evaluation covers 10,000 instances each at n = 20, 50 and 100, plus 128 instances each at n = 200, 500 and 1000, and 16 instances at n = 10000.The larger test set is newly generated for n = 200, 500, 1000 and 10000.
- Results on smaller instances: 0.0000%, 0.0145% and 0.0370% average gaps are achieved at n = 20, 50 and 100, respectively, while matching Concorde ground-truth solutions on most instances.Existing learning-based algorithms struggle to match optimality at n = 100; Att-GCRN+MCTS runtime remains competitive with nearly all learning baselines.
- Results on larger instances: 0.8844%, 2.5365% and 3.2238% average gaps occur at n = 200, 500 and 1000, respectively, clearly outperforming existing learning baselines within short time.Gurobi fails to terminate within reasonable time at n = 1000, whereas Concorde and LKH3 remain effective on these instances.
- Results on 10,000 vertices: 4.3902% average gap is obtained on 16 instances with 10,000 vertices, compared with 501.2737%, 97.3932% and 80.2802% for three learning-based algorithms.Several other baselines fail from memory or time exceptions; Att-GCRN+MCTS runtime is shorter than the best of the three compared learning baselines and remains close to LKH3.
- Ablation study: Removing the heat map causes a drastic performance decrease and a huge optimality gap on every data set, whereas Att-GCRN+MCTS remains very close to optimality.The ablation supports the heat map’s role in identifying promising candidate edges for MCTS.