  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.
