mlsanityData to 14 Oct 2026

Adversarial Instance Generation and Robust Training for Neural Combinatorial Optimization with Multiple Objectives

arXiv 2601.01665 ↗First posted 4 Jan 2026cs.LG cs.AIcited by 0

On the map: Deep reinforcement learning methods → RL for games and combinatorial optimization

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods. Builds on 15 of its 35 references that are in the map. First posted on arXiv 4 Jan 2026.

Builds on

15 of 35 references.

References · 15

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2020Shortcut Learning in Deep Neural Networkscited by 1,969
  3. 2016Neural Architecture Search with Reinforcement Learningcited by 1,499
  4. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 348
  5. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 318
  6. 2021NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problemcited by 103
  7. 2019Deep Reinforcement Learning for Multi-objective Optimizationcited by 90
  8. 2022Pareto Set Learning for Neural Multi-objective Combinatorial Optimizationcited by 56
  9. 2021Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustnesscited by 35
  10. 2022Learning to Solve Travelling Salesman Problem with Hardness-adaptive Curriculumcited by 27
  11. 2023Efficient Meta Neural Heuristic for Multi-Objective Combinatorial Optimizationcited by 21
  12. 2020MODRL/D-AM: Multiobjective Deep Reinforcement Learning Algorithm Using Decomposition and Attention Model for Multiobjective Optimizationcited by 11
3 more
  1. 2016A Survey of Multi-Objective Optimization in Wireless Sensor Networks: Metrics, Algorithms and Open Problemscited by 9
  2. 2024Collaboration! Towards Robust Neural Methods for Routing Problemscited by 9
  3. 2019Average Sensitivity of Graph Algorithmscited by 8

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025Preference-Driven Multi-Objective Combinatorial Optimization with Conditional Computation
  2. 2025Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization
  3. 2025Preference Optimization for Combinatorial Optimization Problems
  4. 2025ASAP: Exploiting the Satisficing Generalization Edge in Neural Combinatorial Optimization
  5. 2024Leader Reward for POMO-Based Neural Combinatorial Optimization
  6. 2024Robust Deep Reinforcement Learning Through Adversarial Attacks and Training : A Survey
  7. 2025Generative Modeling for Robust Deep Reinforcement Learning on the Traveling Salesman Problem
  8. 2026Robust Policy Optimization via Adversarial Importance Sampling