Attention Solves Your TSP

Wouter Kool, Max WellingarXiv 2018 · arXiv

TL;DR

This paper introduces an attention-based neural network model for solving combinatorial optimization problems, specifically routing problems like the Traveling Salesperson Problem (TSP) and Vehicle Routing Problem (VRP). By leveraging attention mechanisms and a novel REINFORCE training strategy with a greedy rollout baseline, they achieve state-of-the-art results on several routing benchmarks, outperforming previous learned heuristics and even specialized algorithms in some cases.

What Problem Does This Paper Address?

Combinatorial optimization problems, such as finding the shortest route for a salesperson to visit multiple cities (TSP), are notoriously difficult to solve optimally, often falling into the NP-hard category. While exact methods guarantee optimality, they are computationally infeasible for large problem instances. Heuristics offer a practical alternative by providing good solutions quickly, but designing effective heuristics often requires significant domain expertise and manual effort. The paper addresses the challenge of automatically learning strong heuristics for these problems using deep learning. Specifically, they aim to improve upon existing neural network approaches by proposing a more powerful model architecture and a more efficient training method.

Methods

The core of the paper's contribution lies in two main areas:

  • Attention-based Model: They propose an "Attention Model" (AM) that utilizes a Transformer-like architecture with multi-head attention layers. This differs from previous approaches like Pointer Networks (PN) which often rely on recurrent (LSTM) layers. The attention mechanism allows the model to weigh the importance of different input nodes when making decisions, leading to more efficient learning and better generalization. Crucially, it makes the model invariant to the input order of nodes, enabling parallelization.
  • REINFORCE with Greedy Rollout Baseline: For training, they employ the REINFORCE algorithm, a policy gradient method. To reduce variance and improve learning efficiency, they introduce a novel baseline: a "greedy rollout" of the current best model. This baseline deterministically selects the most probable action at each step, providing a stable and effective estimate of the instance's difficulty. They also propose a strategy to periodically update this baseline policy to ensure it remains competitive.

Datasets

The paper evaluates their model on several standard routing problem benchmarks:

  • Traveling Salesperson Problem (TSP): Instances of varying sizes (n=20, 50, 100 nodes) are used.
  • Vehicle Routing Problem (VRP): Including Capacitated VRP (CVRP) and Split Delivery VRP (SDVRP).
  • Orienteering Problem (OP): With different prize distributions (constant, uniform, distance-based).
  • Prize Collecting TSP (PCTSP): And its stochastic variant (SPCTSP).

The instances are generated by sampling node locations uniformly in the unit square, with specific methods for generating demands, prizes, and penalties depending on the problem.

Key Insights and Ideas

  • Attention over Recurrence: The shift from recurrent (LSTM) to attention-based architectures for routing problems is a significant advantage. Attention allows for parallel processing and is invariant to input order, leading to faster training and potentially better performance.
  • Greedy Rollout as a Strong Baseline: The proposed greedy rollout baseline proves to be more effective than traditional baselines like exponential moving averages or learned value functions (critics) for training combinatorial optimization models. It stabilizes learning and leads to faster convergence.
  • Unified Model for Diverse Routing Problems: The ability of a single attention-based architecture, with minor modifications to input features and masking, to achieve strong results across a variety of routing problems (TSP, VRP, OP, PCTSP) highlights the generality and power of the approach.
  • Learned Heuristics Can Compete with Specialized Algorithms: The paper demonstrates that learned heuristics can achieve performance comparable to, and in some cases surpass, highly optimized and specialized algorithms that have been developed over decades.

Key Results

The Attention Model (AM) achieves state-of-the-art results on several benchmarks:

  • TSP: For problems up to 100 nodes, the AM gets very close to optimal solutions, outperforming previous learned heuristics and competitive with specialized solvers like Concorde and LKH3. For n=100, their sampling approach achieves a gap of only 0.52% compared to Gurobi.
  • VRP (CVRP/SDVRP): The AM's greedy decoding outperforms previous reinforcement learning baselines and gets significantly closer to state-of-the-art algorithms like LKH3.
  • OP: The AM achieves competitive results, outperforming a Python GA and being only 2% worse than a state-of-the-art Genetic Algorithm (Compass) when sampling.
  • PCTSP: The AM finds almost equally good results as OR Tools with 60s of local search, but in significantly less time.

Limitations and Future Work

  • Scalability: While the attention mechanism enables better parallelization, scaling to extremely large problem instances (e.g., thousands of nodes) remains a challenge. The authors suggest that sparsifying the graph attention network could be a promising direction.
  • Feasibility Constraints: For problems with complex feasibility constraints that cannot be handled by simple masking, the authors propose investigating a combination of heuristic learning and backtracking.
  • Training Time: While the greedy rollout baseline improves learning efficiency, training can still be time-consuming, especially for larger problem sizes. The paper notes that further improvements could be made by optimizing the model for inference.
  • Generalization: While the model shows good generalization across different problem sizes, performance degrades as the test size deviates significantly from the training size. The authors suggest training models for specific instance sizes to maximize performance.

Summary updated

BibTeX
@misc{kool2018attention,
  author = {Wouter Kool and Max Welling},
  title = {{Attention Solves Your TSP}},
  year = {2018},
  eprint = {1803.08475},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1803.08475},
}
Figure