Graph convolutional neural networks for the travelling salesman problem
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 alg...
Saved in:
Main Author: | |
---|---|
Other Authors: | |
Format: | Final Year Project |
Language: | English |
Published: |
2019
|
Subjects: | |
Online Access: | http://hdl.handle.net/10356/77027 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
id |
sg-ntu-dr.10356-77027 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.10356-770272023-03-03T20:34:40Z Graph convolutional neural networks for the travelling salesman problem Joshi, Chaitanya Krishna Xavier Bresson School of Computer Science and Engineering DRNTU::Engineering::Computer science and engineering::Computing methodologies::Artificial intelligence 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. Bachelor of Engineering (Computer Science) 2019-05-02T06:08:08Z 2019-05-02T06:08:08Z 2019 Final Year Project (FYP) http://hdl.handle.net/10356/77027 en Nanyang Technological University 44 p. application/pdf |
institution |
Nanyang Technological University |
building |
NTU Library |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
NTU Library |
collection |
DR-NTU |
language |
English |
topic |
DRNTU::Engineering::Computer science and engineering::Computing methodologies::Artificial intelligence |
spellingShingle |
DRNTU::Engineering::Computer science and engineering::Computing methodologies::Artificial intelligence Joshi, Chaitanya Krishna Graph convolutional neural networks for the travelling salesman problem |
description |
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. |
author2 |
Xavier Bresson |
author_facet |
Xavier Bresson Joshi, Chaitanya Krishna |
format |
Final Year Project |
author |
Joshi, Chaitanya Krishna |
author_sort |
Joshi, Chaitanya Krishna |
title |
Graph convolutional neural networks for the travelling salesman problem |
title_short |
Graph convolutional neural networks for the travelling salesman problem |
title_full |
Graph convolutional neural networks for the travelling salesman problem |
title_fullStr |
Graph convolutional neural networks for the travelling salesman problem |
title_full_unstemmed |
Graph convolutional neural networks for the travelling salesman problem |
title_sort |
graph convolutional neural networks for the travelling salesman problem |
publishDate |
2019 |
url |
http://hdl.handle.net/10356/77027 |
_version_ |
1759856467164266496 |