Neural Multi-Objective Combinatorial Optimization with Diversity Enhancement
Authors: Jinbiao Chen
Zizhen Zhang
Zhiguang Cao
Yaoxin Wu
Yining Ma
Te Ye
Jiahai Wang
Venue: NeurIPS 2023 poster (2023)
Keywords: neural heuristic
diversity enhancement
deep reinforcement learning
multi-objective combinatorial optimization
TL;DR: We propose a novel neural heuristic with diversity enhancement for multi-objective combinatorial optimization problems

Abstract: Most of existing neural methods for multi-objective combinatorial optimization (MOCO) problems solely rely on decomposition, which often leads to repetitive solutions for the respective subproblems, thus a limited Pareto set. Beyond decomposition, we propose a novel neural heuristic with diversity enhancement (NHDE) to produce more Pareto solutions from two perspectives. On the one hand, to hinder duplicated solutions for different subproblems, we propose an indicator-enhanced deep reinforcement learning method to guide the model, and design a heterogeneous graph attention mechanism to capture the relations between the instance graph and the Pareto front graph. On the other hand, to excavate more solutions in the neighborhood of each subproblem, we present a multiple Pareto optima strategy to sample and preserve desirable solutions. Experimental results on classic MOCO problems show that our NHDE is able to generate a Pareto front with higher diversity, thereby achieving superior overall performance. Moreover, our NHDE is generic and can be applied to different neural methods for MOCO.

Neural Multi-Objective Combinatorial Optimization with Diversity Enhancement
Jinbiao Chen', Zizhen Zhang', Zhiguang Cao Yaoxin Wu², Yining Ma²,
Te Ye², and Jiahai Wang1.5.6
School of Computer Science and Engineering, Sun Yat-sen University, P.R. China
School of Computing and Information Systems, Singapore Management University, Singapore Department of Industrial Engincering & Innovation Sciences, Eindhoven University of Technology, Netherlands
Department of Industrial Systems Engineering & Management,
National University of Singapore, Singapore
KKey Laboratory of Machine Intelligence and Advanced Computing, Ministry of Education, Sun Yat-sen University, P.R. China
GGangdoog Key Laboratory of Big Data Analysis and Processing, Guangzhou, P.R. China sysu. edu.
2henjb699mai12..o sysu. edu. en, zhangzzh70mail syyu zgcao@smu edu ag, y. wu2@tue nl, yiningma@u. nus. edu yete@mai12. sysu. edu. cn, wangjiahee sysu edu, cn
Abstract
Most of existing neural methods for multi-objective combinatorial optimization (MOCO) problems solely rely on decomposition, which often leads to repetitive solutions for the respective subproblems, thus limited Pareto set. Beyond decom- position, we propose a novel neural heuristic with diversity enhancement (NHDE) to produce more Pareto solutions from two perspectives. On the one hand, hinder duplicated solutions for different subproblems, enhanced deep reinforcement learning method to guide the model, and design a heterogeneous graph attention mechanism to capture the relations between the instance graph and the Pareto front graph. On the other hand, to excavate more solutions in the neighborhood of each subproblem, optima strategy to sample and preserve desirable solutions. Experimental results classic MOCO problems show that our NHDE is able to generate Pareto front with higher diversity, thereby achieving superior overall performance. Moreover, our NHDE is generic and can be applied to different neural methods for MOCO.
propose an indicator-
present multiple Pareto
Introduction
Multi-objectio combinatorial optimization (MOCO) has been extensively studied in the communities of computer science and operations research [1, 2]. also commonly exists in many industries. such as transportation [3]. manufacturing [4], energy [5], and telecommunication [6]. MOCO features multiple conflicting objectives based on NP-hard combinatorial optimization (CO), practical yet more complex. Rather than finding an optimal solution like in the single-objective optimization, MOCO pursues a set of Pareto-optimal solutions, called Pareto set, to trade-off the multiple objectives. In general, decent Pareto set is captured by both desirable convergence (optimality) and diversity.
Since exactly solving MOCO may require exponentially increasing computational time [7], the heuristic methods [8] have been favored in practice over the past few decades, which aim to yield an
"Corresponding Author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Points
Points F Ulr))
Poluts 5 U(r)
Instanne
Instonces
Waight
Weight 2?
Diversily Eaclorw
E(xe)
21
Diversily Factor
((xe)
FICA Model
[(xe)
FIGA Model
(00)
f(x))
(x))
MPO
F ((0)
Parato from::
Parato front
F(32)
Figure The framework of NHDE. For subproblem i, the heterogeneous graph attention (HGA) model takes instance points Fi (rr, weight X', and diversity factor w as inputs, and generates solutions to optimize the scalar objective and hypervolume (size the gray area). More solutions are sampled and the Pareto front F is then efficiently updated based multiple Pareto optima (MPO).
approximate Pareto set. Despite a relatively high efficiency, heuristic methods need domainnspecific knowledge and massive iterative search. As neural CO methods based on deep reinforcement learning (DRL) recently achieved notable success in CO problems such as routing, scheduling, and bin packing [9-12], number of neural MOCO methods have also been accordingly developed [13-16]. Typically, parameterized as a deep model, Neural MOCO is able to automatically learn a heuristic (or policy), so to directly construct near-optimal solutions in an end-to-end fashion, which takes much less computational time than the traditional ones.
Existing neural MOCO methods mostly decompose an MOCO problem into series of single- objective CO subproblems and derive Pareto set by solving them. However, while enjoying a favorable efficiency for neural MOCO, the sole decomposition is less effective in finding as many diverse solutions as possible, since constructing an optimal solution for the decomposed subproblems is always carried out independently, causing repetitive or duplicated ones for different subproblems.
To tackle this issue, we propose a neural heuristic with diversity enhancement (NHDE), illustrated in Figure 1. Distinguished from existing neural methods, NHDE couples the decomposition with a comprehensive indicator to learn a policy that can produce diverse solutions across the subproblems while further improving the performance. Besides, for given subproblem, multiple relevant solutions, rather than single optimal solution with respect to the scalar objective, are found based on proposed multiple Pareto optima (MPO) strategy, so as to further strengthen the diversity.
Our contributions summarized as follows. (1) We propose an indicator-enhancel DRL method. To encourage the deep model to generate different yet diverse solutions for decomposed subproblems, NHDE inputs the Pareto front composed of the preceding solutions and introduces an indicator comprehensively measuring convergence and diversity in the reward. (2) We design heterogeneous graph attention model effectively capture the correlation between instance graph and its Pareto front graph. (3) We present multiple Pareto optima (MPO) strategy to further identify more relevant solutions the neighborhood of each subproblem and efficiently update the Pareto front. (4) We deploy our NHDE with two different types of neural MOCO methods to demonstrate its versatility, Experimental results based on various MOCO problems show that our NHDE outperforms state-of-the-art neural baselines, especially with significant improvement in the diversity.
2 Related works
Exact and heuristic methods for MOCO. Exact methods [7, 17] for MOCO can attain the accurate Pareto set, but their computational time may grow exponentially, rendering them less practical. As an alternative, heuristic methods such as multi-objective evolutionary algorithms (MOEAs) have gained widespread attention in practice. Dominance-based NSGA-II [18], decomposition based MOEA/D [19], and indicator- based SMS-EMOA [20] are three typical paradigms MOEAs. In these MOEAs, local search, a crucial technique specialized to the target CO, is usually employed [21-23].
Neural CO. In the past few years, neural construction methods [24-26] were proposed to rapidly yield high-quality solutions in an end-to-end fashion. A well-known representative is Attention Model (AM) [27], which was developed based on the Transformer architecture [28]. Then, AM inspired large number of subsequent works [29-35], which further boosted the performance. Among them,

---

the policy optimization with multiple optima (POMO) [36], leveraging the solution and problem symmetries, recognized as a prominent approach. Besides, the other line of works, known as neural improvement methods [37-41], exploited DRI. to assist the iterative improvement process from an initial but complete solution, following a learn-to-improve paradigm.
Neural MOCO. Decomposition is mainstream scheme in learning- based methods for multi- objective optimization [42-44]. An MOCO problem can be decomposed into a series of single- objective CO problems and then solved by neural construction methods to approximate the Pareto set. couple of preliminary works trained multiple deep models with transfer learning [13, 45], where each deep model coped with one subproblem. Evolutionary learning [46, 47] was introduced evolve deep models to further improve the performance. Instead of training multiple deep models for preset weights. preference-conditione multi-objective combinatorial optimization (PMOCO) (14) and Meta-DRL, (MDRL) [15], both of which only trained one deep model, were more flexible and practical. For given weight vector, the former used hypemetwork to derive the decoder parameters to solve the corresponding subproblem, while the latter rapidly fine-tuned pre-trained meta-model to solve the corresponding subproblem. However, those solely decomposition- -based neural MOCO methods are limited in the diversity with respect to the solutions the Pareto set, since some subproblems may lead to duplicated solutions, especially when they are solved independently.
3 Preliminary
3.1 MOCO
An MOCO problem with M objectives can be expressed as min f(x) (((),.. ...., (n)())))
=EX
where X is set of discrete decision variables.
Definition (Pareto dominance), solution x E X dominates another solution x² E (x! x²), if and only if fi(')) S fi(2)) vi E (1...., M) and 3j E {1,.... ( fz < (z²).
Definition (Pareto optimality). A solution x" X' is Pareto-optimal if it is not dominated any other solution, i.e., Alr E X such that x' - x."
Definition 3 (Pareto set/front). MOCO aims to uncover Pareto set, comprising all Pareto optimal solutions P (x" E X fœ' E X x"}. The Pareto front = (f(x) æ E P) corresponds to the objective values of Pareto set, with each f f(x) referred to as point in the objective space.
3.2 Decomposition
For MOCO, decomposition [19] is prevailing scheme due its flexibility and effectiveness. An MOCO problem can be decomposed into N subproblems with N weights. Each subproblem is single-objective CO problem via scalarization g(ælA) with weight À M satisfying Am 2 0 and Σm Am = 1. The Pareto set then can be derived by solving the subproblems.
The simplest yet effective decomposition approach is the weighted sum (WS). It uses the linear scalarization of M objectives, which hardly raises the complexity of the subproblems, as follows,
min ( #EX
Amfm(()
3.3 Indicator
Hypervolume (HV) is a mainstream indicator to measure performance, as it can comprehensively assess the convergence and diversity without the exact Pareto front [48], For a Pareto front F in the objective space, HV, (FF with respect to a fixed reference point r E RM defined as follows,
HV, =M U1(())))))
f(a)EF
where y is the Lebesgue measure, i.e., M M-dimensional volume, and [f(x), r) a dimiensioonll cube. i.c., [f(z), = (f) x ... (M).
3

---

A 2--imennsional example with 5 points in the objective space is depicted in Figure 1, where F = f f(x*), f(=")) (F) equal to the size of the gray area, and finally normalized into [0, 1]. All methods share the same reference point r for problem (see Appendix A).
4
Methodology
Our neural heuristic with diversity enhancement (NHDE) exploits diverse solutions across different subproblems and leverages a multiple Pareto optima (MPO) strategy to find multiple neighbor solutions for each subproblem, as illustrated in Figure 1. Specifically, an MOCO problem is decomposed into N single-objective subproblems with N weights, which are solved dependently by unified heterogeneous graph attention (HGA) model O. For each subproblem i, its features together with the current Pareto front F (points the objective space) constituted by preceding solutions are input to model 0, which is guided by the scalar objective with the HV indicator. Then, MPO utilized to sample multiple solutions and efficiently update F.
DRL to produce
4.1 Indicator-enhanced DRL
Given a problem instance 8, sequentially solve its subproblem i (1, ...,,..,.............. N., each associated denote the obtained solution" at step i, and let F be the
with weight X Let π = { σ Pareto front yielded by solutions from subproblem I to i. In each step we select up to K top points f(T) E Fi-1 from the Pareto front at step i-1 with the ranking determined by the scalar objective g( X²) with respect the new given weight A The corresponding scalar objective and the induced surrogate landscape fi-1 1 C Fi-1 based on those selected solutions are treated as the policy network inputs (see Figure 2), so as to construct a new solution π² and yield a new Ft
The construction of the solution n' with length T for each subproblem i can be cast Markov decision process. In particular, 1) the state includes the weight X user-defined diversity factor w' E R2 satisfying wi, wh 2 O and w| + w/ = 1, partial solution i instance 8, and Fi-1, where f:11 fi-1 U {r) incorporates the aforementioned surrogate landscape at step i and the given reference point r; 2) the action is to add a node कं. into vi:-1:3. 3) the state transition transforms Tia-1 to wi:. denoted as Ti: = ( mi}; 4) the reward defined as R² where we introduce the hypervolume HV, HV- (f(T'))) }}) to guide the search; and 5) the stochastic policy generating the solution σ' expressed as P(T (s, 15 X w²) II=,, Pa (i.
-wi x g(rr's, Iss + x (H,,(F+-UUE
X², w²), with the probability of node selection Pe (T/ITTLL Fi-1 X', w") parameterized by deep model O.
We would like to note that our NHDE is generic, and can directly integrate the base model with the existing decomposition- based neural MOCO methods. We demonstrate this property by applying it to two state-of-the-ar art methods, PMOCO [14] and MDRL [15], denoted as NHDE-P and NHDE-M, respectively. Given A and w² as inputs, NHDE-P uses hypernetwork to generate the decoder parameters of the model O w²), while NHDE-M fine-tunes the pre-trained meta model Ometa with few steps to address the corresponding subproblem. More details are presented in Appendix B.
4.2 Heterogeneous graph attention
To effectively solve subproblem i, the model should jointly capture the representations of both the instance's 's node graph and the Pareto front's point graph. Based on the thus design a heterogeneous graph attention (HGA) model to correlate the two heterogeneous graphs as depicted in Figure 2. In the following section, we omit superscript for better readability.
structure,
Encoder. Given an instance graph s containing n nodes with Z-dimensional features and Pareto front graph Pi-1 containing k points (k S K + 1) with M-dimensional features, their initial embed- (0)
dings h (0) ..... h E Rd and "'),....... .....g9
. E Rd are yielded by a linear projection with trainable parameters W,, and W,, respectively, and d is empirically set to 128. The eventual embeddings
(I.) h ( (1)) and gi ........ g
(I.) are derived by further passing through L 6 attention layers.
"In this sub-section, we consider the construction of only one solution in each step for better readability; however, note that multiple solutions can be sampled and formulation would work in similar manner.

---

Surrogate Landscage
Pareto Front: Graph
Instance Graph
Point Features
Node Features
Linear Projection
Linear Projection
L Layers
Steps
HGA
40
K
Add & Norm
Pi
Ph
e
Softmax
P2N thn
N2P Adin
N2N Att
Feod Forward
Competibility
Add
Add & Norm
HIGA
Heterooanzous GraphAttention
Encoder
Decodlr
Figure 2: Illustration of the proposed heterogeneous graph attention (HGA) model.
Each attention layer is composed of multi-head HGA layer with Y 8 heads and fully con- nected ferw-forward sublayer. For layer I (1....,I, L}, HGA computes the representations h and 9 across the heterogeneous graphs, which are used to update the embeddings h and g Skip-connection [49] and batch normalization [50] are both adopted in each sublayer, as follows,
h BN, + FF(h.)), h. BN (N h Vu E (I....,n) gu BN FF()w)). 9. BN "- + + Vu ()..
Decoder. The decoder, composed of multi-head HGA layer and a compatibility layer, autoregres- sively constructs solution according to the probability distribution with T steps. At decoding step t (1...., T). the glimpse q. of the context embedding he (see Appendix C) is computed by the HGA layer. Then, compatibility a calculated as follows,
node u is masked
Qa
C tanh( L. (W
otherwise
(5)
V
where C is set to 10 [27]. Finally, softmax is employed to calculate the selection probability distribution ss Fi-1, Xi, w²) for nodes, i.e., (o( 1, "" ('') Softmax(a).
HGA. The HGA layer in the encoder captures three key relations between the node graph and the point graph. The first, node-to-node hhh indicates each node's attention towards others within the same instance to construct a promising solution. The second, node-to-point a suggests each node's d attention to points, guiding the constructed solutions distinct from the existing ones in the current Pareto front. The third, point-to-nock aggh, indicates each point's attention to nodes, facilitating the learning of the mapping from a solution to its objective values. We disregard the less meaningful point-to-point attention. Concretely, Eq. (6) defines the above three attention scores, which are separately normalized as Thh ugg and hhy by softmax. Then, h. and gn. are computed by Eq. (7).
(W h.. (WWW h...
(W h..)" (W gv)
(W9 gz)² ) ((W hw)
Ahh 0.ge
gh Oue
(6)
Va/Y
Vd/Y
Vd/Y
Σ shhwy h
W 9 go. gu
Σ
agh Wgh h
(7)
Finally, as for the
attention, hn and 9. are further computed as follows, h W CorfCoonat(ee
Iu Concet(@.........
(8)
where huy and Ju.y for head E {1,..., YY are obtained according to Eq. (7). In the multi- head HGA, W W.K. WV, ".Y,V WO WQ, W.K WV. and Wo are independent trainable parameters. Similarly, in the decoder, the glimpse qe calculated by the context embedding h. with the addition of the context context-to-node and context-to- attention, i.c., replacing h. with h. in the Eq. (6-8).
5

---

Algorithm 1 Training algorithm of NHDE-P
1: Input: weight distribution A, diversity- factor distribution W, instance distribution S, number of training steps E, number of sampled weights per step N', batch size B, instance size n
2: Initialize the model parameters 0
3: for e c==1 to E do
4: 8; ~ Sammpelnstance((S)
Vi (I,
5: Initialize Fi < Vi
6: for n' to N" do
7:
À ~ SampleWeight
8:
w SampleDiveesityyacctr(())))
9:
नं ~ CumppleSolutionn(err.uu (-)81, Fr, w)) We ... , Vj E (1, .
10:
R. -w1g(<= s1 A) wwllV, (f(T))) Vi,j
11:
by " Σド= (-
1
Vi
12:
Fr, A, ww] (J) E Σj= b.) VorA,)))) log Po(a ( TT/1s;,
0 + Adam (J()))
14:
G. + ((T Vi
15:
F. - MPO(R Vi
end for 17: end for
Output: The model parameter
4.3 Multiple Pareto optima strategy
Contrary to single-objective problems that focus on a single optimal solution, MOCO problems involve series of Pareto-optimal solutions. In light of this, we introduce a multiple Pareto optima (MPO) strategy to uncover multiple solutions for each subproblem by leveraging the Pareto optimality.
When solving subproblem i, more than one solution can be attained by sampling, e.g., sampling with multiple start nodes as did in POMO [36]. In this case, F MPO g"), where G contains all the candidate points (find by sampling) to be introduced in the new Pareto front and (P an operator that updates the Pareto front. However, as the complexity of MPO u G¹) is O(( + G [)|G' ). it may take relatively long time, especially when there are thousands of points F and G Thus, we suggest an efficient update mechanism executed on the surrogate Pareto fronts, Fi MPO(F U g'), where ğ' G includes at most (usually setting K) best points selected from f(T)) E g according to g (TT],, X²). The complexity of MPO(F- U is then reduced to O((K- - J)J), which is able to curtail the overall solving time in practice.
4.4 Training and inference
Our NHDE can be applied to different decomposition- based DRL methods, e.g., PMOCO [14] and MDRL and the training algorithm is easy adapt with slight adjustments. where the one for NHDE-P presented in Algorithm 1. The key points include three aspects. (1) Multiple weights are sampled to train the same instance (Line 6), since the solving processes for those subproblems
are dependent. (2) The HV indicator is adopted in the reward (Line 10). (3) Multiple Parcto-optimal solutions are preserved via MPO (Line 15). Note that when training with a batch, the point sets with different sizes of the instances are padded with repetitive reference points, which are masked in the attention, based on the maximum size. The training algorithm of NHDE-M is given in Appendix E.
In the inference phase, for N given weights and diversity factors, the well-trained model is used to sequentially solve N corresponding subproblems, as shown in Figure 1. Moreover, instance augmentation [14] can be also brought into our MPO for each subproblem, i.e., the points of all sampled solutions from an instance and its augmented instances are included in G Our NHDE can achieve desirable performance by using only parts of instance augmentation (see Appendix D), since it can already deliver more diverse solutions.

---

5 Experiments
Problems. We evaluate the proposed NHDDE on three typical MOCO problems that are commonly studied in the neural MOCO literature [13-15], namely the multi-objective traveling salesman problem (MOTSP) [51], multi-objective capacitated vehicle routing problem (MOCVRP) [3], and multi-objective knapsack problem (MOKP) [52]. More specifically, we solve bi-objective TSP (Bi-TSP), tri-objective TSP (Tri-TSP), the bi-objective CVRP (Bi-CVRP) and the bi-objective KP (Bi-KP). For the M-objective TSP with n nodes, each node has M sets of 2-dimensional coordinates, where the m-th objective value of the solution is calculated with respect to the m-th coordinates. Bi-CVRP consists of customer nodes and depot node, with each node featured by a 2-dimensional coordinate and each customer node associated with a demand. Following the literature, we consider two conflicting objectives in Bi-CVRP, i... the total tour length and the makespan (that is the length of the longest route). Bi-KP is defined by n items, with each taking a weight and two separate values. The m-th objective is to maximize the sum of the m-th values but not exceed the capacity. Three sizes of these problems are considered, i.e., n=20/50/100 100 for MOTSP and MOCVRP, and m=50/100//000 for MOKP. The coordinates, demands, and values uniformly sampled from [0, 1J2. {1....,) 9), and [0, 1J. respectively. The vehicle capacity is set to 30/40/50 for MOCVRP20/50/100 The knapsack capacity is set to 1 12.5/25/25 for MOKP50/100/200.
Hyperparameters. We train NHDE-P with 200 epochs, each containing 5,000 randomly generated instances. We use batch size B = 64 and the Adam [53] optimizer with learning rate 10 (10 for MOKP) and weight decay 10 6, During training, N' = =2 weights are sampled for each instance. During inference, we generate N = 40 and N 210 uniformly distributed weights for 2 and M=3, respectively, which are then shuffled so as to counteract biases. The diversity factors linearly shift through the N subproblems from (1,0) to (0.1), which implies a gradual focus from achieving convergence (scalar objective) with a few solutions to ensuring comprehensive performance with a multitude of solutions. We set K 20 and J 200. See Appendix F for the settings of NHDE-M.
Baselines. We compare NHDE with two classes of state-of-the-ard methods. (1) The neural methods, including PMOCO [14]. MDRL [15], and DRL-based multiobjective optimization algorithm (DRL- MOA) [13], all with POMO as the backbone for single-objective CO subproblems. Our NHDE-P and NHDE-M each train unified model with the same gradient steps PMOCO and MDRL, respectively, while DRL-MOA trains 101 (105) models for M = 2 (M- = 3) with more gradient steps, i.e., the first model with 200 epochs and the remaining models with 5-epoch per model via parameter transfer. (2) The non-learnable methods, including the state-of thrt MOEA and strong heuristics. Particularly, PPLS/D-C [23] is specialized MOEA for MOCO with local search techniques, including 2- opt heuristic for MOTSP and MOCVRP, and a greedy transformation heuristic [52] for MOKP, implemented in Python. In addition, LKH [54, 55] and dynamic programming (DP), are employed to solve the weighted-sum (WS) based subproblems for MOTSP and MOKP, denoted as WS-LKK and WS-DP, respectively. All the methods use WS scalarization for fair comparisons. All the methods are tested with an RTX 3090 GPU and an Intel Xeon 4216 CPU. Our code is publicly available".
Metrics. We use hypervolume (HV) and the number of non-dominated solutions (NDS).. A higher HV means better overall performance in terms of convergence and diversity, while [NDS] reflects the diversity when HVs are close. The average HV, gaps with respect to NHDE, and total running time for 200 random test instances are reported. The best (second-best) best) and its statistically insignificant results at 1% % significance level of Wilcoxon rank-sum test are highlighted in bold (underline).
5.1 Main results
All results of NHDE-P and the baselines are displayed in Table 1. Given the same number of weights (wt.), NHDE-P significantly surpasses PMOCO for all problems and sizes in terms of HV and [NDS], which indicates that NHDÉ-P has the potential to discover diverse and high-quality solutions. When instance augmentation (aug.) is equipped, NHDE-P achieves the smallest gap among the methods in most cases, except Bi-TSP100 and Bi-CVRP100 where WS-LKH and DRI-MOA perform better. However, WS-LKH consumes much longer runtime than NHDE-P due iterative search (2.7 hours vs 5.6 minutes), and DRL-MOA costs much more training overhead to prepare multiple models for respective weights. Besides, another reason why NHDE-P inferior to DRL-MOA on Bi-CVRPIOU might be that the hypernetwork (inherited from PMOCO) could be hard to cope with the objectives
"https://ggthhur ftaap::://gituub.com/bbl.i. cjbb//HD
7

---

Table 1: Results of NHDE-P on 200 random instances for MOCO problems.
Bi-TSP20
Bi-TSP50
Bi-TSPI00
Method
HVT
INDS
Gapl
Time
HV1
|NDS
Gapl
Time
HVT
NDS
Gapl
Time
WS-LKH (40 wt.)
0.6266
14
0.46%
4.1m
0.6402
0.42%
42m
0.7072
37
-0.31%
2.7h
PPT.S/D-C (200 iter.)
0.6256
71
0.62%
26m
0.6282
213
2.29%
2.8h
0.6844
373
2.92%
11h
DRL-MOA (101 models)
0.6257
23
0.60%
6s 0.6360
57
1.07%
0.69770
70
1.13%
21s
PMOCO (40 wt.)
0.6258
17
0.59%
4s 0.6331
31
1.52%
5s 00.6938
36
1.59%
8s
PMOCO (600 wt.)
0.6267
23
0.44%
27s 0.6361
68
1.06%
53s
0.6978
131
1.02%
2.1m
NHDE-P (40 wt.)
0.6286
56
0.14%
19s
0,6388
127
0.64%
53s
00.7005
193
0.64%
1.9m
PMOCO (40 wt. aug.)
0.6266
17
0.46%
23s 0.6377
32
0.81%
1. 1.6m 0.6993
37
0.81%
3.0m
PMOCO (100 wt. aug.)
0.6270
20
0.40%
1.4m 0.6395
53
0.53%
3.8m 0.7016
76
0.48%
15m
NHDE-P (40 wt. aug.)
0.6295
81
0.00%
1.5m 0.6429
269
0.00%
2.5m 0.7050
343
0.00%
5.6m
Bi-CVRP20
Bi-CVRP50
Bi-CVRPI00
Method
HV1
[NDS]t
Gapl.
Time
HVT
|NDS|t
Gapl
Time
HV1
NDS
Gap]
Time
PPLS/D-C (200 iter.)
0.4283
14
0.46%
1.3h 0,4007
17
2.15%
9.7h
0.3946
20
1.13%
38h
DRL-MOA (101 models)
0.4287
7
0.37%
10s
0.4076
10
0.46%
12s
0.4055
12
-1.60%
33s
PMOCO (40 wt.)
0.4266
6
0.86%
4s 0.4035
1.47%
7s
0..3
6
1.98%
12s
PMOCO (300 wt.)
0.4268
7
0.81%
20s
0.4039
1.37%
35s
0.3914
8
1.93%
1.2m
NHDE-P (40 wt.)
0,4284
12
0.44%
18s
0.4062
14
0.81%
36s
0..933
10
1.45%
1.1m
PMOCO (40 wt. aug.)
0,4492
6
0.26%
8s
0.4078
0.42%
15s
0.3368
7
0.58%
1.1m
PMOCO (300 wt. aug.)
0.4294
9
0.21%
1.0m 0,4081
0.34%
1.8m
0.3969
9
0.55%
7.0m
NHDE-P (40 wt. aug.)
0.4303
21
0.00%
%
1.2m 0.4095
0.00%
1.5m 0.3991
16
0.00%
2.4m
Bi-KP50
Bi-KPI00
Bi-KP200
Method
HVt
INDS|
Gapl
Time
HVT
|NDS
Gapl.
Time
HVT
NDS
Gap4
Time
WS-DP (40 wt.)
0.3560
10
0.11%
9.6m
0.4529
16
0.26%
1.3h
00.3598
23
0.39%
3.8h
PPLS/D-C (200 iter.)
0.3528
13
1.01%
18m
0,4480
19
1.34%
47m
0.3541
20
1.97%
1.5h
DRE-MOA (101 models)
0,3559
21
0.14%
9s
0.4531
0.22%
18s
0.3601
48
0.30%
1.0m
PMOCO (40 wt.)
0,3550
14
0.39%
6s
0,4518
22
0.51%
9s
00.3590
28
0.61%
25s
PMOCO (300 wt.)
0.3552
17
0.34%
29s
0.4524
31
0.37%
1.1m
0.3597
46
0.42%
3.0m
NHDE-P (40 wt.)
0.3564
30
0.00%
%
29s
0,4541
83
0.00%
1.0m
0,3612
243
0.00%
2.7m
Tri-TSP20
Tri-TSP00
Tri-TSP100
Method
HV1
INDS
Gapl
Time
HV1
INDS|t
Gapl
Time
HVT
NDS
Gapl
Time
WS-LKH (210 wt.)
0.4727
78
0.82%
23m 0.4501
189
1.90%
3.5h
0.5165
209
0.84%
12h
PPLS/D-C (200 iter.)
0,4698
876
1.43%
1.4h 0.4174
3727
9.02%
3.9h
0.4376
8105
15.99%
14)
DRL-MOA (105 models)
0.4675
72
1.91%
5s 0.4285
98
6.61%
9s
0.44550
101
6.89%
19s
PMOCO (210 wt.)
0.4714
113
1.09%
Ils 0.4381
198
4.51%
18s
0..446
207
5.05%
39s
PMOCO (3003 wt.)
0.4741
264
0.52%
2.3m 0.4484
1339
2.27%
4.6m
0.5087
2330
2.34%
10m
NHDE-P (210 wt.)
0.4758
675
0.17%
1.2m 0.4506
2547
1.79%
4.4m
0.5111
4984
1.88%
10m
PMOCO (210 wt. aug.)
0,4427
104
0.82%
21m 0.4471
201
2.55%
1.1h
0.5544
209
3.17%
4.2h
PMOCO (153 wt. aug.)
0.4722
89
0.92%
15m 0.4447
150
3.07%
47m
0.5009
153
3.84%
3.
NHDE-P (210 wt. aug.)
0.4766
527
0.00%
%
14m
0.4588
9047
0.00%
30m
0.5209
16999
0.00%
1.5h
with imbalanced scales. Considering this drawback of PMOCO. we also apply our method to MDRL, i.e., NHDE-M, and demonstrate that NHDE-M outperforms DRI-MOA on Bi-CVRP100 in Table 2. Also, NHDE-M outperforms MDRL in all cases. More results of NHDE-M are given in Appendix G.
Regarding the inference efficiency, NHDE-P generally takes (tolerably) more runtime than the other learning based methods. To be fair, we further enhance the state ofthe-r PMOCO by adjusting the number of the weights, so that it takes similar or even more runtime compared with NHDE-P. The results in the last two lines for each problem shows that NHDE-P still attains the smaller gaps. We also observe that [NDS] hardly grows along with the increase of number of weights for PMOCO, since numerous solutions to different subproblems could be repetitive. In contrast, NHDE-P is able to produce more diverse solutions with much fewer weights.
5.2 Generalization study
To assess the generalization capability of NHDE-P, we compare the trained models (from neural methods) for Bi-TSP100 and the other baselines on 200 random Bi-TSP instances with larger sizes, i..., S5-TSP1100/006 Three commonly used benchmark instances developed from TSPLIB [56].
8

---

Table 2: Results of NHDE-M on 200 random instances for MOCO problems.
Bi-TSP20
Bi-TSP50
Bi-TSPI00
Method
HVT
INDS
Gapl
Time
HVt
|NDS
Gapl
Time
HVT
NDS
Gapl
Time
WS-LKH (40 wt.)
0.6266
14
0.46%
4.1m
0.6402
0.42%
42m
0.7072
37
-0.33%
2.7h
PPL.S/D-C (200 iter.)
0.6256
71
0.62%
26m
0.6282
213
2.29%
2.8h
0.6844
373
2.91%
11h
DRL-MOA (101 models)
0.6257
23
0.60%
6s
0.6360
57
1.07%
0.6970
70
1.12%
21s
MDRL (40 wt.)
0.6264
20
0.49%
2s 0.6342
1.35%
3s 00.6940
36
1.55%
8s
NHDF-M (40 wt.)
0.6287
58
0.13%
20s
0,6393
132
0.56%
57%
(0.7008
195
0.58%
2.0m
MDRL (40 wt. aug.)
0.6267
18
0,44%
21s
0,6384
34
0.70%
1.5m
0.69955
38
0.77%
3.3m
NHDE-M (40 wt. aug.)
0.6295
81
0.00 %
1.5m 0.6429
273
0.00%
2.6m
0.7049
339
0.00%
5.5m
Bi-CVRP20
Bi-CVRP50
Bi-CVRPI00
Method
HVt
INDS
Gapl
Time HVt
INDS|t Gapl.
Time
HV1
NDS Gap]
Time
PPLS/D-C (200 iter.)
0.4287
15
0.42%
1.6h
0.4007
2.34%
9.7h
0.3946
20
3.14%
38h
DRL-MOA (101 models)
0.4287
7
0.42%
10s
0.4076
10
0.66%
12s
0.4055
12
0.47%
33s
MDRL (40 wt.)
0.4284
9
0.49%
3s 0.4057
1.12%
58
00.4055
0
1.45%
10s
NHDE-M (40 wt.)
0.4296
16
0.21%
23s
0.4086
0.41%
47s
0,,455
18
0.52%
1.4m
MDRL (40 wt. aug.)
0.4293
9
0,28%
5s
0,4073
11
0.73%
16s
00.4040
11
0.83%
1.0m
NHDE-M (40 wt. aug.)
0.4305
24
0.00
%
1.2m
0.4103
29
0.00%
1.6m
0.4074
26
0.00%
2.7m
Bi-
Bi-KP100
Bi-KP200
Method
HV1
[NDS|t
Gapl
Time
HV1
[NDS|t
Gapl
Time
HV1
NDS
Gapl
Time
WS-DP (40 wt.)
0.3560
10
0.17%
9.6m 0,4529
16
0.29%
1.3h
0.3598
23
0.30%
3.8h
PPLS/D-C (200 iter.)
0.3528
13
1.07%
18m
0,4480
19
1.37%
47m
0.3541
20
1.88%
1.5h
DRL-MOA (101 models)
0,3559
21
0.20%
9s 0.4531
38
0.24%
18s
0.3601
48
0.22%
1.0m
MDRL (40 wt.)
0.3559
17
0.20%
4s
0.4528
25
0.31%
8s
0.3594
31
0.42%
24s
NHDE-M (40 wt.)
0.3566
41
0.00%
31s
0.4542
93
0.00%
1.0m
0.3609
160
0.00%
2.8m
TH-TSP20
TriTTSP50
Tri-TSP100 NDS
Method
HV1
INDS|t
Gapl.
Time
HVT
|NDS
Gapl
Time
HVT
Gapl
Time
WS-LKH (210 wt.)
0.4727
78
0.82%
23m
0.4501
189
2.00%
3.5h
0.5165
209
-0.92%
12h
PPLS/D-C (200 iter.)
0.4698
876
1.43%
1.4h 0.4174
3727
9.12%
3.9h
0.4376
8105
14.50%
14h
DRL-MOA (105 models)
0.4675
72
1.91%
5s 0.4285
98
6.71%
9s
00.4850
101
5.24%
19s
MDRL. (210 wt.)
0.4723
126
0.90%
14s 0.4388
199
4.46%
20s
(0.4956
207
3.17%
40s
NHDE-M (210 wt.)
0.4763
783
0.06%
1.4m 0.4512
2636
1.76%
4.7m
0.4997
4056
2.36%
11m
MDRL (210 wt. sug.)
0.4727
107
0.82%
14m
0.4473
202
2.61%
53m
0.5006
209
1.21%
4.3h
NHDE-M (210 wt. aug.)
0.4766
748
0.00%
13m
0.4593
10850
0.00%
30m
0.5118
13216
0.00%
1.5h
Table 3: Results on 200 random instances for larger-scale problems.
Bi-TSP150
Bi-TSP200
Method
HVT
INDS
Gapl
Time
HVt
NNSS
Gapl
Time
WS-LKH (40 wt.)
0.7075
39
-0.90%
5.3h
0.7435
40
-1.22%
8.5h
PPLS/D-C (200 iter.)
0.6784
473
3.25%
21h
0.7106
512
2.98%
32h
DRL-MOA (101 models)
0.6901
73
1.58%
45s
0.7219
75
1.43%
87s
PMOCO (40 wt.)
0.6891
37
1.73%
22s
0.7215
38
1.49%
41s
PMOCO (400 wL)
0.6938
160
1.06%
3.7m
0.7259
186
0.89%
6.8m
NHDE-P (40 wt.)
0.6964
231
0.68%
3.0m
0.7280
259
0.60%
4.3m
PMOCO (40 wt. aug.)
0.6944
38
0.97%
20m
0.7264
39
0.82%
40m
NHDE-P (40 wt. aug.)
0.7012
372
0.00%
14m
0.7324
384
0.00%
26m
i.., KroABI00, KroAB150, and KroAB200, are also tested. The comparison results and Pareto fronts are demonstrated in Table 3 and Figure 3, respectively. As shown, NHDE-P outperforms the state-of-the-art MOEA (i.e., PPLS/D-C) and other neural methods significantll, in terms of HV and [NDS), which means superior generalization capability. The figure again verifies that NHDE-P generates a more extended Pareto front than PMOCO, showing a better diversity. Although PPLS//DC finds large number of solutions, they are inferior in terms of the optimality, with a biased distribution (e.g., crowded in certain regions). contrast, NHDE-P generates a more well-distributed Pareto front with stronger convergence. More results on generalization are given in Appendix H.

---

NEEE F AL SAEJ
STEIE E SMBJ
NHDE ALA
TMOCO (T. sig)
PMCCO (GD Ang?
101
PMOCO (-B) 2ngo
PRLSE1-
PPLSID
WS WS-1ID wn3
40
19
27
31
(a)
(b)
(c)
Figure 3: Pareto fronts of benchmark instances. (a) KroABI00. (b) KroAB150. (c) KroAB200.
Bi-TSP50
Tri TSP50
NHDE
NHDE
Pall zug.
NIDE
0.6260
upd
NIDD w/ P2N
NHDE w/ N2P
0L6360
0.6367
[L4593
Gap 0.11%
Cup -0.0%
NHDE w F2P
It 11858
0.6200
0.6250
0.6275
0,6800
0.6575
0,6400
05 1.7
95
HIV
Tinch
(a)
(b)
Figure 4: Ablation study, (a) Effects of indicator-enhanced DRL, HGA, and MPO. (b) Effects the efficient update of MPO and partial instance augmentation.
5.3
Ablation Study
To analyze the effect of the indicator-enhanced DRL, we compare NHDE-P with decomposition-basee DRL without indicator (NHDE w/o I) and indicator-based DRL without decomposition (NHDE w/o D). To verify the valid design of HGA, three attention-based variants, which are formed by removing point-to-node attention (NHDE w/o P2N), removing node-to-point attention (NHDE w/o N2P), and adding point-to-point attention (NHDE P2P), are involved for comparison. To assess the impact of MPO, NHDE w/o MPO also evaluated. More details about these variants are presented in Appendix I. As from Figure 4(a). The performance of NHDE-P is significantly impaired when any of the components is ablated. Instead, NHDE w P2P degrades a bit, which reveals that the extra point-to-pr point-to-point attention may bring noises into the model. Moreover, the efficient update of MPO and partial instance augmentation in Figure 4(b), which shows that either of them saliently diminishes solving time with only little sacrifice of the performance.
evaluate the effectiveness of
Conclusion
This paper proposes a novel NHDE for MOCO problems. NHDE impedes repetitive solutions from different subproblems via indicator-enhanced DRL with HGA model, and digs more solutions in the neighborhood of each subproblem with an MPO strategy. Our generic NHDE can be deployed to different neural MOCO methods. The experimental results on three classic MOCO problems showed the superiority of NHDE, especially with regard to the diversity of Pareto set. A limitation is that HV calculation would expend additional computational time, which might hinder the scalability of NHDE for solving much larger problems with many objectives. In the future, we will explore alternative schemes like the HV approximations [57, 58] to further promote the training efficiency of NHDE, and we also intend to apply it to tackle real-world MOCO problems.
10

---

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 (2022A151501 1690, 2021A1515012299),
References
[1] Naveen Saini and Sriparna Saha. Multi-objective optimization techniques: a survey of the state-of-the-ar and applications: Multi-objective optimization techniques. The European Physical Journal Special Topicx. 230(10):231-233 23335,,,,.,2, 2021.
[2] Qi Liu, Xiaofeng Li, Haitao Liu, and Zhaoxia Guo. Multi-objective metaheuristics for discrete optimization problems: review of the state-of-the-art. Applied Soft Computing, 93:106382, 2020.
[3] Sandra Zajac and Sandra Huber. Objectives and methods in multi-objective routing problems: survey and classification scheme. European Journal of Operational Research, 290(1):1-25, 2021.
[4] Alper Türkyılmaz, Özlem Senvar, Irem Unal, and Serol Bulkan. A research survey: heuristic approaches for solving multi objective flexible job shop problems. Journal of Intelligent 9 31:1949-1983, 2020.
[5] Yunfei Cui, Zhiqiang Geng, Qunxiong Zhu, and Yongming Han. Multi-objective optimization methods and application energy saving. Energy. 125:681-704, 2017.
[6] Zesong Fei, Bin Li. Shaoshi Yang. Chengwen Xing, Hongbin Chen, and Lajos Hanzo. A survey of multi-objective optimization wireless sensor networks: Metrics, algorithms, and open problems. JEEE Communications Surveys & Tutorials, 19(1)5550-58, 2017.
Matthias Ehrgott, Xavier Gandibleux, and Anthony Przybylski. Exact methods for multi-objectivve combinatorial optimisation. Multiple criteria decision analysis: State of the art surveys, pages 817-850, 2016.
[8] Arne Herzel, Stefan Ruzika, Clemens Thielen. Approximation methods for multiobjective optimization problems: A survey. INFORMS Journal on Computing, 33(4):1284-12999 2021.
[9] Cong Zhang, Yaoxin Wu, Yining Ma. Wen Song. Zhang Le, Zhiguang Cao, and Zhang. A review on learning to solve combinatorial optimisation problems in manufacturing. IET Collaborative Intelligent Manufactwring, 5(0)2 2023.
[10] Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnacv, Reinforcement learning for combinatorial optimization: A survey, Computers & Operations Research, 134: 104:00500, 2021.
[11] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d' dohorizo.. European Journal of Operational Research, 290(2):005-411, 2021.
[12] Yimo Yan, Andy HF Chow, Chin Pang Ho, Yong-Hong Kuo, Qihao Wu, and Chengshuo Ying. Rein- forcement learning for logistics and supply chain management: Methodologies, state of the art, and future opportunities. Transportation Research Part E: Logistics and Transportation Review, 162:102712, 2022. 2022.
[13] Kaiwen Li, Tao Zhang, and Rui Wang. Deep reinforcement learning for multiobjective optimization. IEEE Transactions on Cybernetics, 51(())3103-31) 11144113,111,, 2021.
[14] Xi Lin, Zhiyuan Yang, and Qingfu Zhang. Pareto set learning for neural multi-objective combinatorial optimization. In International Conference on Learning Representations, 2022.
[15] Zizhen Zhang, Zhiyuan Wu, Hang Zhang, and Jiahai Wang. Meta-learning beaseing-based deep reinforcement learning for multiobjective optimization problems. IEEE Transactions on Neural Networks and Learning Systems, 34(10):7978-799 2023.
[16] Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, Abhishek Gupta, and Mingyan Lin. Graph learning assisted multi-objective integer programming. In Advances in Neural Information Processing Systems, 2022.
[17] David Bergman. Merve Bodur. Carlos Cardonha, and Andre A Cire. Network models for multiobjective discrete optimization. INFORMS Journal on Computing, 3402);990-1005, 2022.
[18] Kalyanmoy Deb, Amrit Pratap. Sameer Agarwal, and TAMT Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-IL IEEE Transactions Evolutionary Computation, 6(2):182-197 2002.
11

---

[19] Qingfu Zhang and Hui Li. MOEA/D: A multiobjectiiv evolutionary algorithm based on decomposition. IEEE Trunsactions on Evolationary Computation, 11(6):712-711, 2007.
[20] Nicola Beume, Boris Naujoks, and Michael Emmerich. Sms-emoa: Multiohjeettive selection based on dominated hypervolume. European Journal of Operational Research, 181(3)1653-1169, 2007.
[21] Andrzej Jaszkiewicz. Genetic local search for multi-objective combinatorial optimization. European Journal of Operational Research, 137(1):50-71, 2002.
[22] Jialong Shi, Qingfu Zhang, and Jianyong Sun. PPLS/D: Parallel pareto local search based on decomposition. IEEE transactions cybernetics, 50(3):1060 1071, 2020.
[23] 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.
[24] Oriol Vinyals, Meire Fortunato, and Navdoep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, 2015.
[25] Irwan Bello, Hieu Pham, Quoe V Le. Mohammad Norouzi. and Samy Bengio. Neural combinatorial optimization with reinforeement learning. In International Conference on Learning Representations. 2017.
[26] Mohammadreza Nazari, Afshin Oroojlooy, Martin Takáč, and Lawrence Snyder. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, 2018.
[27] Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019.
[28] 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.
[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] Yeong-Dae 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.
[31] Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-NCO: Leveraging symmetricity for neural combinato- rial optimization. In Advances in Neural Information Processing Systems, 2022.
[32] Jieyi Bi, Yining Ma, Jiahai Wang. Zhiguang Cao, Jinbiao Chen, Yuan Sun, and Yeow Meng Chee. Learning generalizable models for vehicle routing problems via knowledge distillation. In Advances in Neural Information Procexsing Systems. 2022.
[33] 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.
[34] Zizhen Zhang, Hong Liu, MengChu Zhou, and Jiahai Wang. Solving dynamic traveling salesman problems with deep reinforcement learning. IEEE Transactions on Neural Networks and Learning Systems, 34(4): 2119-2132, 2023.
[35] Jianan Zhou, Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Towards ommi-generalizablee neural methods for vehicle routing problems. In the 40th International Conference on Machine Learning, 2023.
[36] Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. POMO: Policy optimization with multiple optima for reinforcement learning. In Advances in Neural Information Processing Systems, 2020.
[37] Xinyun Chen and Yuandong Tian, Learning to perform local rewriting for combinatorial optimization. In Advances in Neural Information Processing Systems, 2019.
[38] Hao Lu, Xingwen Zhang, and Shuang Yang. A learning based iterative method for solving vehicle routing problems. In International Conference on Learning Representations, 2020.
12

---

[39] Yaoxin Wu, Wen Song. Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuristics for solving routing problems. IEEE Transactions on Neural Networks and Learning Systems, 3309:5057-5569, 2022.
[40] 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 Neural Information Processing Systems, 2021.
[41] Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song, Hongliang Guo, Yuejiao Gong, and Yeow Meng Chee. Efficient neural neighborhood search for pickup and delivery problems. In International Joint Conferences on Artificial Intelligence, 2022.
[42] Xi Lin, Zhiyuan Yang, Xiaoyuan Zhang, and Qingfu Zhang. Pareto set learning for expensive multi- objective optimization. In Advances in Neural Information Processing Systems, 2022.
[43] Aviv Navon, Aviv Shamsian, Ethan Fetaya, and Gal Chechik. Learning the pareto front with hypernetworks. In International Conference on Learning Representations, 2021.
[44] Lin, Hui-Ling Zhen, Zhenhua Li, Qing-Fu Zhang. and Sam Kwong. Pareto multi-task learning. In Advances in neural information processing systems, 2019.
[45] Hong Wu, Jiahai Wang, and Zizhen Zhang. MODRL/D-AM Multiobjective deep reinforcement learning algorithm using decomposition and attention model for multiobjective optimization. In ISICA 2019, volume CCIS 1205, pages 575-589, 2020.
[46] Yinan Shao, Jerry Chun-Was Lin, Gautam Srivastava, Dongdong Guo, Hongchun Zhang, Hu Yi, and Alireza Jolfaei. dulti-objective neural evolutionary algorithm for combinatorial optimization problems. IEEE Transactions on Neural Networks and Learning Systems, 34(4):2133 2143, 2023.
[47] 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.
[48] Charles Audet, Jean Bigeon, Dominique Cartier, Sébastien Le Digabel, and Ludovic Salomon. Performance indicators in multiobjective optimization. European Journal of Operational Research, 292(2):397-422, 2021.
[49] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEFE Conference on Computer Vision and Pattern Recognition, pages 770-778, 2016.
[50] Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. International Conference on Machine Learning, volume 37, pages 448 2015.
[51] Thibaut Lust and Jacques Teghem. The multiobjective traveling salesman problem: A survey and a new approach. In Advances in Multi-Objective Nature Inspired Computing, pages 1 199114,, 2010.
[52] Hisao Ishibuchi, Naoya Akedo, and Yusuke Nojima. Behavior multiohjective evolutionary algorithms on many-objective knapsack problems. IEEE Transactions on Evolutionary Computation, 19(2):264-283, 2015.
[53] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
[54] Keld Helsgaun. An effective implementation of the lin-kernighan traveling salesman heuristic. European Journal of Operational Research, 126(1) 1):10)-1300, 2000.
[55] Renato Tinós, Keld Helsgaun, and Darrell Whitley. Efficient recombination in the lin bermighan-helsgaane traveling salesman heuristic. In International Conference on Parallel Problem Solving from Nature, pages 95-107,2011
[56] Gerhard Reinelt. TSPLIB traveling salesman problem library. ORSA Journal on Computing, 3(4): 376-384, 1991.
[57] Jim Boelrijk. Bernd Ensing, and Patrick Forré. Multi-objective optimization via equivariant deep hypervol- ume approximation. In International Conference on Learning Representations, 2023.
[58] Ke Shang, Weiyu Chen, Weiduo Liao, and Hisao Ishibuchi. Hv-net: Hypervolume approximation based on deepsets. IEEE Transactions Evolutionary Computation, 2022.
13


Reviews:
[{"review_id": "oadg1mHP25", "reviewer": "Reviewer_fppw", "summary": "This paper focus on solving multi-objective combinatorial optimization by neural methods. The authors observe that decomposition-based neural MOCO methods may acquire similar solutions for neighboring subproblems. Therefore, to enhance the diversity of the non-dominated solution set, they introduce the hypervolume indicator to reward design and propose a heterogeneous graph attention mechanism that learns the interaction between the Pareto Front and the nodes of the instance. Besides, a multiple optimal strategy is proposed to sample and preserve more solutions. Experimental results show that the proposed NHDE generates more diverse solutions and achieves better hypervolume.", "questions": "In lines 164-167, the authors claim that HGA can guide the constructed solutions distinct from existing ones. However, the proposed HGA learns the interaction between the node features (which represent the instance) and the points of Pareto Front (which are objective values), which could not represent the structure of any solutions. Could you explain why HGA can guide the diverse solution construction without explicitly considering the structure of the existing and current solutions?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Hypervolume Indicator is firstly utilized to learn neural MOCO methods and this idea would inspire researchers to develop novel MOCO solvers beyond existing pure decomposition-based methods.\n2. The diversity of the non-dominated solution set is a key point of MOCO problems. It is quite meaningful to enhance diversity.\n3. Sufficient experiments are conducted, and the proposed method achieves better convergence and diversity.", "weaknesses": "The main concern is about the design of HGA. See the questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the valuable comments.\n\n**To Question 1:** The reasons that HGA can guide the diverse solution construction without explicitly considering the structure of the existing and current solutions are as follows.\n\n1. Intuition of implicitly considering the solution structure. Actually, the proposed neural network can use the attention computations to capture the favorable representation learning of the interaction between the node features (which represent the instance) and the points of Pareto front (which are objective values). Intuitively, the interaction contains the structure of solutions to some extent, considering the fact that Pareto front is the mapping from Pareto solutions, conditioned on the instance infomation. Therefore, the learned node and point embeddings implicitly contains the useful information of the existing and current solutions, by progressively  message passing and aggregating between the embeddings, so as to achieve the desirable final performance in our experiments. More specifically, the node-to-node attention reflects each node’s attention towards others for the construction of the current solution (i.e. instance conditioned impact on solution construction); the node-to-point attention reflects each node’s attention to points in the Pareto front for guidance of constructing solutions different from the existing solutions (i.e. instance-Pareto-front joint  impact on solution construction).\n2. Reward driven diverse solution construction. We would like to note that another key design for produing differnt solutions is the reward design based on HV. As we know, this is first time HV is explicitly icluded in rewards for DRL method of multi-objective combinatorial optimization. Specifically, our reward design renders the current Pareto solution produced differently from existing ones in the Pareto front, for achieving higher HV in the final performance.\n3. Complexity to explicitly embed all existing solutions. In our current design, the input of the neural network can be represented as a graph with variable numbers of points with a fixed low dimensions of the point features. Hence, it allows us to adopt a graph neural network, e.g., the graph attention network, to embed the point graphs. However, if we explicitly input the solution structure, which would be a graph with variable numbers of points with a variable high dimensions of the point features. Such embedding requires a quite complex neural network. Thus, we use the current design for a trade-off bewteen the performance and complexity.\n"}, {"review_id": "7qPe3nItaq", "reviewer": "Reviewer_TPc1", "summary": "This work proposes NHDE, a novel neural heuristic with diversity enhancement method, to solve multi-objective combinatorial optimization (MOCO) problems. The main contribution of NHDE is to overcome the crucial duplicated solution issue for the widely-used decomposition-based method, and generate a set of diverse Pareto solutions in a reasonable runtime. The proposed method has two major components: 1) an indicator-enhanced model structure with heterogeneous graph attention (HGA) to generate diverse Pareto solutions, and 2) a simple yet powerful multiple Pareto optima (MPO) strategy to identify more Pareto solutions for each decomposed subproblems.\n\nThe proposed NHDE method is flexible and can be incorporated into different neural MOCO approaches. Experimental results show that NHDE can achieve promising performances on various MOCO problems, such as multi-objective traveling salesman, capacitated vehicle routing, and knapsack problems.", "questions": "- Please address the concerns raised in Weaknesses.\n\n- It is better to also report the results of NHDE + MDRL (NHDE-M) in the main paper.", "limitations": "The limitation of the proposed method is discussed in the conclusion section. ", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "+ This work is generally well-written and easy to follow.\n\n+ Multi-objective combinatorial optimization (MOCO) is important for many real-world applications, and the decomposition-based method is a widely-used approach for MOCO. It is promising to see the proposed NHDE can efficiently tackle the crucial duplicated solution issue for the decomposition-based neural method.\n\n+ NHDE can be flexibly incorporated into different decomposition-based methods, and it obtains promising performance on various MOCO problems.", "weaknesses": "I have the following concerns for the proposed method: \n\n**1. Solution Distribution**\n\nNHDE is a promising approach to tackle the duplicated solution issue for the decomposition-based method. Another important issue for the decomposition method is the shape of generated Pareto front, where the solution distribution will be very sensitive to the scalarization method, especially for problems with more than two objectives. In real-world applications, it is often hard to choose the proper scalarization method for a new problem before optimization. One concrete example can be found in Appendix D.5 in the PMOCO[1] for neural MOCO. Can NHDE also (partially) tackle this issue? It is interesting to know the shape of generated Pareto front by NHDE on the tri-TSP with different scalarization methods. \n\n[1] Pareto Set Learning for Neural Multi-Objective Combinatorial Optimization, ICLR 2022.\n\n**2. Batch Inference and Subproblem Order**\n\nIt seems that NHDE needs to sequentially generate the solutions for different subproblems one by one (even for a single instance) since it takes the current Pareto front as input, while PMOCO and MDRL can generate solutions in batch. Is it possible to design a batch version for NHDE? Will the order of subproblems significantly affect NHDE's performance, especially for problems with more than two objectives?\n\n**3. Runtime Analysis**\n\nNHDE requires longer runtime than PMOCO and MDRL for the same number of preferences. It is interesting to know NHDE's performance with a limited runtime budget (e.g., a few seconds) similar to PMOCO. What is the runtime cost of the indicator-enhanced inference and MPO in NHDE separately?\n\n**4. Effect of MPO**\n\nThe ablation study in Figure 4 is very helpful, and I believe it is for Bi-TSP50. According to the results, it seems that the performance of NHDE w/o MPO (0.6335) is similar to the PMOCO (0.6331) but requires a longer runtime. Does the promising performance of NHDE mainly come from MPO but not the indicator-enhanced inference? What is the performance of PMOCO(600 pref.) with MPO?  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the valuable comments.\n\n**W1: Solution Distribution.** We agree with the reviewer that the scalarization may affect the solution distribution. Our NHDE can better alleviate this compared to pure decomposition-based methods for two reasons:\n* NHDE can generate more diverse solutions as verified by our experiments.\n* NHDE can flexibly deal with arbitrary preferences during inference, thus is able to adopt proper scalarization methods.\n    * When knowing the approximate scales of different objectives beforehand, we can first normalize them into [0,1] to derive a more uniform Pareto front.\n    * NHDE can adopt preference assignment method used in PMOCO (see Appendix D.5 in the original old version of PMOCO paper) to obtain a more uniform Pareto front.\n\nWe have supplemented the results on tri-TSP with asymmetric Pareto fronts, in the PDF under global response. 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. The results show that non-uniform preferences, which are obtained by multiplying uniform preferences by (1,2,10) element-wise and then normalizing them back to $[0,1]^3$, can produce a relatively more uniform Pareto front. Besides, compared with PMOCO, NHDE-P can enhance diversity, thereby alleviating this issue.\n\n**W2: Batch Inference and Subproblem Order.**  NHDE could not accomplish batch inference for subproblems, since NHDE dependently solves subproblems sequentially. However, NHDE itself has achieved batch inference for instances, which can reduce the time for solving a set of instances. Furthermore, we note that the run time of NHDE is acceptable since it can generate a desirable Pareto front with diverse solutions by using relatively fewer preferences, which means a lighter sequential time. \n\nMoreover, though PMOCO and MDRL can achieve batch inference for subproblems essentially, it is still hard to realize it. For a batch of subproblems, PMOCO needs to generate a batch of parameters in the neural network, while MDRL needs to be fine-tuned to derive a batch of neural networks for subproblems. Both of them could consume prohibited large GPU memory in practice.\n\nThe order of subproblems would impact the performance, and we have studied this in Appendix J. We conducted 10 runs with randomly shuffled preferences and found minimal performance variation. Most HV results hovered around 0.6388, with the lowest at 0.6386. Figure 7(c) in Appendix J visualizes these results. While a tailored preference order might enhance performance, it is beyond the scope of this paper. \n\n**W3: Runtime Analysis.** We have added the NHDE and PMOCO results on Bi-TSP50 with similar runtime, by changing the number of preferences used in both methods. We present the comparison in the table below.  When using a few preferences (short runtime), PMOCO is slightly better than NHDE with a close runtime (since the increasing number of preferences can rapidly raise the performance of PMOCO). However, when using more preferences ($N\\geqslant 300$ for PMOCO), NHDE  is consistently better than PMOCO with the close runtime. This further verifies that increasing preferences may not effectively produce more Pareto solutions for existing neural solvers, while our NHDE can boost the limitation of such decomposition-based neural solvers, especially in diversity. Our superiority on larger size (i.e.,100) and more complex CVRP would be more significant.\n\nHV: NHDE-P/PMOCO|&#124;NDS&#124;: NHDE-P/PMOCO|Time: NHDE-P/PMOCO|Pref.: NHDE-P/PMOCO\n:---:|:---:|:---:|:---:\n0.6334/0.6355|76/56|14s/14s|10/150\n0.6373/0.6359|103/63|26s/26s|20/300\n0.6388/0.6361|127/68|53s/53s|40/600\n0.6395/0.6362|146/70|1.3m/1.4m|80/1200\n\nAlso, we have added the runtime proportion of each module in NHDE-P, including the original PMOCO, indicator-enhanced DRL, and MPO. The experiment is conducted on Bi-TSP50 (results shown in the table below). Please note that the runtime of the indicator-enhanced DRL during inference is mainly spent by the heterogeneous graph attention (HGA). The indicator-enhanced inference costs 5% runtime, with the complexity of the attention mechanism in PMOCO being $O(n^2)$ and the additional complexity in HGA being $O(nK)$. MPO costs 82% runtime, since the update of Pareto front needs more computaiton, i.e., $O((K + J)J)$.\n\nModule of NHDE-P|Runtime Proportion\n---|:---:\nPMOCO|13%\nIndicator-enhanced inference|5%\nMPO|82%\n\n**W4: Effect of MPO.** We notice the case mentioned by the reviewer, where the effect of the indicator-enhanced inference on PMOCO is slight by comparing NHDE w/o MPO with PMOCO. However, to more accurately evaluate the effect of the indicator-enhanced inference on our NHDE (with HV 0.6388), NHDE without indicator enhancement (NHDE w/o I with HV 0.6361) should be involved in the comparison, as shown in Figure 4(a). In fact, NHDE w/o I in our implementation is equivalent to PMOCO equipped with MPO, which means that the indicator-enhanced inference leads to more improvement, i.e., 0.6388 over 0.6361, in this case.\n\nDespite this, we observe that the promising performance of NHDE comes more from MPO (see NHDE w/o MPO with HV0.6335 in Figure 4(a)) than the indicator-enhanced inference. As discussed in the previous response (**W3**), the indicator-enhanced inference only costs a very small part of runtime, while MPO costs most of the runtime. Thus, their corresponding contributions to performance are reasonable, considering their compurational efforts.\n\nFollowing the suggestion, we have added the comparative results of PMOCO with MPO (600 pref.) and NHDE-P (600 pref.) on Bi-TSP50. As shown in the table below, our NHDE outperforms PMOCO with MPO, where PMOCO spends similar runtime to NHDE with the extra MPO module.\n\nMethod|HV|&#124;NDS&#124;|Time\n---|:---:|:---:|:---:\nPMOCO w MPO (600 pref.)|0.6372|141|5.9m\nNHDE-P (600 pref.)|0.6405|177|6.3m\n\n**Q1:** We will move the results of NHDE + MDRL (NHDE-M) to the revised main paper."}, {"review_id": "h5MPDOMfpw", "reviewer": "Reviewer_DbfB", "summary": "This paper proposes a number of techniques to improve the diversity of solutions in neural multi-objective combinatorial optimization (MOCO): 1) solving preference-conditioned subproblems dependently by taking a subset of the current Pareto front as input to a graph attention-based policy network; 2) using the hypervolume indicator as the reward; and 3) sampling multiple solutions from the policy for each subproblem to update the Pareto front. Previous decomposition-based MOCO methods are augmented with these techniques, and empirically evaluated on multi-objective TSP, CVRP, and KP benchmark problems. Results show that there is improvement in average hypervolume compared to previous work, and ablations show that each design choice has positive contribution to average performance.", "questions": "The authors should:\n- show that results are statistically significant\n- provide evidence for the claim that the techniques reduce the number of duplicate solutions to subproblems\n- explain how to choose the three hyperparameters and show sensitivity results", "limitations": "The use of a graph attention model limits the method to problems with a graph.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Originality: This paper's ideas of using a reward based on the hypervolume and using the current Pareto front as part of the state input to the policy are novel (to my knowledge). Doing so ensures a stationary environment for RL, in contrast to previous methods that use distance-based rewards without observing the global solution space that leads to nonstationarity for RL.\n\nQuality: The paper covers most of the important details in regards to problem motivation, background and related work, description of methods and analysis of results.\n\nClarity: The technical writing and notation is clear and concise.\n\nSignificance: The topic of multi-objective CO is an important one that arises in practice and there is increasing work on learning-based approaches, so this is a relevant and significant paper for the conference.", "weaknesses": "The abstract claims that the proposed techniques are intended to \"hinder duplicated solutions for different subproblems.\" Even though the results show an increase in average diversity, as measured by the hypervolume, the paper does not provide concrete and direct evidence of this specific claim of reducing number of duplicates.\n\nThe method relies on at least three hyperparameters---$N$, the number of subproblems and preferences used in training; $K$, the number of top solutions from the current Pareto front to use as input to the policy; and $J$, the number of new solutions to be sampled for updating the Pareto front. The main paper does not provide any sensitivity study or guidance on how to choose them in practice, so it is unclear whether the proposed techniques are robust or brittle.\n\nThe results in Table 1, Table 2, and Figure 4 only report the average performance, but do not show the variance of results. It is not possible to determine whether the results are statistically significant.\n\nThe proposed techniques rely on a base method, which has some specific limitations:\n1. The overall approach relies on the base method of sequentially solving subproblems, each determined by a preference. It is not clear how the ordering of subproblems impacts the performance of the method.\n2. The policy is a graph attention network, so it requires the CO problem instances to be defined on a graph, so it's not clear the method generalizes to other CO problems where there is no natural graph structure.\n\nIn Section 4.1, where the paper defines the state space, it is not clear why the preferences are not part of the state, if the policy is expected to act differently for different subproblems with different preferences.\n\nOther minor issues to be fixed or clarified:\n- Lines 32-33 and the claim on lines 35-36 need citations.\n- There are some typographical and grammatical issues: e.g.\n  - line 19-20: \"..., practical yet more complex\"\n  - line 233 is an incomplete sentence\n  - line 257 \"detials\"\n- In line 119, the subscripts $1,\\dotsc,T$ appear without explanation. Readers have to guess that it denotes the sequence representation of the solution.\n- From line 147, one can guess that each solution is represented by its objective values as an $M$-dimensional vector, but this should be explicitly stated.\n- In the results, the best $|\\text{NDS}|$ should also be in bold.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the valuable comments. \n\n**W1: Reduced duplicated solutions.**  We implicitly show the reduced duplicated solutions by the metric &#124;NDS&#124;, i.e., the number of non-dominated solutions. Empirically, more non-dominated solutions mean fewer duplicated solutions and fewer dominated solutions. Thus, the larger NDS values of our method (especially in comparison to the other neural solvers) indicate that our method can produce a smaller number of duplicates to some extent. We will further clarify the above point in our paper.\n\nFurthermore, we have added another evidence to verify that the indicator-enhanced DRL can hinder duplicated solutions for different subproblems. Specifically, we directly report the average number of duplicated solutions (|DS|) of our NHDE-P and NHDE-P without indicator (NHDE w/o I) on Bi-TSP50 in the table below. As can be seen, our NHDE-P using the hypervolume indicator can effectively guide the model to generate fewer duplicated solutions.\nIntuitively, our model is trained to construct new Pareto solutions different from existing ones in the Pareto front, which could achieve higher HV  in the reward. To make it sufficient, we will add the experiment with analyse in our paper.\n\n|Method|&#124;DS&#124;|\n|---|:---:|\n|NHDE-P (40 pref.)|196|\n|NHDE w/o I (40 pref.)|225|\n\n**W2:  Sensitivity study.** First of all, we conducted sensitivity analysis of $K$ in our submission (the first paragraph of Appendix J). Despite that, we followed the suggestion and have added the analyses of $N$ (the number of preferences used in training, which corresponds to the symbol $N'$), and $J$ (the number of new solutions to be sampled for updating the Pareto front). \n\nWe present the results of various $N'$ on Bi-TSP50 in the table below. As shown, $N'=5$ and $N'=10$ cause inferior performance, while proper $N'$ ($20\\leqslant N'\\leqslant 40$) results in desirable performance. Intuitively, when limiting the same total gradient steps in training, a larger $N'$ means fewer instances used for model training. In this sense, too large $N'$, i.e., with insufficient instances, could lead to the inferior performance for solving unseen instances. On the other hand, too small $N'$ could prevent the model from learning favorable preference representations and thus deteriorate the final performance. Hence we choose $N'=20$ in this paper.\n\n|$N'$|HV|\n|---|:---:|\n|5|0.6373|\n|10|0.6382|\n|20|0.6388|\n|40|0.6386|\n\nWe provide the HV and runtime of NHDE-P (210 pref. aug.) on Tri-TSP50 with the changed $J$. We observe that by limiting $J$, the massive time of the update can be curtailed with only a little sacrifice of performance. Since $J=200$ is a good trade-off between HV and runtime, we use it in this paper.\n\n\n|$J$|HV|Time|\n|---|:---:|:---:|\n|50|0.4577|26m|\n|100|0.4584|27m|\n|200|0.4588|30m|\n|400|0.4589|39m|\n|6400 (unlimited)|0.4590|6.2h|\n\nFor $K$, we refer to Appendix J for the experiment with analyses. In summary, we choose $K=20$ for a better trade-off between the state representation of Pareto front and computational effort of the deep model.\n\n**W3:Variance of results.**  Following the suggestion, we test the variances of the results on Bi-TSP20 and report them in the table below. All methods have small variances of hypervolumes, where our NHDE-P achieves the stablest performance. Due to the space limitation here, we will present the variances on all problems in the final version.\n\n|Method|HV|Variance|\n|---|:---:|:---:|\n|WS-LKH (40 pref.)|0.6266|$3.24\\times 10^{-4}$|\n|PPLS/D-C (200 iter.)|0.6256|$3.45\\times 10^{-4}$|\n|DRL-MOA (101 models)|0.6257|$3.31\\times 10^{-4}$|\n|PMOCO (40 pref.)|0.6258|$3.31\\times 10^{-4}$|\n|PMOCO (600 pref.)|0.6267|$3.28\\times 10^{-4}$|\n|NHDE-P (40 pref.)|0.6286|$3.19\\times 10^{-4}$|\n|PMOCO (40 pref. aug.)|0.6266|$3.26\\times 10^{-4}$|\n|PMOCO (100 pref. aug.)|0.6270|$3.28\\times 10^{-4}$|\n|NHDE-P (40 pref. aug.)|0.6295|$3.14\\times 10^{-4}$|\n\nTo further verify our results are statistically significant, we also conducted a Wilcoxon rank-sum test for the results in Table 1, Table 2, and Figure 4 in the main paper. We observe that the best and second-best results achieved by our method are both statistically different from the results by the other methods, at a 1% significance level in all groups, which means our results are statistically significant. \n\n**W4: Sequence of subproblems.** In fact, we also noticed the order of subproblems could impact the performance, and studied this effect in Appendix J (see the 3rd paragraph) in our submission. We independently executed 10 runs with the random shuffle of preferences, and the result indicates the order only exhibits a slight impact on the performance. Specifically, most of HV values are 0.6388, and the worst (only one) HV value is 0.6386. We refer the reviewer to Figure 7(c) in Appendix J for the complete result. Please note that a highly specialized order of the preferences may raise the performance, but it is beyond the scope of this paper.\n\n**W5: Generalization.** As mentioned, our current model based on a graph neural network can only tackle CO problems defined on graphs. However, most CO problems (with their variants) can be actually defined on a graph, such as routing, scheduling, and bin packing. Moreover, it is natural and straightforward to adapt our model to solve other CO problems with different data structures, via replacing the graph neural network with the specialized neural network for any specific CO problem. We hope our work could inspire such future work on various types of CO problems.\n\n**W6: Missing preference.** Thanks for pointing this out.  Actually, we input the preference (as a part of the state) into our deep model, as we described in Section 4.2. But we miss it when describing the state definition. We will add it in Section 4.1 for the coherence .\n\n**W7: Minor issue.**  We will polish the paper accordign to the suggestion."}, {"review_id": "zpLE3iQ1Zi", "reviewer": "Reviewer_ETpH", "summary": "The paper presents a novel neural heuristic approach, called NHDE, for Multi-Objective Combinatorial Optimization (MOCO) problems. The proposed approach enhances the diversity of Pareto solutions by introducing a multiple Pareto optima (MPO) strategy and an indicator-enhanced Deep Reinforcement Learning (DRL) method. Experimental results on classic MOCO problems demonstrate that NHDE outperforms state-of-the-art neural baselines, achieving superior overall performance with a higher diversity of Pareto solutions.", "questions": "1.\tAs far as I know, LKH is a pretty fast heuristic solver for TSP problem. However, the reported running time of LKH in experiments of TSP is extremely slow and much slower than that reported in previous papers (e.g. [2]). Could authors explain this?\n2.\tFrom my understanding, the proposed method is able to conduct two tasks at a same time: (1) solve the CO problem (2) generate diverse solutions. The supported CO problems includes TSP, VRP. What is the scope of CO problems that the proposed diverse enhancement is able to handle? Does the diverse enhancement able to enhance all RL-based solvers? What about other neural solvers that do not use RL (e.g. [3])?\n3.\tHow does other recent neural solvers perform on solution diversity? (e,g. [4,5])\n4. in Line 118, when does the sub-problem required, for the CO solving itself, or diversity enhancement for multiple evaluation metrics? (Why does there N sub-problems instead of M?)\n\n[1] Kwon Y D, Choo J, Kim B, et al. Pomo: Policy optimization with multiple optima for reinforcement learning[J]. Advances in Neural Information Processing Systems, 2020, 33: 21188-21198.\n\n[2] Xin L, Song W, Cao Z, et al. NeuroLKH: Combining deep learning model with Lin-Kernighan-Helsgaun heuristic for solving the traveling salesman problem[J]. Advances in Neural Information Processing Systems, 2021, 34: 7472-7483.\n\n[3] Wang R, Yan J, Yang X. Combinatorial learning of robust deep graph matching: an embedding based approach[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.\n\n[4] Kwon Y D, Choo J, Kim B, et al. Pomo: Policy optimization with multiple optima for reinforcement learning[J]. Advances in Neural Information Processing Systems, 2020, 33: 21188-21198.\n\n[5] Qiu R, Sun Z, Yang Y. DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems[C]//Advances in Neural Information Processing Systems.\n", "limitations": "It could be better if the authors could discuss potential limitations of the paper.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.\tThe paper proposes a novel algorithm to generate diverse solutions for combinatorial optimization (CO) problems.\n2.\tThe proposed method is able to enhance existing methods to achieve improvements on diversity metrics including hypervolumes.\n", "weaknesses": "1.\tThe solving time of proposed solver is relatively slow compared to other RL-based CO solvers. Besides, one of the curious results is that the solving time of LKH is much slower than the time in previous papers. (see question 1)\n2.\tThe authors do not discuss the scope of solvers of proposed diversity enhancement (see question 2). \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable comments. Firstly, **we clarify the scope of this paper, since there seems to be a misunderstanding by the reviewer**. We focus on Multi-Objective CO (MOCO), a domain different from the Single-Objective CO (SOCO), even though the latter can employ diversity enhancement. MOCO seeks a set of Pareto-optimal solutions, each signifying a unique trade-off between various conflicting objectives rather than optimizing them separately as in SOCO  (see Figure 3 for illustration). Hence, solving MOCO is much harder than solving SOCO. We refer the reviewer to Section 3 for the definitions and details about MOCO.\n\n**To W1: More runtime than RL-based CO solvers.** We would like to note that although our NHDE-P takes longer runtime than the original RL-based PMOCO, in our original paper, we compared our NHDE-P not only with the original PMOCO but also its enhanced version for fairness (we adjusted the number of preferences in the enhanced PMOCO, extending its runtime, which, in some cases, even surpassed our runtime). In practice, it is worthy to find more significantly profitable solutions with acceptable prolonged time. As illustrated in Table 1, our method consistently outperforms, even under the modified conditions, e.g., ours (0.00%, 1.5h) outperforms PMOCO's (3.17%, 4.2h) on Tri-TSP100.\n\nWe have further supplemented results on Bi-TSP50 with more choices on the number of preferences, as presented in the table below. When using a few preferences (short runtime), PMOCO is slightly better than NHDE with close runtime. However, when using more preferences ($N\\geqslant 300$ for PMOCO), NHDE  is consistently better than PMOCO with close runtime. This further verifies that increasing runtime may not effectively produce more Pareto solutions for existing neural solvers, especially in diversity. Note that our superiority on larger size (i.e.,100) and more complex CVRP would be more significant.\n\nHV: NHDE-P/PMOCO|Time: NHDE-P/PMOCO|Pref.: NHDE-P/PMOCO\n:-:|:-:|:-:\n0.6334/0.6355|14s/14s|10/150\n0.6373/0.6359|26s/26s|20/300\n0.6388/0.6361|53s/53s|40/600\n0.6395/0.6362|1.3m/1.4m|80/1200\n\n**To W2/Q1: Runtime of WS-LKH.** We clarify that the reported time of WS-LKH (LKH with decomposition using 40 preferences) is reasonable because: 1) decomposition-based MOCO methods need to solve the single-objective CO subproblems multiple (i.e., 40) times, and 2) the practical solving time varies with the hardware.\n\nWe give three specific examples to better illustrate the runtime. For 200 instances of Bi-TSP100, WS-LKH (40 pref.) with 10000 trials costs 2.7 hours in our experiments, so each single-objective subproblem for an instance spends 2.7$\\*$3600/40/200=1.2 (s). **Example 1:** In NeuroLKH[2], LKH with 1000 trials costs 938 seconds for 1000 instances of single-objective TSP100, so each TSP100 instance with 10000 LKH trials spends about 938/1000$\\*$10=9.4 (s). **Example 2:** In AM, LKH with 10000 trials using 32 virtual CPUs expends 21 minutes for 10000 instances of TSP100, so each TSP100 instance spends about 21$\\*$60/10000$\\*$32=4.0 (s). **Example 3:** In [7], WS-LKH for 200 instances of Bi-TSP100 consumes 3.1 hours.\n```\n[6] Attention, Learn to Solve Routing Problems!, ICLR, 2019.\n[7] Pareto Set Learning for Neural Multi-Objective Combinatorial Optimization, ICLR, 2022.\n```\n\n**To W3/Q2: Clarify the scope.** Our studied scope is MOCO, which aspires both desirable optimality and diversity in the Pareto front beyond SOCO with diversity enhancement. **[Scope of CO]** Our NHDE has the potential to solve most CO defined on graphs including routing, scheduling, bin packing, etc, since we adopt a GNN as policy model. For other COs, one can replace the deep model with corresponding ones while keeping our diversity enhancement schemes for MOCO including indicator-enhanced DRL and multiple Pareto optima strategy. **[Scope of solver]** We agree that NHDE is generic to boost existing decomposition based RL solvers for MOCO. We believe it can also be applied to other neural solvers that do not use RL by modifying the training algorithm. However, existing neural MOCO solvers almost use RL, since the label (the exact Pareto front) of MOCO is extremely hard to obtain (even more diffcult than NP-hard SOCO). Note that non-RL neural solve [3] referred by the reviewer is used to solve SOCO setting only. \n\n**To Q3: Solution diversity.** Firstly, unlike the study [4,5] that focused on finding a single optimal solution for optimizing a single objective by exploring diverse solutions, we emphasize that the studied MOCO pursues a set of Pareto solutions captured by both optimality and diversity for optimizing multiple conflicting objectives. We note that the diversity schemes used in these SOCO methods (e.g., POMO and DIMFES) may not be directy used for optimizing multiple conflicting objectives without MOCO techniques such as the decomposition. Nevertheless, we agree that they can inspire future works to further enhance the diversity of the single-objective sub-problem decomposed in MOCO, and we will cite and discuss this in the revised paper.\n\n**To Q4: Why sub-problem required?** Since MOCO optimizes multiple objectives, it pursues a set of Pareto-optimal solutions representing trade-off among the conflicting objectives, rather than outputting solutions for each $M$ objectives separately. Thus, the decomposition-based methods adopt $N$ preferences (usually $N>>M$) to scalarize each MOCO problem into multiple SOCO problems, which correspond to $N$ subproblems with various trade-off. The set of Pareto solutions can be derived by solving the $N$ subproblems, which can approximately solve the original MOCO.\n\n**To Limitation.** We have discussed the limitation in Conclusion, i.e., the HV calculation during training needs extra computational cost, thereby impeding the application of NHDE on many-objective problems. One potential solution is to consider efficient HV approximations to boost the training efficiency in the future.\n"}]

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

1. **Experiments:** We have provided more experimental results and analyses, including the solution distribution, runtime analysis, the evidence results about the reduced duplicated solutions, and more sensitivity analyses on hyperparameters.

2. **Significance:** We have added more analyses on the effect of MPO according to Reviewer TPc1 and the statistical results according to Reviewer DbfB.

3. **Additional questions:** We have explained some additional questions about the subproblem order, batch inference, runtime of the LKH solver, etc.


Meta-review: This paper proposes an algorithm for generating diverse solutions for combinatorial optimization problems. The response addresses concerns raised by the reviewer, including questions about the scope of the proposed method and its runtime compared to other solvers, as well as the limitations of the approach. Overall, this paper presents a novel contribution to neural multi-objective combinatorial optimization.
Decision: Accept (poster)