An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem

By Chaitanya K. Joshi, Thomas Laurent, Xavier Bresson. arXiv.org, 2019

481 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/f598a8afec169c435e48ad19356c3b768f8ce7a7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Industrial and Manufacturing Engineering

Citations in the corpus

Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model (2024, methodology): “Instead of solely depending on neural solvers, many works integrate heuristic algorithms including heat map-based methods (Joshi et al., 2019; Fu et al., 2021; Qiu et al., 2022), heat map guided beam search (Joshi et al., 2019), Monte Carlo tree search (MCTS) (Fu et al., 2021), dynamic programming…”
Diffusion models as plug-and-play priors (2022, methodology): “Successful recent approaches [6, 21, 16, 17, 4] have used Transformer [41] and graph neural network [20] architectures.”
Learning to plan with uncertain topological maps (2020, unknown): “GNNs have been applied to shortest path planning in travelling salesmen problems [33,25] and it has been reasoned that they can approximate optimal symbolic planning algorithms such as the Bellman-Ford algorithm [60].”
What graph neural networks cannot learn: depth vs width (2019, background): “Further, there have been multiple attempts to use graph neural networks in order to devise heuristics for hard or computationally expensive graph-theoretic optimization problems [24, 25], such as the ones discussed above.”
Benchmarking Graph Neural Networks (2023, methodology): “For our experiments with TSP, we follow the learning-based approach to COPs described in [52, 40], where a GNN is the backbone architecture for assigning probabilities to each edge as belonging/not belonging to the predicted solution set.”
DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization (2023, methodology): “Methods in the second category rely on non-autoregressive modeling for scaling up, with a conditional independence assumption among variables as typical [53, 55, 92].”