Unsupervised Training for Neural TSP Solver

Eliza Gaile, Andis Draguns, Emils Ozolins, Karlis Freivalds

Abstract

Traditional neural approaches to the Traveling Salesman Problem (TSP) rely on either computationally expensive supervised labels or unstable reinforcement learning (RL) frameworks. This paper introduces a novel unsupervised learning (UL) approach that trains a Graph Neural Network (GNN) by converting the mathematical constraints of the TSP into a differentiable loss function. By leveraging a relaxation of the Dantzig-Fulkerson-Johnson (DFJ) formulation and a parametric connectivity heuristic, the proposed method achieves high stability and significantly outperforms RL baselines on Asymmetric TSP (ATSP) tasks.

Introduction

The Traveling Salesman Problem (TSP) remains a cornerstone of combinatorial optimization, with applications ranging from logistics to microchip manufacturing. While deep learning has emerged as a promising tool for solving NP-hard problems, current paradigms face significant hurdles. Supervised Learning (SL) requires optimal or near-optimal "labels," which are computationally grueling to generate for large-scale instances. Reinforcement Learning (RL), while label-free, is notoriously sensitive to hyperparameters, exhibits unstable training dynamics, and struggles with Asymmetric TSP (ATSP)—where travel costs between two points depend on the direction of travel.

This research bridges the gap by proposing an Unsupervised Learning (UL) framework. By treating the TSP's mathematical definition as a training signal, the authors enable a GNN to learn generalizable heuristics without ever seeing a pre-solved example.

Methodology

Differentiable Loss Function

The core innovation lies in the translation of the classic Dantzig-Fulkerson-Johnson (DFJ) Integer Linear Program (ILP) into a differentiable loss function. The network is penalized based on three primary criteria:

  1. Path Length: Minimizing the total distance of the predicted tour.
  2. Degree Constraints: Ensuring every city is visited exactly once (entering and leaving).
  3. Subtour Elimination: Preventing the formation of isolated mini-loops that do not connect to the main tour.

Connectivity Heuristic and Discretization

To address the subtour constraint—which is exponentially difficult to compute exactly—the authors implemented a parametric connectivity heuristic. This heuristic identifies potential mini-loops in polynomial time ($O(n^3)$), allowing for efficient backpropagation.

Furthermore, because neural networks naturally output continuous probabilities, the researchers utilized the Gumbel-Softmax technique. This adds controlled noise during the training phase, pushing the model to move away from ambiguous edge probabilities and converge toward clear binary (integer) decisions.

Architecture

The model utilizes a Graph Neural Network (GNN) that processes both node and edge embeddings. The output is an adjacency matrix representing the predicted tour. Interestingly, the researchers found that while direct optimization of a single instance often fails due to local minima, training the GNN across thousands of instances allows it to learn structural patterns, effectively acting as a learned global optimizer.

Experimental Results

The model was evaluated on both Euclidean TSP (symmetric) and Asymmetric TSP (ATSP) datasets with 20 and 50 nodes.

Stability and Asymmetry

One of the most striking findings was the stability of the unsupervised approach compared to RL. While RL training curves showed massive fluctuations and "spikes," the UL loss provided a smooth, consistent learning trajectory.

In the ATSP-50 category, the UL approach demonstrated clear dominance. It achieved an optimality gap of 32.7%, whereas the RL baseline failed to converge effectively, resulting in gaps exceeding 1400%. This success is attributed to the UL loss operating directly on the edge adjacency matrix, which captures directionality more effectively than the node-centric embeddings often used in RL.

Comparison with Supervised Learning

On standard Euclidean TSP-20, the UL method achieved a 1.29% optimality gap, outperforming RL (2.75%) but trailing behind SL (0.2%). While SL remains the performance leader, the authors highlight that UL achieves these results without the massive computational overhead required to generate optimal training labels.

Discussion and Future Work

While the unsupervised framework shows great promise, it currently faces a "supervised ceiling" where it cannot yet match the precision of models trained on optimal solutions. Additionally, the $O(n^3)$ complexity of the subtour check may present a bottleneck for scaling to graphs with thousands of nodes.

However, the flexibility of this framework is a major advantage. Future research could extend this differentiable loss to include real-world constraints such as time windows, vehicle capacities, or dynamic traffic conditions by simply appending new penalty terms to the objective function. This work paves the way for more robust, label-free neural solvers in complex combinatorial domains.

Summary updated

Abstract

There has been a growing number of machine learning methods for approximately solving the travelling salesman problem. However, these methods often require solved instances for training or use complex reinforcement learning approaches that need a large amount of tuning. To avoid these problems, we introduce a novel unsupervised learning approach. We use a relaxation of an integer linear program for TSP to construct a loss function that does not require correct instance labels. With variable discretization, its minimum coincides with the optimal or near-optimal solution. Furthermore, this loss function is differentiable and thus can be used to train neural networks directly. We use our loss function with a Graph Neural Network and design controlled experiments on both Euclidean and asymmetric TSP. Our approach has the advantage over supervised learning of not requiring large labelled datasets. In addition, the performance of our approach surpasses reinforcement learning for asymmetric TSP and is comparable to reinforcement learning for Euclidean instances. Our approach is also more stable and easier to train than reinforcement learning.
BibTeX
@inproceedings{gaile2022unsupervised,
  author = {Eliza Gaile and Andis Draguns and Emils Ozolins and Karlis Freivalds},
  title = {{Unsupervised Training for Neural TSP Solver}},
  booktitle = {LION},
  year = {2022},
  url = {https://openreview.net/forum?id=0Gzq7yYX11},
}
Figure