Pareto Set Learning for Neural Multi-Objective Combinatorial Optimization
Authors: Xi Lin
Zhiyuan Yang
Qingfu Zhang
Venue: ICLR 2022 Poster (2022)
Keywords: Multiobjective Combinatorial Optimization
Combinatorial Optimization
Neural Combinatorial Optimization
Multiobjective Optimization

Abstract: Multiobjective combinatorial optimization (MOCO) problems can be found in many real-world applications. However, exactly solving these problems would be very challenging, particularly when they are NP-hard. Many handcrafted heuristic methods have been proposed to tackle different MOCO problems over the past decades. In this work, we generalize the idea of neural combinatorial optimization, and develop a learning-based approach to approximate the whole Pareto set for a given MOCO problem without further search procedure. We propose a single preference-conditioned model to directly generate approximate Pareto solutions for any trade-off preference, and design an efficient multiobjective reinforcement learning algorithm to train this model. Our proposed method can be treated as a learning-based extension for the widely-used decomposition-based multiobjective evolutionary algorithm (MOEA/D). It uses a single model to accommodate all the possible preferences, whereas other methods use a finite number of solutions to approximate the Pareto set. Experimental results show that our proposed method significantly outperforms some other methods on the multiobjective traveling salesman problem, multiobjective vehicle routing problem, and multiobjective knapsack problem in terms of solution quality, speed, and model efficiency.

Published as a conference paper at ICLR 2022
PARETO SET LEARNING FOR NEURAL MULTI-OBJECTIVE COMBINATORIAL OPTIMIZATION
Xi Lin, Zhiyuan Yang, Qingfu Zhang Department of Computer Science, City University of Hong Kong xi 1 iinmyy- ci tyu. edu. hkk
ABSTRACT
Multiobjective combinatorial optimization (MOCO) problems can be found in many real-world applications. However, exactly solving these problems would be very challenging, partieularly when they are NP-hard. Many handcrafted heuris- tic methods have been proposed to tackle different MOCO problems over the past decades, In this work, we generalize the idea of neural combinatorial optimiza- tion, and develop a learning-based approach to approximate the whole Pareto set for a given MOCO problem without further search procedure. We propose a single inlerence-conditionnn model to directly generate approximate Pareto solutions for any trade-off preference, and design an efficient multiobjective reinforcement learning algorithm train this model. Our proposed method can be treated a sarming-based extension for the widely-used decomposition-bos basodd multiobjec- tive evolutionary algorithm (MOEA/D). It uses single model accommodate all the possible preferences, whereas other methods use finite number of solu- tions approximate the Pareto set. Experimental results show that our proposed method significantly outperforms some other methods on the multiobjective trav- eling salesman problem, multiobjective vehicle routing problem, and multiobjec- tive knapsack problem in terms of solution quality, speed, and model efficiency.
INTRODUCTION
Many real-world applications can be modeled multiobjective combinatorial optimization (MOCO) problems (Ehrgott & Gandibleux] 2000). Examples include the multiobjective traveling salesman problem (MOTSP) (Lust & Teghem| (010a). the multiobjective vehicle routing problem (MOVRP) (Jozefowiez et al. 2008) and the multiobjective knapsack problem (MOKP) (Bazgan al. 2009). These problems have multiple objectives to optimize, and no single solution can op- timize all the objectives at the same time. Instead, there is a set Pareto optimal solutions with different trade-offs among the objectives.
is very challenging to find all the exact Pareto optimal solutions for a MOCO problem. Ac- tually, finding one single Pareto optimal solution be NP-hard for many problems (Ehrgott & Gandibleux 2000), and the number of Pareto solutions could be exponentially large with regard to the problem size (Ehrgott, 2005 Herzel et al. 2021). The decision-maker's preference among dif- ferent objectives is usually unknown in advance, making it very difficult to reduce the problem into single-objective one. Over the past several decades, many methods have been developed to find an approximate Pareto set for different MOCO problems within a reasonable computational time. These methods often need carefully handcrafted and specialized heuristics for each problem. It can be very labor-intensive in practice.
In many real-world applications, practitioners need to solve many different instances for the same particular problem, where the instances can be easily obtained or generated (Bengio et al.) 2020). is desirable to learn the patterns behind these problem instances explicitly or implicitly to design efficient algorithms (Cappart et al.) 202 Machine learning techniques can be naturally used for this purpose. Some learning-basee methods have been recently proposed for solving single-objective combinatorial optimization problems (Bengio et al.) 2020; Vesselinova al.) 2020 Mazyavkinal jet al., [021]] Cappart et al. 2021a). this work, we extend the learning- based method to solve MOCO problems in principled way shown in Figure T Our main contributions include:

---

Published as a conference paper at ICLR 2022
Pref. on Objz
A
Preference:
Cost 2
P.(22,28)
(1,3)
(6,3)
Pref. on Ohj
(10,0118)
(7.9)
[6,4] (1,8)
(,
2,33
(4,5X4.2)
(2,6)
Neural MOCO Model
2g
(5,2)
Fast Forward Inference
Cost
(a) Problem
(b) Model
(c) Solution Generation
Figure/ 1: Iiferencc-Condittooee Neural Multiobjective Combinatorial Optimization: a) The model takes a problem instance as its input. b) The decision makers assign their preferences on different objectives to the model. e) The model directly generates approximate Pareto solutions with different trade-off's via fast forward inference. In this example, the problem is the MOTSP with two cost objectives minimize. The generated solutions P1.P2 and P3 are different optimal trade-off's between the two cost objectives. The ideal model can generate solutions for all possible optimal trade-offs on the Pareto front and not generate poor solution such as Pa.
We propose novel neural multiobjective combinatorial optimization method to approx- imate the whole Pareto set via single preference condiniinnd model. It allows decision makers to obtain any preferred trade-off solution without any search effort.
We develop an efficient end-to-end reinforcement learning algorithm to train the single model for all different preferences simultaneously, and simple yet powerful active adap- tion method handle -iittr-disttiuution problem instances.
We conduct comprchensive experiments on MOTSP, MOVR and MOKP of different set- tings. The results show that our proposed method can successfully approximate the Pareto sets for different problems in an efficient way. It also significantly outperforms other meth- ods in terms of solution quality, speed, and model efficiency.
2 BACKGROUND AND RELATED WORK
Multiobjective Combinatorial Optimization (MOCO). MOCO has been attracting growing re- search efforts from different communities over the past several decades (Sawaragi et al. 1985 Wallenius et al. 20088 Herzel et al. 2021). There are two main approaches to tackle the MOCO problems: the exact methods and the approximation methods (Ehrgott 2005). Exact methods could be prohibitively costly when, it often happens. the MOCO problem is NP-hard and the prob- lem size very large (Florios & Mavrotas 2014). For this reason, many heuristics (Jaszkiewicz, 2002 Zhang& & Li 2007 | & Gandibleux 2008) and approximation methods (Papadimitriou & Yannakakis] 2000; Herzel et al.J (021)) have been developed to find a managcable number of approximated Pareto solutions with reasonable computational budget. However, these methods usually depend on carefully handcrafted designs for each specific problem (Ehrgott & Gandibleux 2000), and the required effort is often nontrivial in real-world applications.
Machine Learning for Combinatorial Optimization. As summarized in Bengio et al. 2220)). there are three main learning-baai based approaches for combinatorial optimization: learning to config- ure algorithms (Kruber et al., 22017] Bonami et al., 2018), learning alongside the algorithms (Lodi & Zarpellon, 2017; Gasse et al. [2099; Chen & Tian 2019). and learning to directly predict the solutions (Nowak et al. 2018, Emami & Ranka 20188 Larsen et al. 2018). Neural combinatorial
optimization (NCO) belongs to the last category where the model directly produces good solu- tion for given problem instance. Vinyals et al. (2015) proposed pointer network to sequentially construct a solution for the TSP problem. [Bello et al. (2017) made a critical improvement to use re- inforcement learning to train the model, eliminating the impractical optimal solutions collection for NP-hard problems. Some other improvements on model structure and training procedure have been proposed in the past years (Nazari et al. 2018 Deudon al. 2018 Kool et al. 2019 Veličkovid & Blundell 2021), especially with graph neural networks (GNNs) (Dai et al. 2017 7 et al. 2018]
Joshi et al.
2019 Dwivedi et al. 2020 Drori et al. 2020). Recent efforts have been made more
2

---

Published as a conference paper at ICLR 2022
efficient learning strategies Kwon et al. 2020 Karalias & Loukas 2020
Lisicki et al.
2020 Geisler
iet al. 2022), learning-basee based graph search (Cappart et al. 2021b; Kool et al. 2021
Fu et al. 2021
Xin et al. 202 Hudson al. 2022), and iterative improvement methods [Wu et al. 2021
2021 Ma et al.
Li et al. 2021).
Neural MOCO. Most of the existing learning-based methods are for single-objective combinatorial
problems. Recently, a few attempts have been made to solve MOCO problems (Li et al., 2020; Wu
2020 Zhang al. a)) These methods adopt the MOEA/D framework (Zhang Lij 2007 to decompose a MOCO problem into a number of single-objective subproblems, and then build a set of models solve each subproblem separately. However, since the number of Pareto solutions would be exponentially large (Ehrgott (2005). the required number of models would be huge for finding the whole Pareto set. In this work, we propose a single preference-conditinn model for solving MOCO problems, with which the decision makers can easily obtain any trade-off solutions. The proposed single neural MOCO solver could be much easier use in real-world system (Veličković & Blundell 2021), than those using large set of different models.
al.
3 PROBLEM FORMULATION
3.1 MULTIOBJECTIVE COMBINATORIAA OPTIMIZATION
multiobjective combinatorial optimization (MOCO) problem can be defined as follows:
min F(x) (2)) I' (2)), #EX
where X' is discrete search space, and F(x) (f1(z), fm. (x)) ) is an m-objective vector. Since the individual objectives conflict each other, no single solution can optimize all them at the same time. Therefore, practitioners are interested in Pareto optimal solutions, defined as follows.
Definition (Pareto Dominance). Let Ta, Th E X, Ta is said to dominate 2y (æa < 1b) and only if fx(xa)) < [1())), Vi (1, m) and (z() < (2x)), 7j m........
Definition (Pareto Optimality). A solution x² E X' a Pareto optimal solution there does not exist & X' such that & x². The set of all Pareto optimal solutions is called the Pareto set, and the image of the Pareto set in the objective space is called the Pareto front.
Each Pareto solution represents an optimal trade-off among the objectives, and it is impossible to further improve one of the objectives without deteriorating any other objectives.
3.2 DECOMPOSITION AND PREFERENCE-BASED SCALARIZATION
Decomposition is mainstream strategy for solving multiobjective optimization problem (Zhang & Li 2007). It decomposes multiobjective problem into number of subproblems, each of which can be a single objective or multiobjective optimization problem. MOEA/D (Zhang & Li 2007) and its variants (Trivedi et (016) solve these subproblems in collaborative manner and generate finite set of Pareto solutions to approximate the Pareto front. The most widely used way for constructing a single objective subproblem is the meffrence-basee scalarization (Ehrgott) 2005 Miettinen 2012). For an m-objective optimization problem, a preference vector for the objective functions can be defined as À E R. that satisfies A; and Σ." X; 1.
Weighted-Sum Aggregation the simplest approach. It defines the aggregation function to mini- mize in the subproblem associated with À as
Dwe (z(A)
Σ A.f((z).
However, this approach can only find solutions on the convex hull of the Pareto front (Ehrgott 2005).
(Weighted-TCH) Aggregation is an alternative approach to minimize: (ua(2 = max (A,lf((x) 1s
where 2 < min f((x) is an ideal value for fz). Any Pareto optimal solution could be an
optimal solution of problem 3 with a specific (but unknown) preference À (Choo & Atkins 1983).
3

---

Published as a conference paper at ICLR 2022
(a) 105 Preferences
(b) 105 Solutions
(c) 1, 035 Solutions
(d) 10, 011 Solutions
Figure 2: Pareto Set Approximation for New Problem Instance: Our method with different numbers of preferences on three objective MOTSP with 50 nodes. a)&b) With a small number of preferences, model can generate sparse approximation to the Pareto set. c)&d) With large number of preferences, it can generate a dense approximation. Our method can generate any trade- off solutions with single model without searching, whereas other methods need solve build model for each preference separately. More discussions can be found in Appendix DD.3 D.5 D.6 D.7
3.3 CURRENT DRAWBACKS AND OUR METHOD
Drawbacks of Existing Methods. For many MOCO problems, the size of the Pareto set would be exponentially large with respect to the input size (c.g., nodes in MOTSP), is computationally impractical for existing methods to find the whole Pareto set (Herzel et al. 202I). For this reason, all of the existing heuristic-bard based and learning- based methods are to find a small subset of approximate Pareto solutions. Decision makers can only select solutions from this small set, which often does not contain their preferred solutions. In addition, scalarization may also produce a complicated single objective subproblem. For example, the Tchebycheff scalarized subproblem of MOTSP is not classic TSP, and thus cannot be solved by the highly specialized solvers such as LKH (Helsgaun 2000 or Concorde (Applegate et al., 2007).
Our Method. Instead of finding a set of finite solutions, we propose a novel way to approximate the whole Pareto set using a single model. With our proposed model, decision makers can easily obtain any solution from the approximate Pareto set to satisfy their preferred trade-offs in real time as shown in Figure 2 This is a clear advantage to support interactive decision making. In addi- tion, our proposed reinforcement learning based method can use a scalarization method to combine multiobjective rewards, and does not need to consider the problem-specific condition. In this paper, mainly consider learning the whole Pareto front. It is possible incorporate preferences on specific regions for model building and inference as discussed in Appendix [D6]. We believe our proposed method is new principled way solve multiobjective combinatorial opti- mization problems.
maker's 's
4
THE PROPOSED MODEL: PREFFRENCE:-ONDDIIONEE NEURAL MOCO
4.1 PREFFRENCE- DONDITIONN SOL.UIIN CONSTRUCTION
Decomposition and scalarization link preferences their corresponding Pareto solutions. This work builds a sreference-conditionee model to accommodate all the preferences. We use the MOTSP as an example to explain our model design. In an MOTSP instance s, fully connected graph of n nodes (cities) with m distance metrics on each edge is given. A feasible solution is a tour that visits each city exactly once and returns to the starting city. The i-th objective to minimize is the tour length (total cost) based on the i-th distance metric. A tour can be represented as a permutation of all the nodes defining the order in which n cities is visited. Our model defines preference-conddtioned stochastic policy Pe(x) (T|s) parameterized by (()) to construct valid solution in sequence:
π (I.,.... ",, ",,,,,n )n),, म. (1,.... ...
n). ,.).............................
Pa(x) (T|s) -i= Po()) (TTls,, T1:-11).
The goal is to learn an optimal preference-conditee policy (T(s) to construct tours with the lowest scalarized costs for each preference X.
4

---

Published as a conference paper at ICLR 2022
E
46
encuder
θ dernder (A
(a) Instance
(b) Encoder
(c) Embedding
(d) Decoder
(c) Solution
Figure 3: Preference-oonditioned Neural MOCO Model: a) The input is problem instance (e.g., graph). b) A shared attention encoder transfers the instance into a set of embeddings. e) The embeddings for all nodes would be used by the decoder multiple times with different preferences. d) A MLP takes the preference À as input, and generates the parameters for the decoder. e) The preference- attention decoder directly generates different approximate Pareto solutions for different preferences. The trainable parameters are in the attention encoder and MLP model.
4.2 THE PROPOSED MODEL
We propose use an Attention Model (AM) (Kool al. 2019 as our basic encoder-decoder model as shown in Figure 3 For the MOCO problems considered in this work, a preference-agnoneeeeeeee encoder is capable to transfer problem instances into embeddings (e-g., embedding for all cities) used in the preference-conditioned decoder. In our model, only the decoder's parameters d are conditioned on the preference X:
0 (A) = [encoderr Qdecuter (X]]-
(5)
Preference-agnostic Encoder. The encoder takes problem instance s (e.g., an MOTSP instance with n cities) as its input, and outputs a set of d-dimensional node embeddings (h1.... hn } for each city. For a given instance, the same embeddings can be used for different preferences. Hence we only need a single forward pass for the dense encoder. We use the attention-based encoder as in Kool et al. (2199) for all preferences.
Preference-based A Attention Decoder. The decoder has the same structure as in the attention-based model (Kool et al. 2019), but with parameters ( = (Wo(M) (A), (A()), (v(A), WMHA (A)] conditioned on the preference A. It takes the nodes embeddings for cities as input, and sequen- tially selects the next node π, with probability Pe(x) (T, [s, T12-)))
At time step f, the decoder first constructs a context embedding fu(c) [f lt ( from the first selected node hm, and the last selected node h 1- The matrix Wº(A) E R2dxd projects the concatenated 2d-dimensional vector d'dimensional vector. Then we further aggregate the context embedding via Multi-Head Attention (MHA) (Vaswani et al. 2017) with the embeddings for all cities (h1, ... ,h,}:
h(c) MH inc),, K (hi, h.,,...,,,,,,, W (hi.... ,,,,) (A) (A), (6)
where Q, K, V are the query, key and value for MHA, respectively. WMHH (A) represents the MHA parameters. The context embedding hic) contains all information for the instance and the current partial tour at step t. We can calculate the logit for selecting each city with its embedding hy:
logit, =
-
C. tanh(
Moch Vd
if otherwise.
AP' <t,
-c0
All already visited cities are masked with -c and will not be selected as the next city. The logits of the rest cities clipped into i-C, C] (C 10) as in the AM model (Kool al. 2019). The probability for choosing the j-th city at time step can be calculated as Po(A) 218, π TIa-1)
logit
/E dlggi, With this probability, the decoder
construct a feasible tour.
One remaining designing issue how to generate the preference--oonditoone parameters 0 deconer ())
Multiplicative interactions (Jayakumar et al. 2020) and hypernetwork (Schmidhuber) 1992 Ha
et al., 2017) provide a powerful and efficient way for conditional computation, which is widely used
for transfer learning (von Oswald et al. 2020 Ehret et al. 2021 Lin et al. 2020 Navon et al. 202
We use a simple MLP hypernetwrkk 6 deecoeer (A) = MLP [X] 1b) to generate the decoder parameters
conditioned on the preference. The details of our proposed model can be found in Appendix B
5

---

Published as a conference paper at ICLR 2022
Algorithm Neural MOCO Training
1: Input: preference distribution A, instances distribution S, number of training steps T, number of preferences per iteration K, batch size B, number of tours N
2: Initialize the model parameters 0
3: for t = to T do
4: λ SampleePreference(A. (A)
Ak E {I.... .K}
5: 8 Samplelnstance ()
Vi Ei, ,B)
6: The SampleTour (Po(s)))) (-18:))
Vk, Vj E [I,..,,N]
7: b(s:)a)) N E (T (k, si) vk (1,...,............. ,K} Vi {1, (1....,B)
8: VJ(0) KBN Σk Ee D Av, si) b(s))/)))) log Pocaa) (T(
9: 0 ADAM (O))))
10: end for
11: Output: The model parameter
Instance Augmentation for MOCO. Our proposed model only has small extra computational and memory overhead to the original single-objective AM solver. We keep our model as simple as possible, making easy for our approach to use other models and other improvements developed for single-objective NCO. These properties are crucially important for generalizing the NCO to multiobjective problems. In this work, we simply extend the instance augmentation method (Kwon et al. 2020) to MOCO. The details can be found in Appendix B.1
5
PREFERENCE-CONDITTONN MULTIOBJECTIVE POLICY OPTIMIZATION
5.1 COST FUNCTION
Our proposed node selection strategy guarantees that the model can always generate feasible solu- tions. In this section, we develop an efficient multiobjective policy optimization method to train the model for all the preferences simultaneously. For an MOTSP problem, the objective functions are vector of m different costs (i.e. lengths) for a tour L(х²) = [TT) Im (T)). We can define Brightee-Tchebycheef scalarized cost for each preference X:
(AL((( (4f e)]}, L( Isism
where =/" is an ideal cost for the i-th objective. For a given instance s, our goal is to minimize the expected cost for all preferences:
J(0ls) = Ex L(T|A),
where A is the uniform distribution over all valid preferences. To train the model, repeatedly sam- ple different instances ~ at each iteration. We define the training loss as J(0) E (0ls).
5.2 MULTTIORJECTIVE REINFORCE
For given instance s and specific preference X, the REINFORCE (Wiliams 1992 to
estimate the gradient for the preference-condiiioneed scalar cost:
[ s) (tr-eennctttl((((]))....
b(s)))) log Po(a) (T[s)]
(10)
where b(s(A) is the bascline of expected cost to reduce the gradient variance. This gradient can be estimated by Monte Carlo sampling. At each update step, randomly sample K preference {AI..... Axk } ~ A, B instances {81, ..., ~ S, and N different tour { ... n Po(A)) (11:)) for each A4-S; combination. The approximated gradient is:
N DULLTIIES s:) - b(s: b(si/AA)) log log k=
K
B
1
VJ(0) R KBN
(1I)
We use the shared bascline baturea (x) N [ De. 8:) over N sampled tours for each A S; combination. The starting node for each tour Th. is chosen in random to force diverse rollouts proposed in (Kwon al. 2020 The algorithm shown in Algorithm

---

Published as a conference paper at ICLR 2022
5.3 ACTIVE ADAPTION
We also propose simple yet powerful active adaption approach to further adjust the whole model approximate the Pareto front for given test instance Appendix B.3 The proposed method
does not depend on specific instance distribution S, and is suitable for out-of-distribation adaption.
EXPERIMENTS
Problems and Model Setting. We consider MOTSP (Lust & Teghem 2010a). MOCVRP (L- comme et al. 2006) and MOKP (Bazgan et al., 2009) in our experimental studies, and use the same model settings for all problems with different task-specific input sizes and mask methods. The main policy model encoder is the Attention Model (Kool et al. 2019) and the hypernetwork is an MLP. We randomly generate 100, 000 problem instances on the fly for each epoch, and train the model for 200 epochs. The optimizer is ADAM with learning rate 7) = 10 and weight decay 10-6. We train our models on a single RTX 2080-Ti GPU, and costs about 10 minutes for an epoch on MOTSPI00. We give detailed model settings, problem formulations, and more experimental results in Appendix HdP The source code can be found in https: http://ggtttbbbcc com Com//oIL//OXXOCOCOOO
Baseline. We call our proposed prefereenee-conditioned multiobjective combinatorial optimization as P-MOCO. We compare it with three widely-used evolutionary algorithm frameworks for MOCO:
MOGLS (Jaszkiewcz, 2002) is multiobjective genetic local search algorithm, NSGAII (Deb 2002) is a Pareto dominance-based multiobjective genetic algorithm, and MOEA/D (Zhang 2007 is a decomposition-batt
et al.
multiobjective evolutionary algorithm. All these algorithm Trameworks need problem-specitne heuristics to generate and search feasible solutions for different problems. We also compare P-MOCO with two other learning -baned methods: DRL-MOA (Li et al.
Li.
2020) decomposes a MOCO with different preferences and builds a Pointer Network (Vinyals jet al.
2015 Bello et al. 2017) to solve each subproblem, and A AM-MOCO is a multi- multi- variant of our proposed model, which builds Attention Model (Kool et al. 2019) for each subproblem. The Weight-Sum scalarization of MOTSP and MOKP are their respective single-objective counterpart. Therefore, we also compare method with the approach that uses some state-of-the-art single-
objective solvers for each weight-sum subproblem.
Table 1: Model Information for the learning-basse -base methods.
Model
#Models
#Params
#Pref.
DRL-MOA
Pointer-Network
101
101 x 0.2M = 20.2M (7%)
Fixed 101
AM-MOCO
Attention Model
101
101x 1.3M 131.3M (1.1%)
Fixed 101
P-MOCO (Ours) Pref-Conditioned AM
1.4M
Flexible
Model Information for the learning-based methods is shown in Table Our model supports flexi- ble preference assignment and only has 1.1% total parameters to the muuti--mdel counterpart.
Inference and Metrics. We report the results and run time for solving 200 random test instances for each problem, with normally 101 to 105 different trade-offed solutions, and up to 10, 011 solutions for our proposed method. In most cases, we report our model's s zero-shot generalization performance without any search and fine-tune. We use the hypervolume indicator (Zitzler et al. 2003) to measure the performance for each method. For a set P R in the objective space, we can find a reference point r* that dominated by all solutions in P, and define the hypervolume HV(P) as volume for:
(12) where HV(P) (S) In general, the larger the hypervolume, the better the solution set tends to be. The ground truth Pareto set always has the largest hypervolume, We report the normalized hypervolume values in [0, 1] with respect to the same r" for all the methods, and also the ratios of hypervolume difference to our method. A Wilcoxon rank-sum test with a significance level 1% is conducted to compare the results for each experiment. More details can be found in Appendix D.I
5 {r E R.m 3 y E P such that y < < <r",
6.1 RESULTS AND ANALYSIS
MOTSP. The results on two and three objective MOTSP are shown in Table 2 and Table 3 respec- tively. MOGLS, NSGALI and MOEA/D all use 2-opt local search heuristic (Jaszkiewic7 2002) to
7

---

Published as a conference paper at ICLR 2022
Table 2: Experimental results on two-objective MOTSP, MOCVRP and MOKP with different input sizes (20,50 and 100). HV is the hypervolume metric, Gap is the ratio of hypervolume difference with respect to our method, and Time is the running run for solving 200 random test instances. The best result and its statistically indifferent results are highlighted in bold.
MOTSP
MOTSP20
MOTSP50
MOTSPI00
Method
HV
Gap
Time
HV
Gap
Time
HV
Gap
Time
Weight-Sum LKH
0.51
2.44%
(3.9m)
0.58
-0.26%
(42m)
0.68
-0.58%
(3.1h)
Weight-Sum OR Tools
0.48
7.29%
(3.7m)
0.52
9.66%
(38m)
0.63
5.64%
(2.8h)
MOGLSSTSP
0.48
7.96%
(1.7h)
0.51
10.7%
(4.5h)
0.59
14.7%
(12h)
NSGAII-TSP
0.47
9.88%
(45m)
0.46
19.7%
(49m)
0.51
26.5%
(53m)
MOEA/D-TSP
0.48 7.82%
(3.1h)
0.47
18.9%
(3,3h)
0.52
25.0%
(3.7h)
DRL-MOA (101 models)
0.46
11.3%
(2s)
0.49
15.0%
(5s)
0.57
17.0%
(15s)
AM-MOCO (101 models)
0.52 0.22%
(2s)
0.57
1.72%
(7s)
0.67
0.72%
(18s)
P-MOCO (101 pref.)
0.52
0.19%
(2s)
0.57
1.80%
(5s)
0.67
0.60%
(168)
P-MOCO (101 pref., aug)
0.52
0.00%
(2.1m)
0.58
0.00%
(4.2m)
0.67
0.00%
(12m)
MOCVRP RRP
MOCVRP20
MOCVRP50
MOCVRPI00
Method
HV
Gap
Time
HV
Gap
Time
HV
Gap
Time
MOGLS-MOCVRP
0.33
6.66%
(2.9h)
0.39
10.5%
(4.1h)
0.38
13.0%
(5h)
NSGAII-MOCVRP
0.31
12.3%
(39m)
0.36
18.0%
(39m)
0.35
20.8%
(41m)
MOEAD-MOCVRP
0.29
17.9%
(1.7h)
0.33
24.8%
(1.8h)
0.34
22.3%
(2h)
DRL-MOA (101 models)
0.32
9.19%
(6s)
0.37
16.0%
(15s)
0.37
16.0%
(33s)
AM-MOCO (101 models)
0.35
0.71%
(8s)
0.43
2.84%
(21s)
0.43
3.04%
(39s)
P-MOCO (101 pref.)
0.35
0.58%
(8s)
0.44
0.65%
(18s)
0.44
0.51%
(36s)
P-MOCO (101 pref., aug)
0.35
0.00%
(1m)
0.44
0.00%
(2.1))
0.45
0.00%
(4.5m)
MОKP
MOKP50
MOKP100
MOKP200
Method
HV
Gap
Time
HV
Gap
Time
HV
Gap
Time
Weight-Sune SumtttSSuuui DP
0.70
2.11%
(16m)
0.83
2.74%
(1.5h)
0.66
2.86%
(4.2h)
Weight-Sum Greedy
0.62
14.0%
(2s)
0.77
10.1%
(4s)
0.63
7.49%
(7s)
MOGLS-KP
0.58
19.1%
(1.8h)
0.72
15.6%
(3.9h)
0.62
9.49%
(9.8h)
NSGAII-KP
0.56
22.0%
(34m)
0.69
19.8%
(33m)
0.58
14.7%
(34m)
MOEAD-KP
0.59
18.2%
(1.5h)
0.76
11.1%
(1.4h)
0.65
5.38%
(1.6h)
DRL-MOA (1O1 models)
0.63
12.9%
(5s)
0.78
9.32%
(I7s)
0.65
4.39%
(35s)
AM-MOCO (101 models)
0.72
0.21 %
(7s)
0.86
0.41 %
(16s)
0.68
0.32%
(42s)
P-MOCO (101 pref.)
0.72
0.00%
(7s)
0.86
0.00%
(15s)
0.68
0.00%
(40s)
search for promising solutions. We also include two weight-sum scalarization baselines with the state-of-the-ee art LKH solver (Helsgaun) 2000; Tinós et al.) 2018) and Google OR tools (Perron & Furnon 2019). For the bi-objective problems, our proposed method with a single model has similar performances compared with AM-MOCO on all problems. It achieves the best performance with instance augmentation, which significantly outperforms other methods but is beaten by the LKH solver. For the three objective problems, our method can further improve its performance by gen- crating much more trade-off solutions within a reasonable amount of time, which other methods cannot do. As shown in Figure 22 and Figure our method can successfully learn the mapping from preferences to the corresponding solutions, and can generate good prediction to the whole Pareto front. Decision makers can easily obtain any preferred trade-off solutions as they like. This flexibil- ity could be desirable in many real-world applications. More discussion on the connection between the preference and Pareto solution for three-objective TSP can be found in Appendix
MOCVRP. In this problem, each node has a demand, and we need to construct multiple return routes for a vehicle with a fixed capacity from the same depot to handle all demands. The ob- jectives we consider are to minimize the tour length for all routes and also the tour length for the longest routes (the makespan in scheduling) (Lacomme et al. 2006). All the non-learning algorithm frameworks use the problem-specife constructive heuristics and local search method proposed in Lacomme et al. (2006) to search feasible non con-dominated solutions. The results in Table 2 show that method significantly outperforms the non-learning heuristics in terms of both solution quality
8

---

Published as a conference paper at ICLR 2022
Table Experimental results on three-objective MOTSP with different input sizes (20, 50 and 100).
The best result and its statistically indifferent results are highlighted in bold.
MOTSP20
MOTSP50
MOTSPI00
Method
HV
Gap
Time
HV
Gap
Time
HV
Gap
Time
Weight-Sum LKH
0.32
5.83%
(4.5m)
0.36
5.48%
(44m)
0.45
4.03%
(3.5h)
Weight-Sum OR Tools
0.31
8.48%
(4.1m)
0.31
15.5%
(39m)
0.41
11.2%
(3.1h)
MOGLS-MOTSP
0.27
19.6%
(2h)
0.27 27.4%
(5h)
0.33
30.5%
(13h)
NSGAII-MOTSP
0.20 39.9%
(47m)
0.18 49.3%
(56m)
0.25
48.4%
(Ih)
MOEA/D-MOTSP
0.21 36.6%
(3.3h)
0.20 46.7%
(3.7h)
0.27
42.7%
(4.
DRI-MMA (105 models)
0.26 21.6%
(2s)
0.28
23.0%
(5s)
0.34
28.8%
(19))
AM-MOCO (105 models)
0.32 5.52%
(2s)
0.33
6.02%
(7s)
0.42
6.53%
(21s)
P-MOCO (105 pref.)
0.32 5.65%
(2s)
0.36
5.76%
(6s)
0.44
5,52%
(19s)
P-MOCO (105 pref., aug)
0.32 5.46%
(2.1m)
0.36
5.43%
(6.5m)
0.45 4.39%
(20m)
P-MOCO (1,035 pref.)
0.33
2.08%
(19s)
0.36 4.03%
(48s)
0.46
2.12%
(2.9m)
P-MOCO (10,011 pref.)
0.34
0.00%
(3m)
0.38 0.00%
(9m)
0.47
0.00%
(33m)
and rumning time. It also outperforms AM-MOCO with 100 individual models, which could be due to the asymmetric objective scales. We provide further analysis in Appendix [D.4
MOKP. The multiobjective 0-1 knapsack problem can be found in many real-world applica- tions (Bazgan et al., (009). We consider the uni-dimension problem, where each item has multi- ple values and one weight. The goal is to select a subset of items to maximize all obtained values with a weight constraint. The non-learning methods use binary coding with a greedy transformation heuristic to maintain feasibility (Ishibuchi et al. 2014). We also include weight-sum scalarization baselines with dynamic programming (DP) and a strong greedy search based on the value-weight ratio. According to the results in Table our method has the best performance all problems. The DP method is also outperformed by our method since the weight-sum scalarization can only find the convex hull of the Pareto front. The Tchebycheff scalarization of MOKP is not KP problem, while our method is more flexible to use Tchebycheff scalarization on the reward function. We also report the results on 10 objective MOKPI00 and the generalization performance problem with 500 items in Appendix D.8
Out-of- -fDsttrbiiiinn Problems and Active Adaption. We also validate the generalization perfor- mance of our method on 6 distrii-iitiittionn (OOD) MOTSP problems from Fonseca et al. (2006). Their ground truth Pareto fronts can be obtained by exhaustive search. The results are shown in Ap- pendix D.2 due to the page limit. With active adaption, our method can achieve good performance (1%- 1.5% HV gap to the ground truth Pareto fronts) on these OOD problems.
7 CONCLUSION AND FUTURE WORK
Conclusion. We have proposed novel Pareto front for MOCO problems using a single model. It allows decision makers to directly ob- tain any trade-off solutions without any search procedure. Experiments on different problems have shown that our proposed method significantly outperforms other methods in terms of performance, speed and model efficiency. We believe the proposed method is a principled way for solving MOCO.
method to approximate the whole
Future Work. In a sense, our method can be regarded as a learning version of the decomposition- based algorithm (MOEA/D (Zhang & Li 2007)) dealing with all the possible trade-off preferences. Instead of maintaining a set of finite solutions as in other MOEA/D vaiants (Trivedi et al,, 20166), we build single learning- based model solve the subproblems for all the preferences simultaneously in collaborative manner. We believe the linlle-mddel-or-all-poe poreall-reeeerence approach is promising methods, and could be an important re-
alternative to the current default pniite-opulation--eee search direction for multiobjective optimization. Our method can be further improved with other advanced models and efficient multiobjective training procedures. In the future, we will study fun- damental issues of multiobjective optimization (e.g., convergence v.s. diversity, exploitation v.s. exploration trade-off) for Pareto set learning methods.
Limitation. It is very difficult to give a convergence guarantee for learning- each preference- based subproblem could be already NP-hard, and the number of Pareto solutions is exponentially large with respect the input size. See detailed discussion in Appendix A
baaneng-based based MOCO, where
9

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
We thank Prof. Hisao Ishibuchi for his valuable comments on an earlier version of this work. This work was supported by the Hong Kong General Research Fund (1 (11008121, CityU-9043148),
REFERENCES
David L Applegate, Robert E Bixby, Vasek Chvatal, and William J Cook. The traveling salesman problem: computational study, 2007.
Cristina Bazgan, Hadrien Hugot, and Daniel Vanderpooten. Solving efficiently the 0-1 multi-
objective knapsack problem. Computers & Operations Research, 36(1):260-279, 2009.
Cristina Bazgan, Florian Jamain, and Daniel Vanderpooten. Discrete representation of the non- dominated set for multi-objective optimization problems using kernels. European Journal of Operational Research, 260(3):8144 14-827, 2017.
Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. In International Conference on Learning Representa- tions (ICLR) Workshops, 2017.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimiza- tion: methodological tour d' d'horizon. European Journal of Operational Research, 2020.
Pierre Bonami, Andrea Lodi, and Giulia Zarpellon. Learning classification of mixed-integer quadratic programming problems. In International Conference on the Integration of Constraint Programming. Artificial Intelligence, and Operations Research (CPAIOR), 2018
Quentin Cappart, Didier Chételat, Elias Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. In Inter- national Joint Conferences on Artificial Intelligence (IJCAI), 2021a.
Quentin Cappart, Thienry Moisan, Louis-Martin Rousseau, Isabeau Prémont-Schwarz, and Andre A Cire. Combining reinforcement learning and constraint programming for combinatorial optimiza- tion. In AAAI Conference on Artificial Intelligence (AAAI), 2021b.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimiza- tion. In Advances Neural Information Processing Systems (NeurIPS), 2019.
Eng Ung Choo and DR Atkins. Proper efficiency in nonconvex multicriteria programming. Mathe- matics of Operations Research, 8(3):467-470, 1983.
Hanjun Dai, Elias Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Indraneel Das and John Dennis. Normal-boundary intersection: A new method for generating the pareto surface in nonlinear multicriteria optimization problems. SIAM journal optimizution, 8 (3):631-657, 1998.
Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan. A fast and elitist mul- tiobjective genetic algorithm: Nsga-ii. IEEE Transactions Evolutionary Computation, 6(2): 182-197, 2002.
Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Martin Rousseau. Learning heuristics for the tsp by policy gradient. International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR), 2018.
Iddo Drori, Anant Kharkar, William R Sickinger, Brandon Kates, Qiang Ma, Suwen Ge, Eden Dolev, Brenda Dietrich, David P Williamson, and Madeleine Udell. Learning to solve combinatorial optimization problems on real-world graphs in linear time. In IEEE International Conference on Machine Learning and Applications (ICMIA), 2020.
10

---

Published as a conference paper at ICLR 2022
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982, 2020.
Benjamin Ehret, Christian Henning, Maria R. Cervera, Alexander Meulemans, Johannes von Os- wald, and Benjamin Grewe. Continual learning recurrent neural networks. In International Conference on Learning Representations (ICLR), 2021.
Matthias Ehrgott. Multicriteria optimization, volume 491. Springer Science Business Media, 2005.
Matthias Ehrgott and Xavier Gandibleux. A survey and annotated bibliography of multiobjective combinatorial optimization. OR-Spektrum, 22(4))425-460, 2000.
Matthias Ehrgott and Xavier Gandibleux. Multiobjective combinatorial optimization-theory methodology, and applications, pp. 369 444. Springer, 2003.
Matthias Ehrgott and Xavier Gandibleux. Hybrid metaheuristics for multi-objective combinatorial optimization. In Hybrid metaheuristics, pp. 221-259. Springer, 2008
Patrick Emami and Sanjay Ranka. Learning permutations with sinkhorn policy gradient. arXiv preprint arXiv: /805 000000, 2018.
Kostas Florios and George Mavrotas. Generation of the exact pareto set in multi-objective traveling salesman and covering problems. Applied Mathematics and Computation, 237:1-19, 2014.
Carlos M Fonseca, Luis Paquete, and Manuel López-Ibánez. An improved dimension-swecy algo- rithm for the hypervolume indicator. In IEEE Congress Evolutionary Computation (CEC), 2006.
Zhang-Hus Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre-trained model arbitrarily large tsp instances. AAAI Conference on Artificial Intelligence (AAAI), 2021.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combina- torial optimization with graph convolutional neural networks. In Advances Neural Information Processing Systems (NeurIPS), 2019.
Simon Geisler, Johanna Sommer, Jan Schuchardt, Aleksandar Bojchevski, and Stephan Günnemann. Generalization of neural combinatorial solvers through the lens of adversarial robustness. In International Conference on Learning Representations (ICLR), 2022.
David Ha. Andrew M. Dai, and Quoc V. Le. Hypemettorks.. In International Conference on Learning Representations (ICLR), 2017.
Pierre Hansen. Bicriterion path problems. In Multiple criteria decision making theory and applica- fion, 1980.
Keld Helsgaun. effective implementation of the lin kennkenn traveling salesman heuristic. European Journal of Operational Research, 126(1):106-13) 130, 2000.
Arne Herzel, Stefan Ruzika, and Clemens Thielen. Approximation methods for multiobjective op- timization problems: A survey. INFORMS Journal on Computing, 2021.
Benjamin Hudson, Qingbiao Li, Matthew Malencia, and Amanda Prorok. Graph neural network guided local search for the traveling salesperson problem. In International Conference on Learn- ing Representations (ICLR), 2022.
Hisao Ishibuchi, Naoya Akedo, and Yusuke Nojima. Behavior of multiobjective evolutionary algo- rithms mony-obeective knapsack problems. IEEE Transactions on Evolutionary Computation, 19(2):264-28. 2014.
Hisao Ishibuchi, Yu Setoguchi, Hiroyuki Masuda. and Yusuke Nojima. decomposition based many-objective algorithms strongly depends on pareto front shapes. IEEE Transactions Evolutionary Computation, 21(2):169-199 190, 2016.
Performance of

---

Published as a conference paper at ICLR 2022
Hisao Ishibuchi, Linjun He, and Ke Shang. Regular pareto front shape is not realistic. In 2019 IEEE Congress on Evolutionary Computation (CEC), pp. 2034-20411 IEEE, 2019.
Andrzej Jaszkiewicz. Genetic local search for multi-objective combinatorial optimization. European Journal of Operational Research, 137(1): 2002.
Siddhant M. Jayakumar, Jacob Menick, Wojciech M. Czarnecki, Jonathan Schwarz, Jack Rae, Si- mon Osindero, Yee Whye Teh, Tim Harley, and Razvan Pascanu. Multiplicative interactions and where find them. In International Conference on Learning Representations (ICLR), 2020.
Chaitanya K Joshi. Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.0122) 2019.
Nicolas Jozefowie7, Frédéric Semet, and El-Ghazali Talbi. Multi-objective vehicle routing prob- lems. European Journal of Operational Research, 189(2):9333309, 2008.
Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Vladlen Koltun and Christos H Papadimitriou. Approximately dominating representatives. In Inter- national Conference Database Theory, pp. Springer, 2005.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference Learning Representations (ICLR), 2019.
Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic pro- gramming for vehicle routing problems. arXiv preprint arXiv:2102.11756 2021.
Markus Kruber, Marco E Lübbecke, and Axel Parmentier. Learning when to use a decomposition. In International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR), 2017.
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 (NeurIPS), 2020.
Philippe Lacomme, Christian Prins, and Marc Sevaux. A genetic algorithm for bi-objective capac- itated are routing problem. Computers & Operations Research, 33(12):3473-344 -3933, 2006.
Eric Larsen, Sébastien Lachapelle, Yoshua Bengio, Emma Frejinger, Simon Jacostt--Julin, and Andrea Lodi. Predicting tactical solutions to operational planning problems under imperfect in- formation. arXiv preprint arXiv::807.1 1876, 2018.
Kaiwen Li, Tao Zhang, and Rui Wang. Deep reinforcement learning for multiobjective optimization. IEEE Transactions Cybernetics, 2020.
Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehicle routing. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Zhuwen Li. Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolu- tional networks and guided tree search. In Advances Neural Information Processing Systems (NeurIPS), 2018.
Xi Lin, Zhiyuan Yang, Qingfu Zhang, and Sam Kwong. Controllable pareto multi-task learning. arXiv preprint arXhv:2010.06313, 2020.
Michal Lisicki, Arash Afkanpour, and Graham W Taylor. Evaluating curriculum learning strategies in neural combinatorial optimization. arXiv preprint arXiv:2011.06188. 2020.
Andrea Lodi and Giulia Zarpellon. On learning and branching: a survey. TOP, 25(2):207-236 2017.
12

---

Published as a conference paper at ICLR 2022
Thibaut Lust and Jacques Teghem. The multiobjective traveling salesman problem: A survey and a new approach. In Advances in Multi Obiectvveee Nature Inspired Computing, pp. 119-141. Springer, 2010a.
Thibaut Lust and Jacques Teghem. Two-phase pareto local search for the biobjective traveling salesman problem. Journal of Heuristicx, 16(3):475-500 2010b.
Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song. Le Zhang, Zhenghua Chen, and Jing Tang. Learning to iteratively solve routing problems with dual-aspect collaborative transformer. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: A survey. Compur. Oper. Res., 2021.
Kaisa Miettinen. Nonlinear multiobjectiive optimization. Springer Science & Business Media, 2012.
Aviv Navon, Aviv Shamsian, Ethan Fetaya, and Gal Chechik. Learning the pareto front with hyper- networks. International Conference on Learning Representations (ICLR), 2021.
Mohammadreza Nazari, Afshin Oroojlooy, Martin Takáč, and Lawrence V Snyder. Reinforcement learning for solving the vehicle routing problem. Advances in Neural Information Processing Systems (NeurIPS), 2018.
Alex Nowak, Soledad Villar, Afonso S Bandeira, and Joan Bruna. Revised note on learning algo- rithms for quadratic assignment with graph neural networks. In JEEE Data Science Workshop (DSW), 2018
Christos H Papadimitriou and Mihalis Yannakakis. On the approximability of trade-offs and optimal access of web sources. In JEEE Symposium on Foundations of Computer Science (FOCS), 2000.
Laurent Perron and Vincent Furnon. Or-tools, 2019. URL /ttp::://deeelopeers.oo google.
com/opttmizztioon
Hiroyuki Sato. Inverted phi in moea/d and its impact on the search performance on multi and many-objective optimization. In Proceedings of the 2014 Annual Conference Genetic and Evolutionary Computation, pp. 645-652, 2014.
Yoshikazu Sawaragi, HIROTAKA NAKAYAMA, and TETSUZO TANINO. Theory of multiobjec- tive optimization. Elsevier, 1985.
Jürgen Schmidhuber. Learning to control fast-weight memories: an alternative to dynamic recurrent networks. Neural Computation, 4(1):131-139 1992.
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In /EEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
Renato Tinós, Keld Helsgaun, and Darrell Whitley. Efficient recombination in the lin-kerigghan- helsgaun traveling salesman heuristic. In International Conference on Parallel Problem Solving from Nature (PPSN), 2018.
Anupam Trivedi, Dipti Srinivasan, Krishnendu Sanyal, and Abhiroop Ghosh. A survey of multi- objective evolutionary algorithms based on decomposition. IEEE Transactions on Evolutionary Computation, 21(3):440-46,, 2016.
Sergei Vassilvitskii and Mihalis Yannakakis. Efficiently computing succinct trade-off curves. The- oretical Computer Science, 348(2-3):334-355 2005.
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 Neural Infor- mation Processing Systems (NeurIPS), 2017.
Petar Veličković and Charles Blundell. Neural algorithmic reasoning. Patterns, 2(7):100273, 2021.
13

---

Published as a conference paper at ICLR 2022
Natalia Vesselinova, Rebecca Steinert, Daniel F Perez-Ramires and Magnus Boman. Learning combinatorial optimization on graphs: A survey with applications to networking. IEEE Access, 110388-120416, 2020.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly, Pointer networks. In Advances in Neural Information Processing Systems (NeurIPS), 2015.
Johannes von Oswald, Christian Henning, João Sacramento, and Benjamin F. Grewe. Continual learning with hypernetworks. In International Conference on Learning Representations (ICLR), 2020.
Jyrki Wallenius, James S Dyer, Peter C Fishburn, Ralph E Steuer, Stanley Zionts, and Kalyanmoy Deb. Multiple criteria decision making, multiattribute utility theory: Recent accomplishments and what lies ahead. Management Science, 54(7):1336- 1349, 2008
Ronald J Williams. Simple statistical gralient-folooingg algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-256, 1992.
Hong Wu, Jiahai Wang. and Zizhen Zhang. Modrl/d-am: Multiobjective deep reinforcement learn- ing algorithm using decomposition and attention model for multiobjective optimization. In Inter- national Symposium Intelligence Computation and Applications (ISICA), 2020.
Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuris- tics for solving routing problems. IEEE Transactions on Neural Networks and Learning Systems, 2021.
Liang Xin, Wen Song. Zhiguang Cao, and Jie Zhang. NeuroLKH: Combining deep learning model with lin seemighan-helsgaan heuristic for solving the traveling salesman problem. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Qingfu Zhang and Hui Li. MOEA/D: multiobjective evolutionary algorithm based on decompo- sition. IEEE Transactions Evolutionary Computation, 11(6):712-733 2007.
Richard Zhang and Daniel Golovin. Random hypervolume scalarizations for provable multi- objective black box optimization. In International Conference on Machine Learning (ICML), 2020.
Yongxin Zhang, Jiahai Wang. Zizhen Zhang, and Yalan Zhou. Modrl/d-el: Multiohjective deep re- inforcement learning with evolutionary learning for multiobjective optimization. In International Joint Conference on Neural Networks (IJCNN), 2021a.
Zizhen Zhang, Zhiyuan Wu, and Jiahai Wang. Meta-lcarning-baste deep reinforcement learning for multiobjective optimization problems. arXiv preprint arXiv:2 (al:::/000.22444 2021b.
Eckart Zitzler, Lothar Thiele, Marco Laumanns, Carlos M Fonseca, and Viviane Grunert Da Fon- seca. Performance assessment of multiobjective optimizers: An analysis and review. IEEE Trans- actions on Evolutionary Computation, 7(2):117-132, 2003.
Eckart Zitzler, Dimo Brockhoff, and Lothar Thiele. The hypervolume indicator revisited: On the design of pareto-compliant indicators via weighted integration. In International Conference Evolutionary Multi-Criteriin Optimization (EMO), 2007.
14

---

Published as a conference paper at ICLR 2022
We provide more discussion, details the method and MOCO problems, experimental results and analysis in this appendix. Specifically:
Learning Ability and Approximation Analysis: We discuss the learning ability of our proposed method, and give a thorough analysis on its approximation ability in Section [
Method and Problem Details: We provide the details on our proposed model and the MOCO problems in Section [ and Section[] respectively.
More Experimental Results: We give detailed introduction to the hypervolume indica- tor, and present more experimental results with analysis in Section D
A PARETO SET LEARNING AND APPROXIMATION ANALYSIS
A.1 PARETO SET LEARNING AND CONVERGENCE GUARANTEE
In this work, we have proposed novel neural combinatorial optimization (NCO) method approx- imate the whole Pareto set for MOCO problems with a single model. The proposed berning-based MOCO solver can directly generate arbitrary trade-off solutions without extra optimization. We believe it is principled way to solve MOCO problems.
However, the lack of exact optimality guarantee is limitation of the proposed method, which is also the case for previous work on singlc-objective neural combinatorial optimization (Vinyals et al.) 2015 Bello al.) 2017 Kool et al., 2019). This limitation mainly due the fact that many single- objective combinatorial optimization (CO) problems are NP-hard, and the size of Pareto sets for MOCO problem would be exponentially huge, which makes it very difficult to exactly solving the problems (Ehrgott 2005; Herzel et al., 2021). In addition, the training for the parameterized policy (neural network model) cannot guarantee fit all training problems perfectly. The generalization ability to problem instances with different patterns catt-of-distribution generalization) is another critical issue that makes it difficult to give an exact optimality guarantee to the proposed learning- based algorithm.
On the other hand, our proposed model is an efficient mapping from the preferences to the corre- sponding approximate set of the Pareto optimal solutions. It provides a flexible way for decision makers to obtain an approximate solution with their preferred trade-off directly. The experimental results also show that our proposed method can generate good approximate Pareto sets for three different MOCO problems. In the next subsection, we provide a thorough discussion on the approx- imation ability our proposed method.
A.2 APPROXIMATION ANALYSIS
For MOCO problem, the number of Pareto solutions could be exponentially large with respect to its imput size, which makes the problem intractable (Ehrgoti (0055 Herzel et al. 202T). The
preference-based scalarization methods and decomposition methods (Choo & Atkins 1983 Zhang
& Li 2007) we used provides a principled way to link the Pareto solutions with preference, allowing us tackle the problem in a systematic manner. In this work, we propose to approximately solve the scalarized subproblem with all preferences via single model.
We first briefly review the weighted scalarization method and its Pareto optimality guarantee as discussed in the main paper. Then we provide further discussion on the approximation analysis.
Our proposed method decomposes MOCO problem into preference- subproblems with the Tchebyche-T scalarization WWeightedTTCH]
min Srch (x = min max (A.lf((x)) - (+f <)]}, xEX
(13)
# Isism
where 2f is the ideal value for objective f((x) (c.g., the lower bound), and u² = 2 - is a
utopia value with small positive component The preference vector X R.t satisfies X; 2
and Em X = 1, where X; is the preference for the i-th objective. This approach has a desirable property:
Lemma
(Choo & Atkins (983)). A feasible solution x E X is Pareto optimal if and only if there weight vector À > O such that x is an optimal solution to the problem [3)
15

---

Published as a conference paper at ICLR 2022
According to Lemma 1, we obtain any Pareto solution by solving the Weighted-TCLI subprob- lem with a specific weight. However, the weight for each Pareto solution depends on its objective values, which are not known in advance (Sawaragi al., [985; Ehrgott 2005). The sicision-maker still needs to solve multiple subproblems with different preferences to find a desirable solution. To find the whole Pareto set, it needs to solve an exponentially huge number of subproblems.
Given a problem instance 8, our proposed model provides a single mapping function zy = h(A) from any preference
its corresponding solution 2 which is constructed by the preference- based policy Pe(x) (s) In the ideal case, if all generated solutions I are the optimal solutions æi of problem (33) with preference X, according to Lemma our proposed model can generate the whole Pareto set (all Pareto optimal solutions) for the original MOCO problem.
In practice, we are interested in the proposed method's s approximation ability. We find that its per- formance strongly depends on the approximation ability of the parameterized policy (neural net- work model) on the single-objective scalarized subproblem. We first give an informal claim on our method's approximation ability, then provide detailed explanations and discussions.
(Informal) Claim 1. the proposed method can approximately solve the subproblem 13 with any preference X, it can generate good approximation to the whole Pareto set for the MOCO problem.
To support this claim, we follow the traditional c-Pareto approximate method for MOCO prob- lems (Papadimitriou & Yannakakis 2000) Herzel et al. (021). First, an c-Pareto domination relation between two individual solutions can be defined as:
Definition 3 (e-Pareto Domination). For a MOCO problem and an 0, let Fo, Tb E X, is said to E-dominate 2y (Ia < (b)) if f((xa) S (1 + e))(()) Vi (1,...m..
This definition is a natural generalization from the (1 - apaproxxinn for single-objective opti- mization. With this concept, an e-approximate Pareto set (Papadimitriou & Yannakakis 2000) can be defined as:
Definition 4 (e-Approximate Pareto Set). For an E > 0, a set Pe C X' is an e-approximate Pareto set, if for any feasible solution E X, there exists solution x' E Pe such that x' <
In other words, all feasible solutions of the MOCO problem can be almost dominated by some solutions in Pa (Papadimitriou & Yannakakis 2000). When the Pareto set is intractable and hard to find, the e-approximate Pareto set would be a reasonable choice to achieve in practice. Each MOCO problem has unique Pareto set, but have different e-approximate Pareto sets. The ability of our proposed method to find an e-approximate Pareto set strongly depends on its performance on each single-objective preference-based subproblem.
Let x², denotes the optimal solution of the problem (3) with preference X, if the proposed method can generate an approximate solution xy <e for any preference X, it is able to generate an E E-approximate Pareto set Pe to the MOCO problem.
Theorem 1.
Proof. Let P be the Pareto set for a MOCO problem, for any Paacto E P, according to Lemma 1, there is weight vector X > 0 such that x 2x, is the optimal solution for subproblem (13) with a specific preference X. Therefore, our proposed method can generate an approximated solution rx Zs _x = Pareto By generating approximate solutions for all 3PPartoo P, our proposed method is able to generate an e-approximate Pareto set Pe to the MOCO problem.
A.3 LIMITATION
Strong Assumption on (Approximately) Solving all Subproblems: The approximation guaran- tee in Theorem heavily depends on the ability to (approximately) solve each weighted subprob- lem. Due to the NP-harness, it is indeed non-trivial to give convergence guarantee to generate e-dominate solutions for any preference with a small enough e. This limitation also applies for other end-to-end learning-based (e.g, neural combinatorial optimization) and heuristic-based methods.
We are aware that some efforts have been made to combine the learning- based method with dynamic programming to achieve asymptotically optimal solution solution for specific single-objective prob- lem in recent works (Cappart et al. 20211] Kool et al., (02T). These methods provide a controllable trade-off between the solution quality and the computational cost for solving ha-hard problems.
16

---

Published as a conference paper at ICLR 2022
However, their generalization to the multi-ojjective problem is not straightforward, since the scalar- ized subproblem for each preference is not necessary the same as its single-objective counterpart. For example. Tchebycheff scalarized MOTSP is not single-objective TSP as discussed at the end of Section [3.2 In addition, according to [Bengio et al. (2020), these methods belong to the class of learning alongside the algorithms, while our proposed approach is learning to directly produce the solutions (neural combinatorial optimization). Therefore, the idea for learning enhanced multi- objective combinatorial algorithm could be important research topic future, but of the scope for the current work.
Dense Approximation for the Whole Pareto Set: Another concern would be the required number of solutions in the e-approximate Pareto set P.. If the required number is exponential to the imput size, the approximation itself also intractable. In their seminal work, (Papadimitriou Yannakakis (2000) establish promising result:
Theorem (Papadimitriou & Yannakakis (2000). For any multiobjective optimization problem and any there is s-approximate Pareto set Pe of which the size is polynomial in the number of solutions and (but exponential in the number of objectives).
However, the existence of such set still does not mean that it can be easily found (Papadimitriou Yannakakis] 2000; Herzel et al,) (022T. The computability (whether Pa can be constructed in polynomial time) would be hard justify for a real-world problem. For new unseen problem in- stance in practice, our proposed method might still need to generate an exponentially large number of solutions to construct e-approximate Pareto set Pe. is also unclear how to properly select
set of preferences in advance. Many research efforts have been made on developing approximation
methods for solving MOCO problems in the past decades (Herzel et [021] Hansen 1980 Pa-
padimitriou & Yannakakis 2000) Vassilvitskii & Yannakakis 2005 Koltun & Papadimitriou [0055
important to better leverage the current advanced ap- proximation strategies to design more efficient preference-bai based methods. In the learning-baa -ased
Bazgan al.J (017). future work,
optimization scenario we consider, it is also possible learn the suitable approximation method and/or preference distribution directly from the data (problem instances).
17

---

Published as a conference paper at ICLR 2022
B DETAILS ON THE PROPOSED MODEL
B.I MODEL SETTING
Table 4: Model Information.
#Models
#Total Params #Encoder Params #Decoder Params #Preference
Attention Model P-MOCO (Ours)
1
1.3M
1.2M
0.IM 0.2M
Fixed 1
1
1.4M
1.2M
Flexible
We use the same model for all MOCO problems while tuning the input size and mask method for each problem. Table shows the number of parameters of standard single-objective attention model (Kool et al.) 2019) and our proposed preference-base bbaee multiobjective attention model. Our model supports flexible preference assignment the inference time with a small overhead, while the other neural MOCO methods all require training multiple AM models for different preferences. We build the single-preference attention models as well as our model following the implementation in Kwon al. (2020).
Attention Encoder. The encoder we use is the standard attention encoder as in Kool et al. (019)) and it is shared by all preferences. The encoder has 6 attention layers, and 128-dimensional node embedding for the input nodes. Each attention layer has a multi-head attention (MHA) with eight 16-dimensional heads, and a fully connected layer (FC) with 512-dimension hidden sublayer. The encoder also includes skip-connection and batch normalization for each attention layer. We use the same model for all MOCO problems (MOTSP, MOCVRP, MOKP) but with different input dimensions for each problem, which will be introduced in the next section.
Preference-Conditione Decoder. The decoder's main model structure is the same the AM decoder (Kool et al. 2019). It has one multi-head attention layer with eight 16-dimensional heads similar to the encoder, but without skip-connection and batch normalization. The decoder uses a single 1 128-dimensional attention head to calculate the probabilities of selecting different nodes at each step. Different problems have different masking methods for probability calculation.
We use a simple MLP model to generate the preference-conditionne conditioned parameters for the decoder. For all MOCO problems, the MLP model has two 128-dimensional hidden layers with ReLu activation. The input is an m--iimensional preference vector À which satisfies A; 2 0 and m X; = 1, where m is the number of objectives and X, is the preference for the i-th objective. We adopt the parameter compression approach in Ha et al. (2017) to control the model size. The MLP model first generates hidden embedding e(A) = MLP (A)b)), then maps the hidden embedding to the decoder parameters via linear projection Odecoder We(A) + b. The learnable parameters & for the MLP model MLP((A/e) and the parameter matrices W and i for the decoder.
Training Procedure. For all problems, we train proposed model for 200 epochs, with 100, 000 problem instances randomly generated on the fly at each epoch. At each iteration step, we need to sample/ K preferences, B problem instances, and N tours calculate the policy gradient. We set K x = 64 to make the batch of 64 instances for training a single AM model, and let N equal to the problem size (e.g., the number of nodes) as in Kwon et al. 22020). We find the model performance is equally good for setting K = 1, 2 and 4, and keep using K = for all problems. In other words, we randomly generate preference that satisfies X; 2 0 and Em X 1 at each training step.
For the AM-MOCO baseline, we adapt the transfer training approach in Li et al. (2020) to train multiple AM models for different preferences. We first train single AM model with single preference on one objective from scratch with 200 epochs, then transfer its parameter to the model for neighhor subproblem with similar preference, and fine-tune the new model with epochs. With sequentially transfer and fine-tune, In most experiments, we set the number of preferences as 101. Therefore, we need to build 101 AM models with total 700 training epochs.
obtain set of trained models for different preferences.
Instance Augmentation for MOCO. Due to the design choice of minimal essential change (e.g., the
decoder). our method can also enjoy the current improvements that were originally proposed for the single objective NCO. Here, we generalize the instance augmentation method proposed in Kwon al. (2020) to the MOCO version.
18

---

Published as a conference paper at ICLR 2022
The key idea of instance augmentation for NCO is to find multiple efficient transformations for the original problem such that they share the same optimal solution. Then, we can use an NCO method to solve all problems and select the best solution among all obtained (potentially different) solu- tions. In this way, we have a more robust result similar to the test-time augmentation for computer vision (Szegedy al.) 2016). For the single-objective euclidean TSP and CVRP, there is set of straightforward transformations, which simply flips or rotates the coordinate for all the 2D locations in problem instance (Kwon et al. 2020). For a location (z. y), there is eight different transforma- tion, namely, (zz v), (v, z), (z. 1- y), (v. 1 1-2), z), (1 v), (1- 111yy,20 2), , (1 1--- 1 y). (1 1
For an m-objective euclidean MOTSP problem, the concrete location representations are indepen- dent for each objective. Therefore. we can independently apply different transformations for each objective. Consider the above eight different transformations for each objective, we can have 8 different problem transformations for an MOTSP instance. We have fixed 8 transformations for MOCVRP since it only has one 2D coordinate, and no transformation for MOKP. The details for each problem can be found in the next section.
B.2 TRAINING EFFICIENCY
We use the same amount of samples to train our proposed preference-based model as the other single-objective solvers need (Kool et al., 2019; Kwon et al. (020). Indeed, our proposed model requires significantly fewer samples and training epochs, compared to the other MOCO methods that need to build multiple models for different preferences.
Table 5: The Performance Single Preference.
AM (Single Obj.)
P-MOCO
P-MOCO
Concorde
LKH
OR Tools
(Single Pref.)
(all pref.)
TSP20
3.83 (5m)
3.83 (42s)
3.86 (1m)
3.83 (4s)
3.83 (4s)
3.83 (4s)
TSP50
5.69 (13m)
5.69 (6m)
5.85 (5m)
5.71 (158)
5.71 (15s)
5.71 (158)
TSP100
7.76 (Ih)
7.76 (25m)
8.06 (23m)
7.82 (Im)
7.82 (1m)
7.82 (Im)
We compare our model's performance on one of the objective (e.g., with preference (1, 0)) with the other SOTA single-objective solver and learning-basse solver, the results are shown in Table 5 The results of KOHOO Tools are from Kwon et al.] (2020), and we run the learning-bas based solver by ourselves. We report the average performance single-objective solver (one model in AM-MOCO), P-MOCO (single preference) is our proposed model but only training on single fixed preference (1, 0), and P-MOCO (all preferences) is our proposed model with the reported result on the preference (1, 0). With the same amount of training samples, our model has similar single-objective performance with learning-based single-objective solver, while it can additionally approximate the whole Pareto front. The learning- based solver's performance can be further improved by sampling or active search.
10, 000 test instances. AM is the
These results indicate that we can use a single encoder to efficiently learn a shared representation for all trade-offs among different objectives, and there is positive knowledge transfer among pref- erences during the learning procedure. In addition, it also confirms the assumption that similar preferences should have similar corresponding (approximate) Pareto solutions for the multiobjec- tive problems we consider in this paper. These findings could be useful to design more powerful learning-bass based models for MOCO in the future.
B.3 ACTIVE ADAPTION
After end-to-end training, our proposed method can directly generate different trade-off solutions to a given problem without further search procedure. However, similar to single-objective neural combinatorial optimization, this approach could still have gap to the Pareto front, especially for problems out of the training distribution S (e.g., with different sizes and patterns) (Lisicki et al. 2020). Iterative search methods, such sampling and beam search, formance for a single solution or single preference (Veličkvićć & Blundell (02T). However, these approaches can not find better approximation to the whole Pareto set for MOCO problem.
further improve the per-
19

---

Published as a conference paper at ICLR 2022
Algorithm 2 Neural MOCO Active Adaption
1: Input: model parameter 0, instance s, preference distribution A, number of adaption steps T,
number of preferences per iteration K, number of tours
2: for t 1 to T do
3: Ag SamplePreference(A))
AA E {1. .......................... K}
4: Tk SampleTour (po
vk E [1, K} (I, ,N
5: b(s)Ax) + و L(T )e,
v/ (1....K]
6: VJ(() RN E - E,
|e. Ves)) log po(s)) (T(
7: A ADAM(0, (J()))
8: end for
9: Output: The model parameter
We propose simple yet powerful active adaption approach shown in Algorithm 2 It iteratively adapts the model parameter (A) to a given instance (or batch of instances) with all preferences from the distribution A rather than searching for specific solution. This method is similar to the active search in Bello et al. (2017) which actively refines the singlc-objective model for efficient candidate solutions searching. Our approach focuses on adapting the whole model for better Pareto front approximation. Since this method is cetributiio-agnosiii (not depend on specific instance distribution S), it suitable for out-of-distribution adaption.
20

---

Published as a conference paper at ICLR 2022
C DETAILS OF THE MOCO PROBLEMS
This section introduces the detailed problem formulation for the MOTSP, MOCVRP and MOKP used this work. We also provide the model configuration (e.g., input size, masks) for each problem.
C.I MOTSP
We consider the Euclidean multiobjective traveling salesman problem (Euclidean MOTSP), which is widely used in the MOCO community (Lust & Teghem 2010b Florios & Mavrotas 2014). Its single objective counterpart, 2D Euclidean TSP, has also been studied in single-objective neural
combinatorial optimization (NCO) (Vinyals et al., 2015 Bello al.) 2017 Kool et al., 2019). A
general m-objective MOTSP instance s with n nodes has 7n n X n cost matrices {C* (x)),
1.... } for m different costs. The problem to find a tour (cyclic permutation лτ) to minimize all the costs:
min L(TT (s) min (T (2(T))), (m(ss)))
(14)
where [(( S (1)
In a Euclidean MOTSP, the cost information stored the nodes rather than the edges. The j-th node has 2m-dimensional vector 23). ............. xx"" where z R² is 2D coordinate for the i-th objective. The i-th cost cj* = ||=] æilla ll2 the Euclidean distance for moving from node j to
If we only have objective
reduces to the single-objective 2D Euclidean TSP:
min L, (T|ss) = [()))))) En(iill2 + Σ a (() (1+11))
(15)
The single-objective TSP is already NP-hard, so does the MOTSP. addition, the Pareto set of MOTSP has an exponential cardinality with respect to its input size (e.g., number of nodes), so it is intractable even for the 2-objective case (Ehrgott & Gandibleux 2003).
Problem Instance. Similar to the previous work single-objective NCO (Lust & Teghem 2010b
Florios & Mavrotas 22144), we randomly sample all n nodes with uniform distribution on the 2m dimensional unit hyper-square (e.g.. [0, 1m for all problem instances.
Model Details. m-objective MOTSP, each node has a 2m-dimensional vector to store cost information, so the input size is 2m for the encoder. To calculate the probability for selecting the next node, the decoder needs to mask all already visited nodes as unavailable. We have valid tour when all node is selected (we assume the end node will connect to the start node).
C.2 MOCVRP
The vehicle routing problem (VRP) is a classical generalization of TSP, which has been studied for several decades. This work studies the capacitated vehicle routing problem (CVRP). In this problem, in addition to the location, each node (city) has a demand o; needed to be satisfied. There an extra depot node and a vehicle with fixed capacity D > 5,, Vi to handle all the demands. The vehicle will always start from the depot node, then goes to different cities to satisfy multiple demands Σ 8, < D. and turns back to the depot node. A solution to this problem a set routes that satisfies the demands for all cities.
In the multiobjective problem, we consider two objectives to optimize. The first one is the total tour length as in the single-objective CVRP, and the other one is the tour length for the longest route (which is also called makespan scheduling theory). This problem has been studied in the MOCO community (Lacomme et al. 2006).
Problem Instance. Similar to the TSP problem, the location n nodes are uniformly sam- pled from the unit square. For the demand, similar to the previous work on the single-objece objectivee counterpart (Kool et al.] 2019;; Kwon et al. 22020), we randomly sample discrete ó, from the set (1.... .9. For problem with size 20. 50, 100, set the capacity as Dao 30, Da0 40
21

---

Published as a conference paper at ICLR 2022
and D100 50, respectively. Without loss of generality, normalize the demands 8, : and capacity ò = P as in the previous work (Kool et al. 2019 Kwon et al. 2020). Split delivery not allowed in this problem.
Model Details. the MOCVRP, the depot node has a 2-dimensional location vector, and the other nodes all have 3-dimensional vectors store their locations and demands. We use different parameter matrices to project the nodes into the imput embedding with the same dimension dn = 128. For node selection, the model records the current capacity of the vehicle and the rest demands for all nodes. If a node has been already visited or has demand larger than the vehicle's current capacity, will be masked as unavailable for the vehicle visit. If no node is available visit, the vehicle will go back to the depot. Once all nodes have 0 demands, the node selection is finished and we have valid solution the problem.
C.3 MOKP
Knapsack problem (KP) is also widely studied combinatorial optimization problem. In this work, we consider the 0)1 multiobjective knapsack problem (MOKP) with m objectives and n items:
max f(x) (xx, ... (x)))),
where fa(z) 1
(16)
subject to Σド 3 E {0,1}.
where each item has a weight wy and m different values {uj, i 1,... m]. The problem (c.g., knapsack) has maximum weight capacity W, and the goal is to select a set of items within the weight capacity to maximize the sum values for each objective. To make this problem nontrivial, we further assume all values vj,, Vi,j. weights wyVj and the total capacity are non-negative real value. The total weight of all items is larger than the capacity Σ wy > W, while each single weight smaller than the capacity w; < W.Wi = 1.... n. The single-ohjective knapsack problem NP-hard, so does the MOKP problem (Ehrgott & Gandibleux (003).
Problem Instance. We randomly generate the values and weight for each item both uniformly in [0, 1]. We consider problems with 50, 100, 200 nodes, and the weight capacities are W60 12.5, W0o0 = W200 25 as in the previous work (Bello et al., 2017 Kwon et al. 2020).
Model Details. In m-objective MOKP, each item has values and 1 weight, so the input dimension is for the encoder. For node selection at each step, we mask all already selected nodes and nodes with weights larger than the remained capacity as unavailable. We terminate the selection when all nodes are labeled as unavailable.
22

---

Published as a conference paper at ICLR 2022
D ADDITIONAL EXPERIMENTAL RESULTS
D.1 HYPERVOLUME INDICATOR
P2
P3
P4
Figure 4: Hypervolume illustration.
To solve MOCO problem, the result for each method is set of approximate Pareto solutions. Since the ground truth Pareto set is usually unknown, we use the hypervolume (HV) indicator (Zitzler et al.) 2007) to numerically compare the performance for each method. The hypervolume indicator is widely used in the MOCO community for algorithm comparison.
The hypervolume of set is the volume in the objective space it dominates. For set P C R in the objective space, we can find reference point r* that dominated by all solutions in P, and define the hypervolume HV the volume of the
S (r E I By E P such that - <<rkr"
(17)
where HV(P) = Vol(S). An illustration example is shown in Figure 4 The grey area is the set dominated by the solutions in set {PI, P2. PP3,P4) with the reference point r". this 2- dimensional case, the hypervolume HV(P) is the size of the grey area.
The hypervolume indicator has two important advantages for measuring the approximate set quality with respect to Pareto optimality (Zitzler et al.) (007). First, if an approximate set A dominates another approximate set B, it will have strictly better hypervolume HV(A) > HV(B). In addition, if an approximate set C contains all Pareto optimal solutions, it is guaranteed to have the maximum hypervolume value. comparison, an approximate set has better performance if it has a larger hypervolume.
With different objective scales, the hypervolume value will vary significantly among different prob- lems. We report the normalized hypervolume values f(()) = HV(P)/II" "I r for all methods and also their performance gaps ence point r", which contains the largest value achieved for each objective. Since all problems we consider have positive objective values, we have 0 < f(P) < for all solution sets. The ground truth Pareto set p* usually has (P*)) < 1, unless the zero vector 0 E R is feasible and in the Pareto set.
method. For each experiment, all methods share the same refer-
23

---

Published as a conference paper at ICLR 2022
D.2 OUT-OF-DISTRIBUTION PROBLEM WITH EXACT PARETO FRONT
Table The Results on Problems with Exact Pareto Front.
LI
L2
Method
HV
HV Gap
IGD
HV
HV Gap
IGD
Exact Pareto front
0.733
0
0.735
0
Weight-Sum LKH
0.728
0.71%
0.008
0.730
0.75%
0.007
Weight-Sum OR Tools
0.721
1.68%
0.012
0.722
1.76%
0.009
P-MOCO (TOT pref.)
0.718
2.01%
0.014
0.717
2.43%
0.013
P-MOCO (101 pref., aug.)
0.722
1.52%
0.012
0.721
1.88%
0.010
P-MOCO (101 pref., aug., active)
0.724
1.21%
0.010
0.724
1.48%
0.008
L3
L4
Method
HV
HV Gap
IGD
HV
HV Gap
IGD
Exact Pareto front
0.737
0
0.737
0
Weight-Sumn LKH
0.733
0.53%
0.007
0.731
0.83%
0.006
Weight- OR Tools
0,723
1.89%
0.012
0.718
2.56%
0.014
P-MOCO (101 pref.)
0.722
2.04%
0.013
0.720
2.27%
0.012
P-MOCO (101 pref., aug.)
0.724
1.72%
0.012
0.723
1.93%
0.011
P-MOCO (101 pref., aug., active)
0.726
1.43%
0.010
0.727
1.33%
0.008
L5
L6
Method
HV
HV Gap
IGD
HV
HV Gap
IGD
Exact Pareto front
0.734
0
0.746
Weight-Sum LKH
0.727
0.92%
0.007
0.742
0.48%
0.006
Weight-Sum OR Tools
0.721
1.79%
0.012
0.728
2.43%
0.015
P-MOCO (101 pref.)
0.719
2.05%
0.014
0.729
2.19%
0.014
P-MOCO (101 pref., aug.)
0.723
1.48%
0.011
0.732
1.82%
0.012
P-MOCO (101 pref., aug., active)
0.725
1.29%
0.009
0.737
1.19%
0.009
We conduct experiments on 6 two-objective MOTSP100 instance (L1-L66 in Florios & Mavrotas (2014) of which the exact Pareto fronts are available. In these problems, the objective functions have different ranges, and the cities are not uniformly located, so they are out of our method's training distribution. The results can be found the T
In addition to hypervolume, we also report the Inverted Generational Distance (IGD) Fonseca et al. 2006) to measure the average Euclidean distance between the set approximated Pareto solutions to the exact Pareto front. A smaller IGD value means the approximated set is closer to the exact Pareto front. According to the results, our method, with the instance augmentation and/or active search (10 min budget), can have good performance these out-of-distributis (OOD) instances with 1% 1.5% hypervolume gap. The proposed method also significantly outperforms the weight-sum OR tools bascline. There is still gap the strong weight-sum LKH bascline. As discussed in the paper, robust OOD generalization is an important research direction for the learning beanning-based solver.
24

---

Published as a conference paper at ICLR 2022
8
2 2
18
02
82
(a) 105 Preferences
(b) 1035 Preferences
(c) 10011 Preferences
11
(d) MOTSP20: 105 Solutions
(e) MOTSP20: 1035 Solutions
(I) MOTSP20: 10011 Solutions
18
31
25
MOTSP50: 105 Solutions
(h) MOTSP50: 1035 Solutions
ii) MOTSP50: 10011 Solutions
20
20
12
(i) MOTSP100: 105 Solutions
(k) MOTSP100: 1035 Solutions
(I) MOTSP100: 10011 Solutions
Figure 5: Different number of uniform distributed preferences and the corresponding solutions gen- erated by our method on MOTSP20, MOTSP50 and MOTSP100. Our model can generate well- distributed solutions with small number of preferences, and generate dense approximation with a large number of preferences.
25

---

Published as a conference paper at ICLR 2022
D.3 FLEXIBLE PREFERENCE BASED APPROXIMATION
With our model, it is flexible to generate different number of solutions to approximate the Pareto front. We present example on the three-objective TSP in Figure We use the structured weight assignment approach from Das & Dennis (1998) to give the sets of weights for different instances. This method can generate their nearest neighbor on the unit simplex (e.g., Σ;=1 A; = 1 with X; 2 0, Vi), where m is the number of objectives and is parameter to control the number of weights.
Cp C evenly distributed weights with an identical distance to
For the three objective TSP problems (m 3), we assign p 13, 44 and 140 to generate 105, 1035 and 10011 weights respectively. We also show the corresponding generated so- lutions for MOTSP instances with 20, and 100 citics. According to the results in Figure 5 our model can generate well-distributed solutions with small number of preferences, and generate dense approximation with more preferences. The ability to generate a dense approximation to the whole Pareto set also allows the decision-maker to generate arbitrary preferred solutions the approximate front.
D.4 CEEFERENCE-SOLUTTEO CONNECTION
Cast
Cost
Souate
Profegec Cont2
Protteacee on Cost
Crif
Proferaca
Proferencs
Proferance Cost
Proferance
(a) 11 Preferences (HV 0.649) (b) 101 Preferences (HV 0.664) (c) 1,001 Preferences (HV 0.669)
Figure 6: Different number of uniformly distributed preferences and their connections to the corre- sponding solutions on MOTSP100.
Woffreca on Oiqeccive
Oileett 1or
Oijject wer
Osjecive
Thelevece
24
60
USS.
174 180 27A
25
02
74
18. 12.6
164
300
215 Preference on Objection
objecdive
Objoctive
(a) MA-MOCO (101 Models, HV = 0.417)
(b) P-MOCO
(c) P-MOCO (1,001 Preferences, HV 0.441)
(101 Preferences, HV = 0.435)
Figure 7: Different number of uniformly distributed preferences and their connections to the corre- sponding solutions on MOCVRP100. We report the approximate Pareto front for MA-MOCO with 101 models, and our model with 101 and 1, 001 preferences.
We further analyze the connection between the preference and its corresponding solution on the uniform and non-uniform Pareto front. F shows the connections in our model with different numbers of preferences for the MOTSPION 100 instance. Since the two objectives (costs) in MOTSP have the same scale, this problem has uniform connection between the preferences and the (ap- proximate) Pareto front. By increasing the number of preferences, we have three sparse to dense generated Pareto front approximations.
We are more interested in MOCVRP, which has non-uniform Pareto front. In this problem, we consider different objectives optimize, namely, the total tour length (objective 1) and the tour
26

---

Published as a conference paper at ICLR 2022
length for the longest route (objective 2). These two objectives are in quite different scales, where the first objective is significantly larger than the second one. In Figure 7 we show different connections for the MOCVRPI00 instance. For MA-MOCO, our proposed model, we report the connections with different numbers of uniform preferences.
report the connections for all 101 models. For
In this problem, 101 models ate a dense approximate Pareto front. The obtained solutions are biased to the area that objective has a much better relative performance. By increasing the number of preferences, our proposed method can generate more solutions that have relatively better performance for objective 2, which leads to a better Pareto front approximation with higher hypervolume. In this work, we always use a straightforward uniform sampling method to select the preferences. It is interesting to design learning-bant -aaed approach to select the preferences for a given problem instance. Preference adjust- ment and model adaption with awareness on the shape of Pareto front are also worthy to investigate. We left them to the future work.
model with 101 uniform preferences are not enough to gener-
In the MOCVRP instance, we also find the 101-mode MA-MOCO has worse performance com- pared to our method with 101 preferences. The reason would be the mismatch between the uniform transfer training and the non-uniform Pareto front. Increasing the training steps for fine-tuning each model might fix this issue, but will lead to an even larger computational overhead, given the current training already require 700 epochs. The fixed preferences assignment is another issue for MA- MOCO. It requires a fixed set of preferences for each model at the start of the training procedure when the decision makers might have no knowledge the problem. When the training procedure is done, it dose not allow any preference adjustment without retraining the models.
D.5 CONNECTION BETWEEN PREFERENCES AND SOLUTIONS
In the previous sections, we use the weighted Tchebycheff aggregation to connect the preference to its corresponding solution for two-objective optimization problems:
(A)) = max (A.]f((x)- - -z =/1]:
(18)
15ism
where 2 minzex (xx is an ideal value for fx(). There are also many other aggregation func- tion we can use to build the connection. For example, modified version of weighted Tchebycheff aggregation can be defiend as:
Uunch (z: = max -x)
-
(19)
1545m X3
where the only difference is the weight vector x.
The penalty-based boundary intersection (PBI) is another widely-used aggregation function for decomposition- multiobjective optimization Zhang & Li 2007):
Opbi (a/lA) di Od2,
dj = (F(x) - -²>>>\///1
X
d2 [1F(x) --- di |X
11
(20)
where 0 is the penalty parameter, F(x) (m) and x" (zf ...,..., 2f) are the ob- jective vector and ideal vector respectively. An inverted version of PBI (IPBI) aggregation func- tion (Sato 2014) can be defined as:
Diphi (x) A) -di + Od2,
dj 1x F(())) \//||aI,
X
d2 || - -F(x) di |
(21)
where NN is the nadir vector that contain each objective's 's worst value among all Pareto solutions. For a two-objective optimization problem, when we can find a dense set of corresponding solutions to cover the Pareto front for each aggregation function, their performance could be similar each
27

---

Published as a conference paper at ICLR 2022
11
33
10
12
15
28
30
(a) TCH: 105 Solutions
(b) TCH: 1035 Solutions
(c) TCH: 10011 Solutions
20
28
21
15
25
(d) Modified TCH: 105 Solutions
(e) Modified TCH: 1035 Solutions
Modified TCH: 10011 Solutions
20
23
26
(g) IPBI: 105 Solutions
(h) IPBI: 1035 Solutions
(i) IPBI: 10011 Solutions
Figure 8: Different number of approximate Pareto solutions generated by our method with uniformly distributed weight vectors and different aggregation functions.
other. However, different aggregation functions would have quite different performances on the problems with three The performances will heavily depend on the shape of Pareto front (Ishibuchi et al. 2016). especially with limited number of approximate solutions.
objective functions (called many-objective optimization problems).
We compare the performance of our proposed method with different aggregation functions on MOTSP50 with 105, 1035 and 10011 preferences respectively in Fig. According to the results, the IPBI method can generate the most uniformly distributed solutions for the MOTSP problem with an inverted triangular shape Pareto front, of which the shape similar the weight vector distribu- tion (e.g., see Fig 5). This observation is consistent with the findings and analysis in Ishibuchi et al. (016)) According to these results, we use the Tchebycheff aggregation for all two-ohjective opti- mization problems and IPBI aggregation for all problems with more than two objective functions in this work. Since the shape of Pareto front tends to irregular for real-world applications (Ishibuchi al. 2019), how to properly choose the aggregation function and assign the preference distribution could be an important future work.
28

---

Published as a conference paper at ICLR 2022
D.6 THREE-OBJECTIN OBJECTIVE MOTSP WITH ASYMMETRIC PARETO FRONT
(a) Uniform Weights
(b) 105 Solutions
(c) 1035 Solutions
(d) 10011 Solutions
(e) Non-Uniform Weights
(l) 105 Solutions
(g) 1035 Solutions
(h) 10011 Solutions
Figure 9: The miforrm/non-unifon distributed preferences and different number of corresponding solutions generated by our method on three-objective 1OTSP100 with asymmetric Pareto front. We use 1035 different preferences as example for the uniform and non-uniform case respectively, and present the results for 105, 1035 and 10011 solutions. Top Row: Uniform distributed preferences and the corresponding non evenly distributed solutions. Bottom Row: Non-uniform distributed preferences and the corresponding solutions which are more evenly distributed.
In this subsection, we conduct experiments on the three-objective MOTSP100 instances with asym- metric Pareto fronts. The definitonn of irregular MOTSP instance is almost the same as in Sec- tion C except the coordinates for the three objectives and randomly sampled from [0, 1]3, [0, 0.5]² and [0, 0.1 respectively, rather than uniformly from [0, 1]6. In this way, the objective values for the MOTSP instance will be in quite different scales, thus leading to irregular Pareto front (the axes in Figure Fare are in different scales).
A well-known drawback of the scalarization balarizzationbbsedd approach is that it cannot evenly explore the ir- regular Pareto front with a set of uniform weights, which can also be observed in Figure ad)-(d). Our proposed approach allows the user to generate arbitrary trade-off Pareto solutions on the infer- ence time, therefore they can directly generate a dense approximation and then select the preferred solutions in Figure d). This flexibility can partially address the unevenly distributed issues caused by a (small) set of fixed weights in the traditional ecalarization-baase approach.
If we know the approximate range of different objectives in advance, we can first normalize them into [0. 1] to encourage more symmetric Pareto front. Otherwise, on the inference time, we can use (prior knowledge-based) biased and non-uniform weight assignment to generate uniformly distributed solutions. In Figure (esure9e)-(hh (h))-(h). we first multiple the three-dimensional weights by (1, 2, 10) and then normalize them back [0, 1|3 which leads set of non-un non-uniform weights as shown in TigureDee. e). With this weight assignment, we have a set of more evenly distributed Pareto solutions as shown in Figure f-
D.7 PREFERENCE-BANE BASED INFERENCE
Even without any prior knowledge, our proposed approach allows the user to adaptively adjust the weights in real-time search for the most suitable solutions in their preferred region(s). Some ex- amples of selected weights and their corresponding solutions are shown in Figure [00 for symmetric Pareto front and Figure for asymmetric Pareto front. If we have prior knowledge of the preference
29

---

Published as a conference paper at ICLR 2022
(e.g., the melsioon-maers, will only care about specific region of the Pareto front), we can modify the training preference distribution A accordingly to enhance the training efficiency.
For the problem with truly irregular Pareto front, it is also possible to adaptively adjust the given weights to make them evenly explore the Pareto front during the learning/searching process. One potential direction could be consider the connection between scalarization and hypervolume max- imization as in Zhang & Golovin (2020). We believe this could be an important research topie for the beaning-basse scalarization approach in future work.
Biased Weights: Objl(b) Biased Weights: Obj2(c) Biased Weights: Obj3 (d) Biased Weights: Mid
(e) Biased Sols.: Objl (1) Biased Sols.: Obj2 (g) Biased Sols.: Obj3 (h) Biased Sols.: Mid
Figure 10: Symmetric Pareto Front. Different set of biased weights and their corresponding solu- tions on different regions of the symmetric Pareto front.
(a) Biased Weights: Objl(b) Biased Weights: Obj((c) Biased Weights: Obj3 (d) Biased Weights: Mid
(e) Biased Sols.: Objl
(1) Biased Sols.: Obj2 (g) Biased Sols.: Obj3 (h) Biased Sols.: Mid
Figure 11: Asymmetric Pareto Front. Different set of biased weights and their corresponding
solutions on different regions of the irregular Pareto front. The uniformness of the weights and the corresponding solutions could be different due to the asymmetry. However, the user can adaptively adjust the weights in real-time to search for the most suitable weight(s) and solution(s).
30

---

Published as a conference paper at ICLR 2022
D.8 PROBLEM WITH MORE OBJECTIVES
NSGAJI
311
311
360
Jka
300-
Osjective
Objective
Osjective
(a) MOEA/D (5 10sh evals.)
(h) NSGA-II (5 10 evals.)
(c) P-MOCO (zero-shot)
The value path plots for the 10-objective MOKPI00 obtained by MOEA/D, NSGA-II and our proposed P-MOCO. the plot, each line (value path) represents solution's 10 objective values with its specific preference. In MOKP, we want to maximize the values for all objectives. Our proposed method has significantly better overall performance.
Figure 12:
MGEAAD
NSGNJI
P-MOLO
Sa3ee5
Objective
Objectre
Objective
MOEA/D (10 10 evals.)
(b) NSGA-II (1O 10 eval.)
(c) P-MOCO (zero-shot)
The value path plots for the 10-objective MOKP with 500 items obtained by MOEA/D, NSGA-II and our proposed P-MOCO. Our model is trained 10-objective MOKP100.
Figure 13:
Finally, we test the performance of our proposed method on the 10-objective knapsack problems. We train new model for the 10 objective MOKP with 100 items with uniform 10-dimension pref- erences. The obtained value path plots on the 10-objective MOKP100 are shown in Figure I2 For problems with more objectives, we need large number of solutions to approximate the Pareto set. Training a large number of neural network models would have a huge computational and storage overhead, which also not desirable practice. Therefore, we do not compare with the AM- MOCO and MOA-DR methods on this problem.
For inference, to approximate the Pareto set, we use the weight assignment approach from (Das & Dennis, 1998) (with m 10. = 4, hence 715). The model generates different trade-off solution for each preference, so there are 715 different value paths (lines) each plot. In MOKP, want to maximize the values for all objectives under the capacity limitation. A set good approximate solutions should have rel- atively high overall values. According to the results, our proposed method has the best performance. We also test the performance of our method on larger problem with 500 items. The results shown in Figure 13 confirm that trained model generalizes well to problems with larger size.
of 715 fixed preferences following
= CC.++4-1
31


Reviews:
[{"review_id": "zfmocvQKVX5", "reviewer": "Reviewer_7hop", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written and presents an interesting approach to solving MOCO problems. The structure is appropriate, there is a very good review of related works, clear problem formulation, a good description of the method, experiments, and results. There are also extensive supplementary materials. The introduced method is novel, might be significant, and the quality of this article seems to be on-par with other papers applying ML techniques to solve TSP published at top-tier conferences (which are also cited in this paper). I don't see significant weaknesses. There are some minor typos (e.g., \"a exceptionally\" -> \"an exceptionally\", p. 4), so I recommend revising the paper before the final publication, but from the methodological point of view, the paper seems to be good enough to be accepted.", "summary_of_the_paper": "The paper proposes a novel preference-conditioned method to approximate the whole Pareto front for Multi-Objective Combinatorial Optimization (MOCO) problems with a single model. According to the authors, this method provides extra flexibility for decision-makers to directly obtain arbitrary trade-off solutions without any extra search, which is a more principled way to deal with MOCO.", "summary_of_the_review": "The paper is well-written and presents an interesting approach to solving MOCO problems. The structure is appropriate, there is a very good review of related works, clear problem formulation, a good description of the method, experiments, and results. There are also extensive supplementary materials. The introduced method is novel, might be significant, and the quality of this article seems to be on-par with other papers applying ML techniques to solve TSP published at top-tier conferences (which are also cited in this paper). I don't see significant weaknesses. There are some minor typos (e.g., \"a exceptionally\" -> \"an exceptionally\", p. 4), so I recommend revising the paper before the final publication, but from the methodological point of view, the paper seems to be good enough to be accepted.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "xe3UHTqXElC", "reviewer": "Reviewer_CKHU", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths\n1. Multi-objective combinatorial optimization is a family of important problems but is really challenging to solve by traditional methods. The efforts of introducing deep reinforcement learning to this direction are appealing and novel. This paper may inspire more ML researchers in this interesting direction.\n1. The experiment results seem detailed and sound. The proposed neural network MOCO method outperforms traditional approaches and other single-objective deep learning baselines.\n\n### Weaknesses\n1. The theoretical part of this paper (Section 6 and appendix A) does not seem sound to me. The assumption that the model can generate $\\epsilon$-dominate solutions for any preference seems to be non-trivial for models with small enough $\\epsilon$. \n\n### Other comments\n1. The hypervolume (HV) metric should be discussed in the main paper instead of in the supplementary material to ensure the main paper is self-contained.", "summary_of_the_paper": "This paper presents a learning approach for multi-objective combinatorial optimization (MOCO), which is a challenging problem but not well-studied by previous machine learning researchers. The proposed model is capable of predicting approximate Pareto optimal solutions from various preferences by a single model, via attention networks, and by a so-called \"hypernetwork\". Experiment result on the multi-objective versions of TSP, VRP, and KP shows the effectiveness of the proposed approach.", "summary_of_the_review": "In general, this paper is novel and sound, and the experiment results are convincing. I am suggesting a borderline accept of this paper, and it will be better if the authors could update the theoretical part of this paper and rearrange some materials to make this paper self-contained.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "Quc5JzHK7hF", "reviewer": "Reviewer_mTSr", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In my opinion, the authors provide an interesting and novel approach to multi-objecive optimization problems. Even representing the potentially exponentially large pareto set is a challenge, and is interesting that this can be done via an ML model. A concern could be that in order to achieve a good approximation of the pareto set, it seems that learning the single objective problem well is required (which often is a difficult problem in itself). Would it be possible to solve the single-objective variants with a traditional combinatorial algorithm? The theoretical contribution of this submission is limited.\n\nThe approach is evaluated for three very relevant problems: the multi-objective traveling salesperson problem, the multi-objective capacitated vehicle routing problem and the capacitated knapsack problem. \n\nA minor concern is that I found the tables with the experimental results hard to read. Could you please add a short explanation for the meaning of the table/column headers?", "summary_of_the_paper": "This submission treats multi-objective combinatorial optimization problems and aims to approximate the pareto set. The idea is to build a single ML model that represents the pareto set by providing a pareto set solution for any desired trade-off. The model is build using reinforcement learning and may either be used to find singular solutions with fixed trade-off, or to approximate the pareto set with uniform samples. The authors prove that the pareto set is approximated well if individual trade-offs are approximated well. ", "summary_of_the_review": "I feel this is an interesting contribution concerning a difficult and relevant problem, whose well-made practical part makes up for a more limited theoretical study. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "9RaKi-Uju8Y", "reviewer": "Reviewer_tRFG", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n\n1. The proposed approach is technically sound and exhibits very competitive performance.\n2. The empirical evaluation is thorough as it considers multiple test problems and a broad range of benchmark methods.\n\nWeaknesses\n\n1. The description of the proposed approach is hard to follow. In particular, I am having a hard time understanding how the decoder is defined when the problem instance is not a graph. In general, I would recommend the authors explain their approach in a general fashion by introducing appropriate notation and then explaining it in the context of a particular problem.\n\n2. The use of the term \"preference\" is confusing. The title and abstract suggest that the proposed approach allows the incorporation of user preferences to focus the search on especific regions of the Pareto front, but that does not seem to be the case. I would suggest the authors to clarify this earlier (and even drop the term preference from their title).\n\n3. Since the proposed method relies on scalarizations, it suffers from several well-known issues of this kind of approaches. In particular, scalarization-based approaches are prone to explore the Pareto front unevenly. The points generated in Figures 2 and 5 are well distributed accross the Pareto front, but I think occurs because the front in this particular case is fairly symmetric. I wonder how an analogous figure would look for a more irregular front. I would also like the authors to explain how the weights that give rise to the points in Figures 2 and 5 were chosen.\n\n4. The novelty in this paper is limited, as it reuses several ideas from single-objective neural combinatorial optimization. The only novel (but key) idea is to make the decoder weight-dependent.", "summary_of_the_paper": "This paper proposes an approach for neural multi-objective combinatorial optimization. This approach uses a preference-agnostic encoder along with a weight-dependent decoder to generate approximate Pareto optimal solutions for any arbitrary set of weights of a weighted Tchebyshev scalarization at virtually no additional cost. This is in contrast with existing approaches, which require a significant amount of computation for every new set of weights. Several numerical experiments are conducted, showing favorable results for the proposed method when compared with several other existing evolutionary and learning-based methods.", "summary_of_the_review": "This paper proposes a novel approach for neural multi-objective combinatorial optimization. The novelty of the proposed approach is limited as it reuses several ideas from single-objective neural combinatorial optimization. However, it is technically sound and exhibits a very competitive performance in a broad range of problems. The description of the method is hard to follow but, in general, the paper is well-written. The use of the term \"preference\" is confusing, so I would recommend the authors explain more clearly that their approach does not incorporate preference information.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper develops a ``preference-conditioned” approach to approximate the Pareto frontier for Multi-Objective Combinatorial Optimization (MOCO) problems with a single model (thus dealing with the thorny problem that there can be exponentially-many Pareto-optimal solutions). It appears to provide  flexibility for users to obtain various preferred tradeoffs between the objectives without extra search. The basic idea is to use end-to-end RL to train the single model for all different preferences simultaneously. 

The technical soundness and practical performance are strong. This work's approximation guarantee depends on the ability to approximately solve several (weighted) single-objective problems. This may be challenging due to the NP-hardness of the latter. However, this limitation seems to also apply to other end-to-end learning-based approaches. 

One area where the novelty is somewhat limited is that the paper borrows some number of ideas from neural single-objective optimization. The contribution overall seems noteworthy for hard multi-objective problems.
Decision: Accept (Poster)