Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization
This addresses scalability issues for real-world applications of NCO, though it is incremental in improving generalization over existing methods.
The paper tackles the challenge of neural combinatorial optimization (NCO) methods failing to scale to large problem instances, proposing a Light Encoder and Heavy Decoder (LEHD) model that generalizes to solve Travelling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) with up to 1000 nodes, achieving nearly optimal solutions.
Neural combinatorial optimization (NCO) is a promising learning-based approach for solving challenging combinatorial optimization problems without specialized algorithm design by experts. However, most constructive NCO methods cannot solve problems with large-scale instance sizes, which significantly diminishes their usefulness for real-world applications. In this work, we propose a novel Light Encoder and Heavy Decoder (LEHD) model with a strong generalization ability to address this critical issue. The LEHD model can learn to dynamically capture the relationships between all available nodes of varying sizes, which is beneficial for model generalization to problems of various scales. Moreover, we develop a data-efficient training scheme and a flexible solution construction mechanism for the proposed LEHD model. By training on small-scale problem instances, the LEHD model can generate nearly optimal solutions for the Travelling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP) with up to 1000 nodes, and also generalizes well to solve real-world TSPLib and CVRPLib problems. These results confirm our proposed LEHD model can significantly improve the state-of-the-art performance for constructive NCO. The code is available at https://github.com/CIAM-Group/NCO_code/tree/main/single_objective/LEHD.