Graph Representation for Learning the Traveling Salesman Problem

Omar Gutiérrez, Erik Zamora, Ricardo Menchaca

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

Training deep learning models for solving the Travelling Salesman Problem (TSP) directly on large instances is computationally challenging. An approach to tackle large-scale TSPs is through identifying elements in the model or training procedure that promotes out-of-distribution (OoD) generalization, i.e., generalization to samples larger than those seen in training. The state-of-the-art TSP solvers based on Graph Neural Networks (GNNs) follow different strategies to represent the TSP instances as input graphs. In this paper, we conduct experiments comparing different graph representations finding features that lead to a better OoD generalization.

Original languageEnglish
Title of host publicationPattern Recognition - 13th Mexican Conference, MCPR 2021, Proceedings
EditorsEdgar Roman-Rangel, Ángel Fernando Kuri-Morales, José Francisco Martínez-Trinidad, Jesús Ariel Carrasco-Ochoa, José Arturo Olvera-López
PublisherSpringer Science and Business Media Deutschland GmbH
Pages153-162
Number of pages10
ISBN (Print)9783030770037
DOIs
StatePublished - 2021
Event13th Mexican Conference on Pattern Recognition, MCPR 2021 - Virtual, Online
Duration: 23 Jun 202126 Jun 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12725 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th Mexican Conference on Pattern Recognition, MCPR 2021
CityVirtual, Online
Period23/06/2126/06/21

Keywords

  • Graph neural networks
  • NP-Hard
  • Neural combinatorial optimization
  • Traveling salesman

Fingerprint

Dive into the research topics of 'Graph Representation for Learning the Traveling Salesman Problem'. Together they form a unique fingerprint.

Cite this