Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization
Authors: Fu Luo
Xi Lin
Fei Liu
Qingfu Zhang
Zhenkun Wang
Venue: NeurIPS 2023 poster (2023)
Keywords: Neural Combinatorial Optimization
Generalization
Large scale problem
Heavy decoder

Abstract: 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.

Neural Combinatorial Optimization with Heavy
Decoder: Toward Large Scale Generalization
Fu Luo Xi Lin Fei Liu
Qingfu Zhang²
Zhenkun Wang
Southern University of Science and Technology
City University of Hong Kong
luof2023dmail www.llssssshhh..mm edu. en, fxi.lin, fliu36-c) @my cityu. edu.hk, zha.fu..hangcityycoo edu edu.kk, waugzhenkuuS@@maillcco
Abstract
Neural combinatorial optimization (NCO) is promising learning-baid -ased 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, propose novel Light Encoder and Hcavy Decoder (LEHD) model with strong generalization ability address this critical issue. The LEHD model can learn to dynamically capture the relationships between all available nodes of varying sizes, which is beneficial develop
for model generalization to problems of various scales. Moreover, 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 1000 nodes, and also generalizes well to solve real-world TSPLib and CVRPLib Li problems. These results confirm our proposed LEHD model can significantly im- prove the state-of- performance for constructive NCO. The code is available at wttp:///ghiiiccccco/c//ccCoooooo httpp///////OOoooo////////a/a/ao oitpaiinnngg_oiptttteeL/EEDD
Introduction
Combinatorial optimization (CO) holds significant practical value across various domains, such as vehicle routing (48), production planning [il]. and drug discovery [34). Due to the NP- WP-hardness and the presence numerous complex variants, solving CÓ problems remains an extremely challenging task [31] In the past few decades, many powerful algorithms have been proposed to tackle different CO problems, but they mainly suffer from two major limitations. Firstly, solving each new problem requires extensive domain knowledge to design proper algorithm by experts, which could lead to a significant development cost. In addition, these algorithms usually require an excessively long execution time due the NP-hardness of CO problems [49. These limitations make the classical algorithms undesirable and impractical for many real-world applications.
Recently, many learning-basse neural combinatorial optimization (NCO) methods have been proposed to solve CO problems without handcrafted algorithm design. These methods build neural network models to generate the solution for given CO problem instances, which can be trained by supervised
learning (SL.)
22
13
23
28
18 or reinforcement learning (RL) 4 27 17
9 53 37
29
36
24
39
40
54
22
Although these methods can achieve promising performance on
Eqqull contributors Corresponning author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

small-scale problems, they perform poorly on solving large-scale problems. Due to the NP-hardness of large-scale problems, the SL-based methods struggle to obtain enough high-quality solutions as labeled training data. Meanwhile, the RL--hased methods could suffer from the critical issues of sparse rewards 47 [.] and device memory limitations for solving large-scale problems. Therefore, it is impractical to directly train the NCO model on large-scale problem instances. One feasible approach is to train the NCO model on small-scale problems and then generalize it to solve large-scale problems. However, the current purely boarning-bases constructive NCO methods have very poor generalization ability, which diminishes their usefulness in solving large-scale real-world problems.
The current constructive NCO models typically have Heavy Encoder and Light Decoder (HELD) structure, which could be an underlying reason for their poor generalization ability. The HELD-based 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 small-scale instances. When the model generalizes to large-scale problem instances, the learned scale-related features may hinder the model from capturing the necessary relations among significantly larger number of nodes. This work proposes a constructive NCO model with a novel Light Encoder and Heavy Decoder (LEHD) structure to tackle this issue. Instead of one-shot embedding learning, our proposed LEHD- based model learns to dynamically capture the relationships among the current partial solution and all the available nodes each construction step via the heavy decoder. As the size of the available nodes varies with construction steps, the model tends to learn scale- indeeenddeeeeent features. Moreover, the model can iteratively adjust and refine the learned node relationships during the training. Therefore, could be less sensitive to the instance size and has much better generalization performance on large-scale problem instances.
becomes impractical to train the proposed LEHD model with RL due to the huge memory and computational cost of the heavy decoder structure. In this paper, we proposed data-efficient training scheme, called learn to construct partial solution, to train the LEHD model in a supervised manner. With this scheme, the model learns to reconstruct partial solutions during the optimization process, which can be treated as a kind of data augmentation for robust model training. Finally, similar to the training process, we propose a flexible solution construction mechanism called Random Re- Construct (RRC) for efficient active improvement at the inference stage, which can significantly improve the solution quality with iterative local reconstructions.
Our contributions can be summarized as follows:
We propose a novel Light Encoder and Heavy Decoder (LEHD) model for generalizable neural combinatorial optimization. By only training on small-scale problem instances, the proposed LEHD model can achieve robust and promising performance on problems with much larger sizes.
We develop data-efficient training scheme and flexible solution construction mechanism for the proposed LEHD model. The data-efficient training scheme enables LEHD to be trained efficiently via supervised learning, while the solution construction mechanism can continuously improve the solution quality through a customized inference budget.
Our purely learning- -bsed constructive method achieve sate-of-the-are performance in solving TSP and CVRP at various scales up to size 1000, and also generalizes well to solve real-world TSPLib/CVRPLib problems.
2
Related Work
Constructive NCO with Balanced Encoder-Decoder In their seminal work, Vinyals et al. [51] propose the Pointer Network neural solver to directly construct solutions for combinatorial optimization problems in an autoregressive manner. This model has balanced encoder-decoder structure where both the encoder and decoder are recurrent neural networks (RNNs) with the same number of layers. The original Pointer Network is trained by supervised learning, while Bello et al. proposes an efficient reinforcement learning method for NCO model training. Some Pointer Network variants have been proposed to tackle different combinatorial optimization problems [37]. However, these models can only solve small-scale problem instances with sizes up to 100 and have poor generalization performance.

---

Constructive NCO with Heavy Encoder and Light Decoder Kool et al. 127 and Deudon et al. [0] leverage the Transformer architecture 46) to design more powerful NCO models. The Attention Model (AM) proposed by Kool et al. [2 has Heavy Encoder and Light Decoder (HELD) structure with three attention layers in the encoder and one layer in the decoder. This model can obtain promising performance on various small-scale problems with no more than 100 nodes. Since then, AM has become a typical model choice, and many AM variants have been proposed for constructive NCO [53 29 14 30 24]. Among them, POMO proposed by Kwon et al. [29] is an AM model with more powerful learning and inference strategy based on multiple optimal policies. The POMO model has heavy encoder with six attention layers and light one-layer decoder. It can achieve remarkable performance on small-scale problems with up to 100 nodes.
However, these constructive models with heavy encoder and light decoder structures still have very poor generalization performance on problem instances with larger sizes, even for those with up to 200 nodes [23] Directly training these models on the large-scale problem is also very difficult if not infeasible [23] Different methods have been proposed to enhance the generalization ability for constructive NCO models in the inference stage, such as Efficient Active Search (EAS) [19 and Simulation-guiin guideed Beam Search (SGBS) [8) While these methods can improve the constructive NCO model's generalization performance on problems with up to size 200, they struggle to solve problems with larger scales.
Very recently, a few approaches have been proposed to use the AM model to tackle large-scale TSP instances. Pan al. (38] propose a Lower-Level Model that learns to construct the solution of sub-problems obtained by an Upper-Level Model. Another method proposed by Cheng et al. 7 uses an AM model to learn to reconstruct segments of given TSP solution and selects the most improving segment to optimize it. However, these methods heavily rely on specialized designs for TSP by human experts, and cannot be used to solve other problems such as CVRP. In a concurrent work, Drakulic et al. [2] propose novel Bisimulation Quotienting (BQ) method for generalizable neural combinatorial optimization by reformulating the Markov Decision Process (MDP) of the solution construction. Our proposed LEHD model has different motivation and model structure from BQ. and a comprehensive comparison is provided in the experiment section.
Con-Constructive NCO Methods In addition to constructive NCO, there are also other learning-
based approaches that work closely with search and improvement methods 33 6 18 21]. Joshi et al. [22] propose graph convolutional network predict the heat map of each edge 's probability in the optimal solution for a TSP instance. Afterward, approximate solutions can be obtained via the heat map guided beam search (22). Monte Carlo search (MCTS) 13], dynamic programming (28). and guided local search (20]. The beatmap-based approach was originally proposed to solve small-
scale problems, and some recent works generalize it for solving large-scale TSP instances [33 42
However, they heavily rely on the carefully deeernddsigned MCTS strategy for TSP [3 and cannot
be used solve other problems.
Learning-augment methods can also be applied to improve and accelerate heuristic solvers via
operation selection 6 35 91. guided improvement [17 5 551 and problem decomposition 44 32]
Many improvement based methods have also been proposed to iteratively improve a feasible initial solution 3 52 36). However, these methods typically rely human-designee heuristic operators more advanced solvers [4 16 for solving different problems. In this work, we mainly focus on the purely learning-based NCO solver without expert knowledge.
3 Model Architecture: Light Encoder and Heavy Decoder
In this section, we propose a novel NCO model with the Light Encoder and Heavy Decoder (LEHD) structure to tackle the critical issue regarding large-scale generalization.
3.1 Encoder
For problem instance S with node features ($1.....s.) s,,) (e.g., the coordinates of n cities), constructive model parameterized by 0 generates the solution in an autoregressive manner, i.e., it constructs the solution by selecting nodes one by one. Our LEHD-based model consists of light encoder and a heavy decoder, as shown in Figure T The light encoder has one attention layer, and the heavy decoder has L attention layers. Given the problem instance with node features
3

---

Starting Node Emneeding
Available Node Embeddings
Destination Node Embedding
Node Embeddings
MHA
Linear Projection
Linear Projection
Add
Attention Layerx
Attention L
Linear Projection
FF
Linear Projection
Softmax
Add
Encoder
Decoder
Attention Layer
4
Node Features
Selected Probability
Figure 1: The structure of our proposed LEHD model, which has single-layer light encoder and heavy decoder with attention layers.
S (S.,..., s,), the light encoder transforms each node features s; to its initial embedding h through a linear projection. The initial embeddings [h (h)) ( } are then fed into one attention
layer to get the node embedding matrix (1) (hl ..... hn
Attention layer The attention layer comprises two sub-layers: the multi-head attention (MHA) sub-layer and the feed-forward (FF) sub-layer [46]. Different from generic NCO models such as AM [27] the normalization removed from our model to enhance generalization performance
(see Appendix A.. Let (i-1) = (h(--1) ..... h ) be the input of the I-th attention layer for
1 1. 1....,,..... L, the output of the attention layer in terms of the i-th node is calculated as:
6,00 h (-11) + MHA(h! (--1, H("))),
(1)
h = 6,00 + +F(h
We denote this embedding process as H AttentionLayer (H (H)))))
3.2 Decoder
The decoder sequentially constructs the solution in n steps by selecting node by node. In the t-th step for t E {L...., n2,, the current partial solution can be written as ( xz-1), the first selected node's embedding denoted as h!4) the embedding of the node selected the previous step is denoted as b and the embeddings of all available nodes is denoted by H. (b i e {1....,7) n \ {xI,.... (rr }. Since the decoder has L attention layers, the 1-th construction step of LEHD can be described as:
(0) Concat(W,hh) (1) W2h (1) 1. Ho);
(1)) (itentionLayer(((())
(1)) AttentionLayer (1
Wo
U;
-0, otherwise
p' softmax(u),
where W1, W2, Wo are learnable matrices. The matrices W1 and W2 are used to re-calculate the embeddings of the starting node (i.e., the node selected the previous step) and the destination node (i.e., the node selected in the first step), respectively. The matrix Wo is used to transform the relation-denoting embedding matrix (L) into vector for the purpose of calculating the selection probability p'. The most suitable node is selected based on p' at each decoding step t. Finally, complete solution x (I1,... ".,) constructed by calling the decoder times.
For the HELD model such as AM (77, the heavy encoder with layers outputs the node embedding
matrix as (L) (h ..... h The average of all nodes' embeddings (i.c., 1 Σi h,,"), the

---

sample
sample
80
8
4
04
7
5
TSP solution
TSP partial solution
CVRP solution
CVRP partial solution
Figure 2: Examples of generating partial solution for TSP and CVRP. For the TSP instance, its optimal solution is (,, and a partial solution randomly sampled as [6.5,4.3.2]. For the CVRP instance, its optimal solution is [0,1,2.3,0,445,6,,4 4.5,6.0.7,8.9. and partial solution 1,3,0,6,5,4.00 is randomly sampled. We impose a restriction for CVRP that the partial solution must end at the depot.
starting node's embedding (i.e., b22 ), the destination node's embedding (i.e., b(l are contacted to form the context node embedding (i.e., h. Thereafter, the light decoder takes the context node embedding and the embeddings of all nodes (i.e., H(L) as input, and computes the selection probability through an MHA operation, the compatibility calculation, and the softmax function, i.e.,
h
M (0) HH()),
10 tanh (Woi!)) (Trch)")Tohh""")
i i #14-1
U
0C,
otherwise
D softmax(uu).
where We and WE are learnable matrices, is parameter determined by the embedding dimension. Since the HELD model's decoder only has static node embedding matrix H(L), the relationships among the nodes it captures not updated throughout the decoding process. In other words, the HELD model's performance relies heavily on the quality of the static node embedding matrix. When the problem size becomes larger, the ability of the static node embedding matrix represent the relationships among all nodes becomes worse, resulting in the poor generalization performance of the model.
In our LEHD model, the heavy decoder dynamically re-embeds the embeddings of the starting node, destination node, and available nodes via L attention layers, thus updating the relationships among the nodes at each decoding step. Such dynamic learning strategy enables the model to adjust and refine its captured relationships between the starting/destination and available nodes. In addition, as the size the nodes varies during the construction steps, the model tends to learn the ceale-independent features. These good properties enable the model dynamically capture the proper relationships between the nodes, thereby making more informed decisions in the node selection on problem instances of various sizes.
4 Learn to Construct Partial Solution
The constructive NCO aims to construct the solution node-by-non using the decoder. The heavy decoder of our LEHD model can result in higher computational cost than that of the HELD model at each construction step. Whereas the RL training method needs to generate the complete solution before computing the reward, which implies it requires significantly huge memory and computational costs. Furthermore, RI. suffers from the challenging issue of sparse reward, especially for problems with large sizes.
According to Yao et al. [56), data augmentation (DA) can significantly reduce the number of required high-quality solutions (i.e., labels) for SL training, and DA-based SL can even outperform RL regarding solution accuracy and generalization performance. Operations based on the property of multiple optimality [29] and optimality invariance (25] are the most commonly used DA methods in NCO. In this work, we develop an efficient DA-based SL training scheme also based on the property of optimality invariance.
For each training data (i.e., set of nodes), its label a sequence all the nodes (i.e., a valid tour). According to the property of optimality invariance, the partial solution of the optimal solution must
5

---

also be optimal. Therefore, we can randomly sample labeled partial solutions with various sizes and different directions from each labeled data, thus greatly enriching our training set. Based on these characteristics, we propose a training scheme called learning to construct partial solutions. The model learns to construct optimal partial solutions of various sizes and random directions, thereby resulting in more efficient and robust training process.
4.1 Generate Partial Solutions during the Training Phase
For routing problem instance S with n nodes (5.....,sp)) ), its optimal solution can be represented by specific node sequence x (also called the tour). The partial solution X is a consecutive subsequence sampled from x with a random size and direction. In this work, we let each partial solution have length with w sampled from the discrete uniform distribution Unif ([4, [Vl)) where [V] is the number of nodes for each TSP/CVRP instance, since problem with size less than 4 is trivial to solve. Each partial solution X is one augmented data point in our method. Two examples of generating partial solutions for TSP and CVRP are provided in Figure
4.2 Learn to Construct Partial Solutions via Supervised Learning
The model learns to construct the partial solution node by node. The first node of Xaub is the starting node, the last node of Xaub is the destination node, and the remaining nodes constitute the available nodes to be selected by the model. For the example Xeub = [6, 3, 5, 4, 1], node 6 is the starting node, node is the destination node, and nodes 3, 4 are available nodes.
In each training step, the model provides each available node s; with a probability p, of being selected. Meanwhile, the label Xuub tells whether the node S; should be chosen in the current step (i.e., Vt 1 or 0). The cross-entropy loss loss = Σi=1 Vi log(p;) is employed to measure the error made by the update the model parameters current model, where is the number of available nodes. Then Throughout the training process, by a gradient-based algorithm (e.g., Adam) with respect to the loss. the number of available nodes gradually decreases, and the starting node dynamically shifts the node selected in the previous step while the destination node remains constant. The training epoch ends when there are no more nodes available. The next epoch starts with new augmented data.
4.3 Generate the Complete Solution during the Inference Phase
During the inference phase, our proposed LEHD model employs greedy step-by-step approach to construct the whole solution for the given instance S. In the beginning, a single node is randomly selected serve as the destination node and also the initial starting node. The remaining nodes constitute the set of available nodes that the model can select step-by-step. Once a node is selected, it will be treated the new starting node and removed from the set of available nodes, i.e., the starting node is dynamically shifting while the destination node remains constant. When no more available nodes exist, the whole solution is generated. In this way, LEHD can easily construct solutions for problems of various sizes as well as unseen large-scale problems.
5 Random Re-Construct for Further Improvement
The constructive model has an inductive bias, which means it could construct a better solution by following its preferred direction. Similarly, different starting and destination nodes will lead to different solution quality since the model may perform better when starting from some well-learned local patterns. The tour generated via greedy search could be not optimal and contain multiple suboptimal local segments (c.g., partial solutions). Therefore, rectifying these suboptimal segments during the inference phase can effectively enhance the overall solution quality.
Our model stems from learning to construct partial solutions, making it appropriate for iteratively reconstructing partial solutions from different directions and different starting and destination nodes. It naturally leads to our proposed flexible construction mechanism, Random Re-Construct(RRC Specifically, being the same as generating the partial solution during training, RRC randomly samples a partial solution from the initial solution and restructures it to obtain new partial solution. If the new partial solution is superior, replaces the old one. This iterative process can enhance the solution quality within a stipulated time budget.

---

Experiment
In this section, we empirically compare our proposed LEHD model with other learning- -ased and classical solvers on TSP and CVRP instances with various sizes and distributions.
Problem Setting We follow the standard data generation procedure of the previous work 27 to generate TSP and CVRP datasets. The training sets consist of one million instances for TSP100 and CVRP100, respectively. The TSP test set includes 10,000 instances with 100 nodes and 128 instances for each of 200, 500, and 1000 nodes, respectively. Similarly, the CVRP test set is constructed with the same number of instances. We obtain optimal solutions for the TSP training set with the Concorde solver (2) and obtain optimal solutions for the CVRP training set with HGS [50]. The training and test datasets can be downloaded from Google Drive or Baidu Cloud f1
Model Setting For our LEHD model, the embedding dimension is set to 128, and the number of attention layers in the decoder is set to 6. each attention layer, the head number of MHA is set to and the dimension of the feed-forward layer is set to 512. In all experiments, we train and test our LEHD models using single NVIDIA GeForce RTX 3090 GPU with 24GB memory.
Training Both the TSP model and CVRP model are trained on one million instances of size 100, respectively. The optimizer Adam (26 with an initial learning rate of le-4. The value of the learning rate decay is set to 0.97 per epoch for the TSP model and 0.9 per epoch for the CVRP model.
With a batch size of 1024, we train the TSP model for 150 epochs and the CVRP model for 40 epochs since it converges much faster.
Baselines We compare our method with (1) Classical Solvers: Concorde [2]. LKH3 [6] HGS [50] and OR-Tools [4] (2) Constructive NCO: POMO (29). MDAM (54), EAS 19), SGBS (8. and BQ 12: (3) Heatmap-based Method: AU-GCNN-CCTS 13
Metrics and Inference We report the optimality gap and inference time for all methods. The optimality gap measures the difference between solutions achieved by different learning and non- learning-based methods and the optimal solutions obtained using Concorde for TSP and LKH3 for CVRP. Since the classical solvers are run on a single CPU, their reported inference times are not directly comparable to those of the learning- methods executed on GPU.
For MDAM, POMO, SGBS, and EAS, we directly run their source code with default settings on our test set. For MCTS we report their original results for the corresponding setting. For BQ. following the settings described in the original paper, we reproduce and train the BQ model by ourselves and report the obtained results on our test set. For our proposed LEHD model, we report both the results for greedy inference as well as for Random Re-Construct (RRC) with various computational budgets.
6.1 Experimental Results
The main experimental results on uniformly distributed TSP and CVRP instances are reported in Table [ For TSP, our proposed LEHD method can obtain good greedy inference performance with a very fast inference time on instances of all sizes. With only 100 RRC iterations, LEHD can significantly outperform all other dearning-basee methods with reasonable inference time. If we have larger budget of more than 500 RRC iterations, LEHD can achieve very promising performance for all instances, of which the gap is nearly optimal for TSP100 and TSP200, less than 0.2% for TSP500, and around 0.8% for TSP1000.
For CVRP, LEHD can also achieve promising greedy inference performance for all instances. With 300 RRC iterations. LEHD can outperform most learning- based methods on all CVRP instances. except for the EAS method on CVRP100, which requires much longer inference time. The EAS's performance significantly decreases for solving larger instances such as CVRP500, and we fail to obtain a result for EAS on CVRP1000 with reasonable budget. SGBS struggles with poor generalization and long inference time for solving large-scale instances. LEHD can also outperform

---

Table 1: Experimental results on TSP and CVRP with uniformly distributed instances. The results of methods with an asterisk (*) are directly obtained from the original paper.
TSPI00
TSP200
TSP500
TSP1000
Concorde
0.000%
34m
0.000%
3m
0.000%
32m
0.000%
7.8h
LKH
0.000%
56m
0.000%
4m
0.000%
32m
0.000%
8.2h
OR-Tools
2.368%
11h
3.618%
17m
4.682%
50m
4.885%
10h
MCTSS
0.037%
15m
0.884%
2m
2.536%
6m
3.223%
13m
MDAM bs50
0.388%
21m
1.996%
3m
10.065%
11m
20.375%
44m
POMO augx8
0.134%
1m
1.533%
5s
22.187%
1m
40.570%
8m
SGBS
0.060%
40m
0.562%
4m
11.550%
54m
26.035%
7.4h
EAS
0.057%
6h
0.496%
28m
17.08%
7.8h
BQ greedy
0.579%
0.6m
0.895%
3s
1 1.834%
0.4m
3. 3.965%
2.4m
BQ bs16
0.046%
11m
0.224%
Im
0,896%
6m
2.605%
38m
LEHD greedy
0.577%
0.4m
0.859%
3s
1 1.560%
0.3m
3.168%
1.6m
LEHD RRC
50
0.0284%
7.4m
0.123%
0.6m
0,482%
3.4m
1.416%
22m
100
0.01 14%
13.7m
0.0761 %
1.2m
0.343%
8m
1.218%
43m
300
0.0044%
40m
0.0363%
3.3m
0.223%
22m
0.899%
2.1h
500
0.0025%
1.1h
0.0280%
5.3m
0.193%
37m
0.818%
3.5h
1000
0.0016% %
2.2h
0.0182% %
10.5m
0.167 %
1.2h
0.719%
7h
CVRP100
CVRP200
CVRP500
CVRP1000
LKHI
0.000%
12h
0.000%
2.1h
0.000%
5.5h
0.000%
7.1h
HGS
-0.533%
4.5h
-1.126%
1.4h
-1.794%
4h
-2.162%
5,3h
OR-Tools
6.193%
2h
6.894%
1h
9.112%
2.2h
11.662%
3h
MDAM bs50
2.211% %
25m
4.304%
3m
10.498%
12m
27.814%
47m
POMO augx8
0.689%
1m
4.866%
7s
19.901% %
1m
10m
SGBS
0.079%
40m
2.581%
1m
15.343%
16m
136.980%
2.3h
EAS
-0.234%
15h
0.640%
33m
11.042%
BQ greedy
2.993%
0.7m
3.527%
4s
5.121%
0.4m
9.812%
2.4m
BQ 16
0.611%
10m
1.41%
0.6m
2.991 %
6m
7.784%
39m
LEHD greedy
3.648%
0.5m
3.312%
3s
3.178%
0.3m
4.912%
1.6m
LEHD RRC
50
0.535%
7.2m
0.515%
0.6m
0.930%
8m
2.814%
27m
100
0.272%
17m
0.217%
1.1m
0.546%
14m
2.370%
45m
300
0.029%
52m
-0.146%
3.6m
0.045%
36m
1.582%
2.3h
500
-0.044%
1.4h
-0.246%
6m
-0.107%
1.270%
1000
11.%
2.8h
-0.383%
11.3m
-0.347%
2h
0.921 %
8h
Table 2: Experimental results on TSPLib and CVRPLib. "#" denotes the number of instances in the corresponding set.
POMO
BQ
LEHD
Size
aug
greedy
bs16
greedy
RRC
<100
0.792%
1.076%
0.500%
0.976%
0.481 %
100-200
2.423%
2,684%
1.318%
2.336%
0.158 %
TSPLib bi
200-500
13.413%
3.177%
2.183%
2.742%
0.200 %
500-1k
31.678%
8.311%
5.521%
4.049%
1.310
>kk
63.810%
42.566%
36.730%
11.267%
4.088
All
70
26.439%
15.668%
12.923%
5.260%
1.529 %
POMO
BQ
LEHD
Set (size)
augx8
greedy
bs16
greedy
RRC
A (31-79)
27
4.970%
6.31(1%
1.627%
5.871%
0.647 %
B (30-77)
23
4.747%
6.859%
2.221%
6.049%
0.812%
CVRPLib
B (12-100)
11
11.402%
5.884%
1.211%
4.809%
0.541 %
(44-134)
15.973%
12.568%
7.404%
9.051%
3.009 %
M (100-199)
4.861 %
8.407%
3.691%
7.094%
1.817% %
(15-100)
1..5255%
5.902%
2.393%
6.611%
0.917% %
X (100-11k
21.684%
12.526%
9.774%
12.520%
3,511
192
15.4500%
9.692%
6.153%
9.465%
2.253%
8

---

LKH3 on CVRP100-CVRP500 with a budget of 500 RRC iterations and can achieve an around 1% gap to LKH3 on CVRP1000 with 1000 RCC iterations. To the best of our knowledge, our method is the first purely learning-based NCO method that can outperform I.KH3 on CVRP200 and CVRP500.
Table Table shows the test results on real-world TSPLib 43 and CVRPLib 45 instances with different sizes and distributions. We report the results with greedy inference and 1000 RRC iterations for our proposed LEHD method. It clear that LEHD has a good greedy inference performance and can significantly outperform POMO and BQ on all instances with 1000 RRC iterations. These results demonstrate the robust generalization ability of LEHD.
6.2 Ablation Study
Table 3: Comparsion of POMO and LEHD with the same SL training method.
TSPI00
TSP200
TSP500
TSP1000
POMO augx8 SL
0.571 %
3.970% 0.859%
20.418%
34.419%
LEHD greedy SL
0.577%
1.560%
3.168%
Heavy Decoder vs. Heavy Encoder We compare the performance of models with the Heavy Encoder structure (POMO) and the Heavy Decoder structure (LEHD). We also train POMO with SL on TSP100 and report the result Table 3, 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 4: Effect of reinforcement learning and supervised learning on training the LEHD model with 10K testing instances for TSP50/100 and 128 testing instances for TSP200/500/1000
TSP50
TSP100
TSP200
TSP500
TSP1000
RL
5.372%
7.891% 0.789 %
12.581 %
25.377% 3.500%
46.441% 6.566 %
SL.
0.375 %
1.545 %
Supervised Learning vs. Reinforcement Learning In Table 4 we conduct a comparison with reinforcement learning and supervised learning for training our proposed LEHD model. Due to the high computational cost, the reinforcement learning method with the POMO strategy cannot converge in reasonable time. Therefore, we use each method to train LEHD model separately on TSP50 with the same computational budget. The results Table Table coonfi confirm that our proposed LEHD model is more suitable to be trained by the supervised learning method.
Table 5: Comparison of POMO and LEHD with random sampling and RRC methods.
(10k instances) TSP100
(Ik instances) TSP500
TSP200
TSP1000
Concorde
0.000%
34m
0.000%
23m
0.000%
4h
0.000%
61h
POMO augx8
0.134%
1m
1.459%
0.6m
21.948%
8m
40.551%
1.1h
POMO augx8-sample100 100
0.080%
1.7h
1.609%
1.2h
37.285%
16h
82.015%
117h
POMO RRCC00
0.115%
2m
1.283%
1.6m
11.900%
11m
25.378%
1.2h
POMO augx8-RRC1000
0.075%
12m
0.820%
8m
6.753%
29m
16.261%
2h
LEHD greedy
0.577%
0.4m
0.849%
0.2m
1.585%
2.1m
3.089%
13m
LEHD RRC
100
14%
13.7m
0.053%
6.5m
0.357%
58m
1.195%
5.3h
1000
0.0016% %
2.2h
0.015%
1h
0.179%
9.5h
0.735%
57h
The Effect of RRC
We also conduct comparisons with POMO with random sampling (POMO- Sample100) well as POMO with RRC (POMO-RRC100) clearly present the advantages of LEHD and RRC.
The experimental results are shown in Table 5 and have the following two main observations:

---

The random sampling strategy is inefficient in improving POMO's solution quality, especially for large-scale problems. contrast, our proposed RRC can efficiently improve POMO's performance at inference time.
POMO-RRC' POMO-Sample:
LEHD-RRC POMO-RRC: Our proposed LEHD model structure provides enough model capacity for learning construct partial solutions for different sizes. It is erucial for the strong generalization ability to large-scale problems.
6.3 Comparison with Search- Saarch--seed/mpproeeeenn--
Methods
Table 6: Comparison with SO-mixed from the original paper.
The results of the SO-mixed method are directly obtained
(128 instances) TSP500
TSP200
TSP1000
Concorde
0.000%
3m
0.000%
32m
0.000%
7.8h
SO-mixed
0.636%
21m
2.401
32m
2.800%
56m
LEHD greedy
0.859%
3s
1.560%
0.3m 8m
3.168%
1.6m
LEHD RRC100
0.0761% %
1.2m
0.343%
1.218%
43m
Table 7: Comparison with H-TSP 38 The results of the H-TSP method are directly obtained from the original paper.
TSP1000 (128 instances)
Concorde
0.000%
7.8h
H-TSP with LKH-3
4.06%
7.5m
LEHD greedy
3.168%
1.6m
LEHD RRC100
1.218%
43m
Recently, Cheng et al. 7 and Pan et al. 38 propose two learning- methods which can tackle large-scale TSP instances. However, these two methods are saurehhbbeedmmprrvveeett-ee approaches that require powerful solvers like LKH3 or specifically designed heuristics, and can only tackle TSP but not other VRP variants. In this work, propose purely learning-bas based construction method to tackle the large-scale TSP/VRP instances, and hence mainly compare with other construction-bass basod methods in the original paper.
We conduct comparison with these methods for a more comprehensive experimental study. The results are reported in Tan T Our proposed method clearly outperforms those methods in terms of both performance and running time. highlights the effectiveness of our proposed LEHD+RRC purely learning-base based method to tackle large-scale problems.
7 Conclusion, Limitation, and Future Work
Conclusion this work, we propose a novel LEHD model for generalizable constructive neural combinatorial optimization. By leveraging the Light Encoder and Heavy Decoder (LEHD) model structure, the LEHD model achieves strong and robust generalization ability as a purely learning- based method. We also develop a learn construct partial solution strategy for efficient model training, and a flexible random solution reconstruction mechanism for online solution improvement with customized computational budgets. Extensive experimental comparisons with other representative methods on both synthetic and real-world instances fully demonstrate the promising generalization ability of our proposed LEHD model. Since the generalization ability is one crucial issue for the current constructive NCO solver, we believe LEHD can provide valuable insights and inspire follow-up works to explore the heavy decoder structure for powerful NCO model design.
Limitation and Future Work Although with a strong generalization performance, the current LEHD model can only be properly trained by supervised learning. It could be interesting to develop an efficient reinforcement learning-based, method for LEHD model training. Another promising future work is to design powerful learning- based method for more efficient partial solution reconstruction.
10

---

Acknowledgments and Disclosure of Funding
This work was supported in part by the National Natural Science Foundation of China under Grant 62106096, in part by the Shenzhen Technology Plan under Grant JCYJ202205301 13013031, in part by the Characteristic Innovation Project of Colleges and Universities Guangdong Province under Grant 2022KTSCX110, in part by the Research Grants Council of the Hong Kong Special Administrative Region under Grant CityU 1 12215622, and part by the 2023 Graduate Innovation Practice Fund Project of Southern University of Science and Technology.
References
Sungsoo Ahn, Younggyo Seo, and Jinwoo Shin. Learning what defer for maximum independent sets. In International Conference on Machine Learning, pages 134-144, 144. PMLR, 2020.
[2] David Applegate, Ribert Bixby, Vasek Chvatal, and William Cook. Concorde isp solver, 2006.
[3] Thomas Barrett, William Clements, Jakob Foerster, and Alex Lvovsky. Exploratory combinatorial opti- mization with reinforcement learning. In AAAI Conference on Artificial Intelligence (AAAI), 2020.
[4] Irwan Bello, Hicu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforeement learning. arXiv preprint arXiv: 1,09940, 2016.
[5] Quentin Cappart, Thierry Moisan, Louis-Martin Rousscau, Isabeau Prémont-Schwarz, and Andre A Cire. Combining reinforcement learning and constraint programming for combinatorial optimization. In AAAI Conference on Artificial Intelligence (AAAI), 2021.
[6] Xinyun Chen and Yuandong Tian. Learning perform local rewriting for combinatorial optimization. Advances in Neural Information Processing Systems, 32, 2019.
[7] Hanni Cheng, Haosi Zheng, Ya Cong, Weihao Jiang, and Shiliang Pu. Select and optimize: Learning to aolve large-scale tsp instances. In International Conference Artificial Intelligence and Statistics, pages 1219-1231. PMIR, 2023.
[8] Jinho Choo, Ycong- Kwon, Jihoon Kim, Jeongwoo Jac, André Hottung, Kevin Tiemny, and Youngjune Gwon. Simulation-guided beam search for neural combinatorial optimization. arXiv preprint arXiv:220.061190. 2022.
[9] Paulo R O Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akcay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Asian Conference Machine Learning. pages 465-480. PMLR, 2020.
[10] Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Martin Rousscau. Learning heuristics for the tsp by policy gradient. In International conference on the integration of construint programming, artificial intelligence, and operations research, pages 170-181. Springer. 2018.
[11] Alexandre Dolgui, Dmitry Ivanov, Suresh Sethi, and Boris Sokolov. Scheduling in production, sup- ply chain and industry 4.0 systems by optimal control: fundamentals, state-of-the-art and applications. International Journal of Production Research, 57(2):411 1-11111222222 2019.
[12] Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Marc Andreoli. Bq-nco: Bisimulation quotienting for generalizable neural combinatorial optimization. arXiv preprint arXiv:2301.0333 2023,
[13] Zhang-Huu Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 7474-7482, 2021.
[14] Gurobi Optimization, Inc. Gurobi optimizer reference manual, 2012. URL latp:::/:////// hwtp:///wwwwwwwb..coo. com
[15] Joshua Hare. Dealing with sparse rewards in reinforcement learning. arXiv preprint arXiv: 1910.09281, 2019.
[16] Keld Helsgaun. An extension of the lin- fin-kemighan-hhlseee tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University. 12, 2017.
[17] André Hottung and Kevin Tierney. Neural large neighhorhood search for capacitated vehicle routing problem. In 24th European Conference on Artificial Intelligence (ECAI 2020), 2020.
[18] André Hottung, Bhanu Bhandari, and Kevin Tierncy. Learning a latent search space for routing problems using variational autoencoders. In International Conference on Learning Representations, 2021.
[19] André Hottung, Ycong- Dac Kwon, and Kevin Tierney. Efficient active search for combinatorial optimization problems. arXiv preprint arXiv:2106. 051266 2021.
[20] Benjamin Hudson. Qingbiao Li, Matthew Malencia, and Amanda Prorok. Graph neural network guided local search for the traveling salesperson problem. arXiv preprint arXiv:2110.05291, 2021.
11

---

[21] Chaitanya K. Joshi and Rishabh Anand. Recent advances in deep learning for routing prob-
lems. In ICLR Blog Track, 2022. URL https://iclr--loe traggg-trak....tttt.. github 10/00//220/022222///////2
problems/
for-routing prrbuutingproblemss/
[22] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint (rXiv:1906.01220 01000.0122..20. 2019.
[23] Chaitanya K Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learning the travelling salesperson problem requires rethinking generalization. Constraints, 27(1-2)77--9, 2022.
[24] Minsu Kim, Jinkyoo Park, et al. Learning collaborative policies to solve np-hard routing problems. Advances in Neural Information Processing Systems, 34: 14:10418- 10430, 2021.
[25] Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-nco: Leveraging symmetricity for neural combinatorial optimization. arXiv preprint arXiv:2205. 13209, 2022.
[26] Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint
arXiv: 1412.9880 2014.
[27] Wouter Kool, Herke van Hoof, and Max Welling. Attention, Iearn solve routing problems! In International Conference on Learning Representations, 2019. MRRLbhttp///opeereere net forum? Id=ByzBFaRqym
[28] Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic programming for vehicle routing problems. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 19th International Conference, CPAIOR 2022, Los Angeles, CA, USA, June 20-23, 2022, Proceedings, pages I 190-213. Springer, 2022.
[29] Yeong-Dat Kwon, Jinho Choo, Byoungjip Kim, I1joo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement lcarning. Advances in Neural Information Processing Systems, 33:21188 1822188--00 21 198, 2020.
[30] Yeong-Dae Kwon, Jinho Choo, I1joo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. In Advances in Neural Information Processing Systems, 2021.
[31] Bingjic Li, Guohua Wu, Yongming Hc, Mingfeng Fan, and Witold Pedrycz. An overview and experimental study of learning- based optimization algorithms for the vehicle routing problem. IEEE/CAA Journal of Automatica Sinica, 9(7):1115-113 1138188111118,,,,,-------1111111 2022.
[32] Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehicle routing. Advances in Neural Information Processing Systems, 34:26198-26211 2021.
[33] Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. In Advonces in Neural Information Processing Syxtems, page 539, 2018.
[34] Ruiwu Liu, Xiaocen Li, and Kit S Lam. Combinatorial chemistry drug discovery. Current opinion in chemical biology, 38:117-126, 2017.
[35] Hao Lu. Xingwen Zhang, and Shuang Yang. A learning-based iterative method for solving vehicle routing problems. In International Conference on Learning Representations, 2019.
[36] Yining Ma. Jingwen Li, Zhiguang Cao, Wen Song. Le Zhang, Zhenghua Chen, and Jing Tang. Learning to iteratively solve routing problems with dual-aspect collaborative transformer. In Advances in Neural Information Processing Systems, 2021.
[37] Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takáe. Reinforcement learning for solving the vehicle routing problem. Advances in neural information processing systems, 31, 2018.
[38] Xuanhao Pan. Yan Jin, Yuandong Ding, Mingxiao Feng. Li Zhao. Lei Song, and Jiang Bian. H-tsp: Hierarchically solving the large- traveling salesman problem. In AAAI 2023, February 2023. URL Ihttps://www mi www.rooooo.ooooooooomooooooo.ooc com/ en us/rrseearc//uullcati.. h- Shsp-hieearchicann solving the- large- scale- travelinaveennee salesman www.eeemmmaaooobeeeeeeeemo
[39] Junyoung Park, Sanjar Bakhtiyar, and Jinkyoo Park. Schedulenet: Learn to solve multi-agen agent scheduling problems with reinforcement learning. arXiv preprint arXiv:2106.03057 2021.
[40] Junyoung Park, Jachyeong Chun, Sang Hun Kim, Youngkook Kim, and Jinkyoo Park. Learning to schedule job-shop problems: representation and policy learning using graph neural network and reinforcement learning. International Journal of Production Research, (9(11):330-3377722 2021.
[41] Laurent Perron and Vineent Furnon. Or-tools, 2023. optimization/
URL
com/
[42] Ruizhong Qiu. Zhiqing Sun, and Yiming Yang. Dimes: A differentiable meta solver for combinatorial optimization problems, arXiv preprint 2rX0v22210001123, 2022.
12

---

[43] Gerhard Reinelt. TSPLIB-a traveling salesman problem library. ORSA Journal on Computing, 3(4):
376-384, 1991.
[44]
Jialin Song, Yisong Yue, Bistra Dilkina, et al. A general large neighborhood search framework for solving integer linear programs, Advances in Neural Information Processing Systems, 33:20012 22-22023, 2020.
[45] Eduardo Uchoa, Diego Pecin, Artur Pessoa, Mareus Poggi. Thibaut Vidal, Anand Subramanian. New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257()):845-855) 2017.
[46] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
[47] Mel Vecerik, Todd Hester, Jonathan Scholz, Fumin Wang. Olivier Pietquin, Bilal Piot, Nicolas Heess, Thomas Rothörl, Thomas I Lampe, and Martin Riedmiller. Leveraging demonstrations for deep reinforce- ment learning on robotics problems with sparse rewards. arXiv preprint /7Xiv:/77.008872 2017.
[48] Matthew Veres and Medhat Moussa. Deep learning for intelligent transportation systems: survey of emerging trends. IEEE Transactions on Intelligent Transportation Systems, 21(8):3152-3168, 2019.
[49] Natalia Vesselinova, Rebecca Steinert, Daniel Perez-Ramirez, and Magnus Boman. Learning combinato- rial optimization graphs: A survey with applications networking. IEEE Access, 8:120388- 1204166, 2020.
[50] Thibaut Vidal. Hybrid genetic search for the evrp: Open-source implementation and swap" neighborhood. Computers & Operations Research, 140:105643 105643, 2022.
[51] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly, Pointer networks. Advances in neural information processing systems, 28, 2015.
[52] Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang. and Andrew Lim. Learning improvement heuristics for salving routing problems. IEFE transactions on neural networks and learning systems, 33(9)55057,506,, 2021.
[53] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Step-wise deep learning models for solving routing problems. IEEE Transactions on Industrial Informatics, 17(7)4861-4871,, 2020.
[54] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Multi-decoder attention model with embedding glimpse for solving vehicle routing problems. In Proceedings of the AAAI Conference on Artificial Inselligence, volume 35, pages 12042-12044 2021.
[55] Liang Xin, Wen Song. Zhiguang Cao, and Jie Zhang. Neurolkh: Combining deep learning model with lin- kernighan-helsgauun heuristic for solving the traveling salesman problem. Advances in Neural Information Processing Systems, 34:7472-7483, 2021.
[56] Shunyu Yao, Xi Lin, Zhenkun Wang, and Qingfu Zhang, eefaciefffccent supervised learning is powerful for neural combinatorial optimization. 2023. URL http::////ppeeeeeeeeee///rrrrre/
uEK
13

---

A Ablation Study of Normalization
A.1 LEHD Model
In T we explore the effects of eliminating normalization from the attention layer in our LEHD) model. We train three LEHD models with the same training scheme and training budget, differing solely in the attention layer: one with batch normalization (BN), one with instance normalization (IN), and one without normalization (w/o). Our experimental results demonstrate that the LEHD model without normalization in the attention layer can significantly outperform the other two models with normalization.
Table 8: Effect of normalization for LEHD model.
TSP100
TSP200
TSP500
TSP1000
BN
0.775%
1.312%
3.808%
12.209%
0.640%
1.197%
34.391%
222.730%
w/o
0,577%
0.859%
1.560%
3.168%
A.2 POMO Model
We also compare the performance of POMO [29] with different types of normalization: one with batch normalization (BN), one with instance normalization (IN), and one without normalization (w/o) in Table We train all three POMO models with the same reinforcement learning method with POMO strategy and training budget (1, 000 epochs). The results show that different types of normalization have little effect on POMO.
Table 9: Effect of normalization for POMO model.
TSP100
TSP200
TSP500
TSP1000
BN
1.325%
5.502%
27.616%
41.631%
IN
1.449%
5.602%
27.454%
41.748%
w/o
1.321%
4.990%
28.598%
45.747%
The results in Table Thhle that removing normalization from the attention layer has little impact on the model with heavy encoder and light decoder. However, the results in Table & show that removing normalization from the attention layer has a positive impact on the performance of the LEHD model, but it is not the critical faccor for the LEHD model's strong generalization ability since the LEHD model with batch normalization still performs significantly better than POMO and SGBS in the case of TSP1000. Instead, can conclude that the underlying reason for the model's strong generalization ability lies in the heavy decoder structure.
B Efficient Self-Improved Training
LEHD uses SL for training, which raises concerns that the performance of LEHD may be upper bounded by the provided (nearly) optimal solutions and the requirement of optimal solutions for LEHD training may make hard solve more complex VRPs. We tackle these two concerns as follows.
B.1 RRC can break the performance upper limit of the labeled solution
Firstly, the performance of our proposed LEHD model with RRC is not limited by the quality of labeled solutions. To demonstrate this point, we train a new LEHD model with labeled solutions generated by OR-Tools of which the quality is far from the optimal solutions (e.g., with 6.762% optimal gap). The results are shown in Table I0
In this experiment, we use OR-Tools generate suboptimal solutions for 100, 000 CVRP100 instances, and use them to train the LEHD model with only epochs (about 1.25 hours). Then compare their performance the same test set with 10k instances. According to the results,
14

---

Table 10: The LEHD model's performance trained with suboptimal label outputted by OR- OR-Tools.
CVRPI00
HGS
0.000%
4.5h
OR-Tools
6. 6.762%
LEHD
greedy
10.428%
0.5m
RRC
6.249%
3m
RRC 50
4.811%
7m
RRC 100
3.915%
17m
RRC 300
2.862%
52m
RRC 500
2.525%
1.4h
although LEHD with greedy inference is outperformed by OR-Tools, LEHD+RRC significantly outperform OR-Tools by a large margin with a reasonable runtime. more training budget is allowed, the performance of LEHD(+RRC) can be further improved.
This result also demonstrates the importance and effectiveness of RRC in our proposed method.
B.2 LEHD can be trained by RL without any labeled solution
Table 11: The LEHD model's performance trained by RL method on TSP20.
(10k instances)
TSP20
TSP100
Concorde LEHD-RL
0.000%
3m
0%
34m
greedy
0.274%
2s
5.463%
0.4m
RRC100
0.014%
0.6m
1.271%
13m
RRC200
0.006%
1.2m
0.983%
26m
RRC300
0.005%
1.7m
0.865%
40m
RRCS00
0.003%
3m
0.740%
1.1h
Secondly, it is possible to directly train the LEHD model using reinforcement learning that does require any labeled data. Experimental results can be found in Table 1T where we train the LEHD model by RL on the small-scale TSP20 instances, and then test its generalization performance on TSP100. The training budget is 40 epochs each with 100, 000 instances on TSP20 (roughly hours). According to the results, trained by RL, LEHD can achieve nearly optimal solution for TSP20, and RRC makes LEHD have reasonably good generalization performance on TSP100.
One concern for the purely RL training for LEHD is the high computational cost and slow convergence speed, as analyzed in Table in the main paper. We design an efficient training method to tackle this concern explained in the next point.
B.3
An efficient self-improved training method for LEHD without any labeled solution
Finally, combining the properties from the above two points, can design efficient self-im self-improved training method without any labeled solutions for LEHD that can generalize well to large-scale problems. The three key steps
Train LEHD by reinforcement learning with reasonable computational budget;
Use LEHD+RRC to generate good solutions for set of problem instances;
Further train LEHD by supervised learning with the solutions generated in step 2.
The results of this new training method (LEHD-SI) can be found in Table 12 For the TSP, we first train LEHD by RL and use LEHD+RRC to generate solutions for 200, 000 TSP100 instances as labels for supervised learning. The training budget is 40 RI epochs and 185 SL epochs, which costs 2.7 days total. The entire training process on TSP does not require external solvers to generate labeled solutions.
15

---

Table 12: Experimental results on TSP. 'LEHD-SD SI means that the LEHD model is trained by the self-improved training method.
(10k instances) TSPI00
(Ik instances) TSPS00
TSP200
TSPI000
Concorde Att-GCNMMCTS*
0.000%
34m
0.000%
23m
0.000%
4h
0.000%
61h
0.037%
2h
0.884 %
16m
2.536%
47m
3.223%
1.7h
MDAM bs50
0.388%
21m
1.944%
23m
9.853%
1.4h
20.306%
5.8h
POMO augx8
0.134%
Im 1.459%
0.6m
21. 11.948%
8m
40.551% 1%
1.1h
SGBS
0.060%
40m
0.516%
30m
11.398%
7.3h
25.997%
58h
EAS
0.057%
6h 0.619%
3.6h
20.322%
61h
BQ greedy
0.579%
0.6m
0.892%
0.4m
1.862%
3m
3.895%
19m
BQ bsl6
0.046%
1 Im
0.221 %
6m
0.945%
46m
2.502%
4.8h
LEHD-SI greedy
1.073%
0.4m
1.445%
0.2m
2.583%
m
4.523%
13m
LEHD-SI RRC
100
0.053%
13.7m
0.18%%
6.5m
0.756%
58m
2.022%
5.3h
200
0.028%
27m
0.129%
12m
0.642%
1.721%
10.5h
LEHD greedy
0.577%
0.4m
0.849%
0.2m
1.585%
2.1m
3.089%
13m
LEHD RRC
0.0284%
7.4m
0.110%
3m
0.475%
31m
1.400%
3.1h
100
0.0114%
13.7m
0.053%
6.5m
0.357%
58m
1.195%
5.3h
1000
0.0016 %
2.2h
0.015
1h
0.179% %
9.5h
0.735%
57h
According the results, with such a training method, LEHD+RRC can still obtain good generalization performance on TSP instances with up to 1, 000 nodes with reasonable inference time. Notably, it can outperform the very strong BQ (with bs16) method trained by supervised learning, especially on large-scale problem instances. The performance of LEHD can be further improved if more computational budget is available.
In summary, LEHD can be efficiently trained without any already labeled (nearly) optimal solutions. Therefore, it is possible extend LEHD to tackle other practical CO problems where the optimal solution is hard to obtain. We will investigate how to design an even more efficient training method for LEHD well apply LEHD solve other CO problems in future work.
C Implementation Details for TSP
C.1 Problem Setup
The task of solving a TSP instance with n nodes involves finding the shortest loop that visits each node exactly once and eventually returns to the first visited node. We generate TSP instances following the approach in Kool et al. (27]. where the coordinates n nodes are sampled uniformly at random from the unit square.
C.2 Implementation Details
For TSP instance S, the node features (s1,..., S,,) are the 2-dimentional coordinates of the nodes in the graph.
In the original AM decoder, irrelevant nodes masked during each construction step. In our model, we remove the embeddings of irrelevant nodes from the decoder input. This removal serves the same purpose as masking them in every decoder attention layer but also saves computational resources since the decoder is not required to perform computations related to irrelevant nodes. Consequently, for each construction step, the input node embeddings for the decoder only consist of the starting node embedding, the destination node embedding, and the available node embeddings.
Here is an extended explanation Equation i the case of TSP. After attention layers, (0) is transformed to (L), Each vector Ni(2) E de (i (f 1 or 2) is transformed into scalar u, by applying the linear projection Wo E Rddxx1 x1 (i.e., u4 Wo where de is the embedding dimension. Then p' softmax(u u) is calculated.
16

---

D Implementation Details for CVRP
D.1 Problem Setup
A CVRP instance involves n customer nodes and one depot node, with each customer node having specific demand ó; that must be fulfilled. We aim determine set of sub-tours starting and ending at the depot such that the sum of demand satisfied by each sub-tour is within the capacity constraint D of the vehicle. Given the capacity constraint D, the objective to minimize the total distance of the set of sub-tours. Similarly, following Kool et al. [27]. we generate CVRP instances where the coordinates of customer nodes and depot nodes are sampled uniformly from the unit square. The demand 5, is sampled uniformly form {1, (.,....9) The vehicle capacities, denoted by D, are 50, 80, 100, and 250 for corresponding values of N. which are 100, 200, 500, and 1000, respectively.
,9).
Following Kool et al. (28) and Drakulic et al. [2]. we define the formation of a feasible solution for CVRP. Rather than treating a visit to the depot as separate step, we use binary variables indicate whether a customer node is reached via the depot or another customer node. Specifically, in a feasible solution, a node is assigned value of if it is reached via the depot and a value of if reached through another customer node.
For example, feasible CVRP solution (0, 1, 0, 4, 0, 7,03 be denoted as follows:
where 0 represents the depot, can
1
2
3
4
5
6
7 0
1
1
In this notation, the first row represents the sequence of visited nodes in the solution, and the second row indicates whether each node is reached via the depot or another customer node.
The purpose of using this notation the same number of customer nodes may have varying numbers of sub-tours, leading to potential misalignment. By employing this notation, we can avoid such issues.
ensure solution alignment. In CVRP instances. solutions with
D.2 Implementation details
For CVRP, the node feature 8; is represented as 3-dimensional vector, comprising the 2-dimensional coordinates and the demand of node i. The demand of the depot assigned value of 0. Without
loss of generality, we normalize the vehicle capacity D D 1, and the demand 8; to 8, 6: (27].
In the decoder, the dynamically changing remaining capacity is added to both the starting node and destination node embeddings, resembling the approach employed in Kwon al. (2)] Similar to TSP, the irrelevant node embeddings are excluded from the decoder input.
Here an extended explanation of Equation in the case of CVRP. After L attention layers, 0 transformed (1), Each vector h E R (i * 1 or 2) is projected to a 2-dimensional vector u; using the linear projection Wo E Rd.x2 ( (i.. u, = Woh(") where de is the embedding dimension. Each u, corresponds to two actions associated with the node either being reached via
the depot or another customer node. This relation corresponds to the notation mentioned in equation
4 Subsequently, is flattened, and the softmax utilized to compute the probability associated with each possible action.
17

---

E Solution Visualizations
shows the results on TSPLib and CVRPLib instances with different sizes and distributions. For TSPLib, we report the results on 2D Euclidean TSP instances with sizes smaller than 5000 (up 4461). For CVRPLib, we report the results on the 2D Euclidean instances without additional constraints such as time windows.
Figures 3 show the solutions of "pr2392" instance in TSPLib. Figures show the solutions of "X-n100T-k43" instance in CVRPLib. For each figure, panel (a) shows the optimal solution, and panel (b), (c), and (d) shows the solution generated by POMO, BQ, and LEHDD, respectively.
E.1
Solution visualizations of two TSPLib instances
(a) Optimal solution
(b) POMO x gap 69.6%
(c) BQ bs16: gap 29.4%
(d) LEHD RRC1000: gap 5.5%
Figure 3: Instance pr2392 with 2392 nodes.
18

---

E.2 Solution visualizations of two CVRPLib instances
(a) Optimal solution
(b) POMO aug gap 24.8%
(c) BQ 1s16: gap 6.9%
(d) LEHD RRC1000: gap 2.9%
Figure 4: Instance X-n1001-k43 with 1000 nodes
19

---

Licenses
Table 13: List of licenses for the codes and datasets we used in this work
Resource
Type
Link
License
OR-Tools
Code
https//gitubb.oom/gggllooooooo
Apache License 2.0
LKH3 16
Code
http://weeblott//rru.dd/ Leldhessarc//LKHH3
Available academic research
HGS 50
Code
MIT License
3-Clause
POMO 29
Code
https///ithhh..com//// kwon/POMO
MIT License
http::/gihhhh.coo//aee///
AI-GCCRNMCCS
EAS 10
Code
https///iihuub.oo. wttp:ubbbcm/hhoottunnEA...
Available online
SGBS 8
https:/gidhub..cmm httpg//hu...ucoyy///oo///SSSS
MIT License
TSPLib
Dataset
http://ormppl ifi uni hei.ballee...eballaaaeSSSSS.....
Available any commercial use
CVRPLi
Dataset
https//erp galgos inf puc rio. hi..rriiohhinddexphppeeen
Availahle academic research use
The licenses for the codes and the datasets used in this work are listed in Table 33
20


Reviews:
[{"review_id": "I5oF4BidwU", "reviewer": "Reviewer_Hd9p", "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.", "questions": "1. How did you train on small-scale problem instances? Is the \"small-scale problem instances\" means the \"argument data\" you generated? \n\n2. 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?", "limitations": "N.A.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The presentation of this manuscript was great, and I enjoy reading this paper.\n\n2. 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time and effort in reviewing our work. We are glad to know you enjoy reading our paper, find our method simple yet effective to tackle large-scale routing problems, and believe this work would be very insightful for the community. \n\nWe address your concerns as follows. \n\n> **W1/Q1. Training Details:** 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?\n\nThank you for raising this concern. We make the following clarification:\n\n**Small-Scale Problem:** We call a problem with no more than 100 nodes a small-scale problem (e.g., TSP50/100 and CVRP50/100), and a problem with at least 500 nodes a large-scale problem (e.g., TSP500/1000, CVRP500/1000).\n\n**Small-Scale Problem Instances:** Each problem (e.g., TSP100) can have infinite different instances with different node distributions, where each one is a concrete graph with a specific number (e.g., 100) of nodes. Each instance is a data point we consider for model training or inference. In the experiment, we randomly generate 1 million TSP100 instances and 1 million CVRP100 instances to train the LEHD model for TSP and CVRP separately. \n\n**Argumented Data from Partial Solution:** For a routing problem instance $\\mathbf{S}$, its optimal solution can be represented by a specific node sequence $\\mathbf{x}$ (also called the tour). A partial solution $\\mathbf{x}\\_{sub}$ is a consecutive subsequence of $\\mathbf{x}$. We call the nodes corresponding to $\\mathbf{x}\\_{sub}$ the augmented data of the original instance $\\mathbf{S}$.  For example, a TSP10 instance $\\mathbf{S} \\subset \\mathbb{R}^{2\\times 10}$ consists of $10$ nodes, and each column is the coordinates of the node. Its optimal solution $\\mathbf{x}$ is a permutation of the ten nodes, e.g., $\\mathbf{x}=[8,7,9,1,4,5,3,6,2,0]$. The partial solution $\\mathbf{x}\\_{sub}$ is a consecutive subsequence sampled from $\\mathbf{x}$ with a random size and direction. For example, $\\mathbf{x}\\_{sub}$ can be $[6,3,5,4,1]$ or $[1,4,5,3,6]$ if its size is five. The partial solution $\\mathbf{x}_{sub}$ along with its correponding nodes is one augmented data point in our method.  \n\n**Model Training with Partial Solutions:** The model learns to construct the partial solution node by node. The first node of $\\mathbf{x}\\_{sub}$ is the starting node, the last one of $\\mathbf{x}\\_{sub}$ is the destination node, and the remaining nodes constitute the available nodes to be selected by the model. For the example $\\mathbf{x}\\_{sub}=[6,3,5,4,1]$, node $6$ is the starting node, node $1$ is the destination node, and nodes $3,5,4$ are available nodes. \n\nIn each training step, the model provides each available node $s\\_i$ with a probability $p\\_i$ of being selected. Meanwhile, the label $\\mathbf{x}\\_{sub}$ tells whether the node $s_i$ should be chosen in the current step (i.e., $y\\_i = 1$ or $0$). The cross-entropy loss $loss = -\\sum\\_{i=1}^{u} y\\_i \\log(p\\_i)$ is employed. Then the Adam optimizer computes gradients based on the loss and updates the model's parameters. Throughout the training process, the number of available nodes gradually decreases, and the starting node dynamically shifts to the node selected in the previous step while the destination node remains constant. The training epoch ends when there are no more nodes available. The next epoch starts with new augmented data.\n\nThis data-efficient training method enables our powerful LEHD model to be trained on small-scale problem instances and then generalize well to much larger problem instances. We will carefully revise the algorithm section to make the training details clear and easy to follow, and also add an intuitive example in the appendix for better illustration.\n\n> **Q2. Other Works for Large-Scale TSP:** 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?\n\n|               |   | TSP1000 (128 instances) |      |\n|---------------|---|:-----------------------:|:----:|\n| Concorde      |   |         0.000\\%         | 7.8h |\n| H-TSP with LKH3        |   |          4.06\\%         |  7.5m |\n| LEHD greedy   |   |         3.168\\%         | 1.6m |\n| LEHD (RRC100) |   |         1.218\\%         |  43m |\n\n|               |   | (128 instances) |      |         |      |         |      |\n|---------------|---|:---------------:|:----:|:-------:|:----:|:-------:|:----:|\n|               |   |      TSP200     |      |  TSP500 |      | TSP1000 |      |\n| Concorde      |   |   0.000\\% | 3m| 0.000\\% |  32m | 0.000\\% | 7.8h |\n| SO-mixed      |   |   0.636\\%  | 21m | 2.401\\% |  32m | 2.800\\% |  56m |\n| LEHD greedy   |   |   0.859\\%  | 3s  | 1.560\\% | 0.3m | 3.168\\% | 1.6m |\n| LEHD (RRC100) |   |   0.0761\\% |1.2m | 0.343\\% |  8m  | 1.218\\% |  43m |\n\nThank you for this valuable suggestion. \n\nThe existing works [7,40] are search-based/improvement-based methods that require powerful solvers like LKH3 or specifically designed heuristics, and can only tackle TSP but not other VRP variants. In this work, we propose a purely learning-based construction method to tackle the large-scale TSP/VRP instances, and hence mainly compare with other construction-based methods in the original paper.\n\nFollowing your suggestion, we will add a comparison with these methods for a more comprehensive experimental study. Some preliminary results are reported in the above table. It is clear that our proposed method can outperform those methods both in performance and running time. It highlights the effectiveness and usefulness of our proposed LEHD+RRC as a purely learning-based method to tackle large-scale problems.\n\n[7] Select and optimize: Learning to solve large-scale tsp instances. AISTATS 2023.\n\n[40] H-TSP: Hierarchically solving the large-scale traveling salesman problem. AAAI 2023."}, {"review_id": "xbF7jRfGxF", "reviewer": "Reviewer_6SQz", "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.", "questions": "1. What is \"w\" in the experiments? Does it also a random number?\n2. For generalizing LEHD to unseen large-scale problems, how does LEHD construct the whole solution? \n3. 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.\n4. Are the solutions obtained by HGS optimal solutions? To my knowledge, HGS is a meta-heuristic method.\n\n", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The motivation and training process is clear and easy to read.\n2. 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.\n3. 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.\n2. The proposed method might be limited in simple VRPs, since obtaining optimal labeled solutions for more complex VRP variants is hard.\n3. The LEHD does not show much superiority to HGS.\n4. The presentation of this paper needs to be further improved. Some details are not clearly described and there are some typos.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time and effort in reviewing our work. We are glad to know you find our work has a clear motivation and is easy to read, the proposed LEHD is novel and can generalize well to problems with various sizes, and has sufficient and promising experiment results especially on large-scale TSP and CVRP.\n\nWe address your concerns as follows. \n\n> **W1. Training Time**\n\n|      |   | Training time  on CVRP |          |\n|------|:-:|:----------------------:|:--------:|\n| POMO |   |    30500 epochs      | 13.6days |\n| BQ  |   |       1000 epochs      | 1.6 days |\n| LEHD |   |        40 epochs       | 2.0 days |\n\nWe totally agree the training time is also important for comparing different methods. Our LEHD model has a comparable running time with the BQ model, while both are much shorter than the POMO training. For CVRP, the training time is roughly 2 days for LEHD, 1.6 days for BQ, and 13.6 days for POMO.\n\nWe will add the training time for the learning-based methods in the main paper for a clear comparison.\n\n> **W2. Limitation to Simple VRP**\n\nThank you for raising this important concern. In short, LEHD can be efficiently trained without any already labeled solutions, and hence it is possible to extend LEHD to tackle complex VRP. \n\nPlease see our general response to all reviewers (C2) for a detailed discussion. We will add the new results and discussions to the revised paper.     \n\n> **W3. Comparison to HGS**\n\nWe agree with the reviewer that LEHD cannot outperform HGS especially on large-scale CVRP instances. However, we want to point out that HGS is a very powerful and currently state-of-the-art heuristic solver for CVRP [1,2], and outperform all the current learning-based solver with a large gap. Indeed, HGS has served as the benchmark algorithm in many competitions [3,4]. However, HGS requires a specific algorithm design with expert knowledge. \n\nManually designing efficient algorithms to tackle different combinatorial optimization problems (such as complex VRP variants) could be extremely hard. One fundamental motivation for neural combinatorial optimization is to get rid of any handcrafted design to solve CO problems. \n\nAs a purely end-to-end learning-based construction method, LEHD has significantly better performance than other neural combinatorial optimization methods. Further experimental studies confirm that LEHD can also significantly outperform other scalable NCO methods that require manually designed solvers for specific problems (see our response to **Q2 for Reviewer Hd9p**). We believe our prosed LEHD model can serve as a strong neural combinatorial optimization baseline for large-scale TSP/CVRP, and inspire more follow-up works from the research community.\n\n[1] A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research 2012.\n\n[2] Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood. Computers \\& Operations Research 2021.\n\n[3] DIMACS VRPTW challenge, 2021\n\n[4] EURO Meets NeurIPS Vehicle Routing Competition, NeurIPS 2022 \n\n> **W4. Presentations and Typos**\n\nThank you for pointing this out. We will carefully revise our paper to improve the presentation and fix all the typos. More details of the LEHD model, the training algorithm, and the RRC method will be provided in the main paper.\n\n> **Q1. What is \"w\" in the experiments? Does it also a random number?**\n\nYes, \"w\" is a random number that represents the length of the partial solution that will be constructed by the LEHD model at each step. We uniformly sample $w \\sim \\textbf{Unif}([4, |V|])$ where $|V|$ is the number of nodes for each TSP/CVRP instance in all experiments. \n\n> **Q2.  For generalizing LEHD to unseen large-scale problems, how does LEHD construct the whole solution?**\n\nOur LEHD model employs a greedy step-by-step approach to construct the whole solution for the given instance $\\mathbf{S}$.\n\nIn the beginning, a random node is used as both the starting and destination point, and the remaining nodes constitute the available nodes that the model can select step-by-step. Once a node is selected, it will be treated as the new starting node and removed from the set of available nodes, i.e., the starting node is dynamically shifting while the destination node remains constant. When no more available nodes exist, the whole solution is generated. In this way, LEHD can easily construct solutions for problems of various sizes as well as unseen large-scale problems. Once a solution is constructed, the RRC method can be applied to further enhance the solution's quality.  \n\nWe will carefully revise the training algorithm subsection and add more training details in the experiment section.\n\n> **Q3. Why not apply \"sampling\" strategy on POMO with the same iterations of RRC?**\n\nThank you for this valuable suggestion. We have now conducted comparison with POMO with random sampling (POMO-Sample 100) as well as POMO with RRC (POMO-RRC100) to clearly present the advantages of LEHD and RRC. \n\nThe experimental results are shown in Table 1 (please see the **PDF file in General Response**), and we have the following two main observations:\n\n- **POMO-RRC > POMO-Sample:** The random sampling strategy is inefficient in improving POMO's solution quality, especially for large-scale problems. In contrast, our proposed RRC can also efficiently improve POMO's performance at inferent time.\n\n- **LEHD-RRC > POMO-RRC:** Our proposed LEHD model structure provides enough model capacity for learning to construct partial solutions for different sizes. It is crucial for the strong generalization ability to large-scale problems.\n\nWe have now added the POMO augx8 (sampling 100) results into the revised Table 1. The revised Table 1 and the ablation study (LEHD-RRC v.s. POMO-RRC) will both be added to the revised paper.\n\n> **Q4. Solution Quality of HGS**\n\nHGS is a powerful and currently state-of-the-art heuristic solver for CVRP, please see the above detailed response to W3."}, {"review_id": "kJ6GKF6A0Q", "reviewer": "Reviewer_8Nbk", "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.", "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.\n\nPlease also see the discussion of weaknesses.", "limitations": "Please see above.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "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.\n\n2.The empirical results are promising especially for the generalization ability.\n\n3.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.\n\n[1] Generalize Learned Heuristics to Solve Large-scale Vehicle Routing Problems in Real-time. ICLR 2023.\n\n[2] Learning to Delegate for Large-scale Vehicle Routing. NeurIPS 2021.\n\n2.The RCC algorithm does not learn to select regions for local improvement, instead randomly enforcing the local policy, which hampers its efficiency.\n\nMinor:\n\n1.Line 166: refind -> refine.\n2.Line 224: construction-base -> construction-based.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time and effort in reviewing our work. We are glad to know you find our proposed method design is insightful and logical, the empirical results are promising especially for the generalization ability, and the paper is well-structured and easy to follow.\n\nWe address your concerns as follows. \n\n> **W1. RRC and Other Divide-and-Conquer Methods**\n\nThank you for pointing out these related works. \n\nDivide-and-conquer strategy is indeed a principled way to deal with large-scale methods. These existing works focus on learning how to decompose a large CVRP instance into multiple smaller subproblems, and then use specific and carefully designed solvers (e.g., LKH3) to tackle each subproblems. Since these two methods are specifically designed for CVRP, they cannot be used for TSP and other variants. In contrast, our proposed LEHD is an end-to-end and purely learning-based construction method.\n\nWe are currently unable to reproduce the results for [1,2], but we have shown that LEHD can significantly outperform other learning-based methods on large-scale TSP (please see our response to **Q2 for Reviewer Hd9p**). In addition, we have also conducted a new experiment to compare POMO-RRC and LEHD-RRC. The results confirm that while RRC can also efficiently improve POMO's performance, the LEHD model structure itself is crucial for the promising generalization performance on large-scale TSP/CVRP instances (please see our response to **Q3 for Reviewer 6SQz**).  \n\nWe will add a discussion with [1,2] in the revised paper, and report the comparison results with analysis in the experiment section.\n\n[1] Generalize Learned Heuristics to Solve Large-scale Vehicle Routing Problems in Real-time. ICLR 2023.\n\n[2] Learning to Delegate for Large-scale Vehicle Routing. NeurIPS 2021.\n\n> **W2. Random Selection for RRC**\n\nTotally agree. In this work, we have shown that our proposed LEHD model with simple random RRC can achieve very promising generalization performance on large-scale TSP/CVRP instances. More advanced learning-based region selection methods (such as those in [1,2]) could be very helpful to further improve the performance of RRC. We will explore this extension in future work.\n\n> **W3. Typos**\n\nThank you for pointing out these typos and they have now been fixed. We will carefully proofread the whole paper to further improve the writing and fix all the typos we can find.\n\n> **Q1. Why is LKH not included in Table 1?**\n\nThank you for this suggestion, and we have now added the LKH3 results in Table 1 (please see the revised Table 1 in the **PDF file in General Response**). LKH3 can obtain optimal solutions for all TSP instances as expected, and its runtime is a bit longer than the very powerful Concorde solver for TSP.\n\nWe will update Table 1 along with more discussion of the new results in the revised paper.\n"}, {"review_id": "w7fVsb3btw", "reviewer": "Reviewer_6PbV", "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).\n\nThe 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.", "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.\n\n**Q2.** How to select partial solution to perform update in RPC?\n\n**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.\n\n**Q4.** Publication information of reference [56] is missed.\n", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**S1.** The architecture of Heavy Decoder Model to yield optimal outputs across a range of node sizes\n\n**S2.** Showing promising experimental results on large-scale TSP and CVRP instances\n\n**S3.** Well-written and easy to read", "weaknesses": "**W1.** Weak novelty of training method and RPC\n\n**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.\n\n**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. \n\n**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.\nexperiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time and effort in reviewing our work. We are glad to know you find our proposed heavy decoder model to learning the state of various node sizes is promising, have promising experimental results on large-scale TSP and CVRP instances, and the paper is well-written.  \n\nWe address your concerns as follows. \n\n> **W1. Weak novelty of training method and RRC**\n\nThank you for raising this concern. \n\nThe proposed data-efficient training method is important for efficiently learning the heavy decoder model for construction-based NCO. It can be further improved to get rid of the requirement of optimal solutions for efficient training (see the next response).\n\nWe have conducted additional experiments to show that  RRC can also improve the POMO performance (see **Q3 for Reviewer 6SQz**), and the construction + RRC approach can outperform some currently proposed divide-and-conquer methods specially designed for TSP (see **Q2 for Reviewer Hd9p**). We will investigate how to further improve RRC (e.g., with learning-based partial solution selection) in future work.\n\n> **W2. Requirement of Optimal Solution**\n\n> **W3. Performance Upper Limit**\n\nThank you for raising these two important concerns. In short, LEHD with RRC can break the performance upper limit of the labeled solutions, and LEHD can be efficiently trained without any already labeled solutions.   \n\nPlease see our **General Response (C2)** for a detailed discussion. We will add the new results and discussions to the revised paper.  \n\n> **W4. Number of Test Instances** \n\nThank you for this valuable suggestion. We have now updated Table 1 to report the results with 1k instances for instances with 200 or more nodes. The relative performance among all methods does not change, and the analysis/discussions we have made are still valid.\n\nThe revised Table 1 can be found in the **PDF file in General Response**, and will be incorporated into the revised paper. \n\n>**Q1. Inference Time Comparision with POMO**\n\n|                    |   |  TSP100 |      |  TSP200 |       |  TSP500  |      |  TSP1000  |      |\n|--------------------|---|:-------:|:----:|:-------:|:-----:|:--------:|:----:|:---------:|:----:|\n| Concorde           |   | 0.000\\% |  34m | 0.000\\% |  23m  |  0.000\\% |  4h  |  0.000\\%  |  61h |\n| POMO single trajec |   | 0.875\\% |  3s  | 4.250\\% |   2s  | 33.969\\% |  5s  |  52.429\\% |  11s |\n| POMO no augx8      |   | 0.364\\% |  9s  | 2.170\\% |   6s  | 23.984\\% |  1m  |  42.189\\% |  8m  |\n| POMO augx8         |   | 0.134\\% |  1m  | 1.459\\% |  0.6m | 21.948\\% |  8m  |  40.551\\% | 1.1h |\n| LEHD greedy        |   | 0.577\\% | 0.4m | 0.849\\% |  0.2m |  1.585\\% | 2.1m |  3.089\\%  |  13m |\n|                    |   | CVRP100 |      | CVRP200 |       |  CVRP500 |      |  CVRP1000 |      |\n| HGS                |   | 0.000\\% | 4.5h | 0.000\\% |  11h  |  0.000\\% |  31h |  0.000\\%  |  41h |\n| POMO single trajec |   | 3.162\\% |  3s  | 9.376\\% |   2s  | 35.371\\% |  6s  | 306.959\\% |  14s |\n| POMO no augx8      |   | 1.216\\% |  12s | 6.035\\% |   7s  | 30.143\\% | 1.2m | 285.635\\% |  10m |\n| POMO augx8         |   | 1.229\\% |  1m  | 5.192\\% |  0.7m | 22.963\\% |  9.4m  |  144.230\\% | 1.3h |\n| LEHD greedy        |   | 4.170\\% | 0.5m | 4.612\\% | 0.23m |  5.214\\% | 2.2m |  8.594\\%  |  13m |\n\nYes, the reason why HELD (POMO) is slower is because of 'augx8'. We have now included the results of POMO with only a single trajectory (POMO-single-trajec) and regular POMO without augmentation (POMO-no-augx8) for both TSP and CVRP instances in the revised Table 1 which can be found in the **PDF file in General Response**. We also report the runtime comparison in the above table.  According to the results, for TSP1000, the run time for POMO with single trajectory/without augx8/with augx8 are 11s/8m/1.1h, separately, and the run time for LEHD is 13m.\n\nFor a problem instance with 1,000 nodes, POMO with a single trajectory only needs to construct 1 path at a time (e.g., like the original AM), POMO without augx8 needs to construct 1,000 paths simultaneously (1,000 different starting nodes), and POMO with augx8 needs to construct 8,000 paths simultaneously. Our proposed LEHD-greedy only needs to greedily construct 1 path at a time, although the decoder requires 1,000 operations. This is the reason why LEHD can be faster than HELD(POMO/AM) aug$\\times$8. \n\nWe will add the above analysis in the revised paper.\n\n> **Q2. How to select partial solution to perform update in RRC?**\n\nIn the current method, we randomly sample the partial solution for the RRC update. The experiment results show that LEHD with simple random RRC can already achieve very promising generalization performance on large-scale TSP/CVRP instances. More advanced learning-based region selection methods could be very helpful to further improve the performance of RRC. We will explore this extension in future work.\n\n> **Q3. HGS as Baseline for CVRP**\n\nThank you for this good suggestion. We have now updated Table 1 accordingly with HGS as GAP 0. \n\nThe revised Table 1 can be found in the **PDF file in General Response**, and will be incorporated into the revised paper. \n\n> **Q4. Publication information of reference [56] is missed.**\n\nThank you for pointing this out. We have now fixed the publication information of reference [56] as:\n\n[56] Shunyu Yao, Xi Lin, Zhenkun Wang, and Qingfu Zhang. Data-efficient supervised learning is powerful for neural combinatorial optimization. ICLR 2023 Submission. URL: openreview.net/forum?id=a\\_yFkJ4-uEK.\n"}]

Author rebuttal:
**General Response**

Dear AC and Reviewers,

We sincerely thank you for your time and effort in reviewing our work. We are glad to know the reviewers enjoy reading our paper  or find it easy to follow (**Hd9p**, **6SQz**, **8Nbk**, **6Pbv**), our method is effective (**Hd9p**) /novel (**6SQz**) /insightful (**8Nbk**) /promising (**6PbV**), has promising generalization performance on large-scale problems (**Hd9p, 6SQz, 8Nbk, 6PbV**), and believe this work could be very insightful to the community (**Hd9p**).

We address some common concerns shared by different reviewers in this response.

> **C1. More Experimental Results**

Following your valuable suggestions, we have put more experimental results in Table 1. The revised Table 1 is attached to this comment and will be added to the revised paper.

Detailed discussions of these new results can be found in the responses to each individual reviewer.

> **C2. Will the requirement of optimal solutions for LEHD training make it hard to solve more complex VRPs? Will the performance of LEHD upper bounded by the provided (nearly) optimal solutions?**

For a better discussion, we tackle these two concerns in a reverse order. 

**1. RRC can break the performance upper limit of the labeled solution**

Firstly, the performance of our proposed LEHD model with RRC is not limited by the quality of labeled solutions. To demonstrate this point, we train a new LEHD model with labeled solutions generated by OR-Tools of which the quality is far from the optimal solutions (e.g., with a 6.762% optimal gap). The results are shown in the following table:

|           |         | CVRP100  |      |
|-----------|:-------:|:--------:|:----:|
| HGS       |         |  0.000\% | 4.5h |
| OR-Tools  |         |  6.762\% |  2h  |
| LEHD      |  greedy | 10.428\% | 0.5m |
|           |  RRC 20 |  6.249\% |  3m  |
|           |  RRC 50 |  4.811\% |  7m  |
|           | RRC 100 |  3.915\% |  17m |
|           | RRC 300 |  2.862\% |  52m |
|           | RRC 500 |  2.525\% | 1.4h |

In this experiment, we use OR-Tools to generate suboptimal solutions for $100,000$ CVRP100 instances, and use them to train the LEHD model with only 10 epochs (about $1.25$ hours). Then we compare their performance on the same test set with 10k instances. According to the results, although LEHD with greedy inference is outperformed by OR-Tools, LEHD+RRC can significantly outperform OR-Tools. If more training budget is available, the performance of LEHD(+RRC) can be further improved. 

This result also demonstrates the effectiveness of RRC in our proposed method.

**2. LEHD can be trained by RL without any labeled solution**

Secondly, it is possible to directly train the LEHD model using reinforcement learning without any labeled data. Experimental results can be found in the following table:

|          |        | (10k instances) |      |         |      |
|----------|:------:|:---------------:|:----:|:-------:|:----:|
|          |        |      TSP20      |      | TSP100  |      |
| Concorde |        |     0.000\%     |  3m  |   0\%   |  34m |
| LEHD-RL  | greedy |     0.274\%     |  2s  | 5.463\% | 0.4m |
|          | RRC100 |     0.014\%     | 0.6m | 1.271\% |  13m |
|          | RRC200 |     0.006\%     | 1.2m | 0.983\% |  26m |
|          | RRC300 |     0.005\%     | 1.7m | 0.865\% |  40m |
|          | RRC500 |     0.003\%     |  3m  | 0.740\% | 1.1h |

Here, we train the LEHD model by RL on the small-scale TSP20 instances, and then test its generalization performance on TSP100. The training budget is 40 epochs each with 100,000 instances on TSP20 (roughly 9 hours). According to the results, LEHD can achieve nearly optimal solution for TSP20, and RRC enables LEHD to have a reasonably good generalization performance on TSP100. 

One concern for the purely RL training for LEHD is the high computational cost as analyzed in Table 4 in the main paper. We design an efficient training method to tackle this concern in the next point. 

**3. An efficient self-improved training method for LEHD without any labeled solution**

Finally, combing the above two points, we can design an efficient self-improved method without any labeled solutions to train LEHD that can generalize well to large-scale problems. The three key steps are:

- Step 1. Train LEHD by reinforcement learning with a reasonable computational budget;

- Step 2. Use LEHD+RRC to generate good solutions for a set of problem instances; 

- Step 3. Further train LEHD by supervised learning with the solutions generated in step 2;  

Results of this method (LEHD-SI) can be found in the revised Table 1 (see attachment). For TSP, we first train LEHD by RL and use LEHD+RRC to generate solutions for 200,000 TSP100 instances as labels for supervised learning. The training budget is 40 RL epochs and 185 SL epochs, which costs 2.7 days in total. For CVRP, the training budget is 80 RL epochs and 70 SL epochs, which cost 2.5 days in total. The entire training process on TSP and CVRP does not require external solvers to generate labeled solutions.

According to the results, LEHD-SI-RRC can still obtain good generalization performance on TSP/CVRP instances with up to 1,000 nodes with a reasonable inference time. Notably, it can outperform the very strong BQ (with bs16) method trained by supervised learning, especially on large-scale problem instances. The performance of LEHD-SI can be further improved if more computational budget is available. 

**In summary**, LEHD can be efficiently trained without any already labeled (nearly) optimal solutions. Therefore, it is possible to extend LEHD to tackle other practical CO problems where the optimal solution is hard to obtain. We will investigate how to design an even more efficient training method for LEHD as well as apply LEHD to solve other CO problems in future work. All the above discussion will be carefully added into the revised paper.

Best Regards,

Paper8077 Authors

Meta-review: The paper leads to an important direction for machine learning for combinatorial optimization (CO): increasing the capacity of the decoder to handle large-scale CO problems. The reviewers found the paper was clearly motivated and well written with convincing experimental results. Also, the technical novelty is good. The authors have addressed the reviewers' questions and all the reviewers gave positive ratings to this paper. Based on these facts and also based on my personal rating, I suggest accepting this paper.
Decision: Accept (poster)