Year: 2021

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. To be concrete, we propose a single weight-dependent attention model to directly generate approximate Pareto solutions with any trade-offs. We design an efficient multiobjective reinforcement learning algorithm to train the model with different preferences simultaneously. Experimental results show that our proposed method significantly outperforms the other methods on the multiobjective traveling salesman problem (MOTSP), multiobjective vehicle routing problem (MOVRP) and multiobjective knapsack problem (MOKP) in solution quality, speed, and model efficiency.

heading: 1 INTRODUCTION
text: Many real-world applications can be modeled as different multiobjective combinatorial optimization (MOCO) problems (Ehrgott & Gandibleux, 2000). The multiobjective traveling salesman problem (MOTSP) (Lust & Teghem, 2010a), multiobjective vehicle routing problem (MOVRP) (Jozefowiez et al., 2008) and multiobjective knapsack problem (MOKP) (Bazgan et al., 2009) are three widely studied problems in the research community. These problems have multiple conflicting objectives to optimize, and no single solution can optimize all the objectives at the same time. Instead, there is a set of Pareto solutions with different optimal trade-offs among the objectives.
It is very challenging to find all exact Pareto optimal solutions for a MOCO problem. Finding only one Pareto solution would be already NP-hard for many problems (Ehrgott & Gandibleux, 2000), and the number of Pareto solutions could be exponentially large to the problem size (Ehrgott, 2005; Herzel et al., 2021). The decision-maker’s preference among different objectives is usually unknown in advance, making it hard to reduce the problem into a 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, which can be very labor-intensive in practice.
In many real-world applications, the practitioners need to repeatedly solve different problems with similar characteristics, of which the problem instances can be easily obtained or generated (Bengio et al., 2020). It is desirable to learn the patterns behind these problem instances explicitly or implicitly to design efficient algorithms (Cappart et al., 2021a). Machine learning techniques can be naturally served for this purpose. Some learning-based methods have been recently proposed for solving single-objective combinatorial optimization problems (Bengio et al., 2020; Vesselinova et al., 2020; Mazyavkina et al., 2021; Cappart et al., 2021a). In this work, we extend the learning-based method to solve MOCO problems in a principled way as shown in Figure 1. Our main contributions include:
• We propose a novel neural combinatorial optimization method to approximate the whole Pareto set with infinite trade-offs via a single model, which allows decision-makers to directly generate any preferred trade-off solution without extra search. This novel and powerful property is not supported by any other learning-based or heuristics-based methods.
• We develop an efficient end-to-end reinforcement learning algorithm to train the single model for all different preferences simultaneously, and a simple yet powerful active adaption method to handle out-of-distribution problem instances.
• We conduct comprehensive experiments on MOTSP, MOVR and MOKP problems with different settings. 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 methods in solution quality, speed, and/or model efficiency.

heading: 2 BACKGROUND AND RELATED WORK
text: Multiobjective Combinatorial Optimization (MOCO). MOCO has been attracting much research effort from different communities over the past several decades (Sawaragi et al., 1985; Wallenius et al., 2008; Herzel et al., 2021). There are two main approaches to tackle the MOCO problems: the exact method and the approximation method (Ehrgott, 2005). Exact methods could be impractically costly when, as it often happens, the MOCO problem is NP-hard and the number of Pareto optimal solutions is huge (Florios & Mavrotas, 2014). For this reason, many heuristics (Jaszkiewicz, 2002; Ehrgott & Gandibleux, 2008) and approximation methods (Papadimitriou & Yannakakis, 2000; Herzel et al., 2021) have been developed to find a moderately sized set of approximated Pareto solutions with a reasonable amount of computational budget. However, these methods usually depend on carefully handcrafted designs for each specific problem (Ehrgott & Gandibleux, 2000), of which the effort would be nontrivial for a new problem in real-world applications.
Machine Learning for Combinatorial Optimization. According to Bengio et al. (2020), there are three main learning-based approaches for CO: learning to configure algorithms (Kruber et al., 2017; Bonami et al., 2018), learning alongside the algorithms (Lodi & Zarpellon, 2017; Gasse et al., 2019; Chen & Tian, 2019; Kool et al., 2021), and learning to directly predict the solutions (Nowak et al., 2018; Emami & Ranka, 2018; Larsen et al., 2018). Neural combinatorial optimization (NCO) belongs to the last category where the training model directly predicts a good solution for a given problem instance. Vinyals et al. (2015) propose the pointer network to sequentially construct a solution for TSP problem. Bello et al. (2017) make a critical improvement to use reinforcement learning to train the model, eliminating the impractical optimal solutions collection for NP-hard problems. Further improvements on model structure and training procedure have been proposed in the past few years (Nazari et al., 2018; Deudon et al., 2018; Kool et al., 2019; Joshi et al., 2020), especially with graph neural networks (GNNs) (Dai et al., 2017; Li et al., 2018; Joshi et al., 2019; Dwivedi et al., 2020; Drori et al., 2020). Some works have recently been proposed to design more powerful training strategies, such as optimization with multiple optimum (Kwon et al., 2020), unsupervised learning (Karalias & Loukas, 2020) and curriculum learning schemes (Lisicki et al., 2020).
Neural MOCO. The current learning-based methods are mostly for solving single-objective combinatorial problems. Recently, a few attempts have been made to solve MOCO problems (Li et al., 2020; Wu et al., 2020; Zhang et al., 2021b;a). They first decompose a MOCO problem into multiple single-objective scalarized subproblems, and then build a set of models for each subproblem. 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. This work proposes a single preference-based model for solving MOCO problems, where the decision-makers can obtain arbitrary trade-off solutions. The proposed single neural MOCO solver could be much easier to use in a real-world system (Veličković & Blundell, 2021), rather than a large set of separate models. Our method’s model efficiency is crucial to truly extend the NCO approach to solve MOCO problems.

heading: 3 PROBLEM FORMULATION

heading: 3.1 MULTIOBJECTIVE COMBINATORIAL OPTIMIZATION
text: A multiobjective combinatorial optimization (MOCO) problem can be defined as follows:
min x∈X F (x) = (f1(x), f2(x), . . . , fm(x)), (1)
where X is a discrete search space, and F (x) = (f1(x), . . . , fm(x)) is an m-objective vector. Since the individual objectives often conflict with each other, no single solution can optimize all of them at the same time. Thus, practitioners are interested in Pareto optimal solutions, defined as follows.
Definition 1 (Pareto Dominance). Let xa, xb ∈ X , xa is said to dominate xb (xa ≺ xb) if and only if fi(xa) ≤ fi(xb),∀i ∈ {1, ...,m} and fj(xa) < fj(xb),∃j ∈ {1, ...,m}. Definition 2 (Pareto Optimality). A solution x∗ ∈ X is a Pareto optimal solution if there does not exist x̂ ∈ X such that x̂ ≺ x∗. The set of all the Pareto 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. For many MOCO problems, the size of Pareto set would be exponentially large with respect to the input size (e.g., nodes in MOTSP), which makes finding the whole Pareto set intractable (Herzel et al., 2021). Therefore, the current heuristic-based and learning-based methods all focus on finding a small subset of approximate Pareto solutions {x1, x2, · · · , xp} (e.g., p = 101). The decision-makers can only select solutions from this fixed small set, which is unlikely to contain their preferred solutions precisely.

heading: 3.2 PREFERENCE-BASED SCALARIZATION
text: Preference-based scalarization is a widely-used approach to solve MOCO problems (Ehrgott, 2005). It decomposes a given multiobjective problem into several subproblems with different preferences. By solving all subproblems, we can obtain a set of approximated Pareto solutions. For an mobjective problems, we can define a preference vector λ ∈ Rm satisfies λi ≥ 0 and ∑m i=1 λi = 1 such that λi is the preference for the i-th objective.
Weight-Sum Scalarization is the most straightforward approach:
min x∈X gws(x|λ) = min x∈X
∑m i=1 λifi(x), (2)
where gws(x|λ) is a single-objective subproblem with preference λ. The decision-makers can assign their preferences among the objectives, and obtain different subproblems. However, the weightedsum method can only find solutions on the convex hull of the Pareto set (Ehrgott, 2005).
Weighted-Tchebycheff (Weighted-TCH) Scalarization is an alternative:
min x∈X gtch(x|λ) = min x∈X max 1≤i≤m {λi|fi(x)− (z∗i − ε)|}, (3)
where z∗i is the ideal value for objective fi(x) (e.g., the lower bound), and u ∗ i = z ∗ i − ε is a utopia value with small positive component ε. According to Choo & Atkins (1983), any Pareto optimal solution could be an optimal solution of problem (3) with a specific (but unknown) preference λ. To find the whole Pareto set, it still needs to solve an exponentially huge number of subproblems.
Drawbacks and Remarks. Although the scalarization methods are straightforward, some critical drawbacks cannot be ignored. First of all, not all scalarized multiobjective problem is the same as its single-objective version (Ehrgott, 2005). For MOTSP, each weight-sum scalarized subproblem is a single objective TSP so that a powerful TSP solver can solve it. However, it is not the case for MOCVRP. Secondly, although the Tchebycheff scalarization has good properties, it involves min-max optimization, which is typically different from the original problem. For example, the Tchebycheff scalarized MOTSP is not a single-objective TSP and cannot be solved by the state-ofthe-art single-objective solver developed in the current years. In our reinforcement learning based framework, we use the Tchebycheff scalarization to combine the rewards of different objectives. It is much more flexible to use, and does not have to consider the problem-specific condition.

heading: 3.3 OUR METHOD
text: In this work, instead of finding a finite set {x1, x2, · · · , xp} as in the current MOCO methods, we propose a novel way to approximate the whole Pareto set {x(λ)| ∑m i=1 λi = 1} with infinite tradeoff preferences via a single model. With our method, the decision-makers can easily obtain any solutions on the approximate Pareto set with their preferred trade-offs as shown in Figure 2. That is, our method provides the decision-makers a much more flexible control on the Pareto set. In this work, we mainly consider learning the whole Pareto front. It is also possible to incorporate the decision-maker’s preference on specific regions for model building and inference as discussed in Appendix D.5. We believe this is a novel and principled way to solve multiobjective combinatorial optimization problems.

heading: 4 THE PROPOSED MODEL: PREFERENCE-CONDITIONED NEURAL MOCO

heading: 4.1 PREFERENCE-CONDITIONED SOLUTION CONSTRUCTION
text: The preference-based scalarization approach provides a connection between the preferences and the Pareto solutions. We build a preference-based neural network to solve the MOCO problems. We use the multiobjective traveling salesman problem (MOTSP) to motivate our model design, similar to using TSP in previous single-objective work (Bello et al., 2017; Kool et al., 2019; Joshi et al., 2020). In MOTSP, a problem instance s is a fully connected graph containing n nodes (cities), with multiple costs on each edge. A valid solution (tour) π = (π1, · · · , πt, · · · , πn), πt ∈ {1, · · · , n} is a permutation of all the nodes where πt 6= π′t,∀t 6= t′. Our model defines a preference-conditioned stochastic policy pθ(λ)(π|s) parameterized by θ(λ) to construct a valid solution in sequence:
pθ(λ)(π|s) = ∏n t=1 pθ(λ)(πt|s,π1:t−1). (4)
The goal is to learn an optimal preference-conditioned policy pθ(λ)(π|s) to construct tours with low scalarized costs for each preference λ.

heading: 4.2 THE PROPOSED MODEL
text: In this work, we propose a preference-conditioned encoder-decoder model as shown in Figure 3, with the Attention Model (AM) (Kool et al., 2019) as our basic model. For the MOCO problems and settings considered in this work, a preference-agnostic encoder is capable to transfer the problem instance into embeddings (e.g., embedding for all cities) used by the preference-conditioned decoder. In our model, only the decoder’s parameters θdecoder(λ) are conditioned on the preference λ:
θ(λ) = [θencoder,θdecoder(λ)]. (5)
Preference-agnostic Encoder. The encoder takes a problem instance s (e.g., an MOTSP instance with n cities) as input, and outputs a set of d-dimensional node embeddings {h1, · · · ,hn} for each city, along with an aggregated embedding h̄(G) = ∑n i=1 hi. For a given instance, the same embeddings can be used multiple times 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. (2019) for all preferences.
Preference-based Attention Decoder. The decoder has the same structure as in the attention-based model (Kool et al., 2019), but with parameters θdecoder(λ) = [WC(λ),WQ(λ),WK(λ),WMHA(λ)] conditioned on the preference λ. It takes the nodes and aggregated embeddings for all cities as input, and sequentially selects the next node πt with probability pθ(λ)(πt|s,π1:t−1).
At time step t, the decoder first constructs a context embedding ĥ(C) = WC(λ)[h̄(G),hπ1 ,hπt−1 ] from the aggregated embedding h̄(G) = ∑n i=1 hi, the first selected node hπ1 , and the last selected node hπt−1 . The matrix WC(λ) ∈ Rd×3d projects the concatenated 3d-dimensional vector to a d-dimensional vector. Then we further aggregate the context embedding via a Multi-Head Attention (MHA) (Vaswani et al., 2017) with the embeddings for all cities {h1, · · · ,hn}:
h(C) = MHA(Q = ĥ(C),K = {h1, · · · ,hn}, V = {h1, · · · ,hn}|WMHA(λ)), (6)
where Q,K, V are the query, key and value for MHA, and WMHA(λ) represents the MHA parameters. The context embedding h(C) contains all information for the problem instance and the current partial tour at step t. Then we can calculate the logit for selecting each city with its embedding hj :
logitj =
{ C · tanh( (WQ(λ)h(C))
T (WQ(λ)hj)√ d ) if j 6= πt′ ∀t′ < t −∞ otherwise.
(7)
All already visited cities are masked with −∞ and will not be selected as the next city. The logits of the rest cities are clipped into [−C,C] (C = 10) as in the AM model (Kool et al., 2019). The probability for choosing the j-th city at time step t can be calculated as pθ(λ)(πt = j|s,π1:t−1) = elogitj/ ∑ k e logitk . With this probability, the decoder can construct a valid tour in sequence.
One designing choice left is how to generate the preference-conditioned parameters θdecoder(λ). 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., 2021). We use a simple MLP hypernetwork θdecoder(λ) = MLP(λ|ψ) to generate the decoder parameters conditioned on the preference. The details of our proposed model can be found in Appendix B.
Algorithm 1 Neural MOCO Training 1: Input: preference distribution Λ, 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 θ 3: for t = 1 to T do 4: λk ∼ SamplePreference(Λ) ∀k ∈ {1, · · · ,K} 5: si ∼ SampleInstance(S) ∀i ∈ {1, · · · , B} 6: πjki ∼ SampleTour(pθ(λk)(·|si)) ∀k, i ∀j ∈ {1, · · · , N} 7: b(si|λk)← 1N ∑N j=1 L(π j ki|λk, si) ∀k ∈ {1, · · · ,K} ∀i ∈ {1, · · · , B}
8: ∇J (θ)← 1KBN ∑K k=1 ∑B i=1 ∑N j=1[(L(π j ki|λk, si)− b(si|λk))∇θ(λk) log pθ(λk)(π j ki|si)]
9: θ ← ADAM(θ,∇J (θ)) 10: end for 11: Output: The model parameter θ
Instance Augmentation for MOCO. The model we propose only has a small computational and memory overhead to the original single-objective AM solver. We keep our model as simple as possible, which makes it easily compatible with other models and improvements that are originally developed for single-objective NCO. These properties are crucial to truly generalize the NCO to deal with multiobjective problems. In this work, we extend the instance augmentation method (Kwon et al., 2020) for solving MOCO, of which the details are discussed in the Appendix B.1.

heading: 5 PREFERENCE-CONDITIONED MULTIOBJECTIVE POLICY OPTIMIZATION

heading: 5.1 COST FUNCTION
text: The proposed node selection strategy guarantees that the model can always generate feasible solutions. In this section, we develop an efficient multiobjective policy optimization method to train the model for different preferences simultaneously. For an MOTSP problem, the objective functions are a vector of m different costs for a tour L(π) = [L1(π), · · · , Lm(π)]. We can define a weighted-Tchebycheff scalarized cost for each preference λ:
L(π|λ) = max 1≤i≤m {λi|Li(π)− (z∗i − ε)|}, (8)
where z∗i is the ideal value for the i-th cost. This method can be easily adapted for the weighted-sum scalarization. For a given instance s, our goal is to minimize the expected cost for all preferences:
J (θ|s) = Eλ∼Λ,π∼pθ(λ)(·|s)L(π|λ), (9) where Λ is the distribution for the preference λ. To train the model, we repeatedly sample different instances s ∼ S at each iteration, so we can define the training loss as J (θ) = Es∼SJ (θ|s).

heading: 5.2 MULTIOBJECTIVE REINFORCE
text: For a given instance s and a specific preference λ, we use the REINFORCE (Williams, 1992) to estimate the gradient for the preference-conditioned scalar cost:
∇J (θ|λ, s) = Eπ∼pθ(λ)(·|s)[(L(π|λ, s)− b(s|λ))∇θ(λ) log pθ(λ)(π|s)], (10) where b(s|λ) is the baseline of expected cost to reduce the gradient variance. This gradient is estimated by Monte Carlo sampling. At each update step, we randomly sample K preference {λ1, · · · , λK} ∼ Λ, B instances {s1, · · · , sB} ∼ S, and N different tour {π1i , · · · ,πNi } ∼ pθ(λk)(·|si) for each λk-si combination. The approximated gradient is:
∇J (θ) ≈ 1 KBN K∑ k=1 B∑ i=1 N∑ j=1 [(L(πji |λk, si)− b(si|λk))∇θ(λk) log pθ(λk)(π j i |si)]. (11)
In this work, we use the shared baseline bshared(si|λk) = 1N ∑N j=1 L(π j ki|λk, si) over N sampled tours for each λk−si combination. The starting node for each tour πjki is chosen in random to force diverse rollouts as proposed in (Kwon et al., 2020). The algorithm is shown in Algorithm 1.

heading: 5.3 ACTIVE ADAPTION
text: We also propose a simple yet powerful active adaption approach to further adjust the whole model to approximate the Pareto front for a given test instance in Appendix B.3. The proposed method does not depend on specific instance distribution S, and is suitable for out-of-distribution adaption.

heading: 6 APPROXIMATION ABILITY
text: It is hard to give a convergence guarantee for MOCO, where each preference-based subproblem could be already NP-hard, and the number of Pareto solutions is exponentially large with respect to the input size. Similar to the single-objective NCO (Vinyals et al., 2015; Bello et al., 2017; Kool et al., 2019), our method can not guarantee to find the exact Pareto set for a MOCO problem. Instead, inspired from the approximation methods for MOCO (Herzel et al., 2021), we give an εPareto approximation guarantee on the whole Pareto set conditioned on the model’s learning ability:
Theorem 1. Let x∗λ denote the optimal solution of the problem (3) with preference λ, if our proposed model can generate an approximate solution xλ ε-dominate x∗λ for any preference λ, it is able to generate an ε-approximate Pareto set Pε to the MOCO problem (1). The detailed definitions, proofs, and further analyses are given in Appendix A.

heading: 7 EXPERIMENTS
text: Problems and Model Setting. We consider MOTSP (Lust & Teghem, 2010a), MOCVRP (Lacomme et al., 2006) and MOKP (Bazgan et al., 2009) in this work, and use the same model settings for all problems with task-specific input size and mask method. 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 η = 10−4 and weight decay 10−6. We train our models on a single RTX 2080-Ti GPU, and it costs about 10 minutes for an epoch on MOTSP100. We put detailed model settings, problem formulations, and more experimental results in Appendix BCD. Our code will be released open-source upon publication.
Baseline. We compare our proposed method with three widely-used algorithm frameworks for solving MOCO problems: 1) MOGLS (Jaszkiewicz, 2002) is a multiobjective genetic local search algorithm, 2) NSGAII (Deb et al., 2002) is a Pareto dominance-based multiobjective genetic algorithm, and 3) MOEA/D (Zhang & Li, 2007) is a decomposition-based multiobjective evolutionary algorithm. These algorithm frameworks all need problem-specific heuristics to solve different problems. We also report the performance for learning-based methods: 4) DRL-MOA (Li et al., 2020) decomposes a MOCO with different preferences and builds a Pointer Network (Vinyals et al., 2015; Bello et al., 2017) to solve each subproblem. 5) AM-MOCO is a multi-models variant of our proposed model, which builds Attention Model (Kool et al., 2019) for each subproblem. We call our proposed model 6) P-MOCO as for preference-conditioned multiobjective combinatorial optimization. 7) The Weight-Sum scalarization of MOTSP and MOKP are equal to their single-objective counterpart. Therefore, we also compare with the competitive approach that uses state-of-the-art single-objective solvers to solve each weight-sum subproblem.
Model Information for the learning-based methods is shown in Table 1. Our model supports flexible preference assignment and only has 1.1% total parameters to the multiple-model 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 for each problem, and up
to 10, 011 solutions for our proposed method. In most cases, we report our model’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. The hypervolume of a set is the volume in the objective space it dominates. For a set P ⊂ Rm 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:
S = {r ∈ Rm | ∃ y ∈ P such that y ≺ r ≺ r∗}, (12)
where HV(P ) = Vol(S). A higher hypervolume means the solution set has better performance, and 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 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.1.

heading: 7.1 RESULTS AND ANALYSIS
text: MOTSP. The results on two and three objective MOTSP are shown in Table 2 and Table 3 respectively. MOGLS, NSGAII and MOEA/D all use 2-opt local search heuristic (Jaszkiewicz, 2002) to search for promising solutions. We also include two weight-sum scalarization baselines with the state-of-the-art LKH solver (Helsgaun, 2000; Tinós et al., 2018) and Google OR tools (Perron & Furnon, 2019). For the two-objective problems, our proposed method has similar performance to
AM-MOCO in all problems only with a single model. It achieves the best performance with instance augmentation, which significantly outperforms other methods but is beaten by the strong LKH solver on the MOTSP100 comparison. For the three objective problems, our method can further improve its performance by generating much more trade-off solutions within a reasonable time, which is not supported by other methods. As shown in Figure 2 and Figure 5, our method has a uniform mapping from the preferences to the corresponding solutions, and can generate a dense prediction to the whole Pareto front. Decision-makers can easily obtain any preferred trade-off solutions as they want. This flexibility could be crucial and desirable for many real-world applications.
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 conflicting objectives we consider are to minimize the tour length for all routes and also the tour length for the longest routes (the makespan in scheduling theory) (Lacomme et al., 2006). All the non-learning algorithm frameworks use the problem-specific constructive heuristics and local search method proposed in Lacomme et al. (2006) to search valid non-dominated solutions. The results in Table 2 show that our method significantly outperforms the non-learning heuristics both in solution quality and running time. It also outperforms AM-MOCO with 100 individual models, which might occur 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 applications (Bazgan et al., 2009). We consider the uni-dimension problem, where each item has multiple 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 exact dynamic programming (DP) and the strong greedy search based on the value-weight ratio. According to the results in Table 2, our method has the best performance for all problems. The DP method is also outperformed since the weight-sum scalarization can only find the convex hull of the Pareto front. The Tchebycheff scalarization of MOKP is not a KP problem, while our method is more flexible to use Tchebycheff scalarization on the reward function. We also report the zero-shot generalization results to problems with up to 10 objectives and 500 items in Appendix D.7.
Out-of-Distribution Problems and Active Adaption. We also validate our method’s generalization performance on 6 out-of-distribution (OOD) MOTSP problem from Fonseca et al. (2006), which have exact Pareto fronts by costly exhaustive search. The results are shown in Appendix D.2 due to page limit. With active adaption, our method can achieve good performance (1% - 1.5% HV gap to exact Pareto fronts) on these OOD problems.

heading: 8 CONCLUSION
text: In this paper, we propose a novel preference-conditioned method to approximate the whole Pareto front for MOCO problems with a single model. It 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. Experiments on different problems confirm that our proposed method can significantly outperform other methods in performance, speed and model efficiency.

heading: A PARETO SET LEARNING AND APPROXIMATION ANALYSIS

heading: A.1 PARETO SET LEARNING AND CONVERGENCE GUARANTEE
text: In this work, we propose a novel neural combinatorial optimization (NCO) method to approximate the whole Pareto set for MOCO problems with a single model. The proposed learning-based MOCO solver can directly generate arbitrary trade-off solutions without extra optimization. We believe it is a principled way to solve MOCO problems.
As briefly discussed in the main paper, however, the lack of an exact optimality guarantee is a limitation of the proposed method, which is also the case for previous work on single-objective neural combinatorial optimization (Vinyals et al., 2015; Bello et al., 2017; Kool et al., 2019). This limitation is mainly due to the fact that many single-objective combinatorial optimization (CO) problems are NP-hard, and the size of Pareto sets for a 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 to fit all training problems perfectly. The generalization ability to problem instances with different patterns (out-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 corresponding approximate set of the Pareto optimal solutions. It provides a flexible way for decisionmakers 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 approximation ability of our proposed method.

heading: A.2 APPROXIMATION ANALYSIS
text: For a MOCO problem, the number of Pareto solutions could be exponentially large with respect to its input size, which makes the problem intractable (Ehrgott, 2005; Herzel et al., 2021). The preference-based scalarization method (Choo & Atkins, 1983; Zhang & Li, 2007) we used provides a principled way to link the Pareto solutions with preference, allowing us to tackle the problem in a systematic manner. In this work, we propose to approximately solve the scalarized subproblem with all preferences via a 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 a MOCO problem into preference-based subproblems with the weighted-Tchebycheff scalarization (Weighted-TCH):
min x∈X gtch(x|λ) = min x∈X max 1≤i≤m {λi|fi(x)− (z∗i − ε)|}, (13)
where z∗i is the ideal value for objective fi(x) (e.g., the lower bound), and u ∗ i = z ∗ i − ε is a utopia value with small positive component ε. The preference vector λ ∈ Rm satisfies λi ≥ 0 and ∑m i=1 λi = 1, where λi is the preference for the i-th objective. This approach has a desirable property:
Lemma 1 (Choo & Atkins (1983)). A feasible solution x ∈ X is Pareto optimal if and only if there is a weight vector λ > 0 such that x is an optimal solution to the problem (13).
According to Lemma 1, we can obtain any Pareto solution by solving the Weighted-TCH subproblem with a specific weight. However, the weight for each Pareto solution depends on its objective values, which are not known in advance (Sawaragi et al., 1985; Ehrgott, 2005). The decision-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 s, our proposed model provides a single mapping function xλ = h(λ) from any preference λ to its corresponding solution xλ, which is constructed by the preferencebased policy pθ(λ)(x|s). In the ideal case, if all generated solutions xλ are the optimal solutions x∗λ of problem (13) with preference λ, according to Lemma 1, 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 approximation ability. We find that its performance strongly depends on the approximation ability of the parameterized policy (neural network 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. If the proposed method can approximately solve the subproblem (13) with any preference λ, it can generate a good approximation to the whole Pareto set for the MOCO problem.
To support this claim, we follow the traditional ε-Pareto approximate method for MOCO problems (Papadimitriou & Yannakakis, 2000; Herzel et al., 2021). First, an ε-Pareto domination relation between two individual solutions can be defined as:
Definition 3 (ε-Pareto Domination). For a MOCO problem and an ε > 0, let xa, xb ∈ X , xa is said to ε-dominate xb (xa ≺ε xb) if fi(xa) ≤ (1 + ε)fi(xb),∀i ∈ {1, · · · ,m}. This definition is a natural generalization from the (1 + ε)-approximation for single-objective optimization. With this concept, an ε-approximate Pareto set (Papadimitriou & Yannakakis, 2000) can be defined as:
Definition 4 (ε-Approximate Pareto Set). For an ε > 0, a set Pε ⊂ X is an ε-approximate Pareto set, if for any feasible solution x ∈ X , there exists a solution x′ ∈ Pε such that x′ ≺ε x. In other words, all feasible solutions of the MOCO problem can be almost dominated by some solutions in Pε (Papadimitriou & Yannakakis, 2000). When the Pareto set is intractable and hard to find, the ε-approximate Pareto set would be a reasonable choice to achieve in practice. Each MOCO problem has a unique Pareto set, but can have different ε-approximate Pareto sets. The ability of our proposed method to find an ε-approximate Pareto set strongly depends on its performance on each single-objective preference-based subproblem.
Theorem 1. Let x∗λ denotes the optimal solution of the problem (13) with preference λ, if the proposed method can generate an approximate solution xλ ≺ε x∗λ for any preference λ, it is able to generate an ε-approximate Pareto set Pε to the MOCO problem.
Proof. Let P be the Pareto set for a MOCO problem, for any xPareto ∈ P , according to Lemma 1, there is a weight vector λ > 0 such that x = x∗λ is the optimal solution for subproblem (13) with a specific preference λ. Therefore, our proposed method can generate an approximated solution xλ ≺ε x∗λ = xPareto. By generating approximate solutions for all xPareto ∈ P , our proposed method is able to generate an ε-approximate Pareto set Pε to the MOCO problem.

heading: A.3 LIMITATION
text: Strong Assumption on (Approximately) Solving all Subproblems: The approximation guarantee in Theorem 1 heavily depends on the ability to (approximately) solve each weighted subproblem. Due to the NP-harness, it is indeed non-trivial to give a convergence guarantee to generate ε-dominate solutions for any preference with a small enough ε. 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 problem in recent works (Cappart et al., 2021b; Kool et al., 2021). These methods provide a controllable trade-off between the solution quality and the computational cost for solving NP-hard problems.
However, their generalization to the multi-objective problem is not straightforward, since the scalarized subproblem for each preference is not necessary the same as its single-objective counterpart. For example, a Tchebycheff scalarized MOTSP is not a 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 predict the solutions (neural combinatorial optimization). Therefore, the idea for learning enhanced multiobjective combinatorial algorithm could be an important research topic in future, but out 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 ε-approximate Pareto set Pε. If the required number is exponential to the input size, the approximation itself is also intractable. In their seminal work, Papadimitriou & Yannakakis (2000) establish a promising result:
Theorem 2 (Papadimitriou & Yannakakis (2000)). For any multiobjective optimization problem and any ε, there is an ε-approximate Pareto set Pε of which the size is polynomial in the number of solutions and 1ε (but exponential in the number of objectives).
However, the existence of such a set still does not mean that it can be easily found (Papadimitriou & Yannakakis, 2000; Herzel et al., 2021). The computability (whether Pε can be constructed in polynomial time) would be hard to justify for a real-world problem. For a new unseen problem instance in practice, our proposed method might still need to generate an exponentially large number of solutions to construct an ε-approximate Pareto set Pε. It is also unclear how to properly select a 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 al., 2021; Hansen, 1980; Papadimitriou & Yannakakis, 2000; Vassilvitskii & Yannakakis, 2005; Koltun & Papadimitriou, 2005; Bazgan et al., 2017). In future work, it is important to better leverage the current advanced approximation strategies to design more efficient preference-based methods. In the learning-based optimization scenario we consider, it is also possible to learn the suitable approximation method and/or preference distribution directly from the data (problem instances).

heading: B DETAILS ON THE PROPOSED MODEL

heading: B.1 MODEL SETTING
text: We use the same model for all MOCO problems while tuning the input size and mask method for each problem. Table 4 shows the number of parameters of a standard single-objective attention model (Kool et al., 2019) and our proposed preference-based multiobjective attention model. Our model supports flexible preference assignment at 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 et al. (2020).
Attention Encoder. The encoder we use is the standard attention encoder as in Kool et al. (2019), 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 one 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-Conditioned Decoder. The decoder’s main model structure is the same as 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 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-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-dimensional preference vector λ which satisfies λi ≥ 0 and ∑m i=1 λi = 1, where m is the number of objectives and λi 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 a hidden embedding e(λ) = MLP(λ|ψ), then maps the hidden embedding to the decoder parameters via linear projection θdecoder = We(λ) + b. The learnable parameters are ψ for the MLP model MLP(λ|ψ) and the parameter matrices W and b for the decoder. Training Procedure. For all problems, we train our 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 to calculate the policy gradient. We set K×B = 64 to make the batch of 64 instances for training a single AM model, and letN equal to the problem size (e.g., the number of nodes) as in Kwon et al. (2020). We find the model performance is equally good for setting K = 1, 2 and 4, and keep using K = 1 for all problems.
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 a single AM model with a single preference on one objective from scratch with 200 epochs, then transfer its parameter to the model for neighbor subproblem with similar preference, and fine-tune the new model with 5 epochs. With sequentially transfer and fine-tune, we can obtain a set of trained models for different preferences. In most experiments, we set the number of preferences as 101. Therefore, we need to build 101 AM models with total 700 training epochs.
Instance Augmentation for MOCO: Due to the design choice of minimal essential change (e.g., the preference-conditioned 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 et al. (2020) to the MOCO version.
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) solutions. In this way, we have a more robust result similar to the test-time augmentation for computer vision (Szegedy et al., 2016). For the single-objective euclidean TSP and CVRP, there is a set of straightforward transformations, which simply flips or rotates the coordinate for all the 2D locations in a problem instance (Kwon et al., 2020). For a location (x, y), there is eight different transformation, namely, {(x, y), (y, x), (x, 1−y), (y, 1−x), (1−x, y), (1−y, x), (1−x, 1−y), (1−y, 1−x)}. For an m-objective euclidean MOTSP problem, the concrete location representations are independent 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 8m 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.

heading: B.2 TRAINING EFFICIENCY
text: 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., 2020). 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.
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-based solver, the results are shown in Table 5. The results of Concorde/LKH/OR Tools are from Kwon et al. (2020), and we run the learning-based solver by ourselves. We report the average performance over 10, 000 test instances. AM is the single-objective solver (one model in AM-MOCO), P-MOCO (single preference) is our proposed model but only training on a 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.
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 a positive knowledge transfer among preferences during the learning procedure. In addition, it also confirms the assumption that similar preferences should have similar corresponding (approximate) Pareto solutions for the multiobjective problems we consider in this paper. These findings could be useful to design more powerful learning-based models for MOCO in the future.

heading: B.3 ACTIVE ADAPTION
text: 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 a 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 as sampling and beam search, can further improve the performance for a single solution or single preference (Joshi et al., 2020). However, these approaches can not find a better approximation to the whole Pareto set for a MOCO problem.
Algorithm 2 Neural MOCO Active Adaption 1: Input: model parameter θ, instance s, preference distribution Λ, number of adaption steps T ,
number of preferences per iteration K, number of tours N 2: for t = 1 to T do 3: λk ∼ SamplePreference(Λ) ∀k ∈ {1, · · · ,K} 4: πjk ∼ SampleTour(pθ(λk)(·|s)) ∀k ∈ {1, · · · ,K} ∀j ∈ {1, · · · , N} 5: b(s|λk)← 1N ∑N j=1 L(π j k|λk, s) ∀k ∈ {1, · · · ,K}
6: ∇J (θ)← 1KN ∑N j=1[(L(π j k|λk, s)− b(s|λk))∇θ(λk) log pθ(λk)(π j k|s)] 7: θ ← ADAM(θ,∇J (θ)) 8: end for 9: Output: The model parameter θ
We propose a simple yet powerful active adaption approach as shown in Algorithm 2. It iteratively adapts the model parameter θ(λ) to a given instance s (or a batch of instances) with all preferences from the distribution Λ rather than searching for a specific solution. This method is similar to the active search in Bello et al. (2017) which actively refines the single-objective model for efficient candidate solutions searching. Our approach focuses on adapting the whole model for a better Pareto front approximation. Since this method is distribution-agnostic (not depend on specific instance distribution S), it is suitable for out-of-distribution adaption.

heading: C DETAILS OF THE MOCO PROBLEMS
text: This section introduces the detailed problem formulation for the MOTSP, MOCVRP and MOKP we used in this work. We also provide the model configuration (e.g., input size, masks) for each problem.

heading: C.1 MOTSP
text: 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 et al., 2017; Kool et al., 2019). A general m-objective MOTSP instance s with n nodes has m n × n cost matrices {Ci = (cijk), i = 1, · · · ,m} for m different costs. The problem is to find a tour (cyclic permutation π) to minimize all the costs:
minL(π|s) = min(L1(π|s), L2(π|s), · · · , Lm(π|s)),
where Li(π|s) = ciπ(n)π(1) + n−1∑ j=1 ciπ(j)π(j+1). (14)
In a Euclidean MOTSP, the cost information is stored in the nodes rather than the edges. The j-th node has a 2m-dimensional vector [x1j ,x 2 j , · · · ,xmj ] where xij ∈ R2 is a 2D coordinate for the i-th objective. The i-th cost cijk = ||xij − xik||2 is the Euclidean distance for moving from node j to k.
If we only have one objective m = 1, it reduces to the single-objective 2D Euclidean TSP:
min π L1(π|s) = ||xπ(n) − xπ(1)||2 + n−1∑ j=1 ||xπ(i) − xπ(i+1)||2. (15)
The single-objective TSP is already NP-hard, so does the MOTSP. In 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 on single-objective NCO (Lust & Teghem, 2010b; Florios & Mavrotas, 2014), we randomly sample all n nodes with uniform distribution on the 2mdimensional unit hyper-square (e.g., [0, 1]2m) for all problem instances.
Model Details. In m-objective MOTSP, each node has a 2m-dimensional vector to store all 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 a valid tour when all node is selected (we assume the end node will connect to the start node).

heading: C.2 MOCVRP
text: 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 δi needed to be satisfied. There is an extra depot node and a vehicle with a fixed capacity D > δi,∀i to handle all the demands. The vehicle will always start from the depot node, then goes to different cities to satisfy multiple demands ∑ δi ≤ D , and turns back to the depot node. A solution to this problem is a set of 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 in scheduling theory). This problem has been studied in the MOCO community (Lacomme et al., 2006).
Problem Instance. Similar to the TSP problem, the location of n nodes are uniformly sampled from the unit square. For the demand, similar to the previous work on the single-objective counterpart (Kool et al., 2019; Kwon et al., 2020), we randomly sample discrete δi from the set {1, · · · , 9}. For problem with size n = 20, 50, 100, we set the capacity as D20 = 30, D50 = 40
and D100 = 50, respectively. Without loss of generality, we normalize the demands δ̂i = δiD and capacity D̂ = DD = 1 as in the previous work (Kool et al., 2019; Kwon et al., 2020). Split delivery is not allowed in this problem.
Model Details. In the MOCVRP, the depot node has a 2-dimensional location vector, and the other nodes all have 3-dimensional vectors to store their locations and demands. We use different parameter matrices to project the nodes into the input embedding with the same dimension dh = 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, it will be masked as unavailable for the vehicle to visit. If no node is available to visit, the vehicle will go back to the depot. Once all nodes have 0 demands, the node selection is finished and we have a valid solution to the problem.

heading: C.3 MOKP
text: Knapsack problem (KP) is also a 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) = max(f1(x), f2(x), · · · , fm(x)), where fi(x) = ∑n j=1 v i jxj ,
subject to ∑n j=1 wjxj ≤W, xj ∈ {0, 1},
(16)
where each item has a weight wj and m different values {vij , i = 1, · · · ,m}. The problem (e.g., knapsack) has a 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 vij ,∀i, j, weights wj∀j and the total capacity are non-negative real value. The total weight of all items is larger than the capacity ∑ wi > W , while each single weight is smaller than the capacity wi < W, ∀i = 1, · · · , n. The single-objective knapsack problem is NP-hard, so does the MOKP problem (Ehrgott & Gandibleux, 2003).
Problem Instance. We randomly generate the values and weight for each item both uniformly in [0, 1]. We consider problems with n = 50, 100, 200 nodes, and the weight capacities are W50 = 12.5,W100 = W200 = 25 as in the previous work (Bello et al., 2017; Kwon et al., 2020).
Model Details. In an m-objective MOKP, each item has m values and 1 weight, so the input dimension is 3 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.

heading: D ADDITIONAL EXPERIMENTAL RESULTS
text: D.1 HYPERVOLUME INDICATOR
To solve a MOCO problem, the result for each method is a 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 a set is the volume in the objective space it dominates. For a set P ⊂ Rm 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 the volume of the set:
S = {r ∈ Rm | ∃y ∈ P such that y ≺ r ≺ r∗}, (17)
where HV(P ) = Vol(S). An illustration example is shown in Figure 4. The grey area is the set S dominated by the solutions in set P = {p1, p2, p3, p4} with the reference point r∗. In 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., 2007). First, if an approximate set A dominates another approximate setB, it will have a 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. In 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 problems. We report the normalized hypervolume values Ĥ(P ) = HV(P )/ ∏m i r ∗ i for all methods and also their performance gaps to our method. For each experiment, all methods share the same reference point r∗, which contains the largest value achieved for each objective. Since all problems we consider have positive objective values, we have 0 ≤ Ĥ(P ) ≤ 1 for all solution sets. The ground truth Pareto set P ∗ usually has Ĥ(P ∗) < 1, unless the zero vector 0 ∈ Rm is feasible and in the Pareto set.

heading: D.2 OUT-OF-DISTRIBUTION PROBLEM WITH EXACT PARETO FRONT
text: We conduct experiments on 6 two-objective MOTSP100 instance (L1-L6) 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 in the Table 6.
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 of 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 a good performance on these out-of-distribution (OOD) instances with a 1%− 1.5% hypervolume gap. The proposed method also significantly outperforms the weight-sum OR tools baseline. There is still a gap to the strong weight-sum LKH baseline. As discussed in the paper, robust OOD generalization is an important research direction for the learning-based solver.

heading: D.3 FLEXIBLE PREFERENCE-BASED APPROXIMATION
text: With our model, it is flexible to generate different number of solutions to approximate the Pareto front. We present an example on the three-objective TSP in Figure 5. We use the structured weight assignment approach from Das & Dennis (1998) to give the sets of weights for different instances. This method can generate n = Cm+p−1p evenly distributed weights with an identical distance to their nearest neighbor on the unit simplex (e.g., ∑m i=1 λi = 1 with λi ≥ 0,∀i), where m is the number of objectives and p is a parameter to control the number of weights.
For the three objective TSP problems (m = 3), we assign p = 13, 44 and 140 to generate n = 105, 1035 and 10011 weights respectively. We also show the corresponding generated solutions for MOTSP instances with 20, 50 and 100 cities. According to the results in Figure 5, our model can generate well-distributed solutions with a small number of preferences, and generate a 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 on the approximate front.

heading: D.4 PREFERENCE-SOLUTION CONNECTION
text: We further analyze the connection between the preference and its corresponding solution on the uniform and non-uniform Pareto front. Figure 6 shows the connections in our model with different numbers of preferences for the MOTSP100 instance. Since the two objectives (costs) in MOTSP have the same scale, this problem has a uniform connection between the preferences and the (approximate) 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 a non-uniform Pareto front. In this problem, we consider two different objectives to optimize, namely, the total tour length (objective 1) and the tour
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 MOCVRP100 instance. For MA-MOCO, we report the connections for all 101 models. For our proposed model, we report the connections with different numbers of uniform preferences.
In this problem, 101 models or our model with 101 uniform preferences are not enough to generate a dense approximate Pareto front. The obtained solutions are biased to the area that objective 1 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 a learning-based approach to select the preferences for a given problem instance. Preference adjustment and model adaption with awareness on the shape of Pareto front are also worthy to investigate. We left them to the future work.
In the MOCVRP instance, we also find the 101-model MA-MOCO has a worse performance compared 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 MAMOCO. 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 on the problem. When the training procedure is done, it dose not allow any preference adjustment without retraining the models.

heading: D.5 THREE-OBJECTIVE MOTSP WITH ASYMMETRIC PARETO FRONT
text: In this subsection, we conduct experiments on the three-objective MOTSP100 instances with asymmetric Pareto fronts. The definition of asymmetric MOTSP instance is almost the same as in Section C.1, except the coordinates for the three objectives and randomly sampled from [0, 1]2, [0, 0.5]2 and [0, 0.1]2 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 an asymmetric Pareto front (the axes in Figure 8 are in different scales).
A well-known drawback of the scalarization-based approach is that it cannot evenly explore the asymmetric Pareto front with a set of uniform weights, which can also be observed in Figure 8(a)(d). Our proposed approach allows the user to generate arbitrary trade-off Pareto solutions on the inference time, therefore they can directly generate a dense approximation and then select the preferred solutions as in Figure 8(d). This flexibility can partially address the unevenly distributed issues caused by a (small) set of fixed weights in the traditional scalarization-based approach.
If we know the approximate range of different objectives in advance, we can first normalize them into [0, 1] to encourage a more symmetric Pareto front. Otherwise, on the inference time, we can use a (prior knowledge-based) biased and non-uniform weight assignment to generate uniformly distributed solutions. In Figure 8(e)-(h), we first multiple the three-dimensional weights by (1, 2, 10) and then normalize them back to [0, 1]3 which leads to a set of non-uniform weights as shown in Figure 8(e). With this weight assignment, we have a a set of more evenly distributed Pareto solutions as shown in Figure 8(f)-(h).

heading: D.6 PREFERENCE-BASED INFERENCE
text: Even without any prior knowledge, our proposed approach allows the user to adaptively adjust the weights in real-time to search for the most suitable solutions in their preferred region(s). Some examples of selected weights and their corresponding solutions are shown in Figure 9 for symmetric Pareto front and Figure 10 for asymmetric Pareto front.
For the problem with a 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 to consider the connection between scalarization and hypervolume maximization as in Zhang & Golovin (2020). We believe this could be an important research topic for the learning-based scalarization approach in future work.

heading: D.7 PROBLEM WITH MORE OBJECTIVES
text: Finally, we test the performance of our proposed method on the 10-objective knapsack problems. The obtained value path plots on the 10-objective MOKP100 are shown in Figure 11. For problems with more objectives, we need a 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 is also not desirable in practice. Therefore, we do not compare with the AM-MOCO and MOA-DRL methods on this problem.
To approximate the Pareto set, each method generates 715 solutions with different trade-offs, so there are 715 different value paths (lines) on each plot. In MOKP, we want to maximize the values for all objectives under the capacity limitation. A set of good approximate solutions should have relatively high overall values. According to the results, our proposed method has the best performance. We also test the performance of our method on a larger problem with 500 items. The results shown in Figure 12 confirm that our trained model generalizes well to problems with a larger size.

Review summaries:
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.

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. 

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.