Show simple item record

dc.contributor.authorJoshi, Chaitanya K
dc.contributor.authorCappart, Quentin
dc.contributor.authorRousseau, Louis-Martin
dc.contributor.authorLaurent, Thomas
dc.date.accessioned2022-06-07T08:11:49Z
dc.date.available2022-06-07T08:11:49Z
dc.date.issued2022-04
dc.identifier.issn1383-7133
dc.identifier.others10601-022-09327-y
dc.identifier.other9327
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/337764
dc.description.abstract<jats:title>Abstract</jats:title><jats:p>End-to-end training of neural network solvers for graph combinatorial optimization problems such as the Travelling Salesperson Problem (TSP) have seen a surge of interest recently, but remain intractable and inefficient beyond graphs with few hundreds of nodes. While state-of-the-art learning-driven approaches for TSP perform closely to classical solvers when trained on trivially small sizes, they are unable to generalize the learnt policy to larger instances at practical scales. This work presents an end-to-end <jats:italic>neural combinatorial optimization</jats:italic> pipeline that unifies several recent papers in order to identify the inductive biases, model architectures and learning algorithms that promote generalization to instances larger than those seen in training. Our controlled experiments provide the first principled investigation into such <jats:italic>zero-shot</jats:italic> generalization, revealing that extrapolating beyond training data requires rethinking the neural combinatorial optimization pipeline, from network layers and learning paradigms to evaluation protocols. Additionally, we analyze recent advances in deep learning for routing problems through the lens of our pipeline and provide new directions to stimulate future research.</jats:p>
dc.languageen
dc.publisherSpringer Science and Business Media LLC
dc.subjectArticle
dc.subjectCombinatorial optimization
dc.subjectTravelling salesperson problem
dc.subjectGraph neural networks
dc.subjectDeep learning
dc.titleLearning the travelling salesperson problem requires rethinking generalization
dc.typeArticle
dc.date.updated2022-06-07T08:11:49Z
prism.endingPage98
prism.issueIdentifier1-2
prism.publicationNameConstraints
prism.startingPage70
prism.volume27
dc.identifier.doi10.17863/CAM.85173
dcterms.dateAccepted2022-03-16
rioxxterms.versionofrecord10.1007/s10601-022-09327-y
rioxxterms.versionVoR
rioxxterms.licenseref.urihttp://creativecommons.org/licenses/by/4.0/
dc.contributor.orcidJoshi, Chaitanya K [0000-0003-4722-1815]
dc.identifier.eissn1572-9354
cam.issuedOnline2022-04-28


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record