KDD-BR 2021: Using Graph Neural Networks for Link Prediction in TSP Problem

• Bruno Klaus de Aquino Afonso UNIFESP
• Willian Dihanster Gomes de Oliveira UNIFESP
• Jéssica Domingues Lamosa UNIFESP
• Lilian Berton UNIFESP

DOI: https://doi.org/10.5753/eniac.2021.18426

Abstract

In the traveling salesman problem (TSP), the objective is to find a route that goes through all the cities and returns to the city of origin with the shortest total distance covered. As an NP-complete problem, finding solutions is not easy, and several heuristics have been proposed. Currently, with the advance in the use of Machine Learning (ML), it is possible to use ML to predict connections between cities in the optimal solution. Our model, based on graph neural networks, obtained an F1-score of 0.10645 in the public leaderboard of KDD-BR 2021, enough to outperform the greedy baseline. This shows ML can be a good technique to generate solutions faster or even build better solutions.

Keywords: Graph-based neural networks, TSP problem, Machine Learning

References

Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction to algorithms. MIT press.

Dwivedi, V. P., Joshi, C. K., Laurent, T., Bengio, Y., and Bresson, X. (2020). Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982.

Joshi, C. K., Cappart, Q., Rousseau, L.-M., Laurent, T., and Bresson, X. (2020). Learning tsp requires rethinking generalization. arXiv preprint arXiv:2006.07054.

Joshi, C. K., Laurent, T., and Bresson, X. (2019). An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227.

Menger, K. (1932). Das botenproblem. Ergebnisse eines mathematischen kolloquiums, 2(4):11–12.

Prates, M., Avelar, P., Lemos, H., Lamb, L., and Vardi, M. (2019). Learning to solve np-complete problems: A graph neural network for decision tsp. Proceedings of the AAAI Conference on Artificial Intelligence, 33:4731–4738.

Wang, Y., Sun, Y., Liu, Z., Sarma, S. E., Bronstein, M. M., and Solomon, J. M. (2019). Dynamic graph cnn for learning on point clouds. Acm Transactions On Graphics (tog), 38(5):1–12.