Per-Instance TSP Solver Using PPO Achieves 1.66% Gap on d1291 Without Pre-training

Summary

A developer presents a novel approach to solving the Traveling Salesman Problem (TSP) using deep learning without pre-training. Instead of relying on large datasets, the solver uses Proximal Policy Optimization (PPO) to learn from scratch for each specific TSP instance. The core hypothesis is that optimal solutions consist mostly of 'minimum edges' (nearest neighbors) with difficulty arising from a small number of 'exception edges' outside local scope. The approach achieved a 1.66% gap on the TSPLIB d1291 benchmark in about 5.6 hours on a single A100 GPU.