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:
- Path Length: Minimizing the total distance of the predicted tour.
- Degree Constraints: Ensuring every city is visited exactly once (entering and leaving).
- 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