TY - GEN
T1 - Graph Representation for Learning the Traveling Salesman Problem
AU - Gutiérrez, Omar
AU - Zamora, Erik
AU - Menchaca, Ricardo
N1 - Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
KW - Graph neural networks
KW - NP-Hard
KW - Neural combinatorial optimization
KW - Traveling salesman
UR - http://www.scopus.com/inward/record.url?scp=85111352755&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-77004-4_15
DO - 10.1007/978-3-030-77004-4_15
M3 - Contribución a la conferencia
AN - SCOPUS:85111352755
SN - 9783030770037
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 153
EP - 162
BT - Pattern Recognition - 13th Mexican Conference, MCPR 2021, Proceedings
A2 - Roman-Rangel, Edgar
A2 - Kuri-Morales, Ángel Fernando
A2 - Martínez-Trinidad, José Francisco
A2 - Carrasco-Ochoa, Jesús Ariel
A2 - Olvera-López, José Arturo
PB - Springer Science and Business Media Deutschland GmbH
T2 - 13th Mexican Conference on Pattern Recognition, MCPR 2021
Y2 - 23 June 2021 through 26 June 2021
ER -