Document Open Access Logo

Learning TSP Requires Rethinking Generalization

Authors Chaitanya K. Joshi , Quentin Cappart, Louis-Martin Rousseau, Thomas Laurent

PDF
Thumbnail PDF

File

LIPIcs.CP.2021.33.pdf
  • Filesize: 4.35 MB
  • 21 pages

Document Identifiers

Author Details

Chaitanya K. Joshi
  • Institute for Infocomm Research, A*STAR, Singapore
Quentin Cappart
  • Ecole Polytechnique de Montréal, Canada
Louis-Martin Rousseau
  • Ecole Polytechnique de Montréal, Canada
Thomas Laurent
  • Loyola Marymount University, LA, USA

Acknowledgements

We would like to thank X. Bresson, V. Dwivedi, A. Ferber, E. Khalil, W. Kool, R. Levie, A. Prouvost, P. Veličković and the anonymous reviewers for helpful discussions.

Cite AsGet BibTex

Chaitanya K. Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learning TSP Requires Rethinking Generalization. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 33:1-33:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CP.2021.33

Abstract

End-to-end training of neural network solvers for combinatorial optimization problems such as the Travelling Salesman Problem is intractable and inefficient beyond a few hundreds of nodes. While state-of-the-art Machine Learning approaches perform closely to classical solvers when trained on trivially small sizes, they are unable to generalize the learnt policy to larger instances of practical scales. Towards leveraging transfer learning to solve large-scale TSPs, this paper identifies 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 zero-shot generalization, revealing that extrapolating beyond training data requires rethinking the neural combinatorial optimization pipeline, from network layers and learning paradigms to evaluation protocols.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Neural networks
Keywords
  • Combinatorial Optimization
  • Travelling Salesman Problem
  • Graph Neural Networks
  • Deep Learning

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. David Applegate, Ribert Bixby, Vasek Chvatal, and William Cook. Concorde tsp solver, 2006. Google Scholar
  2. David L Applegate, Robert E Bixby, Vasek Chvatal, and William J Cook. The traveling salesman problem: a computational study. Princeton university press, 2006. Google Scholar
  3. Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint, 2016. URL: http://arxiv.org/abs/1607.06450.
  4. Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. In International Conference on Learning Representations, 2017. URL: https://openreview.net/pdf?id=Bk9mxlSFx.
  5. Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d'horizon. arXiv preprint, 2018. URL: http://arxiv.org/abs/1811.06128.
  6. Xavier Bresson and Thomas Laurent. An experimental study of neural networks for variable graphs. In International Conference on Learning Representations, 2018. Google Scholar
  7. Xavier Bresson and Thomas Laurent. A two-step graph convolutional decoder for molecule generation. In NeurIPS Workshop on Machine Learning and the Physical Sciences, 2019. Google Scholar
  8. Quentin Cappart, Emmanuel Goutierre, David Bergman, and Louis-Martin Rousseau. Improving optimization bounds using machine learning: Decision diagrams meet deep reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1443-1451, 2019. Google Scholar
  9. Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. In Advances in Neural Information Processing Systems, pages 6278-6289, 2019. Google Scholar
  10. Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. arXiv preprint, 2020. URL: http://arxiv.org/abs/2004.05718.
  11. George Dantzig, Ray Fulkerson, and Selmer Johnson. Solution of a large-scale traveling-salesman problem. Journal of the operations research society of America, 2(4):393-410, 1954. Google Scholar
  12. Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Martin Rousseau. Learning heuristics for the tsp by policy gradient. In International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 170-181. Springer, 2018. Google Scholar
  13. Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint, 2020. URL: http://arxiv.org/abs/2003.00982.
  14. Aaron Ferber, Bryan Wilder, Bistra Dilkina, and Milind Tambe. Mipaal: Mixed integer program as a layer. In AAAI Conference on Artificial Intelligence, 2020. Google Scholar
  15. Antoine François, Quentin Cappart, and Louis-Martin Rousseau. How to evaluate machine learning approaches for combinatorial optimization: Application to the travelling salesman problem. arXiv preprint, 2019. URL: http://arxiv.org/abs/1909.13121.
  16. Zhang-Hua Fu, Kai-Bin Qiu, Meng Qiu, and Hongyuan Zha. Targeted sampling of enlarged neighborhood via monte carlo tree search for tsp, 2020. URL: https://openreview.net/forum?id=ByxtHCVKwB.
  17. Vikas K Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. arXiv preprint, 2020. URL: http://arxiv.org/abs/2002.06157.
  18. Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. arXiv preprint, 2019. URL: http://arxiv.org/abs/1906.01629.
  19. Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pages 1263-1272. JMLR. org, 2017. Google Scholar
  20. Rafael Gómez-Bombarelli, Jennifer N Wei, David Duvenaud, José Miguel Hernández-Lobato, Benjamín Sánchez-Lengeling, Dennis Sheberla, Jorge Aguilera-Iparraguirre, Timothy D Hirzel, Ryan P Adams, and Alán Aspuru-Guzik. Automatic chemical design using a data-driven continuous representation of molecules. ACS central science, 4(2):268-276, 2018. Google Scholar
  21. Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. In International Conference on Learning Representations, 2020. URL: https://openreview.net/forum?id=rygGQyrFvH.
  22. John J Hopfield and David W Tank. “neural” computation of decisions in optimization problems. Biological cybernetics, 52(3):141-152, 1985. Google Scholar
  23. Jiayi Huang, Mostofa Patwary, and Gregory Diamos. Coloring big graphs with alphagozero. arXiv preprint, 2019. URL: http://arxiv.org/abs/1902.10162.
  24. Gurobi Optimization Inc. Gurobi optimizer reference manual. URL http://www. gurobi. com, 2015. Google Scholar
  25. Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint, 2015. URL: http://arxiv.org/abs/1502.03167.
  26. Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In International Conference on Machine Learning, pages 2323-2332, 2018. Google Scholar
  27. Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint, 2019. URL: http://arxiv.org/abs/1906.01227.
  28. Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems, pages 6348-6358, 2017. Google Scholar
  29. Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017. Google Scholar
  30. Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019. URL: https://openreview.net/forum?id=ByxBFsRqYm.
  31. Jan Karel Lenstra and AHG Rinnooy Kan. Some simple applications of the travelling salesman problem. Journal of the Operational Research Society, 26(4):717-733, 1975. Google Scholar
  32. Ron Levie, Michael M Bronstein, and Gitta Kutyniok. Transferability of spectral graph convolutional neural networks. arXiv preprint, 2019. URL: http://arxiv.org/abs/1907.12972.
  33. Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. In Advances in Neural Information Processing Systems, pages 539-548, 2018. Google Scholar
  34. John DC Little, Katta G Murty, Dura W Sweeney, and Caroline Karel. An algorithm for the traveling salesman problem. Operations research, 11(6):972-989, 1963. Google Scholar
  35. Qiang Ma, Suwen Ge, Danyang He, Darshan Thaker, and Iddo Drori. Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning. In AAAI Workshop on Deep Learning on Graphs: Methodologies and Applications, 2020. Google Scholar
  36. Hongzi Mao, Malte Schwarzkopf, Shaileshh Bojja Venkatakrishnan, Zili Meng, and Mohammad Alizadeh. Learning scheduling algorithms for data processing clusters. In Proceedings of the ACM Special Interest Group on Data Communication, pages 270-288. ACM, 2019. Google Scholar
  37. Azalia Mirhoseini, Hieu Pham, Quoc V. Le, Benoit Steiner, Rasmus Larsen, Yuefeng Zhou, Naveen Kumar, Mohammad Norouzi, Samy Bengio, and Jeff Dean. Device placement optimization with reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning - Volume 70, ICML’17, page 2430–2439. JMLR.org, 2017. Google Scholar
  38. Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, pages 9861-9871, 2018. Google Scholar
  39. Alex Nowak, David Folqué, and Joan Bruna Estrach. Divide and conquer networks. In 6th International Conference on Learning Representations, ICLR 2018, 2018. Google Scholar
  40. Alex Nowak, Soledad Villar, Afonso S Bandeira, and Joan Bruna. A note on learning algorithms for quadratic assignment with graph neural networks. arXiv preprint, 2017. URL: http://arxiv.org/abs/1706.07450.
  41. Aditya Paliwal, Felix Gimeno, Vinod Nair, Yujia Li, Miles Lubin, Pushmeet Kohli, and Oriol Vinyals. Regal: Transfer learning for fast optimization of computation graphs. arXiv preprint, 2019. URL: http://arxiv.org/abs/1905.02494.
  42. Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. arXiv preprint, 2019. URL: http://arxiv.org/abs/1910.10683.
  43. Maithra Raghu and Eric Schmidt. A survey of deep learning for scientific discovery. arXiv preprint, 2020. URL: http://arxiv.org/abs/2003.11755.
  44. Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural networks for combinatorial problems. In Advances in Neural Information Processing Systems, pages 4081-4090, 2019. Google Scholar
  45. John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint, 2017. URL: http://arxiv.org/abs/1707.06347.
  46. Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L Dill. Learning a sat solver from single-bit supervision. arXiv preprint, 2018. URL: http://arxiv.org/abs/1802.03685.
  47. Andrew W Senior, Richard Evans, John Jumper, James Kirkpatrick, Laurent Sifre, Tim Green, Chongli Qin, Augustin Žídek, Alexander WR Nelson, Alex Bridgland, et al. Improved protein structure prediction using potentials from deep learning. Nature, pages 1-5, 2020. Google Scholar
  48. Ilya Sutskever, Oriol Vinyals, and Quoc VV Le. Sequence to sequence learning with neural networks. In Advances in Neural Information Processing Systems, pages 3104-3112, 2014. Google Scholar
  49. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pages 5998-6008, 2017. Google Scholar
  50. Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018. URL: https://openreview.net/forum?id=rJXMpikCZ.
  51. Petar Veličković, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural execution of graph algorithms. In International Conference on Learning Representations, 2020. URL: https://openreview.net/forum?id=SkgKO0EtvS.
  52. Clement Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with message-passing. arXiv preprint, 2020. URL: http://arxiv.org/abs/2006.15107.
  53. Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, pages 2692-2700, 2015. Google Scholar
  54. Minjie Wang, Lingfan Yu, Da Zheng, Quan Gan, Yu Gai, Zihao Ye, Mufei Li, Jinjing Zhou, Qi Huang, Chao Ma, et al. Deep graph library: Towards efficient and scalable deep learning on graphs. arXiv preprint, 2019. URL: http://arxiv.org/abs/1909.01315.
  55. Bryan Wilder, Bistra Dilkina, and Milind Tambe. Melding the data-decisions pipeline: Decision-focused learning for combinatorial optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1658-1665, 2019. Google Scholar
  56. Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-256, 1992. Google Scholar
  57. Ronald J Williams and David Zipser. A learning algorithm for continually running fully recurrent neural networks. Neural computation, 1(2):270-280, 1989. Google Scholar
  58. Zhihao Xing and Shikui Tu. A graph neural network assisted monte carlo tree search approach to traveling salesman problem, 2020. URL: https://openreview.net/forum?id=Syg6fxrKDB.
  59. Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint, 2018. URL: http://arxiv.org/abs/1810.00826.
  60. Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? In International Conference on Learning Representations, 2019. Google Scholar
  61. Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. arXiv preprint, 2020. URL: http://arxiv.org/abs/2009.11848.
  62. Emre Yolcu and Barnabas Poczos. Learning local search heuristics for boolean satisfiability. In Advances in Neural Information Processing Systems, pages 7990-8001, 2019. Google Scholar
  63. Jiaxuan You, Bowen Liu, Zhitao Ying, Vijay Pande, and Jure Leskovec. Graph convolutional policy network for goal-directed molecular graph generation. In Advances in neural information processing systems, pages 6410-6421, 2018. Google Scholar
  64. Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint, 2016. URL: http://arxiv.org/abs/1611.03530.
  65. Yanqi Zhou, Sudip Roy, Amirali Abdolrashidi, Daniel Wong, Peter C Ma, Qiumin Xu, Ming Zhong, Hanxiao Liu, Anna Goldie, Azalia Mirhoseini, et al. Gdp: Generalized device placement for dataflow graphs. arXiv preprint, 2019. URL: http://arxiv.org/abs/1910.01578.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact