PaperlayerView exact revision on arXiv

Source-linked AI summary

Pareto Set Learning for Neural Multi-objective Combinatorial Optimization

Xi Lin, Zhiyuan Yang, Qingfu Zhang

arXiv:2203.15386v2cs.LGcs.NEmath.OC

TL;DR

MOCO can have exponentially many Pareto solutions, making exact solution difficult and handcrafted heuristics labor-intensive. This paper trains a single preference-conditioned model with multiobjective reinforcement learning to generate approximate solutions for different trade-offs. Experiments report improvements in solution quality, speed, and model efficiency across three MOCO problem types.

  • Problem

    Finding the exact Pareto set is challenging because individual solutions can be NP-hard to find, the set may grow exponentially, and handcrafted heuristics are problem-specific.

    Source: §1 · p. 1

  • Method

    A single preference-conditioned model directly generates approximate Pareto solutions, trained across preferences with an end-to-end multiobjective reinforcement-learning algorithm.

    Source: §1 · p. 2

  • Results

    The method significantly outperforms other methods in solution quality, speed, and model efficiency on MOTSP, MOVR, and MOKP.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The single-model approach handles all trade-off preferences, unlike finite-solution MOEA/D variants, and is presented as a promising alternative to finite-population methods.

    Source: §7 · p. 9

    A convergence guarantee is difficult because each preference-based subproblem may be NP-hard and the number of Pareto solutions may grow exponentially with input size.

    Source: §7 · p. 9

Abstract

from arXiv · show

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.

1 INTRODUCTION

MOCO problems can have exponentially many Pareto solutions, while preferences may be unknown and handcrafted heuristics are labor-intensive. The paper proposes one preference-conditioned model, trained with multiobjective reinforcement learning, to generate preferred trade-offs; experiments report gains across three problem types.

1 INTRODUCTION

  • Finding all exact Pareto solutions is difficult: individual solutions can be NP-hard to find, and the set can grow exponentially with problem size.Unknown decision-maker preferences also make reducing the problem to one objective difficult; specialized handcrafted heuristics can be labor-intensive.Source: §1 · p. 1
  • Learning from repeated instances is presented as a way to extend neural combinatorial optimization to MOCO problems.Source: §1 · p. 1
  • A single preference-conditioned model approximates the whole Pareto set and generates preferred trade-off solutions without search.The model is designed to support different preferences through the same model.Source: §1 · p. 2
  • An end-to-end reinforcement-learning algorithm trains the model across preferences, and active adaptation handles out-of-distribution instances.Source: §1 · p. 2
  • The method significantly outperforms other methods in solution quality, speed, and model efficiency on MOTSP, MOVR, and MOKP.The experiments cover different settings for these problems.Source: §1 · p. 2

2 BACKGROUND AND RELATED WORK

Prior MOCO approaches seek manageable approximate Pareto sets but typically require problem-specific handcrafted designs. Existing neural MOCO methods also use separate models for decomposed subproblems, motivating a single model that accommodates preferences.

Multiobjective Combinatorial Optimization

  • Exact MOCO methods may be prohibitively costly, while heuristics and approximation methods seek manageable approximate Pareto sets using problem-specific handcrafted designs.Source: §2 · p. 2

Machine Learning for Combinatorial Optimization

  • Neural combinatorial optimization directly predicts solutions for problem instances, and reinforcement learning avoids collecting optimal solutions for NP-hard problems.Source: §2 · p. 2

Neural MOCO

  • Existing neural MOCO methods decompose problems into single-objective subproblems and build separate models, whereas this work uses one preference-conditioned model for trade-offs.The passage notes that exponentially many Pareto solutions could require a huge number of models to approximate the whole set.Source: §2 · p. 3

3 PROBLEM FORMULATION

The section defines MOCO through conflicting objectives over a discrete search space, then reviews preference-based decomposition and its limits. It motivates approximating the whole Pareto set with a single model for interactive trade-off selection.

3.1 MULTIOBJECTIVE COMBINATORIAL OPTIMIZATION

  • MOCO minimizes an m-objective vector over a discrete search space, with conflicting objectives preventing one solution from optimizing them all simultaneously.Source: §3.1 · p. 3
  • A solution is Pareto optimal when no feasible solution dominates it; the Pareto set maps to the Pareto front in objective space.A Pareto solution cannot improve one objective without worsening another.Source: §3.1 · p. 3

3.2 DECOMPOSITION AND PREFERENCE-BASED SCALARIZATION

  • Decomposition assigns preference vectors to subproblems, and MOEA/D-style methods collaboratively generate a finite approximation to the Pareto front.Source: §3.2 · p. 3
  • Weighted-sum aggregation minimizes a preference-weighted combination of the objective values for each subproblem.Source: §3.2 · p. 3
  • Weighted-sum scalarization can find solutions only on the convex hull of the Pareto front.Source: §3.2 · p. 3
  • A specific, unknown preference vector can make any Pareto optimal solution optimal for the corresponding scalarized problem.Source: §3.2 · p. 3

3.3 CURRENT DRAWBACKS AND OUR METHOD

  • Existing methods return small approximate subsets that may omit a decision-maker’s preferred solution, and scalarization can create subproblems incompatible with specialized solvers.For MOTSP, the Tchebycheff subproblem is not a classic TSP and cannot use specialized solvers such as LKH or Concorde.Source: §3.3 · p. 4
  • The proposed single model approximates the whole Pareto set for real-time preference-based selection, supporting interactive decision making.The paper mainly considers learning the whole Pareto front, while preference-specific regions could also be incorporated.Source: §3.3 · p. 4

4 THE PROPOSED MODEL: PREFERENCE-CONDITIONED NEURAL MOCO

The proposed model constructs solutions sequentially with a preference-conditioned policy. It shares instance embeddings across preferences and uses preference-generated decoder parameters to produce different approximate Pareto solutions.

4.1 PREFERENCE-CONDITIONED SOLUTION CONSTRUCTION

  • A preference-conditioned stochastic policy constructs valid tours sequentially to minimize scalarized costs for each preference.For MOTSP, a solution is a permutation visiting each city once and returning to the start.Source: §4.1 · p. 4

4.2 THE PROPOSED MODEL

  • The model uses a preference-agnostic attention encoder and a preference-conditioned attention decoder whose parameters are generated by an MLP.The encoder’s instance embeddings are reused across preferences, while the MLP maps each preference to decoder parameters.Source: Figure 3 · p. 5, §4.2 · p. 5
  • At each decoding step, the decoder attends over city embeddings using a context built from the first and most recently selected cities.The context incorporates the instance and current partial tour.Source: §4.2 · p. 5
  • Previously visited cities are masked, so the decoder selects only unvisited cities and can construct a feasible tour.Source: §4.2 · p. 5
  • Training samples preferences, instances, and tours to update the shared model, while instance augmentation adds only small computational and memory overhead.The model is designed to retain compatibility with improvements developed for single-objective neural combinatorial optimization.Source: §4.2 · p. 6

5 PREFERENCE-CONDITIONED MULTIOBJECTIVE POLICY OPTIMIZATION

The policy optimization assigns each preference a scalarized cost and trains one model across preferences with multiobjective reinforcement learning. An active adaptation method further adjusts the model for a given test instance, including out-of-distribution instances.

5.1 COST FUNCTION

  • A weighted-Tchebycheff scalarized cost represents each preference, and training minimizes expected cost across preferences and instances.The ideal cost for each objective is used in defining the scalarized cost.Source: §5.1 · p. 6

5.2 MULTIOBJECTIVE REINFORCE

  • REINFORCE estimates gradients for preference-conditioned costs, using a baseline to reduce gradient variance and Monte Carlo sampling.Updates sample preferences, instances, and tours; tour starting nodes are randomized to encourage diverse rollouts.Source: §5.2 · p. 6

5.3 ACTIVE ADAPTION

  • Active adaptation adjusts the model for a test instance without depending on the training-instance distribution, supporting out-of-distribution adaptation.Source: §5.3 · p. 7

6 EXPERIMENTS

Experiments evaluate P-MOCO on traveling-salesman, vehicle-routing, and knapsack problems against evolutionary and learning-based baselines. Results vary by task, with reported gains in solution quality, runtime, and model size, plus an out-of-distribution MOTSP evaluation.

6 EXPERIMENTS

  • Training used 100,000 randomly generated instances per epoch for 200 epochs, and evaluation measured hypervolume on 200 random test instances per problem.The reported normalized hypervolume values use a shared reference point; larger hypervolume generally indicates a better solution set.Source: §6 · p. 7
  • P-MOCO was compared with three evolutionary frameworks and two learning-based methods, including a multi-model variant, alongside single-objective solvers for weight-sum subproblems.The evolutionary frameworks require problem-specific heuristics; DRL-MOA and AM-MOCO use separate models for subproblems.Source: §6 · p. 7
  • P-MOCO supports flexible preference assignment with only 1.1% of the total parameters of its multi-model counterpart.Source: Table 1 · p. 7, §6 · p. 7

6.1 RESULTS AND ANALYSIS

  • On two-objective benchmarks, P-MOCO outperformed non-learning methods on MOCVRP and MOKP, while MOTSP instance augmentation beat other methods but not LKH.For bi-objective MOTSP, the single model performed similarly to AM-MOCO; the reported table covers two-objective MOTSP, MOCVRP, and MOKP at input sizes 20, 50, and 100.Source: Table 2 · p. 8, §6.1 · pp. 8–9
  • For three-objective MOTSP, generating many more trade-off solutions within reasonable time further improved P-MOCO’s performance relative to methods unable to do so.The results cover input sizes 20, 50, and 100.Source: §6.1 · p. 8, Table 3 · p. 9
  • With active adaptation, P-MOCO achieved a 1%–1.5% hypervolume gap to ground-truth Pareto fronts on six out-of-distribution MOTSP problems.The ground-truth fronts were obtained by exhaustive search.Source: §6.1 · p. 9

7 CONCLUSION AND FUTURE WORK

The paper presents a single preference-conditioned model for generating approximate Pareto solutions without further search, and reports better performance, speed, and model efficiency than other methods. It also discusses the approach’s approximation conditions, limitations, and future directions.

7 CONCLUSION AND FUTURE WORK

  • The method significantly outperforms other methods in performance, speed, and model efficiency.Experiments also show good approximate Pareto sets for three different MOCO problems.Source: §7 · p. 9
  • The method is framed as a learning version of MOEA/D that handles all preferences with one model instead of maintaining finite solution populations.Future work includes improving the model and training procedures and studying convergence–diversity and exploration–exploitation trade-offs.Source: §7 · p. 9

A.1 PARETO SET LEARNING AND CONVERGENCE GUARANTEE

  • A single preference-conditioned model directly generates arbitrary trade-off solutions without extra optimization.The paper describes it as an efficient mapping from preferences to approximate Pareto solutions.Source: §A.1 · p. 15
  • The method has no exact optimality guarantee, in part because subproblems can be NP-hard, Pareto sets can be exponentially large, and training or generalization may be imperfect.The paper identifies out-of-distribution generalization as another obstacle to an exact guarantee.Source: §7 · p. 9, §A.1 · p. 15
  • The approach can generate an ε-approximate Pareto set when its policy approximately solves each preference-based subproblem.Its approximation ability depends on the policy’s performance on the scalarized subproblems.Source: §A.1 · p. 15

A.2 APPROXIMATION ANALYSIS

The analysis links preference-based scalarized subproblems to Pareto solutions and argues that approximate solutions across preferences can yield an approximate Pareto set. It also explains the scalarization, the ε-approximation criterion, and the model’s dependence on subproblem-solving quality.

A.2 APPROXIMATION ANALYSIS

  • Weighted-Tchebycheff scalarization turns a MOCO problem into preference-based subproblems, with λ assigning weights to objectives.The method uses objective ideal and utopia values; positive weights characterize Pareto-optimal solutions of the scalarized problem.Source: §A.2 · p. 15
  • Finding the full Pareto set can require exponentially many preference subproblems, since the weight associated with each Pareto solution is not known in advance.The analysis notes that the Pareto-set size can be exponential in the input size.Source: §A.2 · pp. 15–16
  • A single mapping from any preference λ to a solution can generate the whole Pareto set if its outputs are optimal for every scalarized subproblem.The paper represents this mapping as xλ = h(λ).Source: §A.2 · pp. 15–16
  • The method’s approximation ability depends strongly on how well its parameterized policy solves each single-objective scalarized subproblem.The paper states that approximate solutions for any preference imply a good approximation to the whole Pareto set.Source: §A.2 · p. 16
  • An ε-approximate Pareto set contains a solution that ε-dominates every feasible solution.The analysis treats such a set as a practical target when the Pareto set is intractable to find.Source: §A.2 · p. 16
  • If the model’s solution ε-dominates the optimal scalarized solution for every preference, its outputs form an ε-approximate Pareto set.The proof connects each Pareto solution to a weighted scalarized subproblem, then applies the assumed approximation to it.Source: §A.2 · p. 16

A.3 LIMITATION

The approximation guarantee depends on approximately solving every weighted subproblem, while both dense Pareto-set construction and extending learning-enhanced algorithms face limits. The model uses a shared architecture with preference-conditioned decoder parameters, configured for each problem.

A.3 LIMITATION

  • Theorem 1’s approximation guarantee depends heavily on approximately solving each weighted subproblem, a nontrivial requirement for NP-hard problems.The authors say a small enough ε-convergence guarantee for every preference is difficult to establish.Source: §A.3 · p. 16
  • Learning-based methods combined with dynamic programming do not straightforwardly extend to multiobjective problems because scalarized subproblems can differ from their single-objective counterparts.The authors leave learning-enhanced multiobjective algorithms outside this work’s scope.Source: §A.3 · p. 17
  • An ε-approximate Pareto set may require exponentially many solutions, and its existence does not ensure it can be efficiently constructed for an unseen instance.The paper also says it is unclear how to select preferences in advance; the method may need exponentially many solutions in practice.Source: §A.3 · p. 17

B.1 MODEL SETTING

  • The model shares an encoder across preferences and generates preference-conditioned decoder parameters from the preference vector using an MLP.The same model is used across MOCO problems with problem-specific input dimensions and masks.Source: §B.1 · p. 18
  • Instance augmentation generalizes transformations that preserve an optimal solution, allowing the method to solve transformed instances and select the best resulting solution.For Euclidean MOTSP, transformations can be applied independently to each objective; MOCVRP uses eight transformations and MOKP none.Source: §B.1 · pp. 18–19

B.2 TRAINING EFFICIENCY

The paper reports that its preference-based model uses fewer samples and training epochs than MOCO methods that train separate models, while retaining comparable single-objective performance to learning-based solvers. It also describes active adaptation, the three problem formulations, and hypervolume evaluation.

B.2 TRAINING EFFICIENCY

  • The preference-based model requires significantly fewer samples and training epochs than MOCO methods that train multiple models for different preferences.With the same training samples, it has similar single-objective performance to a learning-based single-objective solver while also approximating the whole Pareto front.Source: §B.2 · p. 19

B.3 ACTIVE ADAPTION

  • After training, the method directly generates trade-off solutions without further search, but may remain short of the Pareto front on out-of-distribution instances.Sampling and beam search may improve a single solution or preference, but the paper says they cannot improve the whole Pareto-set approximation.Source: §B.3 · p. 19

C DETAILS OF THE MOCO PROBLEMS

  • The paper introduces the problem formulations and model configurations used for MOTSP, MOCVRP, and MOKP.The model configurations include problem-specific input sizes and masking methods.Source: C DETAILS OF THE MOCO PROBLEMS · p. 21

C.1 MOTSP

  • MOTSP seeks a cyclic tour minimizing multiple costs, and its Pareto set can have exponential cardinality in the input size.The study samples node coordinates uniformly from a 2m-dimensional unit hyper-square.Source: §C.1 · p. 21

C.2 MOCVRP

  • MOCVRP solutions are routes that satisfy city demands and vehicle capacity while optimizing total tour length and longest-route length.The latter objective is also called makespan.Source: §C.2 · p. 21

C.3 MOKP

  • MOKP selects items within a weight capacity to maximize the sum of values across objectives.The problem assumes total item weight exceeds capacity while each individual item weighs less than capacity.Source: §C.3 · p. 22

D.1 HYPERVOLUME INDICATOR

  • Hypervolume compares approximate Pareto sets when the ground-truth set is unknown; a larger value indicates better performance under this measure.It measures the objective-space volume dominated by a solution set, relative to a reference point.Source: §D.1 · p. 23

D.2 OUT-OF-DISTRIBUTION PROBLEM WITH EXACT PARETO FRONT

On out-of-distribution MOTSP instances with exact Pareto fronts, the method approaches those fronts with a small hypervolume gap but remains behind LKH. With more preferences, it can generate denser Pareto-set approximations.

D.2 OUT-OF-DISTRIBUTION PROBLEM WITH EXACT PARETO FRONT

  • A 1%–1.5% hypervolume gap is reported for the proposed method with instance augmentation and/or 10-minute active search on six out-of-distribution MOTSP100 instances; it outperforms OR Tools but trails LKH.The instances have exact Pareto fronts, different objective ranges, and non-uniform city locations.Source: Table 6 · p. 24, §D.2 · p. 24

D.3 FLEXIBLE PREFERENCE-BASED APPROXIMATION

  • With 105, 1,035, or 10,011 preferences, the model generates well-distributed or denser approximations, respectively, for three-objective MOTSP instances.The paper reports that this flexibility lets decision-makers generate arbitrary preferred solutions on the approximate front.Source: Figure 5 · p. 25, §D.3 · p. 26

D.4 PREFERENCE-SOLUTION CONNECTION

Preference-to-solution mappings depend on objective scales and Pareto-front shape. Increasing preference counts can improve coverage, while aggregation-function choice also affects solution distribution.

D.4 PREFERENCE-SOLUTION CONNECTION

  • On MOTSP100, whose two costs share a scale, uniformly distributed preferences connect uniformly to the approximate Pareto front, from sparse to dense as their number increases.Figure 6 illustrates the connections for different preference counts.Source: §D.4 · p. 26, Figure 6 · p. 26
  • More uniform preferences improve MOCVRP coverage and hypervolume, while 101-model MA-MOCO performs worse than our model with 101 preferences.The 101-model and 101-preference sets remain too sparse and favor objective 1; more preferences add solutions with better relative performance on objective 2.Source: Figure 7 · p. 26, §D.4 · p. 27

D.5 CONNECTION BETWEEN PREFERENCES AND SOLUTIONS

  • For many-objective problems, aggregation-function performance depends heavily on Pareto-front shape, especially when only a limited number of approximate solutions are available.For two objectives, different aggregation functions may perform similarly when dense corresponding solutions cover the front.Source: §D.5 · pp. 27–28
  • For MOTSP50's inverted-triangular Pareto front, IPBI produces the most uniformly distributed solutions; the study uses Tchebycheff for two objectives and IPBI for more than two.The authors identify choosing aggregation functions and preference distributions for irregular real-world fronts as future work.Source: §D.5 · p. 28, Figure 8 · p. 28

D.6 THREE-OBJECTIVE MOTSP WITH ASYMMETRIC PARETO FRONT

The section examines preference choices for irregular fronts and many-objective problems. The model supports real-time weight adjustment, and its 10-objective knapsack results are reported as best among the compared methods and generalizable to larger instances.

D.6 THREE-OBJECTIVE MOTSP WITH ASYMMETRIC PARETO FRONT

  • Uniform fixed weights cannot evenly explore an irregular front, but dense inference-time preference sampling lets users generate and select preferred solutions.Adaptive weight adjustment for evenly exploring truly irregular fronts remains a possible future direction.Source: §D.6 · p. 29, §D.7 · p. 30
  • On an asymmetric three-objective MOTSP front, non-uniform weights scaled by (1, 2, 10) produce more evenly distributed solutions than uniform weights.The objective coordinates are sampled from different ranges, creating objective values on different scales and an irregular front.Source: §D.6 · p. 29, Figure 9 · p. 29

D.7 PREFERENCE-BASED INFERENCE

  • At inference, users can adapt weights in real time to generate trade-off solutions in preferred Pareto-front regions, even without prior knowledge.When preferences are known, the training preference distribution can be modified to emphasize the relevant region.Source: §D.7 · pp. 29–30, Figure 10 · p. 30, Figure 11 · p. 30

D.8 PROBLEM WITH MORE OBJECTIVES

  • Our method has the best performance on 10-objective MOKP100 and generalizes well to 500-item problems.For MOKP100, inference uses 715 fixed preferences, yielding 715 trade-off value paths; AM-MOCO and MOA-DRL are not compared because training many models would add substantial computational and storage overhead.Source: §D.8 · p. 31, Figure 12 · p. 31

Related papers

Loading 2203.15386v2…