Pareto Set Learning for Neural Multi-objective Combinatorial Optimization
This work addresses the problem of efficiently solving NP-hard multiobjective combinatorial optimization problems for applications in logistics and resource allocation, representing an incremental extension of decomposition-based evolutionary algorithms.
The authors tackled the challenge of approximating the entire Pareto set for multiobjective combinatorial optimization problems by developing a learning-based approach that uses a single preference-conditioned model to directly generate solutions, achieving significant improvements in solution quality, speed, and model efficiency on benchmark problems like the multiobjective traveling salesman and knapsack problems.
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.