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

• URL: http://arxiv.org/abs/2601.01665v1
• Date: Sun, 04 Jan 2026 20:57:43 GMT
• Title: Adversarial Instance Generation and Robust Training for Neural Combinatorial Optimization with Multiple Objectives
• Authors: Wei Liu, Yaoxin Wu, Yingqian Zhang, Thomas Bäck, Yingjie Fan,
• Abstract summary: We propose a unified robustness-oriented framework for preference-conditioned DRL solvers for MOCOPs.<n>We develop a preference-based adversarial attack to generate hard instances that expose solver weaknesses.<n>We also introduce a defense strategy that integrates hardness-aware preference selection into adversarial training.
• Score: 20.700279316676802
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• MO-MIX: Multi-Objective Multi-Agent Cooperative Decision-Making With Deep Reinforcement Learning [68.91090643731987]
  Deep reinforcement learning (RL) has been applied extensively to solve complex decision-making problems.<n>Existing approaches are limited to separate fields and can only handle multi-agent decision-making with a single objective.<n>We propose MO-mix to solve the multi-objective multi-agent reinforcement learning (MOMARL) problem.
  arXiv  Detail & Related papers  (2026-02-28T16:25:22Z)
• Benchmarking MOEAs for solving continuous multi-objective RL problems [3.8936716676293917]
  Multi-objective reinforcement learning (MORL) addresses the challenge of simultaneously optimizing multiple, often conflicting, rewards.<n>This paper investigates the applicability and limitations of multi-objective evolutionary algorithms in solving complex MORL problems.
  arXiv  Detail & Related papers  (2025-05-19T20:54:20Z)
• UC-MOA: Utility-Conditioned Multi-Objective Alignment for Distributional Pareto-Optimality [52.49062565901046]
  Reinforcement Learning from Human Feedback (RLHF) has become a cornerstone for aligning large language models with human values.<n>Existing approaches struggle to capture the multi-dimensional, distributional nuances of human preferences.<n>We introduce Utility-Conditioned Multi-Objective Alignment (UC-MOA), a novel framework that overcomes these limitations.
  arXiv  Detail & Related papers  (2025-03-10T09:52:42Z)
• Pareto Set Learning for Multi-Objective Reinforcement Learning [19.720934024901542]
  We propose a decomposition-based framework for Multi-Objective RL (MORL)<n>PSL-MORL harnesses the generation capability of hypernetwork to produce the parameters of the policy network for each decomposition weight.<n>We show that PSL-MORL significantly outperforms state-of-the-art MORL methods in the hypervolume and sparsity indicators.
  arXiv  Detail & Related papers  (2025-01-12T10:43:05Z)
• UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [51.00436121587591]
  In Multi-objective Reinforcement Learning (MORL) agents are tasked with optimising decision-making behaviours.<n>We focus on the case of linear utility functions parametrised by weight vectors w.<n>We introduce a method based on Upper Confidence Bound to efficiently search for the most promising weight vectors during different stages of the learning process.
  arXiv  Detail & Related papers  (2024-05-01T09:34:42Z)
• Efficient Meta Neural Heuristic for Multi-Objective Combinatorial Optimization [35.09656455088854]
  We propose an efficient meta neural vector (EMNH) to solve multi-objective optimization problems. EMNH is able to outperform the state-of-the-art neurals in terms of solution quality and learning efficiency.
  arXiv  Detail & Related papers  (2023-10-22T08:59:02Z)
• A Unifying Perspective on Multi-Calibration: Game Dynamics for Multi-Objective Learning [63.20009081099896]
  We provide a unifying framework for the design and analysis of multicalibrated predictors. We exploit connections to game dynamics to achieve state-of-the-art guarantees for a diverse set of multicalibration learning problems.
  arXiv  Detail & Related papers  (2023-02-21T18:24:17Z)
• Pareto Set Learning for Neural Multi-objective Combinatorial Optimization [6.091096843566857]
  Multiobjective optimization (MOCO) problems can be found in many real-world applications. We develop a learning-based approach to approximate the whole Pareto set for a given MOCO problem without further search procedure. Our proposed method significantly outperforms some other methods on the multiobjective traveling salesman problem, multiconditioned vehicle routing problem and multi knapsack problem in terms of solution quality, speed, and model efficiency.
  arXiv  Detail & Related papers  (2022-03-29T09:26:22Z)
• On the Convergence and Robustness of Adversarial Training [134.25999006326916]
  Adrial training with Project Gradient Decent (PGD) is amongst the most effective. We propose a textitdynamic training strategy to increase the convergence quality of the generated adversarial examples. Our theoretical and empirical results show the effectiveness of the proposed method.
  arXiv  Detail & Related papers  (2021-12-15T17:54:08Z)
• Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
  We propose an efficient model-based reinforcement learning algorithm for learning in multi-agent systems. Our main theoretical contributions are the first general regret bounds for model-based reinforcement learning for MFC. We provide a practical parametrization of the core optimization problem.
  arXiv  Detail & Related papers  (2021-07-08T18:01:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.