An Effective Cross-Task Unified Multiobjective Neural Metaframework for Solving Combinatorial Optimization Problems.

Abstract

Neural combinatorial optimization methods based on deep reinforcement learning (DRL) have shown promising results recently in solving complex combinatorial optimization problems (COPs). However, existing approaches usually require training separate models for each COP. When facing multiobjective COPs (MOCOPs), a large number of models still need to be trained to solve the single-objective subproblems generated by the weight scalarization strategy. To address the two key challenges of cross-task learning and multiobjective optimization, we propose an effective cross-task unified multiobjective neural metaframework (CUMNM), which uses the novel attribute-sharing attention model (AM) as the base model. It is the first general end-to-end framework for solving various MOCOPs with an arbitrary number of objectives using a single model. Initially, a metamodel is trained on multiple MOCOPs through metalearning. For a specific MOCOP, only a few fine-tuning steps for the metamodel are required to derive a new task-adapted model. Subsequently, the scalarized subproblems of the task can be solved directly by updating only a small subset of parameters in the new model. This enables the construction of an approximate Pareto front (PF) without retraining from scratch for each subproblem. During training, we exploit the symmetry of MOCOP solutions and introduce a low-variance baseline method to stabilize and accelerate the training process. For inference, performance is enhanced via instance augmentation and a novel regret-based multistart search strategy. Comprehensive experiments on four typical MOCOPs demonstrate that our method significantly outperforms other state-of-the-art algorithms in solution quality and model efficiency. It also exhibits strong performance on unseen but structurally similar tasks, demonstrating zero-shot generalization.