Recurrent State Encoders for Efficient Neural Combinatorial Optimization
cs.LG
Submitted: 2025-09-05
Updated: 2026-09-01
Comments: A version of this work was accepted at ECML PKDD 2026, 27 pages, 8 figures
Code: https://github.com/TimD3/Recurrent-NCO
License: http://creativecommons.org/licenses/by/4.0/
The gist: The primary paradigm in Neural Combinatorial Optimization (NCO) consists of construction methods, where a neural network is trained to sequentially add one solution component at a time until a
Terminology
Abstract
The primary paradigm in Neural Combinatorial Optimization (NCO) consists of construction methods, where a neural network is trained to sequentially add one solution component at a time until a complete solution is formed. We observe that the typical changes to the state between two steps are small, since usually only the node added to the solution is removed from the state. An efficient model should be able to reuse computation from prior steps. To that end, we propose a recurrent encoder that computes state embeddings based not only on the current state but also on embeddings from the previous state. We show that this recurrent encoder can achieve equivalent or better performance than a non-recurrent encoder even with 3 times fewer layers, thus significantly improving 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.
Sources
- RouteFinder: Towards Foundation Models for Vehicle Routing Problems
- Accelerating Large Language Model Decoding with Speculative Sampling
- Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attention
- Too Big, so Fail? -- Enabling Neural Construction Methods to Solve Large-Scale Routing Problems
- Deep Recurrent Q-Learning for Partially Observable MDPs
- Memory-based control with recurrent neural networks
- An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
- Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: Local-Consistency Optimisation for Bayesian Neural Networks
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks