Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/77027
Title: Graph convolutional neural networks for the travelling salesman problem
Authors: Joshi, Chaitanya Krishna
Keywords: DRNTU::Engineering::Computer science and engineering::Computing methodologies::Artificial intelligence
Issue Date: 2019
Abstract: Combinatorial optimization problems, also called NP-hard problems, are practical constraint satisfaction problems that are impossible to solve optimally at large scales. In practice, handcrafted heuristic algorithms are able to solve problems with up to a million variables and constraints. These algorithms are the backbone of modern industries such as transportation, supply chain, and scheduling. However, coming up with good heuristics requires significant specialized knowledge. A recent line of work investigates using deep neural networks to directly learn these heuristics from problem instances instead. In this paper, we introduce a novel deep learning approach for approximately solving the most famous NP-hard problem in recent history, the Travelling Salesman Problem. We focus on the 2D Euclidean TSP and use Graph Convolutional Neural Networks and beam search to predict a valid TSP tour given an input graph with up to 100 nodes. Our approach outperforms all recently proposed deep learning techniques in terms of both solution quality and speed when evaluated on problem instances of fixed graph sizes. However, experiments on the generalization capabilities of our models show a drastic drop in performance when evaluated on graph sizes different from those that models were trained on. Our results highlight an important flaw in the current paradigm of learning-based approaches for TSP and combinatorial optimization: comparing among approaches based on performance for discrete problem sizes completely ignores generalization. We advocate for the machine learning community to switch focus towards building size-agnostic models with strong generalization capabilities in order to scale up to realistic problem sizes.
URI: http://hdl.handle.net/10356/77027
Rights: Nanyang Technological University
Fulltext Permission: restricted
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Student Reports (FYP/IA/PA/PI)

Files in This Item:
File Description SizeFormat 
FYP_Thesis_Joshi_CK_Final.pdf
  Restricted Access
5.62 MBAdobe PDFView/Open

Page view(s)

180
Updated on May 14, 2021

Download(s) 50

103
Updated on May 14, 2021

Google ScholarTM

Check

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.