Adversarial Instance Generation and Robust Training for Neural Combinatorial Optimization with Multiple Objectives
This work addresses the robustness issue in neural solvers for multi-objective combinatorial optimization, which is incremental as it builds on existing DRL methods by enhancing their reliability across diverse problem distributions.
The paper tackled the robustness of deep reinforcement learning solvers for multi-objective combinatorial optimization problems by proposing a framework that generates adversarial instances to expose weaknesses and integrates adversarial training with hardness-aware preference selection to improve out-of-distribution performance, resulting in significant strengthening of solver robustness and generalizability on hard instances.
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 insufficiently explored, especially across diverse and complex problem distributions. In this paper, we propose a unified robustness-oriented framework for preference-conditioned DRL solvers for MOCOPs. Within this framework, we develop a preference-based adversarial attack to generate hard instances that expose solver weaknesses, and quantify the attack impact by the resulting degradation on Pareto-front quality. We further introduce a defense strategy that integrates hardness-aware preference selection into adversarial training to reduce overfitting to restricted preference regions and improve out-of-distribution performance. The experimental results on multi-objective traveling salesman problem (MOTSP), multi-objective capacitated vehicle routing problem (MOCVRP), and multi-objective knapsack problem (MOKP) verify that our attack method successfully learns hard instances for different solvers. Furthermore, our defense method significantly strengthens the robustness and generalizability of neural solvers, delivering superior performance on hard or out-of-distribution instances.