Collaboration! Towards Robust Neural Methods for Routing Problems

[1] Learning to solve travelling salesman problem with hardness-adaptive curriculum. In AAAI 2022.
[2] ROCO: A general framework for evaluating robustness of combinatorial optimization solvers on graphs. In ICLR 2023.
[3] POMO: Policy Optimization with Multiple Optima for Reinforcement Learning. In NeurIPS 2020.
[4] DIMES: A differentiable meta solver for combinatorial optimization problems. In NeurIPS 2022.
[5] DeepACO: Neural-enhanced ant systems for combinatorial optimization. In NeurIPS 2023.
[6] Efficient active search for combinatorial optimization problems. In ICLR 2022.
[7] Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems. In ICML 2024.
[8] Model-agnostic meta-learning for fast adaptation of deep networks. In ICML 2017.

We genuinely appreciate the effort the reviewer dedicated to evaluating our paper and providing insightful feedback! Here are our detailed responses to your comments, where W denotes Weakness (W1-W4) and Q denotes Question (Q1-Q2).

W1: An experiment on independent AT.

Actually, the baseline method POMO_AT (3) in Table 1 refers to the independent AT, where 3 models are adversarially trained separately, and output the best solution. The results of training more (yet independent) AT models can be found in Fig. 1, showing that our method achieves a better trade-off between computation and performance.

W2: This paper did not describe the considered threat model.

Specifically, we consider the threat model of [1] in the main paper, which means that our trained model is robust against the perturbation of input attributes (e.g., node coordinates). To demonstrate the versatility of our method, we consider another threat model of [2] in Appendix E.3, which can be viewed as the perturbation of constraints. Due to the page limit, we present the details of each threat model in Appendix C (e.g., C.1 for [1]; C.3 for [2]). Please kindly refer to them.

W3: Elaboration on the inference procedure.

Generally, given a single trained model, we construct the solution using the greedy rollout with x8 augmentations following POMO [3]. Given multiple ($M)$ models, we construct one solution per model following the above procedure, obtain $M$ solutions for each test instance, and report the best one. The clean performance is evaluated on the test dataset whose distribution is the same as the training one. The adversarial performance is evaluated on the adversarial dataset, which is generated by attacking the pretrained or current model. If we use the threat model of [1], adversarial instances are generated by Eqs. (7-8) as shown in Appendix C.1, and $θ^{(t)}$ in Eq. (7) is then adjusted for different methods and evaluation metrics (e.g., $θ^{(t)}$ is set to the parameters of the pretrained model $θ_p$ if the metric of Fixed Adv. is evaluated). Please see lines 256-269 for inference setups. We will include more inference details in the final draft.

W4: Minor issue: The "attack" term, and the real-world scenario.

We understand the reviewer's concern. This term is from the general ML and thus we keep it for consistency in this paper. Generally, the attack procedure can be viewed as a way of generating instances on which the current model underperforms. We discuss the potential attack scenarios and practical significance in Appendix A (lines 686-700). We will clarify this terminology and highlight its difference in the COP domain in the introduction section. Please let us know if you have any better recommendations.

Q1: How robust are test-time adaptation methods such as meta-learning and neural-guided local search?

Thanks for the interesting question. Yes, these test-time adaptation methods [4-6] are relatively robust. This degree of "robustness" primarily comes from 1) traditional local search heuristics and metaheuristics, which can effectively handle perturbations but bring much post-processing runtime, or 2) the costly fine-tuning that incurs more inference time on each test instance. Our CNF can also be combined with them to pursue better performance. For example, we further combine CNF with EAS [6] and deliver better TSPLIB results as shown in Table 1 of the uploaded PDF.

Furthermore, following the reviewer's suggestion, we conduct experiments on DIMES [4] and DeepACO [5]. The results are shown in Tables 2 and 3 of the uploaded PDF, where we observe that 1) CNF (clean: 0.12%; adv: 0.24%) outperforms them in most cases (e.g., w/o advanced search) with a much shorter runtime, and 2) test-time adaptation methods (i.e., the purple columns) improve robustness by adopting much post-search effort and consuming hours of runtime. According to the results, we note that 1) directly comparing CNF with these methods with advanced searches (e.g., MCTS, NLS) is somewhat unfair, since the additional post-processing search makes the analysis of model robustness difficult. For example, recent work finds that MCTS is so strong that using an almost all-zero heatmap can achieve good solutions [7], raising doubts about the real robustness of learned models; 2) the post-processing searches are typically time-consuming and problem-specific, making them non-trivial to be adapted to other COPs.

Finally, we highlight that studies on robustness in COPs are still rare, and most work focused on investigating the robustness of neural solvers themselves, due to their advantages in generality on more complex COPs and inference speed. However, inspired by the reviewer's question, attacking test-time adaption methods is a potential research direction, which we will leave to future work.

Q2: Is it possible to employ meta-learning to speed up the convergence?

RL-based AM/POMO is known for its slow convergence due to the autoregressive decoding and sparse reward problem. DIMES [4] designs a compact continuous parameterization space of the underlying distribution of candidate solutions (i.e., heatmap) to efficiently search for high-quality solutions. Therefore, DIMES shows a faster convergence (due to its novel paradigm and lightweight network) in their Fig. 1. Furthermore, meta-learning is typically leveraged to help the model generalize across tasks (e.g., problem instances in DIMES). The second-order meta-learning (e.g., MAML [8]) is computationally expensive for training POMO. Therefore, we experiment with FOMAML [8], a first-order meta-learning method. We set the inner update step as 1, and follow our original training setups. Unfortunately, we do not observe an improved training efficiency or convergence. However, we will further explore this inspiring idea in the future.

We are grateful to the reviewer for dedicating your precious time to review our paper and offer feedback. Here are our detailed responses to your comments, where W denotes Weakness and Q denotes Question (Q1-Q6).

W: The paper is not organized or written well; This paper is not technically sound.

Due to the space limit, please see the General Response. We will further polish our paper.

Q1: Figure 1 is not clearly explained and not referred.

Fig. 1 is referred in line 34 of Section 1. The motivation of Fig. 1 is to show the robustness issue of existing neural combinatorial solvers and the effectiveness of our CNF compared to vanilla adversarial training (AT). The empirical observations of Fig. 1 can be summarized as follows:

• Based on Fig. 1 (b-c): Recent neural combinatorial solvers (e.g., POMO) suffer from severe robustness issues - their performance significantly deteriorates on adversarial instances (e.g., >> 10% optimality gap on TSP100).
• Based on Fig. 1 (a-b): Vanilla AT (i.e., POMO_AT (1)) can significantly improve the adversarial robustness of the base model (i.e., (b): ~35.80% -> ~0.39%), but at the sacrifice of standard generalization (i.e., (a): 0.14% -> 0.37%). This is the so-called trade-off between standard generalization and adversarial robustness.
• Based on Fig. 1 (a-b): Simply increasing the model capacity by naive ensembling multiple models through AT cannot efficiently mitigate this trade-off (e.g., POMO_AT (9) ensembles 9 models, but the standard generalization is still worse than POMO (1)). In contrast, our CNF can effectively mitigate this trade-off by only using 3 models.

Q2: During inference, how can you tell which is the best solution?

Different from Bayesian optimization, evaluating the solution quality is simple and efficient in routing problems. After constructing multiple solutions, the solution with the minimal objective value (i.e., tour length) is the best one.

Q3: What is collaborative manner exactly?

Note that previous baselines (e.g., POMO_AT ($M$)) are independent, which means $M$ models are independently trained, and output the best solution found by them. With that said, there is no interaction among $M$ models during training. In contrast, our CNF leverages the collaboration mechanism, which can be explained from the below perspectives:

• Adversarial instance generation in the inner maximization: we propose the global attack for synergizing multiple models to generate the global adversarial instance by attacking the best-performing model in each iteration, rather than only leveraging each model to independently generate their own local adversarial instances. Suppose we have $M=3$ models ($\Theta=\{\theta_1, \theta_2, \theta_3\}$), the traditional local adversarial instance $\tilde{x}^{(T)}$ for $\theta_1$ is generated through $T$ iterations, and $\theta_1$ is repeatedly used in each iteration. In contrast, our global adversarial instance $\bar{x}^{(T)}$ can be generated by: $\bar{x}^{(0)} \xrightarrow{\theta_3} \bar{x}^{(1)} \xrightarrow{\theta_1} ... \xrightarrow{\theta_2} \bar{x}^{(T)}$ (i.e., $\theta_3$ performs the best for $\bar{x}^{(0)}$; $\theta_1$ performs the best for $\bar{x}^{(1)}$; ...). Therefore, there is a collaboration among models for instance generation in CNF.
• Policy optimization in the outer minimization: for baselines, each model is solely trained on the local adversarial instance generated by itself. We design a neural router, intending to maximize the improvement of ensemble performance, to adaptively forward training instances to different models for effective training. In this way, we empirically observe that each model tends to have its own expert area (as shown in Fig. 5), and the total model capacity can be reasonably exploited, which is also a kind of collaboration.

In summary, CNF facilitates the interaction (or collaboration) among models, facilitating diverse instance generation and making better use of the limited model capacity, hence significantly outperforming baselines.

Q4: What distribution will the generated adversarial instances follow?

It depends on the attack method and its strength. We have provided an illustration in Fig. 4 of the paper. We further visualize the generated adversarial instances in Fig. 1 of the uploaded PDF, where we show distribution shifts of node coordinates and node demands on CVRP100, respectively.

Q5: Does this paper focus on solving COPs? How?

Not exactly. This paper focuses on improving the robustness and generalization of recent neural combinatorial solvers through AT. Most of these neural solvers leverage the attention mechanism and the variant of Transformer to solve VRPs (see Section 2.1 regarding how they solve VRPs). Nevertheless, their performance greatly degrades on adversarial instances. Therefore, this paper proposes a new training framework to adversarially train these neural solvers in a collaborative way, aiming to enhance their robustness and generalization for solving VRPs.

Q6: There is no discussion on Table 7 or 8.

We summarize the results in lines 326-329. Concretely, the results of Tables 7 and 8 show that our method outperforms baselines on most benchmark instances, which has two implications: 1) raising robustness against attacks through CNF can favorably promote various forms of generalization (e.g., cross-size and cross-distribution); 2) there may exist a neural solver with high generalization and robustness concurrently in the COP domain. With that said, the generalization and robustness may not be conflicting goals in COPs [1], which is different from other domains such as image-based tasks. We will add the above discussion in the final draft.

[1] Generalization of neural combinatorial solvers through the lens of adversarial robustness. In ICLR 2022.

We greatly appreciate the reviewer's time and effort in reviewing our paper and providing constructive comments. Here are our detailed responses to your review, where W denotes Weakness and Q denotes Question (Q1-Q5).

W: The trade-off demonstrated in Figure is not clear; Figures 2 and Algorithm 1 are not intuitive enough.

Thanks for your comments. We will polish them to be clearer. Based on the results from Fig. 1 (a-b), conducting vanilla adversarial training (i.e., POMO_AT (1)) can significantly improve the adversarial robustness of the base model (POMO (1)), i.e., ~35% -> ~0.4%, but at the sacrifice of standard generalization, i.e., ~0.15% -> ~0.36%. This demonstrates the existence of an undesirable trade-off between standard generalization and adversarial robustness in VRPs. We further give a detailed explanation regarding Fig. 1, which will be included in the final draft. Please see our response to Reviewer xLJf Q1.

Q1: For CVRP, Is it possible to perform adversarial training on the demand values as well?

Yes, a round operation can be used to project perturbed demands into the discrete valid domain. Please see the detailed formulation (i.e., Eq. (7)(9)) in Appendix C.1. We further show the percentage frequency distribution shift of node demands if perturbing node demands of CVRP instances. Please see Fig. 1 (d-e) of the uploaded PDF for details.

Q2: What's the setting of ablation models in the part Ablation on Components?

The detailed training setups of ablation studies can be found in lines 969-976 of Appendix E.1. We consider the case of $M=3$ models, and remove each component separately to demonstrate the effectiveness of each component in our proposed CNF. Concretely, our CNF is equivalent to the base model, augmented by the global attack and neural router (i.e., CNF = POMO_AT + Global Attack + Router). 1) If we remove the global attack (i.e., W/O Global Attack), then only the local adversarial instances are generated in the inner maximization. They are then distributed by the neural router in the outer minimization. 2) If we remove the neural router (i.e., W/O Router), then the global and local adversarial instances are generated in the inner maximization. In the outer minimization, the local adversarial instances are distributed to the corresponding model that generates them, while the global adversarial instances are randomly distributed to models for training. 3) If we remove both components, then it is the vanilla adversarial training (i.e., POMO_AT), where there is no interaction or collaboration among models.

Q3: For TSP, is CNF equally effective in different network architectures?

Yes, the proposed CNF can be naturally adapted to other construction solvers, such as ELG [1] and LEHD[2]. In this paper, we mainly consider POMO and MatNet to demonstrate the versatility of CNF to defend against various attacks on different VRPs. Following the reviewer's suggestion, we further conduct an experiment of ELG with a simplified training setup (i.e., half the training instances) due to the tight rebuttal period. The pretrained ELG achieves 0.23% and 15.24% on the clean instances and adversarial instances of TSP100, respectively. Collaboratively training three ELG models through CNF significantly improves the standard generalization and adversarial robustness concurrently (i.e., clean: 0.11%; adv.: 0.25%). This demonstrates the generality of CNF in improving the robustness of neural VRP solvers.

Q4: Can the neural router be used to assign the testing data to facilitate inference?

Yes, the neural router can be used during inference. The positive side is that it can save inference time if the number of models M is extremely large. However, the neural router cannot fully guarantee to select the corresponding best-performing model w.r.t. each test instance. It may also suffer from the generalization issue if facing OOD instances. With that said, its performance is generally inferior to our default inference strategy. So this is a trade-off between computation and performance. Based on the experiments, we find that $M=3$ models are sufficient for CNF, so we decided to deactivate the neural router to maximize performance during inference.

Q5: About minor questions.

We thank the reviewer for the careful review and for bringing these issues to our attention! We will fix them and add the references in the final draft. The formulation of the POMO baseline in Eq. (4) is $b(x)=\frac{1}{N}\sum_{i=1}^Nc(\tau_i)$, where $N$ is the number of start nodes, $c(\cdot)$ is the cost function, and $\tau$ is the constructed solution (or tour) for the input instance $x$.

[1] Towards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy. In IJCAI 2024.
[2] Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization. In NeurIPS 2023.

We sincerely appreciate the reviewer for spending valuable time reviewing our paper and providing positive comments. Here are our detailed responses to your comments, where W denotes Weakness.

W: Theoretical analysis or guarantees.

Thanks for your comment. The majority of the work within the "learning for solving VRP" literature focused on the empirical side. They prioritized closing the gap between neural solvers and traditional solvers, lacking theoretical proof of the improvement. In this situation, it’s challenging for us to provide a solid theoretical analysis within the tight rebuttal period. We will try to add further analysis in the final draft. Here, we would like to give some intuition and empirical proof for the effectiveness and soundness of the proposed method:

• The global attack makes CNF diverse to benefit policy exploration, and it is stronger than the local attack in terms of attacking the ensemble of models. 1) Diverseness: The global attack is a generalization of the local attack, which means the local attack could be viewed as a kind of global attack when the same model is repeatedly used to generate adversarial examples in each attack iteration. Therefore, by leveraging different model parameters during the attack, the adversarial instances generated by global adversaries can be more diverse than those only generated by local adversaries. 2) Strongness: The collaborative performance of CNF depends on the best-performing model $θ_b$ (w.r.t. each instance) since its solution will be chosen as the final solution during inference. In CNF, the goal of inner maximization is to construct adversarial instances that can successfully fool the entire framework. Intuitively, if we choose to attack other models rather than $θ_b$, the constructed adversarial instances may not successfully fool $θ_b$, and therefore the final solution to the adversarial instance could still be good, which contradicts the goal of the inner maximization. Therefore, to increase the success rate of attacking the CNF framework, for each clean instance, we propose the global adversary and choose the corresponding best-performing model $θ_b$ to be attacked in each iteration of the inner maximization. To empirically justify it, we record the training dynamics of CNF (3) at the middle stage of training on TSP100. We observe that the global adversary could maximally degrade the model performance by increasing the optimality gap to 0.52% while the local adversary could only degrade the model to 0.37%. Please note that a smaller optimality gap denotes a weaker attack.

• The neural router empowers CNF to reasonably exploit the overall model capacity. Intuitively, by distributing instances to suitable models for training, each model might be stimulated to have its own expert area. Accordingly, the overlap of their vulnerability areas may be decreased, which could promote the collaborative performance of CNF. As shown in Fig. 5, not all models perform well on each kind of instance. Such diversity in model expertise contributes to the mitigation of the trade-off between standard generalization and adversarial robustness, thereby significantly outperforming vanilla AT with multiple models.

In summary, instead of independently training multiple models, the effectiveness of the proposed collaboration mechanism in CNF can be attributed to its diverse adversarial data generation and the reasonable exploit of overall model capacity. As shown in the ablation study (Fig. 3(a)), the diverse adversarial data generation is helpful in further improving the adversarial robustness (see results of CNF vs. W/O Global Attack). Meanwhile, the neural router has a bigger effect in mitigating the trade-off (see results of CNF vs. W/O Router). Both components contribute to the power of CNF, thereby significantly outperforming other baselines.