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

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

Problem Statement
Deep Reinforcement Learning (DRL) has emerged as a promising approach for solving Multi-Objective Combinatorial Optimization Problems (MOCOPs), offering superior efficiency compared to traditional exact and heuristic algorithms. However, the robustness of these DRL solvers remains underexplored, particularly regarding their performance across diverse and complex problem distributions. Existing studies on single-objective problems suggest that DRL models may suffer from "shortcut learning," overfitting to specific distributional cues and failing when tested on out-of-distribution (OOD) instances. In the context of MOCOPs, where the goal is to approximate a Pareto front balancing multiple conflicting objectives, the vulnerability of neural solvers to distribution shifts and the lack of systematic robustness evaluation pose significant challenges to their practical deployment.

Methodology
The authors propose a unified framework comprising two core components: a Preference-based Adversarial Attack (PAA) to expose solver weaknesses and a Dynamic Preference-augmented Defense (DPD) to enhance robustness.

1. Preference-based Adversarial Attack (PAA):

   • Objective: To generate "hard" instances that specifically degrade the performance of DRL solvers under specific preference conditions.
   • Mechanism: The method treats the problem input (e.g., node coordinates in TSP) as a learnable variable. It iteratively updates the input $x$ via gradient ascent to maximize the reinforcement loss $\ell(x; \theta)$ of a target solver.
   • Loss Function: The loss is defined as the normalized subproblem loss $L(\pi|x)$ divided by a baseline, multiplied by the log-probability of the solution. By maximizing this, the attack forces the solver to produce solutions with poor Pareto front quality (measured by Hypervolume, HV) for specific preference vectors $\lambda$.
   • Outcome: The process generates an adversarial instance pool tailored to different preferences, effectively lowering the quality of the resulting Pareto fronts.

2. Dynamic Preference-augmented Defense (DPD):

   • Objective: To improve the generalizability and robustness of neural solvers through adversarial training.
   • Mechanism: DPD performs fine-tuning on a mixture of clean instances and a pre-generated adversarial pool.
   • Hardness-Aware Preference Selection: During training, for each sampled instance and preference $\lambda$, the method generates a set of locally augmented preferences $\{\lambda'_i\}$ by applying small random perturbations. It evaluates the Tchebycheff values of solutions generated under these augmented preferences (with model parameters fixed) and selects the preference $\lambda'_{adv}$ that yields the worst solution quality (highest Tchebycheff value).
   • Training: The solver is then updated to minimize the scalarized loss specifically for this "hardest" augmented preference within the mini-batch. This strategy aims to prevent overfitting to restricted preference regions and forces the model to learn robust representations across the preference space.

Key Contributions

• PAA Method: Introduction of a method to systematically generate hard instances for MOCOPs by targeting specific preferences, demonstrating that neural solvers can be significantly impaired by distribution shifts tailored to their subproblem weaknesses.
• DPD Method: Proposal of a defense strategy integrating hardness-aware preference selection into adversarial training. This approach mitigates overfitting and improves out-of-distribution performance without requiring changes to the underlying model architecture.
• Comprehensive Evaluation: The framework is validated across three classical MOCOPs: Multi-Objective Traveling Salesman Problem (MOTSP), Multi-Objective Capacitated Vehicle Routing Problem (MOCVRP), and Multi-Objective Knapsack Problem (MOKP).

Experimental Results

• Attack Efficacy: The PAA method successfully generated instances that significantly reduced the Hypervolume (HV) of solutions produced by competitive neural solvers (EMNH, PMOCO, CNH) compared to clean instances and other distribution perturbations (log-normal, beta, gamma). In several cases, PAA outperformed existing learning-based attack methods like ROCO-RL.
• Defense Performance: Models trained with DPD (e.g., PMOCO-DPD, CNH-DPD, EMNH-DPD) demonstrated consistent improvements in robustness.
  • On Gaussian OOD instances, DPD-enhanced solvers achieved lower optimality gaps compared to their non-defended counterparts.
  • Notably, on Bi-CVRP100, the WE-CA-DPD model improved HV by 2.23% over the WS-LKH baseline, the largest gain observed.
  • DPD models maintained strong performance on larger scale instances (up to 200 nodes) and diverse benchmark instances (kroAB100, etc.), often approaching the performance of exact solvers while maintaining significantly lower inference times (seconds vs. hours for exact methods).
• Efficiency: The defense method adds minimal computational overhead during training and inference, with DPD-trained models running orders of magnitude faster than non-learnable exact solvers (e.g., WS-DP).

Significance and Claims
The paper claims that the proposed framework addresses a critical gap in the literature regarding the robustness of neural MOCOP solvers. By explicitly exposing solver vulnerabilities through PAA and systematically addressing them via DPD, the authors demonstrate that neural solvers can be made significantly more robust to distribution shifts and preference variations. The results suggest that adversarial training with hardness-aware preference selection is an effective strategy for enhancing the generalizability of DRL-based combinatorial optimization, making these solvers more viable for real-world applications where problem distributions are dynamic and complex. The authors conclude that their work lays the groundwork for future extensions to dynamic real-world MOCOPs and online environments.