Recurrent State Encoders for Efficient Neural Combinatorial Optimization

2025/09/05 by Tim Dernedde, Dernedde, Tim, Daniela Thyssens +3
Computer Science · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Neural Networks and Applications

paper · pdf · doi:10.48550/arxiv.2509.05084

openalex publication_date 2025/09/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The primary paradigm in Neural Combinatorial Optimization (NCO) are construction methods, where a neural network is trained to sequentially add one solution component at a time until a complete solution is constructed. We observe that the typical changes to the state between two steps are small, since usually only the node that gets added to the solution is removed from the state. An efficient model should be able to reuse computation done in prior steps. To that end, we propose to train a recurrent encoder that computes the state embeddings not only based on the state but also the embeddings of the step before. We show that the recurrent encoder can achieve equivalent or better performance than a non-recurrent encoder even if it consists of 3× fewer layers, thus significantly improving on latency. We demonstrate our findings on three different problems: the Traveling Salesman Problem (TSP), the Capacitated Vehicle Routing Problem (CVRP), and the Orienteering Problem (OP) and integrate the models into a large neighborhood search algorithm, to showcase the practical relevance of our findings.

Citations

• Neural Deconstruction Search for Vehicle Routing Problems
• RouteFinder: Towards Foundation Models for Vehicle Routing Problems
• GOAL: A Generalist Combinatorial Optimization Agent Learner
• The Road Less Scheduled
• Self-Improved Learning for Scalable Neural Combinatorial Optimization
• PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimization
• Recurrent Reinforcement Learning with Memoroids
• Hydra: Sequentially-Dependent Draft Heads for Medusa Decoding
• GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time
• Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt
• Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization
• Too Big, so Fail? -- Enabling Neural Construction Methods to Solve Large-Scale Routing Problems
• When Do Transformers Shine in RL? Decoupling Memory from Credit Assignment
• RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark
• Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem
• Unsupervised Learning for Solving the Travelling Salesman Problem
• DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization
• Accelerating Large Language Model Decoding with Speculative Sampling
• Human-Timescale Adaptation in an Open-Ended Task Space
• BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization
• Fast Inference from Transformers via Speculative Decoding
• Simulation-guided Beam Search for Neural Combinatorial Optimization
• Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization
• NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem
• Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer
• Learning to Delegate for Large-scale Vehicle Routing
• Matrix Encoding Networks for Neural Combinatorial Optimization
• Efficient Active Search for Combinatorial Optimization Problems
• Decision Transformer: Reinforcement Learning via Sequence Modeling
• Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problems
• POMO: Policy Optimization with Multiple Optima for Reinforcement Learning
• Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attention
• ReZero is All You Need: Fast Convergence at Large Depth
• A Deep Reinforcement Learning Algorithm Using Dynamic Attention Model for Vehicle Routing Problems
• Root Mean Square Layer Normalization
• An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
• Blockwise Parallel Decoding for Deep Autoregressive Models
• Learning Combinatorial Optimization Algorithms over Graphs
• Memory-based control with recurrent neural networks
• Deep Recurrent Q-Learning for Partially Observable MDPs

Related

• Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization
• Self-Improved Learning for Scalable Neural Combinatorial Optimization
• Neural Combinatorial Optimization with Reinforcement Learning
• Neural Solver Selection for Combinatorial Optimization
• Learning with Local Search MCMC Layers