On Size and Hardness Generalization in Unsupervised Learning for the Travelling Salesman Problem

Introduction

The paper discusses using machine learning, specifically unsupervised learning, to solve the Traveling Salesman Problem (TSP). TSP is a well-known optimization problem where the goal is to find the shortest route that visits each city exactly once and returns to the starting point.

Traditional methods like Lin-Kernighan-Helsgaun heuristics and the Concorde solver have been used to approximate or find optimal solutions for TSP. However, recent research has explored applying machine learning techniques, such as supervised learning and reinforcement learning, to tackle TSP.

The paper focuses on an unsupervised learning approach called UTSP proposed by Min et al. (2024). This method learns a data-driven heuristic for TSP without relying on labeled datasets, which overcomes the challenges faced by supervised and reinforcement learning methods.

The main contributions of the paper are:

1. Proposing a way for the TSP model to generalize across different problem sizes once trained, which was a limitation of the previous UTSP model.
2. Finding that training on larger problem sizes can improve model performance.
3. Exploring the impact of different embedding dimensions on TSP performance, with larger dimensions leading to better representations.
4. Investigating how the model performs when trained on datasets of varying distributions, with harder instances leading to better performance.

The paper highlights the importance of training data selection and its impact on the effectiveness of machine learning models for combinatorial optimization problems like TSP. It addresses the gap in understanding the generalization behavior of these models and provides practical guidelines for improving generalization and performance.

Related works

The paper discusses different machine learning approaches for solving the Traveling Salesperson Problem (TSP). Reinforcement Learning (RL) aims to train an agent to find short routes by maximizing future rewards, but it struggles with sparse rewards and getting trapped in local minima for larger TSP instances. Supervised Learning (SL) trains models on datasets of optimal TSP solutions, but generating these optimal solutions is computationally expensive, especially for larger problems.

The paper proposes an Unsupervised Learning (UL) approach that trains a graph neural network using a surrogate loss function, without requiring labeled optimal solutions or exploring better solutions through sparse rewards. This method aims to overcome the limitations of RL and SL by generating heat maps through a non-autoregressive process.

The paper is structured as follows: Section 3 introduces the background of UL for TSP. Section 4 presents a method for generalizing across various problem sizes. Section 5 investigates the generalization behavior with respect to different embedding dimensions and training sizes. Section 6 explores the generalization across different distributions through the lens of instance hardness.

UL for TSP

The paper discusses an unsupervised approach called UTSP for solving the Traveling Salesman Problem (TSP). TSP involves finding the shortest possible route that visits all cities exactly once and returns to the starting city.

The authors reformulate the TSP into two constraints: 1) finding the shortest path, and 2) ensuring the solution is a Hamiltonian Cycle (visits all cities exactly once). They create proxies for these constraints using a soft indicator matrix and a heat map generated by a Graph Neural Network (GNN).

The heat map represents the probability distributions of directed edges between cities. The authors optimize two terms: minimizing the total distance of the cycle, and enforcing the Hamiltonian Cycle constraint implicitly through a clever transformation of the indicator matrix.

The model is trained using a loss function that encourages the indicator matrix to behave like a permutation matrix, discourages self-loops in the heat map, and minimizes the overall distance.

However, a limitation is that the model cannot generalize to instances with different numbers of cities than it was trained on, since the dimensions of the indicator matrix are fixed based on the training instances.

Size Generalization

The paper discusses a generalized model for the Traveling Salesman Problem (TSP) using a Graph Neural Network (GNN). The GNN generates an n-dimensional embedding for each city. For TSP instances of different sizes, the GNN outputs an m-dimensional embedding for each node. A Softmax activation function is applied to each column of the embedding matrix, resulting in a matrix T.

The matrix H is then constructed from T, where H represents the relationship between the cities. When the dimensions m and n are not equal, H is not doubly stochastic. The authors experimented with adjusting T or H by scaling factors involving n and m, but these yielded similar results.

The matrix H is defined as a sum of outer products between columns of T, forming a cycle over the columns. This formulation is analogous to an earlier equation involving a matrix V, allowing the problem to be solved using matrix operations.

The section explains how the model is trained using a loss function L. The loss has two main components:

1. Row and column-wise constraint: This constraint ensures that the sum of values in each row and column of the predicted heat map H equals 1. This is achieved by minimizing the squared differences between 1 and the sums of row/column values.

2. Minimize the distance: This component aims to minimize the distance between the predicted heat map H and some given distance matrix D. The distances in D likely represent the desired relationships between cities.

Additionally, the model uses a graph neural network (GNN) to output an m-dimensional embedding for each city. This embedding allows the model to generalize across different instances, ensuring that the predicted heat map H matches the size of the input cities (n x n matrix).

In summary, the loss function guides the model to predict a heat map H that satisfies two criteria: 1) its row and column sums equal 1, and 2) it is close to a given distance matrix D, while also allowing generalization through city embeddings.

Experiment

The paper explores the impact of a generalized model on different problem sizes for the Traveling Salesman Problem (TSP). The model is trained on larger datasets (TSP-2000, TSP-1000, TSP-400) and tested on smaller instances (TSP-1000, TSP-500, TSP-200). The training datasets consist of randomly distributed points on a 2D plane, with 5,000 training instances each.

The model's performance is evaluated using the performance gap, calculated as (l - l_opt) / l_opt, where l is the TSP length generated by the model, and l_opt is the optimal length. The search process involves generating a heat map, extracting the top values, and symmetrizing the heat map to guide the search.

The results show that the model achieves a gap of 0.0558% for TSP-200, 0.8229% for TSP-500, and 1.1616% for TSP-1000, outperforming other methods for the largest instance size. The paper highlights the model's ability to generalize across different problem sizes and effectively enhance the search process, demonstrating its robustness and scalability.

The paper investigates the impact of varying the embedding dimension m and instance size n on the training performance of the proposed model for the Traveling Salesman Problem (TSP).

Increasing the embedding dimension m from 500 to 1500 improved the overlap ratio (ability to identify optimal solutions) from 82.7% to 94.93% when considering the top 5 solutions. It also reduced the performance gap (deviation from optimal solution) from 2.07% to 1.41%. With the top 20 solutions, m=1000 and m=1500 achieved 100% overlap ratio, outperforming m=500. However, m=1000 performed marginally better than m=1500, suggesting diminishing returns beyond a certain embedding dimension.

Training on larger TSP instances (n=2000) yielded better performance than smaller instances (n=400 or n=1000). With the top 5 solutions, the performance gap improved from 3.08% to 1.41% when training on n=2000 instead of n=400. For the top 20 solutions, the gap decreased from 1.19% to 1.16%.

The results demonstrate the benefits of increasing the embedding dimension and training instance size to enhance the model's ability to identify optimal solutions and improve overall performance on the TSP.

Hardness Generalization

The paper investigates the relationship between different distributions of the Traveling Salesman Problem (TSP) instances and the effectiveness of using machine learning techniques to guide the search and reduce the search space. It focuses on correlating the hardness of different distributions with the efficiency of using machine learning for solving TSP.

The concept of phase transition is introduced, which refers to a change in the solvability of NP-hard problems like TSP when certain parameters are varied. The paper uses a parameter called τ (tau) to measure the hardness of TSP instances, where a higher τ value indicates a harder instance.

Four different distributions (Uniform, Implosion, Explosion, and Expansion) are studied, and their τ values are calculated for different instance sizes (200, 500, and 1000). The Uniform distribution is found to be closest to the phase transition point, suggesting it is the hardest distribution.

The paper then trains machine learning models on these four distributions and evaluates their performance in terms of overlap ratio (how well the solutions align with optimal solutions) and performance gap (difference from optimal solutions). Models trained on harder distributions like Uniform exhibit higher overlap ratios and better search performance, indicating they can better represent the search space.

When selecting the top solutions from each distribution for larger instances (TSP-1000), all distributions achieve 100% overlap ratio, but training on harder distributions like Uniform still shows slightly better performance in terms of the performance gap.

The paper concludes that training machine learning models on harder distributions leads to better generalization and more effective search space reduction for solving TSP instances.

Conclusion

The research introduces a new method that enables a trained, unsupervised traveling salesperson problem (TSP) model to generalize across different problem sizes. The results demonstrate that training on larger problem instances can improve performance compared to training with smaller instances. The study explores the influence of embedding dimensions on TSP results, showing that larger embedding dimensions are important for constructing more effective representations that guide the search process more efficiently.

Furthermore, the research investigates the model's performance using training datasets with varying levels of difficulty. It shows that training on harder instances can improve model performance, emphasizing the importance of selecting training instances with appropriate difficulty levels. The models are trained on different TSP distributions to understand their impact on the effectiveness of unsupervised learning models.

The study indicates a clear relationship between the inherent hardness of the distribution and the model's ability to generalize and effectively solve TSP instances. This is the first study to systematically investigate and demonstrate this connection. The results highlight the relationship between the characteristics of training instances (size and hardness), embedding dimensions, and model performance in unsupervised learning, particularly when addressing combinatorial optimization problems such as the TSP.

The findings emphasize the benefits of training on larger, harder instances with increased embedding dimensions, which can inspire further research in the application of unsupervised learning to combinatorial optimization tasks.

Acknowledgement

The research is funded by various organizations, including the Eric and Wendy Schmidt AI in Science Postdoctoral Fellowship, a program by Schmidt Futures. It receives support from government agencies like the National Science Foundation (NSF), the National Institute of Food and Agriculture (NIFA), the Air Force Office of Scientific Research (AFOSR), and the Department of Energy. Additionally, it is backed by the Toyota Research Institute (TRI), a prominent automotive research organization.