Recurrent State Encoders for Efficient Neural Combinatorial Optimization

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.

Machine Learning (cs.LG)

arXiv:2509.05084 [cs.LG]

(or arXiv:2509.05084v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2509.05084 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.