Learning Heuristics for the TSP by Policy Gradient

By Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, Louis-Martin Rousseau. Integration of AI and OR Techniques in Constraint Programming, 2018

381 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/4db4f1af1b94fbd5defa0fa0010fdc449dd1e96c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Deep Reinforcement Learning for Multiobjective Optimization (2019, methodology): “Moreover, the advanced Transformer model is employed to solve the routing problems and proves to be effective as well [21], [22].”
Differentiation of Blackbox Combinatorial Solvers (2019, background): “Some works have again targeted the TRAVELING-SALESMAN-PROBLEM [6, 9, 25] as well as other NP-Hard problems [27].”
Learning Improvement Heuristics for Solving Routing Problems (2019, methodology): “Based on elaborately designed deep structures such as recurrent neural network (RNN) [14], [15], [16] and attention mechanism [17], [18], [19], these methods are able to learn heuristics that can produce high-quality solutions.”
An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem (2019, methodology): “Deudon et al. [2018] showed that a hybrid approach of using 2OPT local search [Croes, 1958] on top of tours produced by the model improves performance.”
Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model (2024, methodology): “Kool et al. (2018) and Deudon et al. (2018), and their variants (Xin et al., 2020; Kwon et al., 2020; 2021) achieve superior performance utilizing the Transformer architecture (Vaswani et al., 2017).”
Large Language Models as Optimizers (2023, background): “…including heuristic algorithms and solvers (Rosenkrantz et al., 1977; Golden et al., 1980; Optimization et al., 2020; Applegate et al., 2006; Helsgaun, 2017), and approaches based on training deep neural networks (Kool et al., 2019; Deudon et al., 2018; Chen & Tian, 2019; Nazari et al., 2018).”
Combinatorial optimization and reasoning with graph neural networks (2021, background): “GNN Architectures Deudon et al. [2018], Nazari et al. [2018], and Kool et al. [2019] were perhaps the ﬁrst to use attention-based models for routing problems.”
Learning to Perform Local Rewriting for Combinatorial Optimization (2018, methodology): “Our approach is tested on multiple domains with extensive ablation studies, and could also be extended to other closely related tasks such as code optimization [41, 12], theorem proving [25, 30, 4, 24], text simplification [14, 37, 18], and classical combinatorial optimization problems beyond routin”
Attention, Learn to Solve Routing Problems! (2018, neutral): “Independently of our work, Deudon et al. (2018) presented a model for TSP using attention in the OR community.”
Reinforcement Learning for Combinatorial Optimization: A Survey (2020, methodology): “Parallel to [Deudon et al. , 2018], an approach to solve TSP, two variants of VRP (Capacitated VRP and Split Delivery VRP), Orienteering Problem (OP), Prize Collecting TSP (PCTSP) and Stochastic PCTSP (SPCTSP) has been proposed by [Kool et al. , 2018].”
Diffusion models as plug-and-play priors (2022, methodology): “Successful recent approaches [6, 21, 16, 17, 4] have used Transformer [41] and graph neural network [20] architectures.”
POMO: Policy Optimization with Multiple Optima for Reinforcement Learning (2020, neutral): “Classical heuristic operations as post-processing may also be applied on the solutions produced by the neural net [25, 22] to further enhance their quality.”