Preference Conditioned Neural Multi-objective Combinatorial Optimization
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 preference-based attention model to directly generate approximate Pareto solutions of all the different 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.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationTraveling Salesman ProblemMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Pareto Set Learning for Neural Multi-objective Combinatorial Optimization
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 handcraf…
Combinatorial OptimizationTraveling Salesman ProblemAdversarial Instance Generation and Robust Training for Neural Combinatorial Optimization with Multiple Objectives
Deep reinforcement learning (DRL) has shown great promise in addressing multi-objective combinatorial optimization problems (MOCOPs). Nevertheless, the robustness of these learning-based solvers has remained insufficient…
Reinforcement LearningAdversarial AttackSCOPE: Synthetic Conditional Objectives for Policy Evolution in Black-Box Combinatorial Optimization
Black-box combinatorial optimization requires systematically identifying high-quality solutions under a limited evaluation budget, yet the unknown objective function provides little guidance for deciding where the search…
WeCon: An Efficient Weight-Conditioned Neural Solver for Multi-Objective Combinatorial Optimization Problems
Existing neural solvers for Multi-Objective Combinatorial Optimization Problems (MOCOPs) commonly adopt decomposition-based strategies that scalarize a MOCOP into multiple subproblems associated with distinct weight vect…
Neural Combinatorial Optimization via Preference Optimization
Neural Combinatorial Optimization (NCO) has emerged as a promising approach for NP-hard problems. However, prevailing RL-based methods suffer from low sample efficiency due to sparse rewards and underused solutions. We p…
Combinatorial OptimizationJob Shop SchedulingScheduling