Efficient Meta Neural Heuristic for Multi-Objective Combinatorial Optimization
Authors: Jinbiao Chen
Jiahai Wang
Zizhen Zhang
Zhiguang Cao
Te Ye
Siyuan Chen
Venue: NeurIPS 2023 poster (2023)
Keywords: neural heuristic
meta learning
deep reinforcement learning
multi-objective combinatorial optimization
TL;DR: We propose an efficient meta neural heuristic for multi-objective combinatorial optimization problems

Abstract: Recently, neural heuristics based on deep reinforcement learning have exhibited promise in solving multi-objective combinatorial optimization problems (MOCOPs). However, they are still struggling to achieve high learning efficiency and solution quality. To tackle this issue, we propose an efficient meta neural heuristic (EMNH), in which a meta-model is first trained and then fine-tuned with a few steps to solve corresponding single-objective subproblems. Specifically, for the training process, a (partial) architecture-shared multi-task model is leveraged to achieve parallel learning for the meta-model, so as to speed up the training; meanwhile, a scaled symmetric sampling method with respect to the weight vectors is designed to stabilize the training. For the fine-tuning process, an efficient hierarchical method is proposed to systematically tackle all the subproblems. Experimental results on the multi-objective traveling salesman problem (MOTSP), multi-objective capacitated vehicle routing problem (MOCVRP), and multi-objective knapsack problem (MOKP) show that, EMNH is able to outperform the state-of-the-art neural heuristics in terms of solution quality and learning efficiency, and yield competitive solutions to the strong traditional heuristics while consuming much shorter time.

Efficient Meta Neural Heuristic for Multi-Objective Combinatorial Optimization
Jinbiao Chen', Jiahai Wang -2.3,, Zizhen Zhang!." Zhiguang Cao*, Te Ye', Siyuan Chen
"School of Computer Science and Engineering, Sun Yat-sen University, P.R. China Key Laboratory of Machine Intelligence and Advanced Computing, Ministry of Education, Sun Yat-sen University, P.R. China
3 Guangdong Key Laboratory of Big Data Analysis and Processing, Guangzhou, P.R. China School of Computing and Information Systems, Singapore Management University, Singapore chenj b69@mai12 sysu. edu. en, {wangjiah 2hangzzh7] (aatrngzz2)))mmmaa @maalm.mypp edu. zgcao0smu. edu.sg, (yete, (hensy47)0mai12 sysu. edu. cn
Abstract
Recently, neural heuristics based on deep reinforcement learning have exhibited promise in solving multi-objective combinatorial optimization problems (MO- COPs). However, they are still struggling to achieve high learning efficiency and solution quality. To tackle this issue, propose efficient meta neural heuristic (EMNH), in which a meta- moetll is first trained and then fine-tuned with a few steps to solve corresponding single-objectivy subproblems. Specifically, for the training process, (partial) architecture-shaeed multi-task model is leveraged to achieve parallel learning for the meta-model, so speed up the training; meanwhile, a scaled symmetric sampling method with respect to the weight vectors is designed to stabilize the training. For the fine-tuning process, efficient hierarchical method is proposed to systematically tackle all the subproblems. Experimental results on the multi-objective traveling salesman problem (MOTSP), multi-objective capaci- tated vehicle routing problem (MOCVRP), and multi-objective knapsack problem (MOKP) show that, EMNH is able to outperform the state-of-the-ar neural heuris- tics in terms of solution quality and learning efficiency, and yield competitive solutions the strong traditional heuristics while consuming much shorter time.
Introduction
Multi-objective combinatorial optimization problems (MOCOPs) [1] are widely studied and applied in many real-world sectors, such telecommunication, logistics, manufacturing, and inventory. Typically, an MOCOP requires the simultaneous optimization of multiple conflccting objectives, where the amelioration of objective may lead to the deterioration of others. Therefore, set of trade-off solutions, known as Pareto-optimal solutions, are usually sought for MOCOPs.
Generally, it is difficult to exactly find all the Pareto-optimal solutions of an MOCOP [2], especially given that the decomposed single-objective subproblem might already be NP-hard. Hence, heuristic methods [3] are usually preferred to solve MOCOPs in reality, they can attain approximate Pareto-optimal solutions in (relatively) reasonable time. Nevertheless, the traditional heuristics are still lacking due their reliance handcrafted rules and massive iterative steps, and superfluous computation even for instances of the same (or similar) class.
Recently, inspired by the success of deep reinforcement learning (DRL) in learning neural heuristics for solving the single-objective combinatorial optimization problems (COPs) [4-7], a number of
"Jiahai Wang and Zizhen Zhang the corresponding authors.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

m iterations
Test instances
T, steps
Training
Fine- tunning instances
instances
head,
((2)
(1)
1
2
inni
0 body head
body
i head,
meta
0
0
(2)
2
0
Ñ symmetric
e head
N test weights
sampled weights
ON
A ccelerated meta- process
Hierachical fine-tuning process Inference process
Figure 1: The overall framework of EMNH.
DRL-based neural heuristics [8-13] have also been investigated for MOCOPs. While bypassing the handcrafted rules, these neural heuristics adopt an end-to-end paradigm to construct solutions without iterative search. Benefiting from a large amount data (i.e., problem instances), a well-trained deep model allows the neural heuristic to automatically extract informative and expressive features for decision making and generalize to unseen instances as well.
Although demonstrating promise for solving MOCOPs, those neural heuristics still struggle to achieve high learming efficiency and solution quality. Particularly, in this line of works, the early attempts [8-11] always train multiple deep models, i.e., one for each preference (weight) combination, making iinttrennce-onddttionn
multi-objeccive combinatorial optimization (PMOCO) [12] realized unified deep model by introducing a huge hypernetorrk, it leaves considerable gaps in terms of solution quality. The recent Meta- DRLa (MDRL) [13] has demonstrated the capability to enhance solution quality over existing state-of-the-art algorithms. However, still faces challenges related to inefficient and unstable training procedures, as well as undesirable fine-tuning processes. This paper thereby proposes efficient meta neural heuristic (EMNH) to further strengthen the learning efficiency and solution quality, the framework of which is illustrated in Figure 1. Following the meta-learning paradigm [13, 14], EMNH first trains meta-model and then quickly fine-tunes it according to the weight (preference) vector to tackle the corresponding single-objective subproblems.
them less practical. While the well-known
Our contributions are summarized as follows. (1) We propose an efficient meta-learning scheme to accelerate the training. Inspired by the feature reuse of meta-learning [15], we introduce a multi-task model composed parameter-shared body (all other layers neural network except the last one) and respective task-related heads (the last layer of the network), rather than respective submodels, to train the meta-model, which is able to handle different tasks (subproblems) parallel. (2) We design scaled symmetric sampling method regarding the weight vectors stabilize the training. In each meta- iteration, once a weight vector is sampled, its scaled symmetric weight vectors will also be engendered, which help avoid fluctuations of the parameter update for the meta-model, especially problems with objectives of imbalanced domains. (3) We present a hierarchical fine-tuning method to efficiently cope with all the subproblems. Since it is redundant derive specific submodel for each subproblem in the early tuning process, our meta-model can be gradually fine-tuned to act as specialized submodels from low level to high level. which takes much fewer fine-tuning steps in total. Moreover, experimental results on three classic MOCOPs confirmed the effectiveness of our designs.
2 Related works
Exact and heuristic methods for MOCOPs. Over the past decades, MOCOPs have been attracting increasing attention from the computational intelligence community, and tremendous works have been proposed. Generally, exact methods [2] are able gain the accurate Pareto-optimal solutions, but their computational time may exponentially grow. Heuristic methods such as multi-objective

---

evolutionary algorithms (MOEAs) are popular in practice, where the representative paradigms for the general multi-objective optimization include NSGA-II [16] and MOEA/D [17]. Among them, a number of MOFAs outfitted with local search [ [18-20] are specifically designed for MOCOPs, which iteratively perform a search in the solution space to find approximate Pareto-optimal solutions.
Neural heuristics for COPs. As the early attempts, neural construction heuristics based on deep models [21-23] were proposed to learn to directly construct solutions for (single-objective) COPs. Among them, the classic Attention Model (AM) [24] was proposed inspired by Transformer architec- ture [25], and known as milestone for solving vehicle routing problems. A number of subsequent works [26-30] were developed based on AM. including the popular policy optimization with multiple optima (POMO) [26], which leveraged the solution symmetries and significantly enhanced the perfor- mance over AM. Besides, graph neural networks were also employed to learn graphic embeddings for solving COPs [31-34]. Different from the above neural construction heuristics, neural improvement heuristics [35-39] were proposed to assist peration-based methods to refine an initial solution.
Neural heuristies for MOCOPs. MOCOPs seek for set of trade-off solutions, which could be obtained by solving a series of single-objective subproblems. According to the number of trained models, neural heuristics could be roughly classified into multi-model and single-model ones. The former adopts multiple networks to tackle respective subproblems, where the set of networks could also be collaboratively trained with a neighborhood -ased parameter- -rannsfrr strategy [8. 9], or evolved with MOEA [10, 11]. Differently, the latter usually exploits a unified network to tackle all the subproblems, which more flexible and practical. For example, taking the weight (preference) vector of subproblem as the input, PMOCO introduces hypernetwork to learn the decoder parameters [12]. However, the hypernetwork may cause extra complexity to the original deep reinforcement learning model, rendering it less effective to learn more accurate mapping from the preference to the optimal solution of the corresponding subproblem. By contrast, MDRL [13] leverages the meta-learning to train deep reinforcement learning model that could be fine-tuned for various subproblems. However, its learning efficiency is far from optimal, especially given the slow and unstable training due to sequential learning of randomly sampled tasks, and inefficient fine-tuning due to redundant updates.
3 Preliminary
3.1 MOCOP
In general, MOCOP could be defined
min fxx = ((())). (M,(()) TEA'
where f() is an M-objective vector, X' is a discrete decision space, and the objectives might be conflicted. The Pareto-optimal solutions concerned by decision makers defined as follows.
Definition 1 (Pareto dominance). Let u, E X, u said to dominate v (u < v) if and only fi(u) & fi()), Vi E (1,..., M) and 7j E {1,.... M), [u) < (r().
Definition 2 (Pareto optimality). A solution x: X' is Pareto-optimal if is not dominated by any other solution in X. i.e., dr' E X such that x' x x². The set of all Pareto optimal solutions P= fa* E X da E X: x' x**) is called the Pareto set. The image of Pareto set in the objective space, i.e., PF = (f(z) x E PJ is called the Pareto front.
3.2 Decomposition
The decomposition strategy is always applied for solving MOCOPs [17], since is straightforward yet effective to guide the search towards prescribed directions. Specifically, MOCOPs can be decomposed into N scalarized single-objective subproblem g(x| where the weight vector RM satisfies
Am 2 0 and ΣM -m=12 Am = Then, PF is approximated by solving the subproblems systematically.
Regarding the decomposition strategy, the weighted sum (WS) and Tchebycheff [40] are commonly used. As simple representative, WS considers the linear combination of M objectives as follows,
M
min Jws (ar) A)) = Σ Amfm(z).
(x|
x
m=1
3

---

Given the weight vector X, the corresponding single-objective subproblem could be cast as sequential decision problem and solved through DRL. In particular, a solution is represented
a sequence ( h with length T, and stochastic policy for yielding solution т from instance is calculated P(T]s) =
II (m | 1:t 11=-1110 8). where ( 8) the node selection probability parameterized by 0 (the subscript of 0. Ti P. for subproblem i is omitted for readability).
3.3 Meta-learning
Meta-learning [14, 41] aims to train a model that can learn to tackle various tasks (i.e., subproblems) via fine-tuning. Naturally, a meta-model can be trained to quickly adapt to N corresponding subprob- lems given N weight vectors. Generally, meta-learning comprises three processes for MOCOPs. In the meta-learning process, model @ is trained by repeatedly sampling tasks from the whole task space. In the fine-tuning process, N submodels ....... d based on the given weight vectors are fine-tuned from 0 using fine-tuning instances (also called query set). In the inference process, N subproblems of an instance are solved using the submodels to approximate the Pareto set.
4 Methodology
Our efficient meta neural heuristic (EMNH) includes an accelerated and stabilized meta-learning process, a hierarchical fine-tuning process, and an inference process, depicted in Figure 1. EMNH is generic, where we adopt the first-order gradient-based Reptile [14] as the backbone of meta- learning, and employ the popular neural solver POMO [26] as the base model. In our meta-learning process, the model 0 is trained with T.m meta-iterations. where a multi-task model is exploited to speed up the training and scaled symmetric sampling method is designed stabilize the training. In our fine-tuning process, the meta-model 0 is hierarchically and quickly fine-tuned with a few gradient updates to solve the corresponding subproblems. The details for each design are presented below.
4.1 Accelerated training
In the accelerated training process, as shown in Algorithm 1, the meta-model @ is trained with Ti meta-iterations. In each iteration, the model needs to be optimized by learning Ñ sampled tasks (subproblems) with Tu-step gradient updates. Inspired by the feature reuse of meta-learning [15], is unnecessary and expensive to serially update the meta-model through the Ñ respective submodels of the same architecture. On the other hand, it is reasonable to assume that only the head Onead is specified for a task, while the body Ohody can be reused for all tasks. To realize such a lightweight meta-learning scheme, we further introduce a multi-task model Ô which is composed of shared body and N respective heads to learn the Ñ tasks in parallel.
Specifically, since our EMNH adopts the encoder-dccoder structured POMO as the base model, as depicted in Figure 2(a), 1) Opead could be defined as the decoder head, i.c., W K E Rdxd in the last single-head attention layer, where d is empirically set to 128 [26]; 2) Obody could be composed of the whole encoder Oen and the decoder body 0 body- For a problem instance with nodes, the node
embeddings hi...., hn E Rd are computed by Pen at the encoding step. At each decoding step, the query q. Rd first computed by dddy using the node embeddings and problem-spor -ppeciffc context embedding he Then, the last single-head attention layer computes the probability of node selection Po ([()))) using qe and the key ki...., ........ kn E Rd, where ky for node i' is computed by 0head. i.e., h2 = W h2p More details are presented in Appendix A.
As demonstrated in Figure 2(b), for natural accommodation, the multi-task model Ô consists of @body and (head, ..., θ he where Gbody and 0head, have the same architecture as Obody and Ohead respectively. Note that Qpead, is individually updated for subproblem i, while @oody is shared for N tasks. Coneretely, since the subproblems captured by different weight vectors but the same (or similar) node features, the shared node embeddings computed by θ.n. At each decoding step, for subproblem the query qe is first computed by a Oddybody using the node embeddings and context embedding he Then, the key is computed as ky = w h, for node y' Finally, the single-head attention layer computes the probability of node selection Pa. (TT) [s) for subproblem i using qo, and ki, kn In practice, W.K.. ...., W are concatenated to tackle the N tasks in parallel.

---

Algorithm Accelerated training process
Input: initialized meta-model 0, number of symmetric sampled weight vectors N, initialized multi- task model 0, initial meta-learning rate number of meta-iterations Tm, number of update steps of the multi-task model Tu. batch size B, problem size n
1:
2: for im to I' do
3:
A; is obtained by the scaled symmetric sampling method,
Vi E (1...., N}
4: Obody body
5:
Onead, -- head, Vi
6:
for lu = 1 to Tw do
7:
8J Samplelnstance(())
E (l,..., B} E (L...., vi, Vj
8:
{ k 55. } ~ (oaipleeRolout(aa(
9:
bij =k=1 1s,
B
n
VL(0) - NBn ΣΣ
Uiaty Viog (T=
=
Ø <- Adam O VL(O))
12:
end for
i body body
i Onead t- heaad c( Σ/ 0 head,; headd)
15:
é t c co/Ti,
16: end for
Output: The trained meta-model 0
Node Feeture
Node Fosture
Solubios
LP
Solution
M
M
MILA
Maziond Softmax
H. Layend
xT Steps
Computiblliyy
ADD & BN
Lapers
Stape
Comput billty
At
EF
MILA 1oe besty!
Wy
ADD &
Om
(6read)
ADD & BN
Ma texty?
68
A-V
Encodee
Decodae
Encoder
Decodee
(a)
(b)
Figure 2: Model architectures. (a) Base model (POMO). (b) Multi-task model.
We extend REINFORCE [42] train the multi-task model Ô, including Gbody for all tasks and Ohead for task Specifically, Ô is optimized by gradient descent with the multi-task loss VL Vis where (0)ss) is the i-th task loss and its gradient is estimated follows,
N
( s) (7)) A:) (s(s)) Vlogl', (T|s)
where be(s) Σ ( |s. >2)) a baseline to reduce the gradient variance; π| ,....., T"hh are solutions produced by POMO with different starting nodes. In practice, VL is approximated using Monte Carlo sampling, and computed by a batch with B instances as follows,
V R
Σ Mst b.,,-b,)))oee (T
(4)
NBn
t=1 j=1k=1
where 9i, =g(T<*19) A.) and by b,(s)). Ø is then optimized with T. steps using Adam [43].

---

model
Meta model update Rotational symmetry
Balanced space (1,0)
2 Sampled weight
(0.1)
À Symmetric weight
Scale
2 - 23
(0.37,0663)
(0.63,0.37)
22 (0.4,0.6)
2
2
2, (0.2,0.8)
22 (0.43,0.57)
(0.2,0.8)
(0.2,0.8)
(0.8,0.2)
(0,1)
(1,0)
(0,1)
(1,0)
(0.1)
(1,0)
f = Balance
4 = by Balance
f/f2 7/3, Imbalance
(a)
(b)
(c)
Figure 3: (a) Random sampling. (b) Symmetric sampling. (c) Scaled symmetric sampling.
4.2
Stabilized training
In each meta-iteration, the deviation of Ñ (usually small number) randomly sampled weight vectors may cause fluctuations to the parameter update of the meta-model, thereby leading to unstable training performance. For example, as shown in Figure 3()), the biased samples of weight vectors, i.e., A and X2, make the meta-model tend to favor the second objective more in this iteration.
To address this issue, first design a symmetrie sampling method for the case of balanced objective domain, illustrated in Figure 3(b). Once weight vector Àι is sampled, its M-1 rotational symmetric weight vectors Ag...., Ass are calculated and used to reduce the bias follows,
Xmmm 5mm=( {
İ A-- otherwise
m m=1
(5)
For the case of imbalanced objective domains, we further design scaled symmetric sampling method. In particular, the m-tth weight Am is scaled as Am/ fm where f* is the ideal objective value but difficult to be calculated beforehand. Thus, fm is replaced with fm which is dynamically estimated using the meta-model on a validation dataset with = (1/M, 1/M) during training.
Concretely, for a sampled Å it is first multiplied by f to scale objectives into the balanced domains. Then, its M-1 rotational symmetric weight vectors are obtained by Eq. (5). Finally, they are divided by f' to scale back to the original domain to attain the genuine rotational symmetric weight vectors. An example for Å₁ = (0.2, 0.8) and its scaled symmetric Å₂ (0.43, 0.57) are demonstrated in Figure 3(c), In summary, the scaled symmetric ,2,..., for a given Å are calculated as follows,
A Sho//im X X fmm-1/ f/mm
Xi. =
m otherwise
Then, the vectors are normalized di, sampling method for the weight vectors presented in Appendix B.
The pseudo code of the scaled symmetric
EM M.m.
4.3 Hierarchical fine-tuning
Once the meta-model is trained, it can be fine-tuned with a number of gradient updates to derive customized submodels for given weight vectors. However, it still might be expensive for MOCOPs since numerous submodels need to be individually fine-tuned from the meta-model. From a systematic perspective, the early coarse-tuning processes in which the parameters of neighboring submodels might be close, could be merged. In this sense, we propose hierarchical method to efficiently fine-tune the numerous subproblems from the lowest to the highest level, illustrated in Figure 1.

---

We suggest an L-level and a-section hierarchy to gradually produce more specific submodels, Partic- ularly, all NO weight vectors in level l are defined as the centers of their corresponding subspaces that uniformly divide the whole weight vector space based on the Das and Dennis [44] method. N submodels are then fine-tuned to derive N(++1) = aN(()) submodels with K((+1 fine-tuning steps in level [+1, Finally, N(L-1) submodels are fine-tuned to derive N N submodels, which are used to solve the N given subproblems. More details of this fine-tuning are presented in Appendix C.
For the L-level and a-section hierarchy with at = N and K(1) = ... = K = K, the total fine-tuning step is 7 = Ein Ka! = Ka(at - ()/(a- - 1). For the vanilla process, each submodel needs KL fine-tuning steps to achieve comparable performance, thus Tÿ KLN = KLa " steps in total. Hence, the hierarchical fine-tuning only needs T /TŞ z 1/ of the vanilla fine-tuning steps.
Experimental results
5.1 Experimental settings
We conduct computational experiments to evaluate the proposed method on the multi-objectivv trav- eling salesman problem (MOTSP), multi-objective capacitated vehicle routing problem (MOCVRP), and multii-ojeective knapsack problem (MOKP). Following the convention in [26, 12], we consider the instances of different sizes n=20/50/100 for MOTSP/MOCVRP and n=50/100/200 for MOKP. All experiments are run on a PC with an Intel Xeon 4216 CPU and an RTX 3090 GPU.
Problems. Four classes of MOTSP [45] are considered, including bi-objective TSP type 1&2 (Bi- TSP-1, Bi-TSP-2) and tri-objective TSP type 1&2 (Tri-TSP-1, Tri-TSP-2). For the M Mobjeective TSP where the m-th cost between node i and is defined as the Euclidean distance Cjj = ||=:"" x="" 11/ For the . M-objective TSP type 2, a node contains M-1 2D coordinates together with the altitude, so the M-th cost is defined as the altitude variance. For the bi-objective CVRP (Bi-CVRP) [46], two conflicting objectives with imbalanced domains, i.e., the total traveling distance and the traveling distance of the longest route (also called makespan), are considered. For the bi-objective KP (Bi-KP) [47], item i has a single weight and two distinct values. More details of these MOCOPs are presented in Appendix D.
type 1, node i has M 2D coordinates {a...... ....,.... x, MM
cm
Hyper-parameters. The meta-learning rate e is linearly annealed to 0 from 60 initially. A constant learning rate of the Adam optimizer is set to 10-². We set B = 64, Tm = 3000, T, = 100, and Ñ = M. The N weight vectors in PF construction are produced according to [44], where N = --C-1 #+M--- H is set to 100 (N = 101) and 13 (N- = 105) for M = 2 and M 3, respectively. WS scalarization is adopted. In the hierarchy of fine-tuning, the whole weight space uniformly divided by the Das and Dennis [44] method with H 2'. i.c., level / has 2 or 4' subspaces and L = 7 or L = 4 for M = 2 or M = 3. The number of fine-tuning steps at each level is K(O) = K = 20 or (D)) = K = 25 for M = 2 or M = 3.
Baselines. Two kinds of strong baselines are introduced, and all of them adopt WS (weighted sum) scalarization for fair comparisons. (1) The state-of-the-art neural heuristics, including MDRL [13], PMOCO [12], and DRL-based multiobjective optimization algorithm (DRL-MOA) [8]. Same as EMNH, all these neural heuristics adopt POMO as the base model for single-objective subproblems. (2) The state-of-the-ar traditional heuristics, including PPLS/D-C [20]. WS-LKH, and WS-DP. PPLS/D-C is a Docal-search-bar based MOEA proposed for MOCOPs, where a 2-opt heuristic used for MOTSP and MOCVRP, and greedy transformation heuristic [48] is used for MOKP, running with 200 iterations for all the three problems. WS-LKH and WS-DP are based on the state-of-the- heuristics for decomposed single-objective subproblems, i.e., LKH [49, 50] for MOTSP and dynamic programming (DP) for MOKP, respectively. Our code is publicly available?.
Metrics. Our EMNH is evaluated in terms of solution quality and learning efficiency. Solution quality is mainly measured by hypervolume (HV) [51]. where a higher HV mcans a better solution set (the definition is presented in Appendix E). Learning efficiency mainly refers to the training and fine-tuning efficiency, which are measured by training time for the same amount of training instances and solution quality with the same total fine-tuning steps (see Appendix F), respectively.
httpp::///gituub.ooo/iib/i cjjb/MMIH
7

---

Table I: Results on 200 random instances for MOCOPs with balanced objective domains.
Bi-TSP-1 (n=20)
Bi-TSP-1 (n=50)
Bi-TSP-1
(n=
Method
HVT
Gap/
Time
HVT
Gapl
Time
HV1
Gapt
Time
WS-LKH
0.6270
0.02%
10m
0.6415
-0.11
1.8h
0.7090
-0.95%
6.0h
PPLS/D-C
0.6256
0.24%
26m
0.6282
1.97%
2.8h
0.6844
2.55%
11h
DRL-MOA
0.6257
0.22%
6s
0.6360
0.75%
9s
0.6970
0.75%
21s
PMOCO
0.6259
0.19%
6s
0.6351
0.89%
10s
0.6957
0.94%
19s
MDRL
0.6271
0.00% %
5s
0.6364
0.69%
0.6969
0.77%
17s
EMNH
0.6271
0.00%
5s
0,6364
0.69%
9s
0.6969
0.77%
16s
PMOCO-Aug
0.6270
0.02%
45s
0.6395
0.20%
2.3m
0.7016
0.10%
15m
MDRL-Aug
0.6271
0.00 %
33s
0.6408
0.00%
1.7m
0.7022
0.01%
14m
EMNH-Aug
0.6271
0.00
33s
0.6408
0.00%
1.7m
0.7023
0.00%
14m
Bi-KP (n=50)
Bi-KP (n=100)
Bi-KP (n=200)
Method
HVT
Gap4
Time
HV1
Gapl
Time
HV1
Gap/
Time
WS-DP
0.3561
0.00%
22m
0.4532
0.07%
2.0h
0.3601
0.06%
5.8h
PPLS/D-C
0.3528
0.93%
18m
0.4480
1.21%
47m
0.3541
1.72%
1.5h
DRL-MOA
0.3559
0.06%
9s
0.4531
0.09%
18s
0.3601
0.06%
1.0m
PMOCO
0,3552
0.25%
6s
0.4523
0.26%
22s
0.3595
0.22%
1.3m
MDRL
0.3530
0.87%
6s
0,4532
0.07%
21s
0.3601
0.06%
1.2m
EMNH
0.3561
0.00%
6s
0.4535
0.00%
21s
0.3603
0.00%
1.2m
Tri-TSP-1 (n=20)
Tri-TSP-1 (n=50)
Tri-TSP-1 (n=100)
Method
HV1
Gap4
Time
HV1
Gapl
Time
HV1
Gap.
Time
WS-LKH
0.4712
0.00%
12m
0.4440
-0.50%
1.9h
0.5076
-2.07% %
6.6h
PPLS/D-C
0.4698
0.30%
1.4h
0.4174
5.52%
3.9h
0.4376
12.00%
14h
DRL-MOA
0.4699
0.28%
6s
0.4303
2.60%
0.4806
3.36%
19s
PMOCO
0.4693
0.40%
5s
0,4315
2.33%
8s
0.4858
2.31%
18s
MDRL
0.4699
0.28%
5s
0.4317
2.29%
0.4852
2.43%
16s
EMNH
0.4699
0.28%
5s
0.4324
2.13%
9s
0.4866
2.15%
16s
PMOCO-Aug
0.4712
0.00%
3.2m
0.4409
0.20%
28m
0.4956
0.34%
1.7h
MDRL-Aug
0.4712
0.00% %
2.6m
0.4408
0.23%
25m
0.4958
0.30%
1.7h
EMNH-Aug
0.4712
0.00%
2.6m
0.4418
0.00%
25m
0.4973
0.00%
1.7h
5.2
Solution quality
The results for MOTSP, MOCVRP, and MOKP are recorded in Tables 1 and 2, including the average HV, gap, and total running time for solving 200 random test instances. To further show the significant differences between the results, a Wilcoxon rank-sum test at 1% significance level is adopted. The best result and the one without statistical significance to it are highlighted bold. The second-best result and the one without statistical significance are highlighted as underline. The method with "-Aug" represents the inference results using instance augmentation [12] (see Appendix G).
Optimality gap. The gaps of HV with respect to EMNH-Aug are reported for all methods. Accord- ing to the results in Tables and 2, EMNH outperforms other neural heuristics without instance augmentation on all problems. When equipped with instance augmentation, EMNH-Aug further improves the solution, and performs superior to most of the baselines, while slightly inferior to WS-LKH on MOTSP with 5= and n=100. However, as iteration- based methods, WS-LKH and MOEAs take quite long running time MOCOPs. For the neural heuristics, DRL-MOA is less agile since it trains multiple fixed models for a priori weight vectors. For new weight vectors concerned by decision makers, EMNH, MDRL, and PMOCO are able to efficiently produce high-quality trade-off solutions, where EMNH achieves the smallest gap.
Imbalanced objective domains. As demonstrated in Table 2, the gaps between EMNH and PMOCO or MDRL. are further increased on the problems with imbalanced objective domains, i.e., Bi-CVRP, Bi- TSP-2, and Tri-TSP-2 EMNH exhibits more competitive performance these problems, revealing

---

Table 2: Results on 200 random instances for MOCOPs with imbalanced objective domains.
Bi-CVRP (n=20)
Bi-CVRP (n=50)
Bi-CVRP (n=100)
Method
HVT
Gap4
Time
HVT
Gapl
Time
HV1
Gapt
Time
PPLS/D-C
0.4287
0.35%
1.6h
0.4007
2.41%
9.7h
0.3946
3.26%
38h
DRL-MOA
0.4287
0.35%
10s
0,4076
0.73%
12s
0.4055
0.59%
33s
PMOCO
0.4267
0.81%
7s
0.4036
1.70%
12s
0.3913
4.07%
328
MDRL
0.4291
0.26%
8s
0.4082
0.58%
13s
0.4056
0.56%
32s
EMNH
0.4299
0.07%
8s
0.4098
0.19%
12s
0.4072
0.17%
32s
PMOCO-Aug
0.4294
0.19%
13s
0,4080
0.63%
36s
0.3969
2.70%
2.7m
MDRL-Aug
0.4294
0.19%
11s
0.4092
0.34%
36s
0.4072
0.17%
2.8m
EMNH-Aug
0.4302
0.00%
11s
0.4106
0.00 %
35s
0.4079
0.00%
2.8m
Bi-TSP-2
(n=20)
Bi-TSP-2 (n=50)
Bi-TSP-2
(n=100)
Method
HV1
Gap
Time
HV1
Gapl
Time
HV1
Gap/
Time
WS-LKH
0.6660
0.13%
11m
0.7390
-0.07 %
1.8h
0.8055
-0.74%
6.1h
PPLS/D-C
0.6662
0.10%
27m
0.7300
1.15%
3.3h
0.7859
1.71%
10h
DRL-MOA
0.6657
0.18%
0.7359
0.35%
0.7965
0.39%
18s
PMOCO
0.6590
1.18%
5s
0.7347
0.51%
8s
0.7944
0.65%
17s
MDRL
0.6669
0.00%
5s
0.7361
0.32%
9s
0.7965
0.39%
15s
EMNH
0.6669
0.00%
5s
0.7361
0.32%
9s
0.7965
0.39%
15s
PMOCO-Aug
0.6653
0.24%
13s
0.7375
0.14%
33s
0.7988
0.10%
3.5m
MDRL-Aug
0.6669
0.00%
8s
0.7385
0.00%
22s
0.7996
0.00%
2.8m
EMNH-Aug
0.6669
0.00
8s
0.7385
0.00%
22s
0.7996
0.00%
2.8m
Tri-TSP-2
(n=20)
Tri-TSP-2
(n=50)
Tri-TSP (n=100)
Method
HV1
Gap
Time
HV1
Gapl
Time
HV1
Gap.
Time
WS-LKH
0.5035
0.00%
13m
0.5305
-0.49
2.0h
0.5996
-1.70%
6.6h
PPLS/D-C
0.5035
0.00%
1.4h
0.5045
4.42%
4.1h
0.5306
10.01%
15h
DRL-MOA
0.5019
0.32%
6s
0.5101
3.37%
8s
0.5488
6.92%
19s
PMOCO
0.5020
0.30%
5s
0.5176
1.95%
8s
0.5777
2.02%
18s
MDRL.
0.5024
0.22%
0.5183
1.82%
0.5806
1.53%
16s
EMNH
0.5024
0.22%
5s
0.5205
1.40%
9s
0.5813
1.41%
16s
PMOCO-Aug
0.5035
0.00%
55s
0.5258
0.40%
6.1m
0.5862
0.58%
32m
MDRL-Aug
0.5035
0.00% %
37s
0.5267
0.23%
4.2m
0.5886
0.17%
30m
EMNH-Aug
0.5035
0.00%
37s
0.5279
0.00%
4.2m
0.5896
0.00%
30m
the effectiveness of the proposed scaled symmetric sampling method in tackling the imbalance of objective domains. We further equip PMOCO with the same sampling method, which actually also improved the solutions for those problems, but still performed inferior to EMNH (see Appendix H).
Generalization ability. We test the generalization ability of the model on 200 larger-scale random instances (v=150/200) and 3 commonly used MOTSP benchmark instances (KroAB 100/1 (00/15)000) in TSPLIB [52]. The zero-shot generalization performance the model trained and fine-tuned both on the instances with n=100 is reported in Appendix I. The results suggest that EMNH has a superior generalization ability compared with MOEAS and other neural heuristics for larger problem sizes.
Hyper-parameter study. The results in Appendix showed that the number of sampled weight vectors N M is more desirable setting and WS a simple yet effective scalarization method.
5.3 Learning efficiency
As verified above, EMNH is able to produce superior solutions to the state-of-the. art neural heuristics, especially demonstrating a significant advantage over PMOCO terms of solution quality. Then we further show that EMNH also has favorable learning efficiency against MDRL.
Training efficiency. EMNH, MDRL,, and PMOCO only train one model to tackle all subproblems, where EMNH and MDRL use the same amount of training instances, and PMOCO requires a few

---

6-
60
BE-VVRP
Bi B8-TSP-2
Speed-up Ratio
5-
5.0
5.6
0,670-
4-
40
47
0.22-
0.665
0.680
3-
20
3.0
29
0.41
0.655
0.650-
EMNHAA
PMDD0
MODRLAAg
1.0
110
200
BI-TSP-1
BI-CVRP
0.653-
EMNH
MDRL
1
2
3
4
033
RMNH
1200
RMINSS
1900
2400
3000
0.690
10
Tm
K
(a)
(b)
(c)
Figure 4: Learning efficiency. (a) Training efficiency. (b) Training stability. (c) Fine-tuning efficiency.
more training instances according to its original setting. DRL-MOA needs to train multiple submodels with more training instances. More details are presented in Appendix F. Figure 4(a) displays the speed-up ratio, i.c., the ratio of the training time of MDRL to EMNH. Due to the multi-task based training for (partial) architecture reuse, training time of EMNH is only about 1/Ñ of that of MDRL.
Training stability. Figure 4(b) shows the stability of the training process, where EMNH-S and EMNH-R refer to EMNH with the symmetric sampling and the random sampling, respectively. EMNH achieves the stablest and best training performance, compared to EMNH-S, EMNH-R, and MDRL,, as the proposed sampling method in EMNH considers symmetric weight vectors and (imbalanced) objective domains. More details presented in Appendix F.
Fine-tuning efficiency. Figure 4(C) compares the hierarchical fine-tuning in EMNH with the vanilla fine-tuning method in MDRL, where the HV of EMNH with K fine-tuning steps at each level and the HV of MDRL with approximately equal total fine-tuning steps are presented. The results demonstrate that EMNH attains higher fine-tuning efficiency than MDRL, i.e., larger gaps with smaller fine-tuning steps. Furthermore, PMOCO also equipped with the hierarchical fine-tuning (for both versions) for a fair comparison. It is worth noting that fine-tuning process is performed individually for each weight vector on dedicated fine-tuning instances. As can be seen, PMOCO could hardly get improved by fine-tuning for zero-shot inference test instances, since it has already converged for the corresponding subproblems. This means that EMNH has favorable potential to derive more desirable submodels to tackle specific tasks. Notably, EMNH with few finettuning steps (e.g.,
K 5) outperforms PMOCO in most cases, as demonstrated in Appendix F.
Conclusion
This paper proposes efficient meta neural heuristic (EMNH) for MOCOPs. Specifically, EMNH reduces training time, stabilizes the training process, and curtails total fine-tuning steps via (partial) architecture-shared multi-task learning, scaled symmetric sampling (of weight vectors), and hierarchi- cal fine-tuning, respectively. The experimental results on MOTSP, MOCVRP, and MOKP verified the superiority of EMNH in learning efficiency and solution quality. A limitation is that EMNH, as the same as other neural heuristics, can not guarantee obtaining the exact Pareto front. In the future, we will (1) extend EMNH to other MOCOPs with complex constraints; (2) investigate other advanced meta-learning algorithms and neural solvers as the base model to further improve the performance.
Acknowledgments and disclosure of funding
This work is supported by the National Natural Science Foundation of China (62072483), and the Guangdong Basic and Applied Basic Research Foundation (2022A151 1690, 1121A151501220
References
Matthias Ehrgott and Xavier Gandibleux. A survey and annotated bibliography of multiohjective combina- torial optimization. Op-spektrum, 22 22(4):255446) 2000.
[2] Kostas Florios and George Mavrotas. Generation of the exact pareto set in multi-objective traveling salesman and set covering problems. Applied Mathematics and Computation, 237:1-19, 19, 2014.
10

---

[3] Arn Herzel, Stefan Ruzika, and Clemens Thielen. Approximation methods for multiobjectivv optimization problems: A survey. INFORMS Journal Computing, 33(4):1284-1299, 2021.
[4] Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Wenjie Jiang, Ebrahim Songhori, Shen Wang. Young-Joon Lee, Eric Johnson, Omkar Pathak, Azade Nazi, Jiwoo Pak. Andy Tong, Kavya Srinivasa. William Hang. Emre Tuncer, Quoe V. Le. James Laudon, Richard Ho, Roger Carpenter, and Jeff Dean. graph placement methodology for fast chip design. Nature, 594:207-212, 2021.
[5] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d' d'horizon. European Journal of Operational Research, 290(2):405 421, 2021.
[6] Nina Mazyavkina, Sergey Sviridov. Sergei Ivanov, and Evgeny Burnaev. Reinforvement learning for combinatorial optimization: A survey. Computers & Operations Research, 134: 105400, 2021.
[7] Qi Wang and Chunlei Tang. Deep reinforcement learning for transportation network combinatorial optimization: A survey, Khowledge-Basee 2 233:107526, 2021.
[8] Kaiwen Li, Zhang, and Rui Wang. Deep reinforcement learning for multiobjective optimization. IEEE Transactions on Cybermetics, 51(6)310333114, 2021.
[9] Hong Wu, Jiahai Wang, and Zizhen Zhang. MODRL/D-AM Multiobjective deep reinforcement learning algorithm using decomposition and attention model for multiobjective optimization. In /SICA 2019, volume CCIS 1205, pages 575-589, 2020.
[10] Yinan Shao, Jerry Chun Wei Lin, Gautam Srivastava, Dongdong Guo, Hongchun Zhang, Hu Yi, and Alireza Jolfaei. Multi-ohjective neural evolutionary algorithm for combinatorial optimization problems. IEEE Transactions on Neural Networks and Learning Systems, 2021.
[11] Yongxin Zhang, Jiahai Wang. Zizhen Zhang, and Yalan Zhou. MODRL/D-EL: Multiobjective deep reinforcement learning with evolutionary learning for multiobjective optimization. In International Joint Conference on Neural Networks, 2021.
[12] Xi Lin, Zhiyuan Yang, and Qingfu Zhang. Pareto set learning for neural multi-objective combinatorial optimization. International Conference on Learning Reprexentations, 2022.
[13] Zizhen Zhang, Zhiyuan Wu, Hang Zhang, and Jiahai Wang. Meta-learning-hasee deep reinforcement learning for multiobjective optimization problems. IEEE Transactions on Neural Networks and Learning Systems, 34(10):7978 1791887991111111 2023.
[14] Alex Nichol, Joshua Achiam, and John Schulman. On first-order meta-learning algorithms, 2018.
[15] Aniruddh Raghu, Maithra Raghu, Samy Bengio, and Oriol Vinyals. Rapid learning feature reuse? towards understanding the effectiveness maml. International Conference on Learning Representations, 2020.
[16] Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182-197, 2002.
[17] Qingfu Zhang and Hui Li. MOEA/D: A multiohjecttive evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 11(6)712-731, 2007.
[18] Andrzej Jaszkiewicz. Genetic local search for multi-ohjective combinatorial optimization. European Journal of Operational Research, 137(1):50-71, 2002.
[19] Jialong Shi, Qingfu Zhang, and Jianyong Sun. PPLS/D: Parallel pareto local search based on decomposition. IEEE transactions on Cybernetics, 50(3): 1060-101,, 2020.
[20] Jialong Shi, Jianyong Sun, Qingfu Zhang. Haotian Zhang, and Ye Fan. Improving pareto local search using cooperative parallelism strategies for multiohjective combinatorial optimization. IEFE Transactions on Cybernetics, 2022.
[21] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, 2015.
[22] Irwan Bello, Hicu Pham, Quoe V Lc, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning, In International Conference Learning Representations, 2017.
[23] Mohammadreza Nazari, Afshin Oroojlooy, Martin Takáč, and Lawrence V. Snyder. Reinforvement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, 2018.

---

[24] Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019.
[25] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, 2017.
[26] Ycong-Das Dac Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Scungjai Min. POMO: Policy optimization with multiple optima for reinforcement learning. In Advances in Neural Information Processing Systems, 2020.
[27] Minsu Kim, Jinkyoo Park, et al. Learnnng collaborative policies to solve np-hard routing problems. In Advances in Neural Information Processing Systems, 2021.
[28] Yeong-Dax Dae Kwon, Jinho Choo, Iljoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. In Advances in Neural Information Processing Systems, 2021.
[29] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Multi-decoder attention model with embedding glimpse for solving vehicle routing problems. In AAAI Conference on Artificial Intelligence, pages 12042-12049, 2021.
[30] Bo Peng. Jiahai Wang. and Zizhen Zhang. A deep reinforcement learning algorithm using dynamic attention model for vehicle routing problems. In ISICA 2019, volume CCIS 1205, pages 636-650, 2020.
[31] Elias Khalil, Hamjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems, 2017.
[32] Sahil Manchanda, Akash Mittal, Anuj Dhawan, Sourav Medya, Sayan Ranu, and Ambuj Singh. GCOMB: Learning budget-constrained combinatorial algorithms over billion-sized graphs. In Advances in Neural Information Processing Systems, 2020.
[33] Lu Duan. Yang Zhan, Haoyuan Hu, Yu Gong, Jiangwen Wei, Xiaodong Zhang, and Yinghui Xu. Efficienlly solving the practical vehicle routing problem: A novel joint learning approach. In ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 3054-3063, 2020.
[34] Jinbiao Chen, Huanhuan Huang, Zizhen Zhang, and Jiahai Wang. Deep reinforcement learning with two- stage training strategy for practical electric vehicle routing problem with time windows. In International Conference on Parallel Problem Solving from Nature, 2022.
[35] Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. In Advances in Neural Information Processing Systems, 2019.
[36] Hao Lu, Xingwen Zhang, and Shuang Yang. lcarning-based iterative method for solving vehicle routing problems. In International Conference on Learning Representations, 2020.
[37] André Hottung and Kevin Tierney. Neural large neighhorhood search for the capacitated vehicle routing problem. European Conference on Artificial Intelligence, 2020.
[38] Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuristics for salving routing problems. IEEE Transactions on Neural Networks and Learning Systems, 3309)55057-5069 2022.
[39] Yining Ma, Jingwen Li. Zhiguang Cao. Wen Song. Zhang, Zhenghua Chen, and Jing Tang. Learning to iteratively solve routing problems with dual-aspect collaborative transformer. In Advances in Neurul Information Procensing Systems, 2021.
[40] Xiaoliang Ma. Qingfu Zhang, Guangdong Tian, Junshan Yang. and Zexuan Zhu. On tchebycheff decom- position approaches for multiobjective evolutionary optimization. IEEE Transactions on Evolutionary Computation, 22(2):226- 244, 2017.
[41] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnoste meta- learnig for fast adaptation of deep networks. In Intermational Conference Machine Learning, pages 1126 1135, 2017.
[42] Ronald J Williams. Simple statistical gradient-following algorithuss for connectionist reinforcement learning. Machine Learning, 8(3):229-22) 226, 1992.
[43] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
12

---

[44] Das and JE Dennis. Normal-boundeen intersection: A new method for generating pareto-optimal points in multieriteria optimization problems. SIAM Journal Optimization, 8(3):631-657. 1998.
[45] Thibaut Lust and Jacques Teghem. The multiobjective traveling salesman problem: A survey and new approach. Advances in Multi- Objective Nature Inspired Computing, pages 119-141, 2010.
[46] Nicolas Jozefowiez. Frédéric Semet, and El-Ghazali Talbi. Multi-objective vehicle routing problems. European Journal of Operational Research, 189(2):293-309, 2008.
[47] Cristina Bazgan, Hadrien Hugot, and Daniel Vanderpooten. Solving efficiently the 0-1 multi-objective knapsack problem. Computers & Operations Research, (66)22260- 2009.
[48] Hisao Ishibuchi, Naoya Akedo, and Yusuke Nojima. Behavior of multiobjective evolutionary algorithms many-objective knapsack problems. IEEE Transactions Evolutionary Computaatoon 19(2):264-283, 2015.
[49] Keld Helsgaun. An effective implementation of the lin-kernighan traveling salesman heuristic. European Journal of Operational Research, 126(1):106-130, 2000.
[50] Renato Tinós, Keld Helsgaun, and Darrell Whitley. Efficient recombination in the iin-ernighan-heeggamm traveling salesman heuristic. International Conference on Parallel Problem Solving from Nature, pages 95-107, 2018.
[51] Charles Audet, Jean Bigeon, Dominique Cartier, Sébastien Le Digabel, Ludovic Salomon. Performance indicators in multiobjective optimization. European Journal of Operational Research, 292(2):397-422, 2021.
[52] Gerhard Reinelt. TSPLIB a traveling salesman problem library. ORSA Journal on Computing, 3(4): 376-384, 1991.
13


Reviews:
[{"review_id": "bVztnzTEbe", "reviewer": "Reviewer_TTgk", "summary": "In order to achieve higher learning efficiency and better solution quality, this paper proposed an efficient meta neural heuristic (EMNH), in which a meta model is first trained and then fine-tuned with a few steps to solve corresponding single-objective subproblems. For the training process, an architecture-shared multi-task model is leveraged to achieve parallel learning for the meta model, so as to accelerate the training; meanwhile, a scaled symmetric sampling method with respect to the weight vectors is designed to stabilize the training. For the fine-tuning process, an efficient hierarchical method is proposed to systematically tackle all the subproblems. The general idea of this paper is clear and logical.", "questions": "1. In the Experimental Results part, the experiment results in tables should be further analyzed. \n2. In the Training Efficiency part, more current comparison method should be added in order to support the experimental conclusion with more sufficient and comprehensive experimental results.\n3. Are there any control parameters in the proposed method? how sensitive are them?  \n4. The picture in Figure 4 is too small for clearly understanding of readers.\n5. The writing of the paper could be improved for better description and clarification.", "limitations": "1. The experimental problems of this method are limited to real-world problems, and further experimental verification should be carried out on synthetic problems.", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The methodology part of the paper is clearly described and has a certain degree of logic.", "weaknesses": "1. In the Methodology part, this paper proposed three methods for accelerate training, stabilize training and hierarchical Fine-tuning. However, in the Introduction part, the connection between motivation of this paper and the proposed stabilized training method should be clearer described.\n2. In the Experimental Results part, ablation experiment should be added in order to verify the effect of the proposed method. To be more specific, as for the experiments towards learning efficiency, the comparison between original method and method without adding stabilized training part should be done.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the valuable comments, and considering our idea clear and logical. We hope the point-to-point response below would address the remaining concerns.\n\n**To Weakness 1:**  We acknowledge and appreciate the reviewer's concern. It is indeed crucial to establish a clear connection between the motivation of our paper and the proposed stabilized training method. As a result, we will carefully revise and add the following statements to ensure consistency in conveying these points throughout the paper.\n\n'...The recent Meta-DRL (MDRL) [13] has demonstrated the capability to enhance solution quality compared with PMOCO. However, it still faces challenges related to inefficient and unstable training procedures, as well as undesirable fine-tuning processes.'\n\n'During the meta-learning process, the deviation of a few randomly sampled weight vectors may cause fluctuations to the parameter update of the meta model, leading to the unstable training performance. This motivates us to introduce a stabilized training method.'\n\n\n**To Weakness 2:** Thank you for your suggestion regarding the ablation study. In our original submission, we have already conducted an ablation experiment specifically focusing on the proposed scaled symmetric sampling method. The detailed results can be found in Section 5.3 and Appendix F.2.\n\nTo be specific, we compared EMNH with two variants EMNH-R (EMNH with random sampling) and EMNH-S (EMNH with symmetric sampling). EMNH-R reflects the overall effect of the complete scaled symmetric sampling method, while EMNH-S isolates the effect of the corresponding scaling operation. The results clearly demonstrate that the proposed scaled symmetric sampling method effectively stabilizes the training process.\n\n\n**To Question 1:**  Thanks for raising the concern on the experimental results anaysis. We acknowledge that the analysis provided in the original submission was concise due to rich presented results and limited space. According to the suggestions, we will add more detailed analysis in the final version. For example, the analysis about the results in Figure 4(c) will be supplemented as follows.  \n\n'...Notably, we observed that EMNH with a few fine-tuning steps (e.g., $K = 5$) generally outperforms PMOCO in most cases, as demonstrated in Appendix F. It is important to note that our fine-tuning process is performed individually for each weight vector on dedicated fine-tuning instances. As a result, the fine-tuning does not enhance the performance of the well-trained PMOCO model for zero-shot inference on test instances. This finding indicates that PMOCO has already converged for the subproblems corresponding to the given weight vectors...'\n\n**To Question 2:**  The objective of this paper is to evaluate neural solvers or heuristics for MOCOP. We have carefully selected MDRL [1], PMOCO [2], and DRL-MOA [3] as the neural solvers for comparison. The selection of these representatives is based on the following reasons. As show in the Related Works section, DRL-MOA is acknowledged as a well-known classic neural heuristic for MOCOP. MDRL and PMOCO are recognized as state-of-the-art neural heuristics, surpassing previous approaches, including DRL-MOA. \n\nFrom our perspective, the experimental results provide compelling evidence to support our conclusion. The original submission includes a comprehensive analysis of training efficiency in Section 5.3 and Appendix F.1. The results clearly demonstrate that EMNH achieves a training time of approximately 1/$\\tilde{N}$ compared to MDRL. Moreover, the total training time of EMNH is comparable to that of PMOCO. In contrast, DRL-MOA requires training multiple models, resulting in significantly more time, which is less competitive.\n\n**To Question 3:** Thank you for raising the concern about the parameters. We have addressed this issue in Section 5.1, where all the control hyperparameters are listed. Most of these parameters are adopted from previous works, including the learning rate [1,2], the meta-learning rate $\\epsilon$ [1], the number of gradient steps for the inner-loop update $T_u$ [1], the batch size $B$ [2], and the number of weight vectors $N$ [2].\n\nWe specifically investigated those parameters used in our EMNH, which include the number of sampled weight vectors $\\tilde{N}$, the scalarization method, and the number of fine-tuning steps at each level $K$. The sensitivity analysis of $\\tilde{N}$ and the scalarization method can be found in Appendix J, while the analysis of $K$ can be found in Appendix F.3. In summary, our findings suggest that setting $\\tilde{N}=M$ and using the weighted-sum scalarization method yield desirable results. Additionally, we observed that the model has nearly converged when $K=20$.\n\n**To Question 4:**  Thanks for pointing it out. We appreciate the suggestion, and will consider enlarging the picture in Figure 4 if we have sufficient space in the final version.\n\n**To Question 5:** Thanks for the suggestion. We will thoroughly proofread and revise the writing in the final version. \n\n**To Limitation 1:** Thanks for raising this concern. We want to clarify that our experiments were conducted on a diverse set of problem instances, including both real-world problems and synthetic instances. For the real-world problems, we utilized the KroAB instances from TSPLIB, as indicated in Table 8. These instances have also been used in previous works [1][3].\n\nIn addition to the real-world problems, we also incorporated randomly generated instances for our experiments. The details and results of these instances can be found in Tables 1 and 2, which are consistent with the approaches taken in prior studies [1][2][3].\n\n[1] Meta-learning-based Deep Reinforcement Learning for Multiobjective Optimization Problems, IEEE TNNLS, 2022.\n\n[2] Pareto Set Learning for Neural Multi-Objective Combinatorial Optimization, ICLR, 2022.\n\n[3] Deep Reinforcement Learning for Multiobjective Optimization, IEEE TCYB, 2021.\n"}, {"review_id": "5frTtmUtSW", "reviewer": "Reviewer_R5xR", "summary": "The paper introduces a meta neural heuristic in which a meta model is first trained and then fine-tuned with a few steps\nto solve corresponding single-objective subproblems. For the training process, a partial architecture-shared multi-task model is leveraged to achieve parallel learning for the meta model, so as to speed up the training. Meanwhile, a scaled symmetric sampling method with respect to the weight vectors is designed to stabilize the training. For the fine-tuning process, an efficient hierarchical method is proposed to systematically tackle all the subproblems.\n\nThe article contains a review of related works and preliminaries, then it presents the introduced methodology.\nThis is followed by the description of experiments, their settings, results, and analysis. The experiments were carried out for\nthe multi-objective traveling salesman problem, multi-objective capacitated vehicle routing problem, and multi-objective knapsack problem. They showed that the introduced method is able to outperform the state-of-the-art neural heuristics in terms of solution quality and learning efficiency and yield competitive solutions to the strong traditional heuristics while consuming a much shorter time.\n\nThe main text is followed by supplementary materials.", "questions": "I don't have any specific questions.", "limitations": "The main limitation, according to the authors, is that the method can not guarantee to obtain the exact Pareto front (similar to other neural heuristics). Also, the code and the datasets used in experiments are not available, so it is difficult to verify and reproduce the results. However, the authors provided some pseudocode and declared that the code will be made publicly available. I didn't find other limitations, but it is possible that I didn't understand some parts.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The introduced methodology is quite advanced and seems to be innovative and successful. \nI also like that it was tested on several problems from different domains and besides reporting efficiency and the quality of the found solutions, the required time is reported too. The paper is well written and it is good that it is followed by the supplementary materials. I like that there is a pseudocode in the supplementary materials and the authors declared that the codes for all the methods will be made available.", "weaknesses": "The main weakness I found is that the code and the datasets used in experiments are not available, so it is difficult to verify and reproduce the results. However, the authors provided some pseudocode and declared that the code will be made publicly available. Besides, didn't find serious weaknesses of this paper, but it is possible that I didn't understand some parts.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the valuable comments, and considering our method advanced and our paper well written. Regarding the source code, on the one hand, we have stated clearly in our original submission - ' Our codes for all the methods will be made available'. On the other hand, we will upload our source code and datasets, and share the url with the AC (according to the NeurIPS rebuttal policy). We thank the reviewer for the support again.\n"}, {"review_id": "A49171ShYg", "reviewer": "Reviewer_d8Lb", "summary": "This work proposes EMNH, an efficient meta neural heuristic, for solving multi-objective combinatorial optimization problems. It builds a single meta model to tackle different trade-offs among multiple objectives during training, which can be efficiently fine-tuned into specialized submodels to solve different trade-offed subproblems. The main contributions are: 1) a multi-task meta model with parameter-shared body and task-related heads that can handle different trade-offs at the same time; 2) a scaled symmetric sampling method to stabilize the multi-objective training with imbalanced objectives; and 3) a hierarchical fine-tuning method to gradually fine-tune a set of submodel with much fewer steps. Experimental results show that the proposed EMHN method can outperform other neural combinatorial optimization methods on different combinatorial optimization problems such as MOTSP, MOCVRP, and MOKP.", "questions": "- Please address the concerns raised in Weaknesses.", "limitations": "The limitation of the proposed method has been discussed in the conclusion section.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ This paper is well-written and easy to follow.\n\n+ Multi-objective combinatorial optimization is important for real-world applications. Neural heuristic is a promising approach to tackle this problem, but only a few methods have been proposed recently. This work is a timely contribution to a promising research direction.\n\n+ The proposed method obtains promising performances on various multi-objective combinatorial optimization problems.", "weaknesses": "I have the following concerns for the proposed method: \n\n**1. Runetime and Efficiency of Fine-tune**\n\nThe runtime of the fine-tuning approach is not clearly discussed in the paper. In my understanding, for solving a new problem instance, the meta-learning based methods need to first fine-tune the meta model into different submodels, and then run each submodel to generate corresponding approximate solutions. In other words, the prediction is not zero-shot inference. However, in all experiments, the reported runtimes for MDRL and EMNH are similar to DRL-MOA and PMOCO which support zero-shot inference. Why the cost of fine-tuning is not included in the runtime? \n\n**2. Structure of Multi-Task Meta Model**\n\nThe proposed multi-task meta model has a single model body that is shared by all tasks and specialized heads for different tasks. Recent work has also investigated fine-tuning a small part of the neural combinatorial optimization model to improve the performance of each instance for single-objective problems [1]. What is the advantage of the proposed model structure for multi-objective optimization? Is there any guideline for model design? \n\n[1] Efficient Active Search for Combinatorial Optimization Problems, ICLR 2022.\n\n**3. Solution Distribution**\n\nEMNH mainly uses the weighted-sum strategy to decompose a multi-objective optimization problem into multiple subproblems. According to PMOCO [1], different decomposition methods will lead to very different solution distributions on a given problem instance, especially those with more than two objectives. In addition, as reported in a current work [2], the decomposition-based PMOCO will generate redundant solutions for different preferences. Will EMNH also have these two issues? Can these issues be addressed by the scaled symmetric weight sampling method? \n\n[2] Pareto Set Learning for Neural Multi-Objective Combinatorial Optimization, ICLR 2022.\n\n[3] Graph Learning Assisted Multi-Objective Integer Programming, NeurIPS 2022.\n\n**4. Fine-Tuning PMOCO**\n\nAs reported in this work, PMOCO usually has a promising zero-shot prediction performance, but it cannot be further improved with the fine-tuned approach. In my understanding, PMOCO is also a variant of the AM structure in POMO. According to recent works [1], only fine-tuning a small part of the model parameters in POMO can significantly improve the performance of single-objective optimization. It is interesting to know why fine-tuning does not work for PMOCO.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the valuable comments, and considering our paper well written with timely contribution and promising performance. We hope the point-to-point response below would address the remaining concerns.\n\n**To Weakness 1: Runtime and Efficiency of Fine-tune.** The fine-tuning time is not included in the runtime, as the runtime refers to the inference time on test instances. It's important to note that all our inference results are zero-shot on test instances. As explained in Section 3.3, a submodel corresponding to a specific weight vector is fine-tuned from the well-trained meta-model using fine-tuning instances, rather than using the test instances as done in [8]. This means that the submodel hasn't seen the test instances before the inference. Therefore, the runtime represents the zero-shot inference time. In this sense, the runtime of EMNH and MDRL is also similar to that of DRL-MOA and PMOCO.\n\n[8] Meta-learning-based Deep Reinforcement Learning for Multiobjective Optimization Problems, IEEE TNNLS, 2022.\n\n**To Weakness 2: Structure of Multi-Task Meta Model.** One advantage of our model over [1] is faster inference due to its simpler architecture. In [1], EAS is instance-specific, whereas our model is task-specific, meaning it can infer a batch of instances from a similar task in parallel. Unlike [1], our meta-model has the same architecture as the single-objective neural model, eliminating the need for additional model designs. The multi-task model only requires multiple heads to operate in parallel and does not need to be saved after training the meta-model.\n\nOur model design follows the guideline of feature reuse in meta-learning [4]. As discussed in [4], only the head of the meta-model is updated to align with a specific task, while the body remains reusable for all tasks. This principle has inspired us to propose a multi-task model that accelerates the training of the meta-model.\n\n[1] Efficient Active Search for Combinatorial Optimization Problems, ICLR, 2022.\n\n[4] Rapid learning or feature reuse? towards understanding the effectiveness of MAML, ICLR, 2020\n\n**To Weakness 3: Solution Distribution.** Similar to other decomposition-based methods like PMOCO, EMNH also faces the challenge of different decomposition methods resulting in different solution distributions. However, this issue can be mitigated by employing appropriate weight assignment methods, as demonstrated in PMOCO. EMNH offers the flexibility to handle arbitrary weight vectors. Specifically, when the approximate scales of different objectives are known, we can normalize them to [0,1] to achieve a more uniform Pareto front. Alternatively, we can adjust the weight assignment to generate a more uniform Pareto front. In future work, more advanced weight assignment methods [5] could be explored to address irregular Pareto fronts beyond the scope of this paper.\n\nFurthermore, like other decomposition-based methods, EMNH may generate redundant solutions for different weight vectors. This is an inherent limitation of the decomposition approach. To promote greater diversity in solutions, one potential direction is to consider a diversity indicator [6] or divide the objective space into regions [7].\n\nThe scaled symmetric sampling method is proposed to stabilize the training process and can be directly used to address these issues. We also attempt to apply the scaling operation to the weight assignment during inference to alleviate the first issue. Specifically, each uniform weight vector $\\lambda$ is scaled by $f'$ as $\\lambda_m/f'_m$ and normalized to $[0,1]^M$. Here,$f'_m$ is estimated using a validation dataset associated with $\\lambda=(1/M,\\dots,1/M)$. The advantage of this scaling weight assignment (SWA) method is that it does not require prior problem information.\n\nIn the \"Global Rebuttal\" PDF, we have included additional results on tri-TSP instances with asymmetric Pareto fronts. For these instances, the coordinates for the three objectives are randomly sampled from $[0,1]^2$, $[0,0.5]^2$, $[0,0.1]^2$, respectively. The results demonstrate that EMNH-SWA effectively produces a more uniform Pareto front. Compared to a scaling weight method with prior knowledge, where uniform weight vectors are element-wise multiplied by (1,2,10) and then normalized back to $[0,1]^3$, EMNH-SWA achieves desirable performance.\n\n[5] A Survey of Weight Vector Adjustment Methods for Decomposition based Multi-objective Evolutionary Algorithms, IEEE TEVC, 2020.\n\n[6] Performance Indicators in Multiobjective Optimization, EJOR, 2021.\n\n[7] Improving Pareto Local Search Using Cooperative Parallelism Strategies for Multiobjective Combinatorial Optimization, IEEE TCYB, 2022\n\n**To Weakness 4: Fine-Tuning PMOCO.** Fine-tuning is not effective for PMOCO, since PMOCO has already converged for the subproblems corresponding to the given weight vectors. As mentioned earlier, our fine-tuning process is performed on fine-tuning instances, not on test instances. This approach differs from the 'fine-tuning' executed on each test instance, also known as active search [1]. Hence, our fine-tuning does not improve the performance of the well-trained PMOCO model for zero-shot inference on test instances.\n"}, {"review_id": "FbrFGfwLfR", "reviewer": "Reviewer_qYcb", "summary": "The paper proposes efficient meta neural heuristic (EMNH) for solving multi-objective combinatorial optimization problems (MOCOP). The paper provides novel scaled sampling method for stability and a hierarchical fine-tune method for sub-task specific performance improvement over MDRL. The idea is sound and the experiments yield better performance than the state-of-the-art methods for MOCOP.", "questions": "1. According to Table 2, although the traditional heuristics may yield the best performance, it would take them much more time to solve the problem. Given the same amount of fine-tuning time, what is the performance of the proposed MOCOP method EMNH? (i.e. set K to a large number).", "limitations": "The proposed EMNH provides no guarantee for the pareto front.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The idea of using multi-task body with different heads in meta-learning is sound.\nThe experiments are detailed and convincing.\n", "weaknesses": "I’m not an expert in MOCOP problem, as far as I’m concerned, I detect no weakness of this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the valuable comments, and finding our experiments detailed and convincing. Our EMNH method, when provided with a sufficiently large value of $K$ (the number of fine-tuning steps), may not outperform traditional strong solvers like WS-LKH. We conducted a study to examine the impact of $K$ on performance in the original submission, and the results are presented in Figure 4(c) and Figure 7. It is evident that the model has almost converged when $K$ equals 20. Consequently, further increasing $K$ has little effect on performance, which aligns with our additional tests. It is worth noting that the model is fine-tuned on the fine-tuning instances for a given weight vector, rather than the test instances.\n\nNevertheless, our EMNH approach excels in generating a desirable Pareto set within a short solving time. It can also serve as an initial solution generator, which can be further enhanced using active search techniques [1] or traditional heuristics. However, we understand and acknowledge the concern of the reviewer. To further improve the performance of EMNH, we also plan to investigate more advanced meta-learning algorithms and employ more powerful base models, as outlined in the future work section of our paper.\n\n[1] Efficient Active Search for Combinatorial Optimization Problems, ICLR, 2022.\n\n"}, {"review_id": "vd9jWE3pyz", "reviewer": "Reviewer_EY2k", "summary": "This article presents an efficient neural heuristic method based on meta-learning, referred to as EMNH (Efficient Meta-learning Neural Heuristic), for solving Multi-Objective Combinatorial Optimization Problems (MOCOPs). The authors employ a shared multi-task model to expedite the meta-learning process and introduce a weight vector-based scaling symmetric sampling approach to stabilize this process. Furthermore, they propose a layered fine-tuning method to effectively address all sub-problems. Experimental results demonstrate that EMNH outperforms existing neural heuristic methods on three classical MOCOPs and can also compete with traditional heuristic methods.", "questions": "1. Did the authors consider using other types of neural network structures or meta-learning algorithms to implement the proposed method? If so, how do they compare to POMO and Reptile?\n2. Did the authors attempt to test the proposed method on other types or scales of MOCOPs? If yes, what were the results? If not, what were the reasons?", "limitations": "1. The proposed method might require substantial training data and computational resources to achieve ideal results, potentially limiting its feasibility and scalability in practical applications.\n2. The proposed method might struggle with MOCOPs featuring nonlinear or non-convex objective functions, dynamic or stochastic constraints, multi-modal or multi-peak distributions, and other complex features.\n3. The proposed method might not guarantee the identification of true Pareto-optimal solution sets, only approximated solution sets, potentially affecting evaluators' judgments on solution quality and diversity.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The article addresses the practical and challenging issue of MOCOPs, presenting a novel neural heuristic approach that combines ideas from meta-learning, multi-task learning, and layered fine-tuning.\n2. The proposed method's advantages are theoretically analyzed, including accelerated and stabilized meta-learning processes, along with reduced fine-tuning steps.\n3. The article conducts comprehensive experiments on three different types of MOCOPs, comparing against various benchmark methods. It showcases the proposed method's advantages in terms of solution quality, learning efficiency, and generalization ability.", "weaknesses": "1. The article inadequately discusses the limitations and shortcomings of the proposed method, such as its applicability to more complex or higher-dimensional MOCOPs, sensitivity to weight vector selection, and risks of overfitting or underfitting.\n2. The article lacks sufficient details to explain the model architecture, hyperparameter settings, experimental setup, etc. This might affect the replicability and credibility of the results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the valuable comments, and finding our method novel, experiment comprehensive, and results advantegous. We hope the point-to-point response below would address the remaining concerns.\n\n**To Weakness 1:** Our method is designed for general MOCOPs. Other advancing techniques can be integrated to address more complex or higher-dimensional MOCOP.\n\nRegarding underfitting and overfitting, we observe from the training curves (see Figures 4(b) and 6) that our model has converged. Additionally, we evaluate our model on 200 randomly generated instances for each problem, as well as on larger-scale and real-world benchmark instances. The results demonstrate the desirable generalization ability of our model.\n\nWe would like to supplement the discussion on weight vector selection as follows.\n\nDifferent weight vectors will lead to different solution distributions. EMNH can utilize proper weight selection methods to obtain a more uniform Pareto front, since EMNH can flexibly tackle arbitrary weight vectors. Specifically, two methods are used for demonstration. (1) A weight assignment method used in PMOCO [1]. (2) We design a scaling weight assignment (SWA) method as follows. Each of the uniform weight vectors $\\lambda$ is scaled by $f'$ as $\\lambda_m/f'_m$ and normilized into $[0,1]^M$, where $f'_m$ is estimated on a validation dataset associated with $\\lambda=(1/M,\\dots,1/M)$.\n\nWe have supplemented the results on tri-TSP with asymmetric Pareto fronts, as presented in the PDF in \"Global Rebuttal\". For tri-TSP instances, the coordinates for the three objectives are randomly sampled from $[0,1]^2$, $[0,0.5]^2$, $[0,0.1]^2$, respectively. According to the first method, the non-uniform weight vectors which are obtained by multiplying uniform weight vectors by (1,2,10) element-wise and then normalizing them back to $[0,1]^3$. The results show that two weight vector selection methods can produce a relatively uniform Pareto front.\n\nFurthermore, in our framework, more complex and effective weight vector selection methods [2] can be adapted to handle irregular Pareto fronts.\n\n\n[1] Pareto Set Learning for Neural Multi-Objective Combinatorial Optimization, ICLR, 2022.\n\n[2] A Survey of Weight Vector Adjustment Methods for Decomposition based Multi-objective Evolutionary Algorithms, IEEE TEVC, 2020.\n\n\n**To Weakness 2:** We have tried to provide a comprehensive description of the model architecture in Section 4.1 and Appendix A, along with detailed information on hyperparameter settings and the experimental setup in Section 5.1 and Appendix D. Furthermore, we have made our source code and datasets used in the experiments available, enabling readers to replicate and validate the results.\n\n\n**To Question 1:** We have focused on utilizing POMO and Reptile, as they are currently considered state-of-the-art methods in the field of single-objective neural combinatorial optimization and meta-learning, respectively. To ensure fairness in our comparisons, all the neural heuristics we compared with employed POMO as their single-objective base model, while the MDRL method we compared with also utilized Reptile. In future research, we plan to explore more advanced meta-learning algorithms and more powerful base models to further enhance the performance of our method.\n\n\n**To Question 2:** We have conducted experiments on three classic MOCOPs: MOTSP, MOCVRP, and MOKP. The MOTSP consists of four different types. Each problem includes at least three scales, and even five scales for MOTSP. \n\nIn our future work, we plan to expand the scope of our method by testing it on more complex MOCOPs. We also aim to improve its generalization capabilities across various problem types and scales by leveraging leading techniques such as pre-training and knowledge distillation. \n\n\n**To Limitation 1:** Our method may require a large amount of training data and computational resources. However, the offline computational cost is affordable and worthy in practical applications because a well-trained model can quickly generate high-quality solutions for similar problem instances within a specific problem class. This capability makes our method highly valuable in scenarios where efficiency and quality are crucial considerations.\n\n\n**To Limitation 2:** Our method is designed to address a wide range of MOCOPs, including those with nonlinear or non-convex objective functions. The objective function of a combinatorial problem is inherently non-convex. In the case of the Tchebycheff-decomposed subproblem (as described in Appendix J.2), it even becomes nonlinear.\n\nTo handle more complex problem features, our method can be combined with other techniques. For instance, when dealing with complex constraints, our method can incorporate a constraint-handling technique [2] to effectively handle them. Additionally, for dynamic problems, our method can leverage a spatio-temporal neural model [3] to enhance its performance in such scenarios.\n\n[2] Deep Reinforcement Learning with Two-Stage Training Strategy for Practical Electric Vehicle Routing Problem with Time Windows, PPSN, 2022.\n\n[3] Solving Dynamic Traveling Salesman Problems With Deep Reinforcement Learning, IEEE TNNLS, 2023\n\n**To Limitation 3:** Due to the NP-hardness of MOCOPs, finding the exact Pareto set within acceptable computational time is often impractical, especially for large-scale problems. Therefore, it is crucial to design approximate methods that can provide near-optimal solutions within a reasonable timeframe.\n"}]

Author rebuttal:
Many thanks for all reviewers' constructive and valuable comments. Following their suggestions, we have made the following main revisions:

1. **Motivation:** We have revised some descriptions to make the connection between our motivation and the proposed method clearer according to the comments of Reviewer TTgk.

2. **Method:** We have supplemented more details of our method, including the model design, fine-tuing process, and inference process.

3. **Experiment:** We have conducted the experiments about the solution distribution according to the suggestions of Reviewer d8Lb.

4. **Addition:** We have further clarified some results of the ablation and hyperparameter study.

Meta-review: All of the reviewers except TTgk agree that the paper should be accepted and reviewer TTgk did not have major concerns - their remaining concerns were around the "modest degree of enhancement and the relatively minor contributions". Other reviewer's found this "This work is a timely contribution to a promising research direction." Given the lack of major concerns and general enthusiasm for the paper by the reviewers, I'm inclined to accept the paper.
Decision: Accept (poster)