Source-linked AI summary
Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization
Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, Zhenkun Wang
TL;DR
Constructive NCO methods struggle to generalize from small training instances to large problems, limiting their practical usefulness. The paper proposes LEHD with dynamic decoding, data-efficient supervised training, and flexible reconstruction, achieving strong TSP and CVRP performance up to 1000 nodes. The method also generalizes to real-world benchmark instances, although current training is limited to supervised learning.
Problem
Constructive NCO methods perform poorly on large-scale problems because obtaining large-scale supervised labels is difficult and reinforcement learning faces sparse rewards and memory limitations.
Method
LEHD combines a light encoder and heavy decoder that dynamically capture relationships among partial solutions and available nodes, with partial-solution supervised training and flexible reconstruction.
Results
The purely learning-based method achieves state-of-the-art TSP and CVRP performance across scales up to 1000 and generalizes well to real-world TSPLib and CVRPLib problems.
Takeaways & Limitations
LEHD provides a generalizable constructive NCO approach that can be trained on small-scale instances and applied to substantially larger routing problems.
Takeaways & Limitations
The current LEHD model can only be properly trained by supervised learning, motivating future work on efficient reinforcement-learning training.
Abstract
from arXiv · showhide
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.
1 Introduction
Constructive NCO avoids handcrafted algorithm design but struggles to generalize from small training instances to large problems. LEHD addresses this gap with a light encoder, heavy decoder, data-efficient training, and flexible inference, achieving strong performance across scales.
- Classical combinatorial optimization algorithms require substantial expert knowledge and often incur long execution times on NP-hard problems.
- Large-scale constructive NCO is difficult because supervised learning lacks enough high-quality labels, while reinforcement learning faces sparse rewards and memory limits.
- LEHD dynamically captures relationships between the partial solution and available nodes, encouraging scale-independent features instead of static, one-shot embeddings.
- LEHD combines a data-efficient supervised training scheme with flexible solution construction that can improve quality under a customized inference budget.
- The purely learning-based method achieves state-of-the-art performance on TSP and CVRP across sizes up to 1000 and generalizes to real-world TSPLib and CVRPLib instances.
2 Related Work
Related work includes constructive, non-constructive, and learning-augmented NCO methods. Existing approaches often perform well at small scales but rely on specialized designs, heuristic operators, or advanced solvers for larger problems.
- Constructive NCO with Balanced Encoder-Decoder: Pointer Network introduced autoregressive constructive solving with a balanced recurrent encoder-decoder and later supported both supervised and reinforcement-learning training.
- Constructive NCO with Heavy Encoder and Light Decoder: Transformer-based Attention Models use Heavy Encoder and Light Decoder structures and achieve promising performance primarily on problems with no more than 100 nodes.
- Constructive NCO with Heavy Encoder and Light Decoder: Heavy-encoder constructive models generalize poorly to larger instances, while direct large-scale training is difficult or infeasible.
- Large-scale TSP methods use subproblem construction or segment reconstruction but depend heavily on TSP-specific human-designed mechanisms.
- Non-Constructive NCO Methods: Non-constructive heatmap methods guide beam search, Monte Carlo tree search, dynamic programming, or guided local search to obtain approximate solutions.
- Non-Constructive NCO Methods: Learning-augmented and improvement-based methods commonly rely on human-designed heuristic operators, advanced solvers, or iterative improvement procedures.
3 Model Architecture: Light Encoder and Heavy Decoder
LEHD reverses the usual allocation of model capacity: a one-layer encoder initializes node embeddings, while an L-layer decoder repeatedly updates relationships during autoregressive construction. This dynamic decoding is designed to improve large-scale generalization.
- LEHD uses a Light Encoder and Heavy Decoder structure to address large-scale generalization in constructive NCO.
- Encoder: The encoder linearly projects node features and processes the resulting embeddings with one attention layer.
- Decoder: The decoder computes selection probabilities from the context embedding and all available-node embeddings, then selects one node at each step.
- Decoder: For CVRP partial solutions, the construction examples impose the restriction that each partial solution must end at the depot.
- Decoder: Unlike HELD, whose static node embeddings do not update relationships during decoding, LEHD refines relationships at every step as the available-node set changes.
- Decoder: At each construction step, the decoder uses L attention layers to dynamically re-embed the starting node, destination node, and available nodes.
4 Learn to Construct Partial Solution
The paper trains LEHD with supervised learning on randomly sampled optimal partial solutions, reducing label demands while supporting robust node-by-node construction. During inference, the model greedily constructs complete solutions from a randomly selected destination and dynamically updated starting node.
- The heavy decoder makes reinforcement-learning training impractical because complete-solution generation requires substantial memory and computation, while rewards are sparse for large problems.
- Data augmentation can reduce the number of high-quality labels required for supervised NCO training.
- Optimal partial solutions are sampled from labeled tours with random sizes and directions, enriching training data through optimality invariance.Partial-solution lengths are sampled uniformly from [4, |V|].
- During supervised learning, LEHD predicts each available node's selection probability and uses cross-entropy loss against the partial-solution label.The starting node shifts after each selection, while the destination remains constant until no nodes remain available.
- At inference, LEHD greedily constructs the full solution step by step, beginning with a randomly selected destination and initial starting node.Selected nodes become the new starting node and are removed from the available set.
5 Random Re-Construct for Further Improvement
Greedy tours can contain suboptimal local segments, and the model's partial-solution training enables Random Re-Construct to iteratively rebuild them from varied directions and endpoints.
- Different starting and destination nodes can produce different solution quality because the constructive model favors particular local patterns.
- Random Re-Construct samples a partial solution from the initial solution and restructures it into a new partial solution.The mechanism mirrors partial-solution generation during training.
6 Experiment
Experiments evaluate LEHD against classical, constructive learning-based, and heatmap-based solvers on synthetic and real-world TSP/CVRP instances. LEHD generalizes from small-scale training to large-scale problems, with RRC improving solution quality under larger inference budgets.
- Experimental setup: Experiments compare LEHD with classical, constructive NCO, and heatmap-based solvers on TSP and CVRP across sizes and distributions.Reported metrics are optimality gap and inference time; CPU and GPU inference times are not directly comparable.
- Uniformly distributed instances: With 300 RRC iterations, LEHD outperforms most learning-based CVRP methods across tested sizes, while EAS and SGBS face larger-instance performance or runtime limitations.EAS remains stronger on CVRP100 but requires much longer inference time, and no reasonable-budget EAS result is obtained for CVRP1000.
- Uniformly distributed instances: LEHD outperforms LKH3 on CVRP100–CVRP500 with 500 RRC iterations and reaches an around 1% gap to LKH3 on CVRP1000 with 1000 iterations.The authors identify this as the first purely learning-based NCO method known to outperform LKH3 on CVRP200 and CVRP500.
- Real-world instances: On real-world TSPLib and CVRPLib instances, LEHD significantly outperforms POMO and BQ with 1000 RRC iterations, demonstrating robust generalization.The reported TSPLib instances contain fewer than 5000 nodes, while the CVRPLib set excludes additional constraints such as time windows.
- Ablation study: Under the same supervised-learning training, POMO performs well on TSP100 but poorly on larger-scale problems, whereas LEHD retains promising generalization.The comparison attributes the difference to the heavy decoder structure rather than supervised learning itself.
- Ablation study: LEHD is more suitable for supervised than reinforcement-learning training because the heavy decoder makes RL computationally expensive and slow to converge.The RL method with the POMO strategy fails to converge within a reasonable time, so the comparison uses TSP50 under equal computational budgets.
7 Conclusion, Limitation, and Future Work
LEHD provides a generalizable constructive NCO model with strong performance across synthetic and real-world instances, but currently requires supervised learning for proper training.
- Conclusion: LEHD is proposed as a generalizable constructive NCO model with strong and robust generalization ability.The model is evaluated on synthetic and real-world instances.
- Conclusion: The model achieves promising performance on both synthetic and real-world instances through extensive experimental comparisons.
- Limitation and Future Work: LEHD currently can only be properly trained by supervised learning.Future work includes efficient reinforcement-learning training and more efficient partial solution reconstruction.
A Ablation Study of Normalization
Normalization affects LEHD and POMO differently: removing attention-layer normalization benefits LEHD, while normalization choices have little effect on POMO.
- LEHD: Removing normalization from LEHD’s attention layer significantly outperforms batch normalization and instance normalization.The comparison uses three LEHD models trained with the same scheme and budget.
- POMO: Different normalization types have little effect on POMO under the same reinforcement-learning method, strategy, and training budget.The comparison uses batch normalization, instance normalization, and no normalization.
- Interpretation: Removing attention-layer normalization is not the critical factor behind LEHD’s strong generalization ability.LEHD with batch normalization still significantly outperforms POMO and SGBS in the cited comparison.
B.1 RRC can break the performance upper limit of the labeled solution
Random Re-Construct allows LEHD to improve solutions beyond the quality of supervised labels, while reinforcement-learning training remains computationally costly and slow to converge.
- RRC and labeled-solution quality: LEHD trained on suboptimal OR-Tools labels can outperform OR-Tools when combined with RRC at reasonable runtime.The OR-Tools labels have a 6.762% optimal gap, and additional training budget can further improve performance.
- RRC and labeled-solution quality: RRC is important and effective for improving the performance of the proposed LEHD method.
- RL training: LEHD can be trained by reinforcement learning without labeled data and generalize from TSP20 to TSP100 with RRC.The RL-trained model achieves a nearly optimal solution on TSP20, while RRC provides reasonably good generalization on TSP100.
- RL training: Pure reinforcement-learning training for LEHD has high computational cost and slow convergence speed.
B.3 An efficient self-improved training method for LEHD without any labeled solution
LEHD can be self-improved without pre-existing labeled solutions by combining limited reinforcement learning, RRC-generated labels, and subsequent supervised learning.
- Training method: An efficient self-improved training method combines reinforcement learning, LEHD+RRC solution generation, and supervised learning on those generated solutions.The three steps are applied sequentially without requiring already labeled solutions.
- Training method: The TSP self-improved training process uses 40 RL epochs and 185 supervised-learning epochs, costing 2.7 days in total.LEHD+RRC generates labels for 200,000 TSP100 instances, without external solvers.
- Results: LEHD+RRC retains good generalization on TSP instances with up to 1,000 nodes and can outperform supervised-learning BQ with bs16, especially at large scales.More computational budget can further improve LEHD performance.
- Conclusion: LEHD can be efficiently trained without already labeled nearly optimal solutions, supporting extension to practical CO problems where optimal solutions are hard to obtain.
C Implementation Details for TSP
TSP instances use randomly sampled 2D coordinates, while LEHD reduces decoder computation by excluding irrelevant nodes and computes selection probabilities after decoder attention processing.
- TSP instances contain n nodes whose 2D coordinates are sampled uniformly from the unit square.
- At each construction step, the decoder input contains only the starting node, destination node, and available node embeddings.This removes irrelevant-node computations while serving the same purpose as masking them.
- After L attention layers, each non-starting or destination embedding is linearly projected to a scalar before softmax produces the node-selection probabilities.
D Implementation Details for CVRP
CVRP solutions encode depot-based subtours through binary reachability indicators, while the decoder incorporates changing capacity and predicts two actions per customer. Experiments evaluate large real-world benchmark instances, including examples with 2392 and 1000 nodes.
- D.1 Problem Setup: CVRP has n customer nodes plus one depot, and minimizes total subtour distance subject to each route’s capacity constraint D.
- D.1 Problem Setup: A feasible CVRP solution assigns each node a binary value indicating whether it is reached via the depot or another customer node.This notation avoids alignment problems caused by solutions with different numbers of subtours.
- D.2 Implementation details: CVRP node features combine 2D coordinates with demand, while depot demand is set to 0 and vehicle capacity is normalized to 1.
- D.2 Implementation details: The decoder adds dynamically changing remaining capacity to the starting and destination embeddings and excludes irrelevant node embeddings.
- D.2 Implementation details: Each customer-node embedding is projected to two actions—reached via the depot or another customer—before flattening and softmax computation.
- Experiments: The benchmark evaluation covers TSPLib instances up to 4461 nodes and unconstrained 2D Euclidean CVRPLib instances; figures show 2392-node TSP and 1000-node CVRP examples.Panels compare optimal solutions with solutions generated by POMO, BQ, and LEHD.