Recurrent State Encoders for Efficient Neural Combinatorial Optimization
This work addresses computational bottlenecks in neural combinatorial optimization, offering a more efficient method for solving routing and scheduling problems, though it is incremental in nature.
The paper tackles the inefficiency of neural combinatorial optimization methods by proposing a recurrent encoder that reuses prior computations, achieving equivalent or better performance with 3x fewer layers and reduced latency on problems like TSP, CVRP, and OP.
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\times$ 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.