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.
Paper
Similar papers
Peer review
Summary
This paper proposes a neural network model in the form of a Light Encoder Heavy Decoder, as well as its training method for solving combinatorial optimization problems. In addition, this paper suggests an RPC method based on updating partial solutions as a way to improve solutions during the inference process. These methods show promising results in experiments with large scale Travelling Salesman Problems (TSP) and Capacitated Vehicle Routing Problems (CVRP). The approach of learning the state of various node sizes through a heavy decoder is promising. However, using supervised learning as a training method and optaining an optimal solution for training with an existing algorithm has limitations in general use.
Strengths
**S1.** The architecture of Heavy Decoder Model to yield optimal outputs across a range of node sizes **S2.** Showing promising experimental results on large-scale TSP and CVRP instances **S3.** Well-written and easy to read
Weaknesses
**W1.** Weak novelty of training method and RPC **W2.** If there is no optimal solution, or if there is no existing high-performance algorithm such as Concorde/HGS, learning by the method of this paper is not possible, but many practical CO problems cannot secure an optimal solution. Therefore, for most practical CO problems where the optimal solution cannot be known, it is difficult to apply the method in this paper. **W3.** The optimization degree of the algorithm that outputs the optimal solution (or near optimal solution) of the training data seems to be the upper limit of the optimization degree of LEHD. **W4.** The number of instances used in the node experiments of 200, 500, and 1000 is too small at 128. It is expected that the experimental values may change as the 128 samples are altered. On the other hand, previous studies [20,8,12] mainly used 1k instances in experiments with 200 or more nodes. experiments.
Questions
**Q1.** From the experimental results, the inference of the LEHD greedy model was performed faster than the POMO using the HELD model. In the case of TSP 1000, the encoder performs 1 operation and the decoder 1000 operations, so I don't understand how LEHD can be faster than HELD(POMO). If the reason why HELD (POMO) is slower is because of 'augx8', I would like to know the difference in inference time between the HELD(POMO/AM) without augx8 and LEHD. **Q2.** How to select partial solution to perform update in RPC? **Q3.** In the CVRP results in Table 1, HGS performed better than LKH3 and was used as the optimal solution for LEHD learning, so it seems better to organize the table with HGS as GAP 0. **Q4.** Publication information of reference [56] is missed.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
N/A
Summary
The paper proposes a learning-based approach called the Light Encoder and Heavy Decoder (LEHD) to solve combinatorial optimization (CO) problems. The proposed method learns less from the static graphs (via a light encoder), and pays more attention to dynamically capturing the relationships between all available nodes of varying sizes (via a heavy decoder), which allows for better generalization to various scales. The devised paradigm naturally divides the problem into sub-problems, and the pipeline is designed to first predict the general route greedily, followed by refining the route using its local construction policy. Experimental evaluations demonstrate the state-of-the-art performance of the proposed method, particularly in terms of its generalization capability.
Strengths
1.The methodology design is insightful and logical. The division into the shortest Hamilton path problem is meaningful for addressing routing problems such as the Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP), as it facilitates local improvement naturally. 2.The empirical results are promising especially for the generalization ability. 3.The paper is well-structured and easy to follow.
Weaknesses
1.The RCC algorithm bears resemblance to methods that employ a divide-and-conquer strategy, such as [1] and [2]. It is recommended for the authors to explore and discuss this line of research. [1] Generalize Learned Heuristics to Solve Large-scale Vehicle Routing Problems in Real-time. ICLR 2023. [2] Learning to Delegate for Large-scale Vehicle Routing. NeurIPS 2021. 2.The RCC algorithm does not learn to select regions for local improvement, instead randomly enforcing the local policy, which hampers its efficiency. Minor: 1.Line 166: refind -> refine. 2.Line 224: construction-base -> construction-based.
Questions
1.Why is LKH not included in Table 1? LKH is expected able to achieve optimality for the problem scales in Table 1, but the runtime comparison is essential and should not be missed. Please also see the discussion of weaknesses.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
4 excellent
Presentation
3 good
Contribution
3 good
Limitations
Please see above.
Summary
The paper focuses on a class of NP-hard combinatorial optimization problems called Vehicle Routing Problems (VRP) which is of wide practical interest. This paper proposes a novel Light Encoder and Heavy Decoder (LEHD) model for enabling neural construction methods well handling large-scale routing problems. It incorporates a data-efficient training scheme in the supervised manner and a flexible solution construction mechanism for further enhancing the performance. By training on small-scale problem instances, the LEHD model achieves robust and promising performance on problems with much larger sizes, especially for TSP and CVRP.
Strengths
1. The motivation and training process is clear and easy to read. 2. LEHD could dynamically capture the relationships between all available nodes of varying sizes, which enables the model to generalize well to problems of various scales. 3. Sufficient experiments are conducted to prove the effectiveness and the generalization of LEHD, which has promising results on large-scale TSP and CVRP.
Weaknesses
1. There is some confusion about the training time, since training time is also important. 2. The proposed method might be limited in simple VRPs, since obtaining optimal labeled solutions for more complex VRP variants is hard. 3. The LEHD does not show much superiority to HGS. 4. The presentation of this paper needs to be further improved. Some details are not clearly described and there are some typos.
Questions
1. What is "w" in the experiments? Does it also a random number? 2. For generalizing LEHD to unseen large-scale problems, how does LEHD construct the whole solution? 3. Why not apply "sampling" strategy on POMO with the same iterations of RRC? For example, POMO (sampling) with 100 trials should be compared to LEHD RRC 100. 4. Are the solutions obtained by HGS optimal solutions? To my knowledge, HGS is a meta-heuristic method.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
2 fair
Contribution
3 good
Limitations
Yes
Summary
In summary, this work proposed a new solution that generalizes well on large-scale problem instances for routing problems. A data-efficient training scheme and solution construction mechanism are further proposed for efficient training. Experiments verify the effectiveness of the proposed method, and an impressive gap is observed between the proposed method and the existing works.
Strengths
1. The presentation of this manuscript was great, and I enjoy reading this paper. 2. This work proposed a simple yet effective strategy to solve routing problems, which is able to generate nearly optimal solutions for large-scale settings. It also generalized well on real-world datasets. In addition, the effectiveness of such a design is well studied in Section 6.2. I believe this work would be very insightful for the community.
Weaknesses
1. The training details need more illustration. How did you train on small-scale problem instances? Is the "small-scale problem instances" means the "argument data" you generated?
Questions
1. How did you train on small-scale problem instances? Is the "small-scale problem instances" means the "argument data" you generated? 2. There are some existing works that aim to tackle large-scale TSP instances, for example, [40] and [7] mentioned in your paper. Why no comparison with these works?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
N.A.
lets followup author response
Hi all, Thanks for serving as the reviewers for this submission. As the authors have already provided their responses. Now let's start further discussion. Here is a to-do list: (1) Please acknowledge the authors when you finish reading their responses. (2) Please indicate whether you have any further questions for the authors such that they can continue to response. (3) Please indicate whether you are willing to change the ratings. best, The AC
I will increase the rating of this paper.
My main concerns were W2(Requirement of Optimal Solution) and W3(Performance Upper Limit), I highly appreciate the authors showcasing the potential for addressing these issues through appropriate experiments and additional discussions in General Response C2. I will increase the rating of this paper by 1. I have no further questions. Thank you for the detailed responses and additional experiments.
Thank you very much for increasing your rating
Thank you very much for increasing your rating to 5, and we are glad to know you highly appreciate our response with appropriate experiments and discussions to address your main concerns. We would like to know if there is any concern left that makes it hard for you to further increase the rating. We are more than happy to further address any potential concerns.
Dear authors, To elaborate further, I believe that a model with the LEHD structure can, of course, be trained using RL. However, when training LEHD with RL, I anticipate there might be challenges compared to when using HELD structure. In the case of the CO problem, there's one Encoder operation followed by multiple Decoder operations (typically over 100 times). And RL generally requires more iterations than SL during training, so a Heavy Decoder structure would likely demand a significantly high computational load for training. Conducting specific experiments on this matter and proposing solutions if issues arise would make this a remarkable study. Additionally, a comparative analysis of accuracy over training time with existing models (like AM/POMO and their subsequent studies) would also be beneficial. I believe the motivation and advantages of LEHD have been well explained in this paper. While I acknowledge that the authors have demonstrated the potential to address my primary concerns, W2 and W3, in their rebuttal, fundamentally, this paper employs a learning method based on SL. Therefore, I believe a detailed discussion on RL-based training for the LEHD structure model might fall outside the scope of this submitted paper. This is the reason I refrained from asking further questions and limited my rating to 5 points. Nonetheless, I find the approach based on the Heavy Decoder for CO solver to be very impressive and intriguing.
Sincerely thank you for your valuable and constructive comments
Sincerely thank you for your valuable and constructive comments. We fully understand your concerns about the efficiency of RL training for LEHD, and we want to provide the following responses: **1. RL training is also extremely inefficient for the classical HELD model on large-scale problems, and it will not hurt our main contribution.** Although most existing constructive HELD models are trained with RL, the problem sizes these methods can properly handle for TSP/CVRP are typically up to 100 (e.g., AM/POMO and follow-up works such as sym-NCO). It could be extremely hard to use RL to train HELD models on problems with a larger size (e.g., 200), while its generalization performance to large-scale problems is very poor. Therefore, the ability to handle large-scale problems is a serious limitation of the popular HELD models. Our proposed LEHD model, even considering the original SL training, is already a crucial contribution for constructive NCO to handle large-scale problems. As shown in the below tables, our proposed RL+SI for LEHD training method is much more efficient than the RL training for classical constructive NCO on CVRP100, while it has significantly better generalization performance. We will carefully incorporate all the related discussions of RL training with more experimental analyses into our revised paper. We totally agree with you that efficient RL training for both HELD and LEHD models is a very important research topic, but we believe it will not hurt our key contribution for promising large-scale generalization in this work. Table A: Training time on CVRP (days) | Model | POMO | Sym-NCO | BQ | LEHD | LEHD-SI | |:---------------:|:----:|:-------:|:---:|:----:|:-------:| | Training method | RL | RL | SL | SL | RL+SI | | Time | 13.6 | 11.1 | 1.6 | 2.0 | 2.5 | Table B: Comparison of POMO, Sym-NCO, BQ and LEHD on CVRP. | | | CVRP100 | | CVRP200 | | CVRP500 | | CVRP1000 | | |------------------|---|:------------------:|:----:|:------------------:|:-----:|:------------------:|:----:|:------------------:|:----:| | HGS | | 0.00\% | 4.5h | 0.00\% | 11h | 0.00\% | 31h | 0.00\% | 41h | | POMO augx8 | | 1.23\% | 1m | 5.19\% | 0.7m | 22.96\% | 9.4m | 144.23\% | 1.3h | | Sym-NCO augx8 | | 1.45\% | 1.2m | 6.08\% | 0.8m | 17.61\% | 11m | 147.18\% | 1.6h | | BQ bs16 | | 1.15\% | 10m | 2.23\% | 5m | 4.98\% | 50m | 10.39\% | 5.5h | | LEHD-SI greedy | | 5.27\% | 0.5m | 5.49\% | 0.23m | 5.92\% | 2.2m | 9.23\% | 13m | | LEHD-SI RRC200 | | $\underline{1.12\\%}$ | 34m | $\underline{1.73\\%}$ | 13m | $\underline{2.85\\%}$ | 2.1h | $\underline{5.12\\%}$ | 12h | | LEHD greedy | | 4.17\% | 0.5m | 4.61\% | 0.23m | 5.21\% | 2.2m | 8.59\% | 13m | | LEHD RRC300 | | $\textbf{0.57\\%}$ | 52m | $\textbf{0.95\\%}$ | 19m | $\textbf{1.94\\%}$ | 3h | $\textbf{4.33\\%}$ | 18h | **2. The Contribution of RRC** Furthermore, we do hope that you could re-examine the novelty and contribution of RRC. Although the RRC design is straightforward, it plays a crucial role to achieve promising generalization performance, and is the key to tackle your main concern W3(Performance Upper Limit) and W2(Requirement of Optimal Solution). Indeed, according to the results in Table 1, RRC significantly outperforms all the widely-used (random sampling, beam search) and state-of-the-art advanced search methods (EAS [1], SGBS [2]) for NCO to tackle large-scale generalization. We believe RRC is also an important contribution to the community, since the search method itself is already an important research topic for NCO [1,2]. We really appreciate that you think our proposed Heavy Decoder for CO solver to be very impressive and intriguing. We sincerely hope our response can further address your concerns, and your rating is very important to our work. [1] Efficient Active Search for Combinatorial Optimization Problems. ICLR 2022. [2] Simulation-guided beam search for neural combinatorial optimization. NeurIPS 2022.
I appreciate the additional responses from the authors. My evaluation of the submitted paper remains a lukewarm accept rating of 5. Considering the submitted paper and the discussions so far, I do not see a need to adjust the scoring further. The final decision on the submitted paper will be determined by comprehensively considering the content of the paper, the reviewer's evaluation, rebuttal, and discussion. I believe the Area Chair will make an appropriate decision.
Thank you for your comments.
Thank you again for all your comments. We appreciate your time and effort in engaging with us in the author-reviewer discussion.
Thanks for the response.
Thanks for your time in the rebuttal. My concerns have been addressed, and I would keep my rating.
Thanks for the response.
My previous concerns are well addressed. Thanks for the detailed clarification and experimental results. I have one additional question, in Table 1, the POMO augx8 gets 40.57% on TSP1000 and 128.88% on CVRP1000, and I see in Table 4, LEHD with RL gets 46.441% on TSP1000. Given the 6.56% achieved by the RL training approach, is the additional gain between your method and POMO comes from the supervised training process rather than the heavy decoder design? It would be great to conduct a discussion of why the RL-based methods (e.g., POMO and LEHD model with RL) do not generalize well on large scaled problems in Section 6.1 or 6.2.
Thank you very much for your comment [1/2].
Thank you very much for your comment and glad to know your previous concerns are well addressed. We address your new question as follows. > **1. The poor generalization performances of LEHD-RL and POMO are caused by completely different reasons.** **LEHD-RL:** The poor performance of LEHD-RL comes from the extremely inefficient RL training for LEHD. Our original goal of Table 4 is to compare the RL v.s SL training for our proposed LEHD model. In this experiment, all methods are trained on TSP50 (rather than TSP100 in Table 1) with a limited training budget (2 days rather than 2 weeks for POMO in Table 1). According to the result, we find that LEHD-SL can reach a good training performance on TSP50 ($0.375\\%$) while LEHD-RL cannot converge and has a poor training performance on TSP50 ($5.372\\%$). The poor training performance of LEHD-RL directly leads to its poor large-scale generalization performance. Table A: Effect of RL and SL on training the LEHD model with 10K testing instances for TSP50/100 and 1K testing instances for TSP200/500/1000. | | TSP50 | TSP100 | TSP200 | TSP500 | TSP1000 | |--------------|:----------------:|:----------------:|:----------------:|:----------------:|:----------------:| | RL (2.2days) | 5.372\% | 7.891\% | 13.379\% | 25.685\% | 46.463\% | | RL (6.9days) | 2.576\% | 4.390\% | 9.398\% | 22.318\% | 40.911\% | | SL (2.2days) | $\textbf{0.375\%}$ | $\textbf{0.789\%}$ | $\textbf{1.502\%}$ | $\textbf{3.528\%}$ | $\textbf{6.623\%}$ | In the preliminary study of this project, we have tried to train LEHD-RL longer to check its performance, and the result is reported in the above table. With more computational budget (e.g., 6.9 days), LEHD-RL can obtain better training performance on TSP50 and hence also better generalization performance on large-scale problems. However, the RL training for LEHD still requires a much longer time to converge. This high computational cost for LEHD-RL is indeed expected since the heavy decoder needs to be called $n$ times at each step for training on each instance with size $n$. We will add this result and discussion on RL training into the revised paper, along with a novel self-improvement RL method to tackle this issue (see point 3 below). **POMO:** The poor performance of POMO on large-scale problems actually comes from its poor generalization ability. In Table 1, we train POMO with RL on TSP100 with a large computational budget (e.g., 2 weeks). POMO has a quite promising training performance on TSP100 (e.g., $0.134\\%$ with augx8) in Table 1, which means it is sufficiently trained on TSP100. However, its generalization performance dramatically decreases and obtains a $40.551\\%$ gap on TSP1000. This poor generalization performance of POMO (and other HELD models) has also been observed in many existing NCO works, and the supervised training process cannot overcome such a generalization gap (see next point). > **2. The heavy decoder design is crucial for the promising generalization performance.** To investigate the effect of model structure on the generalization performance, we also train POMO with SL on TSP100 and report the result in the table below. According to the results, POMO trained by SL can also reach a good training performance on TSP100 while it still performs poorly on large-scale problems. Therefore, the promising generalization performance of our proposed method does come from the heavy decoder structure rather than the SL training. Table B: POMO-SL v.s. LEHD-SL | | TSP100 | TSP200 | TSP500 | TSP1000 | |----------------|:----------------:|:----------------:|:-----------------:|:----------------:| | POMO aug×8 SL | **0.571\%** | 3.970\% | 20.418\% | 34.419\% | | LEHD greedy SL | 0.577\% | **0.859\%** | **1.560\%** | **3.168\%** | **Why the heavy decoder model is better for generalization:** As discussed in the main paper, the current HELD model aims to learn the embeddings of all nodes via a heavy encoder in one shot and then sequentially construct the solution with the static node embeddings via a light decoder. This one-shot embedding learning may incline the model to learn scale-related features to perform well on training instances, but hinder the model from capturing the necessary relations among a significantly larger number of nodes. In contrast, our proposed LEHD model learns to dynamically capture the relationships among the current partial solution and all the available nodes at each construction step via the heavy decoder. As the size of nodes varies with construction steps, the model tends to learn scale-independent features. Therefore, it could be less sensitive to the instance size and has much better generalization performance on large-scale problem instances.
Thank you very much for your comment [2/2].
> **3. The shortcomings of both SL/RL training for LEHD can be overcome by RL-SI.** As in the **General Response C2**, we have proposed a novel self-improved method with reinforcement learning (RL-SI) to overcome the crucial shortcoming for both SL (requirement of labeled optimal solution) and RL (high computational cost) training for LEHD. As shown in the below tables, our proposed RL-SI training for LEHD is much more efficient than the RL training for classical constructive models (e.g., POMO and Sym-NCO) on CVRP100, while it has significantly better generalization performance. Table C: Training time on CVRP100 (days). | Model | POMO | Sym-NCO | LEHD | LEHD-SI | |:---------------:|:----:|:-------:|:----:|:-------:| | Training method | RL | RL | SL | RL+SI | | Time | 13.6 | 11.1 | 2.0 | 2.5 | Table D: Comparison of POMO, Sym-NCO and LEHD on CVRP. | | | CVRP100 | | CVRP200 | | CVRP500 | | CVRP1000 | | |------------------|---|:------------------:|:----:|:------------------:|:-----:|:------------------:|:----:|:------------------:|:----:| | HGS | | 0.00\% | 4.5h | 0.00\% | 11h | 0.00\% | 31h | 0.00\% | 41h | | POMO augx8 | | 1.23\% | 1m | 5.19\% | 0.7m | 22.96\% | 9.4m | 144.23\% | 1.3h | | Sym-NCO augx8 | | 1.45\% | 1.2m | 6.08\% | 0.8m | 17.61\% | 11m | 147.18\% | 1.6h | | LEHD-SI greedy | | 5.27\% | 0.5m | 5.49\% | 0.23m | 5.92\% | 2.2m | 9.23\% | 13m | | LEHD-SI RRC200 | | $\underline{1.12\%}$ | 34m | $\underline{1.73\%}$ | 13m | $\underline{2.85\%}$ | 2.1h | $\underline{5.12\%}$ | 12h | | LEHD greedy | | 4.17\% | 0.5m | 4.61\% | 0.23m | 5.21\% | 2.2m | 8.59\% | 13m | | LEHD RRC300 | | **0.57\%** | 52m | **0.95\%** | 19m | **1.94\%** | 3h | **4.33\%** | 18h | All the above discussions will be carefully added to the revised paper. Our code and model will also be open-source upon publication.
Thanks for the prompt response, I would like to increase my rating to 7 in this case.
Thank you very much.
Thank you very much for your effort in reviewing our paper and engaging with us in the discussion. We are thrilled to know your concerns are all well addressed, and you have increased your rating to 7.
Thank you again for your time and effort in reviewing our work. Since there is only 1 day left to the discussion deadline, we could want to know whether all of your concerns have been properly addressed. We are more than happy to further address any remaining concerns or questions you might have.
Decision
Accept (poster)