PaperlayerView exact revision on arXiv

Source-linked AI summary

An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem

Chaitanya K. Joshi, Thomas Laurent, Xavier Bresson

arXiv:1906.01227v2cs.LGstat.ML

TL;DR

The paper addresses approximate solution of the 2D Euclidean TSP, where finding optimal tours is NP-hard. It uses deep graph ConvNets to predict tour-edge probabilities and highly parallelized beam search to produce non-autoregressive tours, outperforming prior deep learning methods on fixed graph sizes across solution quality, inference speed, and sample efficiency. However, the approach generalizes poorly across graph sizes and remains behind standard Operations Research solvers.

  • Problem

    The paper tackles approximate solution of the 2D Euclidean TSP, whose optimal solution requires searching for a minimum-length tour and is NP-hard.

  • Method

    Deep graph ConvNets predict an edge adjacency matrix of tour probabilities, which highly parallelized beam search converts into valid one-shot, non-autoregressive tours.

  • Results

    For fixed graph sizes, the framework outperforms previous deep learning techniques in solution quality, inference speed, and sample efficiency.

  • Takeaways & Limitations

    The approach provides an efficient learned approximate solver for fixed-size TSP instances by combining graph representation learning, parallelized computation, and optimal-solution supervision.

  • Takeaways & Limitations

    The non-autoregressive models show drastic performance drops when evaluated on unseen graph sizes, indicating poor generalization.

Abstract

from arXiv · show

This paper introduces a new learning-based approach for approximately solving the Travelling Salesman Problem on 2D Euclidean graphs. We use deep Graph Convolutional Networks to build efficient TSP graph representations and output tours in a non-autoregressive manner via highly parallelized beam search. Our approach outperforms all recently proposed autoregressive deep learning techniques in terms of solution quality, inference speed and sample efficiency for problem instances of fixed graph sizes. In particular, we reduce the average optimality gap from 0.52% to 0.01% for 50 nodes, and from 2.26% to 1.39% for 100 nodes. Finally, despite improving upon other learning-based approaches for TSP, our approach falls short of standard Operations Research solvers.

1 Introduction

The paper presents a non-autoregressive graph ConvNet approach for approximately solving TSP, using edge probabilities and beam search to produce tours. It targets solution quality, inference speed, and sample efficiency on fixed-size graphs.

  • TSP asks for the shortest tour that visits every city once and returns to the origin, an NP-hard optimization problem.
  • Recent deep learning methods typically use graph neural networks with autoregressive decoding to construct tours one node at a time.
  • Its components are highly parallelized, and solutions are produced in a one-shot, non-autoregressive manner.
  • The proposed graph ConvNet extracts node and edge features, predicts an edge adjacency matrix, and converts those predictions into a valid tour with beam search.
  • The model is trained supervisedly on problem instances paired with optimal solutions generated by Concorde.
  • The approach is evaluated on TSP instances with 20, 50, and 100 nodes, emphasizing solution quality, inference speed, and sample efficiency.

2 Related Work

Related work spans handcrafted Operations Research heuristics and learning-based methods that represent TSP instances with sequences or graphs. Most recent neural approaches decode tours autoregressively, while earlier one-shot graph models motivate this paper’s non-autoregressive design.

  • TSP is NP-hard even in the 2D Euclidean case, and practical solvers use handcrafted heuristics to approximate solutions for large graphs.
  • Neural approaches seek to learn approximate policies because designing effective combinatorial optimization heuristics can require substantial specialized knowledge.
  • Pointer Networks use attention to autoregressively output TSP permutations and can be trained on problem instances paired with Concorde solutions.
  • Graph neural network methods better reflect TSP’s combinatorial structure than sequence-to-sequence models by being invariant to node order.
  • Graph Attention Network approaches use attention-based decoders trained with reinforcement learning to build TSP solutions autoregressively.
  • An earlier supervised graph model directly predicted a tour adjacency matrix and used beam search, but performed poorly on very small instances because it could not condition on partial tours.
  • Related learning-based techniques also address Vehicle Routing, multiple TSP, Minimum Vertex Cover, Maximum Cut, and Maximal Independent Set.

3 Dataset

The study focuses on 2D Euclidean TSP instances whose city locations lie in the unit square. It uses fixed-size datasets with optimal tours generated by Concorde.

  • The technique is developed for 2D Euclidean TSP, while also being applicable to sparse graphs.
  • Each instance contains n cities represented by points x_i in the two-dimensional unit square [0,1]^2.
  • A tour is a permutation that visits every node once and minimizes total Euclidean length.
  • Separate training, validation, and test datasets are created for graphs with 20, 50, and 100 nodes.
  • Training sets contain one million instance-solution pairs, while validation and test sets each contain 10,000 pairs.
  • Node locations are sampled uniformly in the unit square, and Concorde is used to find each instance’s optimal tour.

4 Model

The model directly predicts a probabilistic adjacency matrix for a TSP tour using a graph ConvNet, then converts it into a valid permutation through search.

  • Model architecture: The graph ConvNet directly outputs an adjacency matrix corresponding to a TSP tour, trained end-to-end with cross-entropy loss.Ground-truth tours are represented as adjacency matrices, and evaluation converts predictions into valid tours using beam search.
  • Model architecture: Node coordinates, edge distances, and k-nearest-neighbor indicators form the graph’s input features.The k-nearest-neighbor graph restricts the input structure and can speed learning because tour edges usually connect nearby nodes.
  • Model architecture: Additional edge features and a dense attention map extend the graph ConvNet representation, making graph diffusion anisotropic.The proposed architecture builds on prior graph ConvNets by incorporating edge-feature representations and dense attention information.
  • Tour decoding: The model’s edge probabilities form a heat-map over possible tour connections rather than a directly valid tour.Each predicted edge probability represents the strength of that connection in the adjacency matrix.
  • Tour decoding: Argmax decoding can produce invalid tours, so the model uses greedy search, beam search, or shortest-tour selection among beam candidates.Beam search expands the b most probable partial tours, while the shortest-tour heuristic selects the shortest complete candidate.
  • Implementation: The experiments use 30 graph convolution layers, 3 MLP layers, hidden dimension 300, k = 20, and beam width b = 1,280.The same hyperparameters are used across all three problem sizes to compare against a method sampling 1,280 solutions.

5 Experiments

The experiments train graph ConvNet models with supervised optimization and evaluate predicted tours against optimal solutions using length, optimality gap, and evaluation time.

  • Training: The graph ConvNet is trained by minimizing cross-entropy loss with gradient descent on input graphs and corresponding TSP-tour adjacency matrices.The training procedure directly supervises adjacency-matrix prediction.
  • Training: Training samples are drawn from a one-million-instance dataset, with each epoch using 10,000 instances divided into 500 mini-batches.Each mini-batch contains 20 instances and is optimized with Adam.
  • Training: The learning rate is decayed when validation loss fails to improve by at least 1% over the previous validation loss.Validation is performed every five training epochs, and the learning rate is divided by 1.01 when the criterion is unmet.
  • Evaluation: Evaluation converts model adjacency matrices into valid tours using search strategies and compares them with Concorde-derived optimal solutions.Because evaluation requires no backpropagation, batch sizes can fill available GPU memory.
  • Evaluation metrics: Predicted tour length averages lTSP over 10,000 test instances.This metric measures the average length of the tours produced by the model.
  • Evaluation metrics: Optimality gap averages the percentage ratio of predicted tour length lTSP relative to optimal solution length l̂TSP over 10,000 test instances.The metric quantifies closeness to the optimal solution.
  • Evaluation metrics: Evaluation time measures the wall-clock time to solve 10,000 test instances on either one GPU or 32 virtual CPUs in parallel.Reported runtime depends on the hardware and parallel execution setting.
  • Evaluation considerations: Searching or sampling more solutions can trade increased runtime for improved solution quality across learning-based approaches.Runtime comparisons also vary with implementation language and hardware.

6 Results

For fixed graph sizes, the approach is compared with exact solvers, heuristics, and deep learning methods across solution quality, inference time, sample efficiency, and generalization. Beam search improves quality and speed over sampling-based learning methods, while variable-size generalization remains poor.

  • Performance comparisons: Table 1 compares the technique with exact solvers, greedy methods, and sampling/search-based methods across multiple TSP instance sizes.The optimality gap is measured relative to Concorde, with methods categorized by solver type and training technique.
  • Greedy setting: In the greedy setting, learning-based approaches outperform non-learned heuristics, but the graph ConvNet trails Kool et al. in performance and evaluation time.Independent edge predictions and post-hoc greedy search add time overhead relative to autoregressive decoding.
  • Search/sampling setting: With 1,280 searched or sampled solutions, graph ConvNet beam search outperforms Kool et al. in both closeness to optimality and evaluation time.The paper attributes the gains to deeper graph representations and highly parallelized GPU implementations.
  • Combining learned and traditional heuristics: Adding the shortest tour heuristic to beam search improves performance but increases evaluation time, motivating further study of performance–computation trade-offs.The paper also identifies local search heuristics such as 2-OPT as a future direction for beam-search decoding.
  • Sample efficiency for SL vs. RL: For TSP20, both approaches reach within 1% of optimality after fewer than 500,000 samples, while larger instances require more samples.The supervised setup is more sample efficient because it trains with complete problem information rather than sparse reinforcement-learning rewards.
  • Generalization to variable problem sizes: The model can theoretically apply across graph sizes because its parameters are independent of n, but experiments show drastic performance drops on unseen sizes.The learned representations appear to memorize size-specific patterns, producing poor transfer compared with Kool et al.

7 Conclusions

The paper introduces graph ConvNets with beam search for approximately solving 2D Euclidean TSP. For fixed graph sizes, it reports improvements over prior deep learning methods in quality, speed, and sample efficiency, while identifying transfer learning and reinforcement learning as future directions.

  • 7 Conclusions: The framework uses graph ConvNets and beam search to approximately solve the 2D Euclidean Travelling Salesman Problem.For fixed graph sizes, it improves solution quality, inference speed, and sample efficiency over previous deep learning techniques.

A Summary Statistics for Datasets

The paper describes TSP dataset statistics and graph-convolution representations that encode node and edge information through layered, anisotropic message passing.

  • Dataset statistics: Concorde solver time increases with problem size, and datasets larger than 1,000 nodes would be impractical to generate on similar hardware.Solver timings use a single-thread program on a 32-core CPU server under average load.
  • Graph representations: The graph ConvNet maps a center node feature and an unordered set of neighboring node features to a new node representation.The neighborhood is defined by the graph structure, making the mapping suitable for graph-structured inputs.
  • Graph representations: Learnable normalized edge gates make graph diffusion anisotropic, allowing edge features to control information flow between nodes.The network also learns edge representations through a non-diffusion process on edge features.
  • Graph representations: Residual connections help minimize vanishing-gradient effects, while batch normalization supports fast training of deep architectures.Figure 3 illustrates the resulting graph convolution model.
  • Graph representations: Graph convolution computes h-dimensional representations for each node and edge, using node and edge information to update the next layer.Multiple layers progressively extract compositional features from the input graph.

C Additional Results

Additional experiments examine training behavior, model capacity, beam width, and attention type, showing how these choices affect validation optimality gaps and computational efficiency.

  • Training behavior: Models for TSP50 and TSP100 begin overfitting after approximately 4 million samples, although validation optimality gaps do not worsen.The training loss continues to decrease smoothly as the learning rate decays to very small values.
  • Model capacity: Smaller models achieve approximately the same closeness to optimality on smaller problem sizes, while larger capacities are essential for scaling to large problems.Increasing capacity also leads to longer training time.
  • Beam width: For smaller instances, increasing beam width beyond 200 has minor impact, whereas large beam widths are essential for TSP100 performance.The main experiments use beam width 1,280 for direct comparison with Kool et al. (2019).
  • Beam width: The non-autoregressive model can search with beam widths considerably larger than 1,280 within 1 second on a single GPU.This contrasts with the comparison setup, which uses beam width 1,280.
  • Attention type: Sigmoid-based dense attention gives marginally better performance and uses less GPU memory than classical softmax-based sparse attention.The comparison concerns validation optimality-gap behavior across attention mechanisms.

D Comments on Supervised Learning vs Reinforcement Learning

The paper contrasts supervised and reinforcement learning for TSP, emphasizing supervised learning’s sample efficiency while recognizing its dependence on optimal solutions and limited scalability.

  • Supervised versus reinforcement learning: Supervised learning requires optimal or high-quality solution pairs, restricting it to well-studied problems and small-scale training sizes.These requirements arise because supervised models depend on large sets of optimal or high-quality solutions.
  • Supervised versus reinforcement learning: Reinforcement learning is more computationally expensive and less sample efficient, but it avoids generating paired problem instances and solutions.RL can train from reward signals for sequential decisions when such a formulation is available.
  • Supervised versus reinforcement learning: Using one million optimal TSP solutions, the deep graph ConvNet outperforms other learning-based approaches in solution quality and sample efficiency.The advantage of supervised learning diminishes for larger instances.
  • Limitations and future work: Generating one million training samples beyond hundreds of nodes can become computationally intractable because TSP’s combinatorial complexity rapidly increases.The paper identifies this combinatorial explosion as preventing the approach from scaling to large TSPs.
  • Limitations and future work: Future work proposes combining supervised training on small instances with reinforcement-learning fine-tuning on larger instances without optimal solutions.The proposed direction aims to apply the graph ConvNet and beam search beyond hundreds of nodes.

E Solution Visualizations

The visualizations compare each instance’s input graph and ground-truth tour with the model’s edge-probability heat map and beam-search tour. As instances grow, less-certain predictions make beam search increasingly important for recovering optimal tours.

  • Each visualization presents the input k-nearest neighbor graph alongside the ground-truth TSP tour.
  • The middle panel shows the graph ConvNet’s probabilistic heat-map output for candidate tour edges.
  • The final panel shows the predicted TSP tour obtained by applying beam search to the heat map.
  • As instance size increases, the heat map reflects TSP’s combinatorial explosion, making beam search essential for finding the optimal tour.
Loading 1906.01227v2…