Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances

Abstract

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.

References in corpus (8)

• Learning Combinatorial Optimization Algorithms over Graphs
• Neural Combinatorial Optimization with Reinforcement Learning
• An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
• Attention, Learn to Solve Routing Problems!
• Learning a SAT Solver from Single-Bit Supervision
• Learning the Multiple Traveling Salesmen Problem with Permutation Invariant Pooling Networks
• M-Walk: Learning to Walk over Graphs using Monte Carlo Tree Search
• Learning Permutations with Sinkhorn Policy Gradient

Cited by in corpus (5)

• Learning Collaborative Policies to Solve NP-hard Routing Problems
• Efficient Active Search for Combinatorial Optimization Problems
• A Game-Theoretic Approach for Improving Generalization Ability of TSP Solvers
• Learning Enhanced Optimisation for Routing Problems
• A New Constructive Heuristic driven by Machine Learning for the Traveling Salesman Problem