Unsupervised Training for Neural TSP Solver

  • 2022-07-27 18:33:29
  • Elīza Gaile, Andis Draguns, Emīls Ozoliņš, Kārlis Freivalds
  • 1


There has been a growing number of machine learning methods for approximatelysolving the travelling salesman problem. However, these methods often requiresolved instances for training or use complex reinforcement learning approachesthat need a large amount of tuning. To avoid these problems, we introduce anovel unsupervised learning approach. We use a relaxation of an integer linearprogram for TSP to construct a loss function that does not require correctinstance labels. With variable discretization, its minimum coincides with theoptimal or near-optimal solution. Furthermore, this loss function isdifferentiable and thus can be used to train neural networks directly. We useour loss function with a Graph Neural Network and design controlled experimentson both Euclidean and asymmetric TSP. Our approach has the advantage oversupervised learning of not requiring large labelled datasets. In addition, theperformance of our approach surpasses reinforcement learning for asymmetric TSPand is comparable to reinforcement learning for Euclidean instances. Ourapproach is also more stable and easier to train than reinforcement learning.


Quick Read (beta)

loading the full paper ...