{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,17]],"date-time":"2025-11-17T14:29:56Z","timestamp":1763389796721,"version":"3.41.0"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,7,23]],"date-time":"2024-07-23T00:00:00Z","timestamp":1721692800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Evol. Learn. Optim."],"published-print":{"date-parts":[[2024,9,30]]},"abstract":"<jats:p>Neural Combinatorial Optimization has emerged as a new paradigm in the optimization area. It attempts to solve optimization problems by means of neural networks and reinforcement learning. In the past few years, due to their novelty and presumably good performance, many research papers have been published introducing new neural architectures for a variety of combinatorial problems. However, the incorporation of such models in the conventional optimization portfolio raises many questions related to their performance compared to other existing methods, such as exact algorithms, heuristics, or metaheuristics. This article aims to present a critical view of these new proposals, discussing their benefits and drawbacks with respect to the tools and algorithms already present in the optimization field. For this purpose, a comprehensive study is carried out to analyze the fundamental aspects of such methods, including performance, computational cost, transferability, and reusability of the trained model. Moreover, this discussion is accompanied by the design and validation of a new neural combinatorial optimization algorithm on two well-known combinatorial problems: the Linear Ordering Problem and the Permutation Flowshop Scheduling Problem. Finally, new directions for future work in the area of Neural Combinatorial Optimization algorithms are suggested.<\/jats:p>","DOI":"10.1145\/3647644","type":"journal-article","created":{"date-parts":[[2024,2,9]],"date-time":"2024-02-09T11:54:12Z","timestamp":1707479652000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Applicability of Neural Combinatorial Optimization: A Critical View"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7243-6116","authenticated-orcid":false,"given":"Andoni","family":"I. Garmendia","sequence":"first","affiliation":[{"name":"University of the Basque Country UPV\/EHU, Donostia-San Sebastian, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7120-6338","authenticated-orcid":false,"given":"Josu","family":"Ceberio","sequence":"additional","affiliation":[{"name":"University of the Basque Country UPV\/EHU, Donostia-San Sebastian, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7271-1931","authenticated-orcid":false,"given":"Alexander","family":"Mendiburu","sequence":"additional","affiliation":[{"name":"University of the Basque Country UPV\/EHU, Donostia-San Sebastian, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,7,23]]},"reference":[{"key":"e_1_3_3_2_1","unstructured":"Hans Achatz Peter Kleinschmidt and J. Lambsdorff. 2006. Der corruption perceptions index und das linear ordering problem. ORNews 26 (2006) 10\u201312."},{"key":"e_1_3_3_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-008-0001-1"},{"key":"e_1_3_3_4_1","doi-asserted-by":"publisher","DOI":"10.3934\/fods.2021002"},{"key":"e_1_3_3_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11081-021-09650-y"},{"key":"e_1_3_3_6_1","unstructured":"David Applegate Ribert Bixby Vasek Chvatal and William Cook. 2006. Concorde tsp solver. http:\/\/www.tsp.gatech.edu\/concorde"},{"key":"e_1_3_3_7_1","unstructured":"O Becker. 1967. Das helmst\u00e4dtersche reihenfolgeproblem\u2014die effizienz verschiedener n\u00e4herungsverfahren. In Computer Uses in the Social Sciences Berichteiner Working Conference."},{"key":"e_1_3_3_8_1","article-title":"Neural combinatorial optimization with reinforcement learning","author":"Bello Irwan","year":"2016","unstructured":"Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, and Samy Bengio. 2016. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.09940 (2016).","journal-title":"arXiv preprint arXiv:1611.09940"},{"key":"e_1_3_3_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2020.07.063"},{"key":"e_1_3_3_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/937503.937505"},{"key":"e_1_3_3_11_1","article-title":"On the linear ordering problem and the rankability of data","author":"Cameron Thomas R.","year":"2021","unstructured":"Thomas R. Cameron, Sebastian Charmot, and Jonad Pulaj. 2021. On the linear ordering problem and the rankability of data. arXiv preprint arXiv:2104.05816 (2021).","journal-title":"arXiv preprint arXiv:2104.05816"},{"key":"e_1_3_3_12_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1012793906010"},{"key":"e_1_3_3_13_1","article-title":"Combinatorial optimization and reasoning with graph neural networks","author":"Cappart Quentin","year":"2021","unstructured":"Quentin Cappart, Didier Ch\u00e9telat, Elias Khalil, Andrea Lodi, Christopher Morris, and Petar Veli\u010dkovi\u0107. 2021a. Combinatorial optimization and reasoning with graph neural networks. arXiv preprint arXiv:2102.09544 (2021).","journal-title":"arXiv preprint arXiv:2102.09544"},{"key":"e_1_3_3_14_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i5.16484"},{"key":"e_1_3_3_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2014.09.041"},{"key":"e_1_3_3_16_1","article-title":"Learning to perform local rewriting for combinatorial optimization","volume":"32","author":"Chen Xinyun","year":"2019","unstructured":"Xinyun Chen and Yuandong Tian. 2019. Learning to perform local rewriting for combinatorial optimization. Adv. Neural Inf. Process. Syst. 32 (2019).","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"e_1_3_3_17_1","article-title":"On the properties of neural machine translation: Encoder-decoder approaches","author":"Cho Kyunghyun","year":"2014","unstructured":"Kyunghyun Cho, Bart Van Merri\u00ebnboer, Dzmitry Bahdanau, and Yoshua Bengio. 2014. On the properties of neural machine translation: Encoder-decoder approaches. arXiv preprint arXiv:1409.1259 (2014).","journal-title":"arXiv preprint arXiv:1409.1259"},{"key":"e_1_3_3_18_1","doi-asserted-by":"crossref","unstructured":"Nicos Christofides. 1976. The vehicle routing problem. Revue fran\u00e7aise d\u2019automatique informatique. Recherche op\u00e9rationnelle 10 V1 (1976) 55\u201370.","DOI":"10.1051\/ro\/197610V100551"},{"key":"e_1_3_3_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-93031-2_12"},{"key":"e_1_3_3_20_1","unstructured":"Michael R. Garey and David S. Johnson. 1979. Computers and intractability. The Journal of Symbolic Logic (1979)."},{"key":"e_1_3_3_21_1","article-title":"Neural improvement heuristics for preference ranking","author":"Garmendia Andoni I.","year":"2022","unstructured":"Andoni I. Garmendia, Josu Ceberio, and Alexander Mendiburu. 2022. Neural improvement heuristics for preference ranking. arXiv preprint arXiv:2206.00383 (2022).","journal-title":"arXiv preprint arXiv:2206.00383"},{"key":"e_1_3_3_22_1","article-title":"Exact combinatorial optimization with graph convolutional neural networks","volume":"32","author":"Gasse Maxime","year":"2019","unstructured":"Maxime Gasse, Didier Ch\u00e9telat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. 2019. Exact combinatorial optimization with graph convolutional neural networks. Adv. Neural Inf. Process. Syst. 32 (2019).","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"e_1_3_3_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3422622"},{"volume-title":"Or-tools, Google Optimization Tools","year":"2016","key":"e_1_3_3_24_1","unstructured":"Google. 2016. Or-tools, Google Optimization Tools. Retrieved from https:\/\/developers.google.com\/optimization\/routing"},{"key":"e_1_3_3_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02932410"},{"key":"e_1_3_3_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2005.02.001"},{"key":"e_1_3_3_27_1","article-title":"Gaussian error linear units (GELUS)","author":"Hendrycks Dan","year":"2016","unstructured":"Dan Hendrycks and Kevin Gimpel. 2016. Gaussian error linear units (GELUS). arXiv preprint arXiv:1606.08415 (2016).","journal-title":"arXiv preprint arXiv:1606.08415"},{"key":"e_1_3_3_28_1","first-page":"6840","article-title":"Denoising diffusion probabilistic models","volume":"33","author":"Ho Jonathan","year":"2020","unstructured":"Jonathan Ho, Ajay Jain, and Pieter Abbeel. 2020. Denoising diffusion probabilistic models. Adv. Neural Inf. Process. Syst. 33 (2020), 6840\u20136851.","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"e_1_3_3_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00339943"},{"key":"e_1_3_3_30_1","article-title":"Learning TSP requires rethinking generalization","author":"Joshi Chaitanya K.","year":"2020","unstructured":"Chaitanya K. Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. 2020. Learning TSP requires rethinking generalization. arXiv preprint arXiv:2006.07054 (2020).","journal-title":"arXiv preprint arXiv:2006.07054"},{"key":"e_1_3_3_31_1","doi-asserted-by":"crossref","unstructured":"John Jumper Richard Evans Alexander Pritzel Tim Green Michael Figurnov Olaf Ronneberger Kathryn Tunyasuvunakool Russ Bates Augustin \u017d\u00eddek Anna Potapenko Alex Bridgland Clemens Meyer Simon A. A. Kohl Andrew J. Ballard Andrew Cowie Bernardino Romera-Paredes Stanislav Nikolov Rishub Jain Jonas Adler Trevor Back Stig Petersen David Reiman Ellen Clancy Michal Zielinski Martin Steinegger Michalina Pacholska Tamas Berghammer Sebastian Bodenstein David Silver Oriol Vinyals Andrew W. Senior Koray Kavukcuoglu Pushmeet Kohli and Demis Hassabis. 2021. Highly accurate protein structure prediction with AlphaFold. Nature 596 7873 (2021) 583\u2013589.","DOI":"10.1038\/s41586-021-03819-2"},{"key":"e_1_3_3_32_1","article-title":"Learning combinatorial optimization algorithms over graphs","volume":"30","author":"Khalil Elias","year":"2017","unstructured":"Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. 2017a. Learning combinatorial optimization algorithms over graphs. Adv. Neural Inf. Process. Syst. 30 (2017).","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"e_1_3_3_33_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2017\/92"},{"key":"e_1_3_3_34_1","article-title":"Attention, learn to solve routing problems!","author":"Kool Wouter","year":"2018","unstructured":"Wouter Kool, Herke Van Hoof, and Max Welling. 2018. Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08475 (2018).","journal-title":"arXiv preprint arXiv:1803.08475"},{"key":"e_1_3_3_35_1","first-page":"21188","article-title":"POMO: Policy optimization with multiple optima for reinforcement learning","volume":"33","author":"Kwon Yeong-Dae","year":"2020","unstructured":"Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. 2020. POMO: Policy optimization with multiple optima for reinforcement learning. Adv. Neural Inf. Process. Syst. 33 (2020), 21188\u201321198.","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"e_1_3_3_36_1","first-page":"5138","article-title":"Matrix encoding networks for neural combinatorial optimization","volume":"34","author":"Kwon Yeong-Dae","year":"2021","unstructured":"Yeong-Dae Kwon, Jinho Choo, Iljoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. 2021. Matrix encoding networks for neural combinatorial optimization. Adv. Neural Inf. Process. Syst. 34 (2021), 5138\u20135149.","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"e_1_3_3_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0548(98)00104-X"},{"key":"e_1_3_3_38_1","volume-title":"Input-output Economics","author":"Leontief Wassily","year":"1986","unstructured":"Wassily Leontief. 1986. Input-output Economics. Oxford University Press."},{"key":"e_1_3_3_39_1","volume-title":"Anytime Tree Search for Combinatorial Optimization","author":"Libralesso Luc","year":"2020","unstructured":"Luc Libralesso. 2020. Anytime Tree Search for Combinatorial Optimization. Ph. D. Dissertation. Universit\u00e9 Grenoble Alpes."},{"key":"e_1_3_3_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(00)00137-5"},{"key":"e_1_3_3_41_1","article-title":"Decoupled weight decay regularization","author":"Loshchilov Ilya","year":"2017","unstructured":"Ilya Loshchilov and Frank Hutter. 2017. Decoupled weight decay regularization. arXiv preprint arXiv:1711.05101 (2017).","journal-title":"arXiv preprint arXiv:1711.05101"},{"key":"e_1_3_3_42_1","article-title":"A diversity-aware memetic algorithm for the linear ordering problem","author":"Lugo L\u00e1zaro","year":"2021","unstructured":"L\u00e1zaro Lugo, Carlos Segura, and Gara Miranda. 2021. A diversity-aware memetic algorithm for the linear ordering problem. arXiv preprint arXiv:2106.02696 (2021).","journal-title":"arXiv preprint arXiv:2106.02696"},{"key":"e_1_3_3_43_1","article-title":"Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning","author":"Ma Qiang","year":"2019","unstructured":"Qiang Ma, Suwen Ge, Danyang He, Darshan Thaker, and Iddo Drori. 2019. Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning. arXiv preprint arXiv:1911.04936 (2019).","journal-title":"arXiv preprint arXiv:1911.04936"},{"key":"e_1_3_3_44_1","article-title":"Learning heuristics over large graphs via deep reinforcement learning","author":"Manchanda Sahil","year":"2019","unstructured":"Sahil Manchanda, Akash Mittal, Anuj Dhawan, Sourav Medya, Sayan Ranu, and Ambuj Singh. 2019. Learning heuristics over large graphs via deep reinforcement learning. arXiv preprint arXiv:1903.03332 (2019).","journal-title":"arXiv preprint arXiv:1903.03332"},{"key":"e_1_3_3_45_1","unstructured":"Vinod Nair Sergey Bartunov Felix Gimeno Ingrid Von Glehn Pawel Lichocki Ivan Lobov Brendan O\u2019Donoghue Nicolas Sonnerat Christian Tjandraatmadja Pengming Wang Ravichandra Addanki Tharindi Hapuarachchi Thomas Keck James Keeling Pushmeet Kohli Ira Ktena Yujia Li Oriol Vinyals and Yori Zwols. 2020. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13349 (2020)."},{"key":"e_1_3_3_46_1","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"Papadimitriou Christos H.","year":"1998","unstructured":"Christos H. Papadimitriou and Kenneth Steiglitz. 1998. Combinatorial Optimization: Algorithms and Complexity. Courier Corporation."},{"key":"e_1_3_3_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/525"},{"key":"e_1_3_3_48_1","unstructured":"Gerhard Reinelt. 2002. Linear ordering library (LOLIB). Retrieved October 10 2023 from http:\/\/comopt.ifi.uni-heidelberg.de\/software\/LOLIB\/"},{"key":"e_1_3_3_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2017.131"},{"key":"e_1_3_3_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2015.2507785"},{"key":"e_1_3_3_51_1","doi-asserted-by":"crossref","unstructured":"Julian Schrittwieser Ioannis Antonoglou Thomas Hubert Karen Simonyan Laurent Sifre Simon Schmitt Arthur Guez Edward Lockhart Demis Hassabis Thore Graepel Timothy Lillicrap and David Silver. 2020. Mastering atari go chess and shogi by planning with a learned model. Nature 588 7839 (2020) 604\u2013609.","DOI":"10.1038\/s41586-020-03051-4"},{"key":"e_1_3_3_52_1","volume-title":"Reinforcement Learning: An Introduction","author":"Sutton Richard S.","year":"2018","unstructured":"Richard S. Sutton and Andrew G. Barto. 2018. Reinforcement Learning: An Introduction. MIT Press."},{"key":"e_1_3_3_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(93)90182-M"},{"key":"e_1_3_3_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3459664"},{"key":"e_1_3_3_55_1","doi-asserted-by":"publisher","DOI":"10.3115\/1699571.1699644"},{"key":"e_1_3_3_56_1","article-title":"Attention is all you need","volume":"30","author":"Vaswani Ashish","year":"2017","unstructured":"Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, \u0141ukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. Adv. Neural Inf. Process. Syst. 30 (2017).","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"e_1_3_3_57_1","article-title":"Pointer networks","volume":"28","author":"Vinyals Oriol","year":"2015","unstructured":"Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. 2015. Pointer networks. Adv. Neural Inf. Process. Syst. 28 (2015).","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"e_1_3_3_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00992696"},{"key":"e_1_3_3_59_1","doi-asserted-by":"crossref","unstructured":"Yaoxin Wu Wen Song Zhiguang Cao Jie Zhang and Andrew Lim. 2021. Learning improvement heuristics for solving routing problems. IEEE Transactions on Neural Networks and Learning Systems 33 9 (2021) 5057\u20135069.","DOI":"10.1109\/TNNLS.2021.3068828"},{"key":"e_1_3_3_60_1","first-page":"1","article-title":"Solving combinatorial optimization tasks by reinforcement learning: A general methodology applied to resource-constrained scheduling","volume":"1","author":"Zhang Wei","year":"2000","unstructured":"Wei Zhang and Thomas G. Dietterich. 2000. Solving combinatorial optimization tasks by reinforcement learning: A general methodology applied to resource-constrained scheduling. J. Artif. Intell. Res. 1 (2000), 1\u201338.","journal-title":"J. Artif. Intell. Res."}],"container-title":["ACM Transactions on Evolutionary Learning and Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3647644","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3647644","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:38Z","timestamp":1750291418000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3647644"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,23]]},"references-count":59,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9,30]]}},"alternative-id":["10.1145\/3647644"],"URL":"https:\/\/doi.org\/10.1145\/3647644","relation":{},"ISSN":["2688-299X","2688-3007"],"issn-type":[{"type":"print","value":"2688-299X"},{"type":"electronic","value":"2688-3007"}],"subject":[],"published":{"date-parts":[[2024,7,23]]},"assertion":[{"value":"2022-10-26","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-02-03","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-07-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}