On Learning Paradigms for the Travelling Salesman Problem

Chaitanya K. Joshi, Thomas Laurent, Xavier Bresson
10/16/2019
cs.LGstat.ML

Official code: chaitjo/learning-paradigms-for-tsp (32 stars, MIT, PyTorch, last commit 2020-12-17).

Abstract

We explore the impact of learning paradigms on training deep neural networks for the Travelling Salesman Problem. We design controlled experiments to train supervised learning (SL) and reinforcement learning (RL) models on fixed graph sizes up to 100 nodes, and evaluate them on variable sized graphs up to 500 nodes. Beyond not needing labelled data, our results reveal favorable properties of RL over SL: RL training leads to better emergent generalization to variable graph sizes and is a key component for learning scale-invariant solvers for novel combinatorial problems.

View on arXivView PDF

Code Implementations(1)

chaitjo/learning-paradigms-for-tspOfficial100%
PyTorchMIT

Code for the paper 'On Learning Paradigms for the Travelling Salesman Problem' (NeurIPS 2019 Graph Representation Learning Workshop)

324C++, ShellOct 16, 20195 years agoMIT
combinatorial-optimizationdeep-learninggeometric-deep-learninggraph-neural-networkspytorch+1 more

Similar Papers

Learning the Travelling Salesperson Problem Requires Rethinking Generalization

85% match1 repo2442020

GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training

84% match1 repo3312020

Tackling GNARLy Problems: Graph Neural Algorithmic Reasoning Reimagined through Reinforcement Learning

84% match2025

It's Much Easier for Neural Networks to learn Game of Life Dynamics with the Right Activation Function: Polynomial Kolmogorov-Arnold Networks

84% match1 repo52026

A Unified Pre-training and Adaptation Framework for Combinatorial Optimization on Graphs

84% match2023

Train Small, Deploy Large: Zero-Shot GNN Transfer Through Geometric Renormalization

84% match2026

Cite this paper

@article{joshi2019learning,
  title  = {On Learning Paradigms for the Travelling Salesman Problem},
  author = {Chaitanya K. Joshi and Thomas Laurent and Xavier Bresson},
  year   = {2019},
  eprint = {1910.07210},
  archivePrefix = {arXiv},
  url    = {https://arxiv.org/abs/1910.07210}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/1910.07210.svg)](https://codeofpaper.com/paper/1910.07210)

Discussion