Collaboration! Towards Robust Neural Methods for Routing Problems

Authors: jianan  zhou
yaoxin  wu
zhiguang  cao
wen  song
jie  zhang
zhiqi  shen
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-03 14:14:49

Abstract: Despite enjoying desirable efficiency and reduced reliance on domain expertise, existing neural methods for vehicle routing problems (VRPs) suffer from severe robustness issues — their performance significantly deteriorates on clean instances with crafted perturbations. To enhance robustness, we propose an ensemble-based *Collaborative Neural Framework (CNF)* w.r.t. the defense of neural VRP methods, which is crucial yet underexplored in the literature. Given a neural VRP method, we adversarially train multiple models in a collaborative manner to synergistically promote robustness against attacks, while boosting standard generalization on clean instances. A neural router is designed to adeptly distribute training instances among models, enhancing overall load balancing and collaborative efficacy. Extensive experiments verify the effectiveness and versatility of CNF in defending against various attacks across different neural VRP methods. Notably, our approach also achieves impressive out-of-distribution generalization on benchmark instances.

Main paper: 
 introduction: 
 Combinatorial optimization problems (COPs) are crucial yet challenging to solve due to the NPhardness. Neural combinatorial optimization (NCO) aims to leverage machine learning (ML) to automatically learn powerful heuristics for solving COPs, and has attracted considerable attention recently [2] . Among them, a large number of NCO works develop neural methods for vehicle routing problems (VRPs) -one of the most classic COPs with broad applications in transportation [54] , logistics [35] , planning and scheduling [52] , etc. With various training paradigms (e.g., reinforcement learning (RL)), the neural methods learn construction or improvement heuristics, which achieve competitive or even superior performance to the conventional algorithms. However, recent studies show that these neural methods are plagued by severe robustness issues [20] , where their performance drops devastatingly on clean instances (sampled from the training distribution) with crafted perturbations.Although the robustness issue has been investigated in a couple of recent works [87, 20, 42] , the defensive methods on how to help forge sufficiently robust neural VRP methods are still underexplored. [38] on TSP100 against the attacker in [87] . The value in brackets denotes the number of trained models. We report the average optimality (opt.) gap over 1000 test instances. (c) Solution visualizations on an adversarial instance. These results reveal the vulnerability of existing neural methods to adversarial attacks, and the existence of undesirable trade-off between standard generalization (a) and adversarial robustness (b) in VRPs. Details of the attacker and experimental setups can be found in Appendix B.1 and Section 5, respectively.In particular, existing endeavours mainly focus on the attack2 side, where they propose different perturbation models to generate adversarial instances. On the defense side, they simply follow the vanilla adversarial training (AT) [48] . Concretely, treated as a min-max optimization problem, it first generates adversarial instances that maximally degrade the current model performance, and then minimizes the empirical losses of these adversarial variants. However, vanilla AT is known to face an undesirable trade-off [66, 85] between standard generalization (on clean instances) and adversarial robustness (against adversarial instances). As demonstrated in Fig. 1 , vanilla AT improves adversarial robustness of the neural VRP method at the expense of standard generalization (e.g., POMO (1) vs. POMO_AT (1)). One key reason is that the training model is not sufficiently expressive [20] . We empirically justify this viewpoint by increasing the model capacity through ensembling multiple models, which partially alleviates the trade-off. However, it is still an open question on how to effectively synergize multiple models to achieve favorable overall performance on both clean and adversarial instances within a reasonable computational budget.In this paper, we focus on the defense of neural VRP methods, aiming to concurrently enhance both the standard generalization and adversarial robustness. We resort to the ensemble-based AT method to achieve this objective. Instead of separately training multiple models, we propose a Collaborative Neural Framework (CNF) to exert AT on multiple models in a collaborative manner. Specifically, in the inner maximization optimization of CNF, we synergize multiple models to further generate the global adversarial instance for each clean instance by attacking the best-performing model, rather than only leveraging each model to independently generate their own local adversarial instances. In doing so, the generated adversarial instances are diverse and strong in benefiting the policy exploration and attacking the models, respectively (see Section 4). In the outer minimization optimization of CNF, we train an attention-based neural router to forward instances to models for effective training, which helps achieve satisfactory load balancing and collaborative efficacy.Our contributions are outlined as follows. 1) In contrast to the recent endeavors on the attack side, we concentrate on the defense of neural VRP methods, which is crucial yet underexplored in the literature. We empirically observe that the defense through vanilla AT may lead to the undesirable trade-off between standard generalization and adversarial robustness in VRPs. 2) We propose an ensemble-based collaborative neural framework to concurrently enhance the performance on both clean and adversarial instances. Specifically, we propose to further generate global adversarial instances, and design an attention-based neural router to distribute instances to each model for effective training. 3) We evaluate the effectiveness and versatility of our method against various attacks on different VRPs, such as the symmetric and asymmetric traveling salesman problem (TSP, ATSP) and capacitated vehicle routing problem (CVRP). Results show that our framework can greatly improve the adversarial robustness of neural methods while even boosting the standard generalization. Beyond the expectation, we also observe the improved out-of-distribution (OOD) generalization on both synthetic and benchmark instances, which may suggest the favorable potential of our method in promoting various types of generalization of neural VRP methods.There is a recent research trend on the robustness of neural methods for COPs [68, 20, 42] , with only a few works on VRPs [87, 20, 42] . In general, they primarily focus on attacking neural construction heuristics by introducing effective perturbation models to generate adversarial instances that are underperformed by the current model. Following the AT paradigm, [87] perturbs node coordinates of TSP instances by solving an inner maximization problem (similar to the fast gradient sign method [22] ), and trains the model with a hardness-aware instance-reweighted loss function. [20] proposes an efficient and sound perturbation model, which ensures the optimal solution to the perturbed TSP instance can be directly derived. It adversarially inserts several nodes into the clean instance by maximizing the cross-entropy over the edges, so that the predicted route is maximally different from the derived optimal one. [42] leverages a noworse optimal cost guarantee (i.e., by lowering the cost of a partial problem) to generate adversarial instances for asymmetric TSP. However, existing methods mainly follow vanilla AT [48] to deploy the defense, leaving a considerable gap to further consolidate robustness.Robustness in Other Domains. Deep neural networks are vulnerable to adversarial examples [22] , spurring the development of numerous attack and defensive methods to mitigate the arisen security issue across various domains. 1) Vision: Early research on adversarial robustness mainly focus on the continuous image domain (e.g., at the granularity of pixels). The vanilla AT, as formulated by [48] through min-max optimization, has inspired significant advancements in the field [65, 60, 85, 7, 86] . 2) Language: This domain investigates how malicious inputs (e.g., characters and words) can deceive (large) language models into making incorrect decisions or producing unintended outcomes [14, 72, 50, 91, 74] . Challenges include the discrete nature of natural languages and the complexity of linguistic structures, necessitating sophisticated techniques for generating and defending against adversarial attacks. 3) Graph: Graph neural networks are also susceptible to adversarial perturbations in the underlying graph structures [92] , prompting research to enhance their robustness [29, 15, 19, 23, 63] . Similar to the language domain, challenges stem from the discrete nature of graphs and the interconnected nature of graph data. Although various defensive methods have been proposed for these specific domains, most are not adaptable to the VRP (or COP) domain due to their needs for ground-truth labels, reliance on the imperceptible perturbation model, and unique challenges inherent in combinatorial optimization. 
limitations: 
 Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: The limitations are discussed in see Section 6.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
neural vrp methods: 
 Problem Definition. Without loss of generality, we define a VRP instance x over a graph G = {V, E}, where V = {v i } n i=1 represents the node set, and(v i , v j ) ∈ E represents the edge set with v i ̸ = v j .The solution τ to a VRP instance is a tour, i.e., a sequence of nodes in V. The cost function c(•) computes the total length of a given tour. The objective is to seek an optimal tour τ * with the minimal cost: τ * = arg min τ ∈Φ c(τ |x), where Φ is the set of all feasible tours which obey the problem-specific constraints. For example, a feasible tour in TSP should visit each node exactly once, and return to the starting node in the end. For CVRP, each customer node in V is associated with a demand δ i , and a depot node v 0 is additionally added into V with δ 0 = 0. Given the capacity Q for each vehicle, a tour in CVRP consists of multiple sub-tours, each of which represents a vehicle starting from v 0 , visiting a subset of nodes in V and returning to v 0 . It is feasible if each customer node in V is visited exactly once, and the total demand in each sub-tour is upper bounded by Q. The optimality gap c(τ )-c(τ * )c(τ * )× 100% is used to measure how far a solution is from the optimal solution.Autoregressive Construction Methods. Popular neural methods [37, 38] construct a solution to a VRP instance following Markov Decision Process (MDP), where the policy is parameterized by a neural network with parameters θ. The policy takes the states as inputs, which are instantiated by features of the instance and the partially constructed solution. Then, it outputs the probability distribution of valid nodes to be visited next, from which an action is taken by either greedy rollout or sampling. After a complete tour τ is constructed, the probability of the tour can be factorized via the chain rule as p θ (τ |x) = S s=1 p θ (π s θ |π <s θ , x), where π s θ and π <s θ represent the selected node and the partial solution at the s th step, and S is the number of total steps. Typically, the reward is defined as the negative length of a tour -c(τ |x). The policy network is commonly trained with REINFORCE [75] . With a baseline function b(•) to reduce the gradient variance and stabilize the training, it estimates the gradient of the expected reward as:∇ θ L(θ|x) = E p θ (τ |x) [(c(τ ) -b(x))∇ θ log p θ (τ |x)].(1)Adversarial training is one of the most effective and practical techniques to equip deep learning models with adversarial robustness against crafted perturbations on the clean instance. In the supervised fashion, where the clean instance x and ground truth (GT) label y are given, AT is commonly formulated as a min-max optimization problem:EQUATIONwhere D is the data distribution; ℓ is the loss function; f θ (•) is the model prediction with parameters θ; N ϵ [x] is the neighborhood around x, with its size constrained by the attack budget ϵ. The solution to the inner maximization is typically approximated by projected gradient descent:EQUATIONwhere α is the step size; Π is the projection operator that projects the adversarial instance back to the neighborhood N ϵ [x]; x (t) is the adversarial instance found at step t; and the sign operator is used to take the gradient direction and carefully control the attack budget. Typically, x (0) is initialized by the clean instance or randomly perturbed instance with small Gaussian or Uniform noises. The adversarial instance is updated iteratively towards loss maximization until a stop criterion is satisfied.AT for VRPs. Most ML research on adversarial robustness focuses on the continuous image domain [22, 48] . We would like to highlight two main differences in the context of discrete VRPs (or COPs). 1) Imperceptible perturbation: The adversarial instance x is typically generated within a small neighborhood of the clean instance x, so that the adversarial perturbation is imperceptible to human eyes. For example, the adversarial instance in image related tasks is typically bounded by N ϵ [x] : ∥x -x∥ p ≤ ϵ under the l p norm threat model. When the attack budget ϵ is small enough, x retains the GT label of x. However, it is not the case for VRPs due to the nature of discreteness. The optimal solution can be significantly changed even if only a small part of the instance is modified. Therefore, the subjective imperceptible perturbation is not a realistic goal in VRPs, and we do not exert such an explicit imperceptible constraint on the perturbation model (see Appendix A for further discussions). In this paper, we set the attack budget within a reasonable range based on the attack methods. 2) Accuracy-robustness trade-off: The standard generalization and adversarial robustness seem to be conflicting goals in image related tasks. With increasing adversarial robustness the standard generalization tends to decrease, and a number of works intend to mitigate such a trade-off in the image domain [66, 85, 73, 57, 80] . By contrast, a recent work [20] "" "# "$ $" $# $$ # " "," (') # " ",# (') # " ",$ (') " " # * + , $ " $" $" $ # $# $$ $" $# $$ ̅ " " (") ̅ " # (") ̅ " $ (") ̅ " " (') ̅ " # (') ̅ " $ (') ℒ "" "# $" $# $$ "" # " "," ̅ " " ̅ "$ Figure 2:The overview of CNF. Suppose we train M = 3 models (Θ = {θ 1 , θ 2 , θ 3 }) on a batch (B = 3) of clean instances. The inner maximization generates local (x) and global (x) adversarial instances within T steps. In the outer minimization, a neural router θ r is jointly trained to distribute instances to the M models for training. Specifically, based on the logit matrix P predicted by the neural router, each model selects the instances with TopK-largest logits (e.g., red ones). The neural router is optimized to maximize the improvement of collaborative performance after each training step of Θ. For simplicity, we omit the superscripts of instances in the outer minimization. neural solvers with high accuracy and robustness in COPs. They state that a sufficiently expressive model does not suffer from the trade-off given the problem-specific efficient and sound perturbation model, which guarantees the correct GT label of the perturbed instance. However, by following the vanilla AT, we empirically observe that the undesirable trade-off may still exist in VRPs (as shown in Fig. 1 ), which is mainly due to the insufficient model capacity under the specific perturbation model. Furthermore, similar to combinatorial optimization, although the language and graph domains are also discrete, their methods cannot be trivially adapted to VRPs (see Appendix A).Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [NA]• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
collaborative neural framework: 
 In this section, we first present the motivation and overview of the proposed framework, and then introduce the technical details. Overall, we propose a collaborative neural framework to synergistically promote adversarial robustness among multiple models, while boosting standard generalization. Since conducting AT for deep learning models from scratch is computationally expensive due to the extra inner maximization steps, we use the model pretrained on clean instances as a warm-start for subsequent AT steps. An overview of the proposed method is illustrated in Fig. 2 .Motivation. Motivated by the empirical observations that 1) existing neural VRP methods suffer from severe adversarial robustness issue; 2) undesirable trade-off between adversarial robustness and standard generalization may exist when following the vanilla AT, we propose to adversarially train multiple models in a collaborative manner to mitigate the above-mentioned issues within a reasonable computational budget. It then raises the research question on how to effectively and efficiently train multiple models under the AT framework, involving a pair of inner maximization and outer minimization, which will be detailed in the following parts. Note that despite the accuracy-robustness trade-off being a well-known research problem in the literature of adversarial ML, most works focus on the image domain. Due to the needs for GT labels or the dependence on the imperceptible perturbation model, their methods (e.g., TRADES [85] , Robust Self-Training with AT [57] ) cannot be directly leveraged to solve this trade-off in VRPs. We refer to Appendix A for further discussions.Overview. Given a pretrained model θ p , CNF deploys the AT on its M copies (i.e., Θ (0) = {θ (0) j } M j=1 ← θ p ) in a collaborative manner. Concretely, at each training step, it first solves the inner maximization optimization to synergistically generate the local (x) and global (x) adversarial instances, on which the current models underperform. Then, in the outer minimization optimization, we jointly train an attention-based neural router θ r with all models Θ by RL in an end-to-end manner. By adaptively distributing instances to different models for training, the neural router can reasonably exploit the overall capacity of models and thus achieve satisfactory load balancing and collaborative efficacy. During inference, we discard the neural router θ r and use the trained models Θ to solve eachInput: training steps: E, number of models: M , attack steps: T , batch size: B, pretrained model: θp; Output: robust model set with the gradient ∇ θ (e-1) r L using Eq. ( 6) 16: end for instance. The best solution among them is returned to reflect the final collaborative performance. We present the pseudocode of CNF in Algorithm 1, and elaborate each part in the following subsections.EQUATIONThe inner maximization aims to generate adversarial instances for the training in the outer minimization, which should be 1) effective in attacking the framework; 2) diverse to benefit the policy exploration for VRPs. Typically, an iterative attack method generates local adversarial instances for each model only based on its own parameter (e.g., the same θ in Eq. ( 3) is repetitively used throughout the generation). Such local attack (line 6) only focuses on degrading each individual model, failing to consider the ensemble effect of multiple models. Due to the existence of multiple models in CNF, we are motivated to further develop a general form of local attack -global attack (line [7] [8] , where each adversarial instance can be generated using different model parameters within T generation steps. Concretely, given each clean instance x, we generate the global adversarial instance x by attacking the corresponding best-performing model in each iteration of the inner maximization. In doing so, compared with the sole local attack, the generated adversarial instances are more diverse to successfully attack the models Θ (see Appendix A for further discussions). Without loss of generality, we take the attacker from [87] as an example, which directly maximizes the variant of the reinforcement loss as follows:EQUATIONwhere b(•) is the baseline function (as shown in Eq. ( 1)). On top of it, we generate the global adversarial instance x such that:EQUATIONwhere x(t) is the global adversarial instance and θ(t)b is the best-performing model (w.r.t. x(t) ) at step t. If x(t) is out of the range, it would be projected back to the valid domain N by Π, such as the min-max normalization for continuous variables (e.g., node coordinates) or the rounding operation for discrete variables (e.g., node demands). We discard the sign operator in Eq. (3) to relax the imperceptible constraint. More details are presented in Appendix B.1.In summary, the local attack is a special case of the global attack, where the same model is chosen as θ b in each iteration. While the local attack aims to degrade a single model θ, the global attack can be viewed as explicitly attacking the collaborative performance of all models Θ, which takes into consideration the ensemble effect by attacking θ b . In CNF, we involve adversarial instances that are generated by both the local and global attacks to pursue better adversarial robustness, while also including clean instances to preserve standard generalization.After the adversarial instances are generated by the inner maximization, we collect a set of instances X with |X | = N , which includes clean instances x, local adversarial instances x and global adversarial instances x, to train M models. Here a key problem is that how are the instances distributed to models for their training, so as to achieve satisfactory load balancing (training efficiency) and collaborative performance (effectiveness)? To solve this, we design an attention-based neural router, and jointly train it with all models Θ to maximize the improvement of collaborative performance.Concretely, we first evaluate each model on X to obtain a cost matrix R ∈ R N ×M . The attentionbased neural router θ r takes as inputs the instances X and R, and outputs a logit matrix f θr (X , R) = P ∈ R N ×M , where f is the decision function. Then, we apply Softmax function along the first dimension of P to obtain the probability matrix P, where the entity Pij represents the probability of the i th instance being selected for the outer minimization of the j th model. For each model, the neural router distributes the instances with TopK-largest predicted probabilities as a batch for its training (line 10-13). In doing so, all models have the same amount (K) of training instances, which explicitly ensures the load balancing (see Appendix A). We also discuss other strategies of instance distributing, such as sampling, instance-based choice, etc. More details can be found in Section 5.2.After all models Θ are trained with the distributed instances, we further evaluate each model on X , obtaining a new cost matrix R ′ ∈ R N ×M . To pursue desirable collaborative performance, it is expected that the neural router θ r can reasonably exploit the overall capacity of models. Since the action space of θ r is huge and the models Θ are changing throughout the training, we resort to the reinforcement learning (based on trial-and-error) to optimize parameters of the neural router θ r (line 14-15). Specifically, we set (min R -min R ′ ) as the reward signal, and update θ r by gradient ascent to maximize the expected return with the following approximation:EQUATIONwhere the min operator is applied along the last dimension of R and R ′ , since we would like to maximize the improvement of collaborative performance after training with the selected instances. Intuitively, if an entity in (min R -min R ′ ) is positive, it means that, after training with the selected instances, the collaborative performance of all models on the corresponding instance is increased. Thus, the corresponding action taken by the neural router should be reinforced, and vice versa. For example, in Fig. 2 , if the reward entity for the first instance x 1 is positive, the probability of this action (i.e., the red one in the first row of P) will be reinforced after optimization. Note that the unselected (e.g., black ones) will be masked out in Eq. ( 6). In doing so, the neural router learns to effectively distribute instances and reasonably exploit the overall model capacity, such that the collaborative performance of all models can be enhanced after optimization. Further details on the neural router structure and the in-depth analysis of the learned routing policy are presented in Appendix C. 
experiments: 
 In this section, we empirically verify the effectiveness and versatility of CNF against attacks specialized for VRPs, and conduct further analyses to provide the underlying insights. Specifically, our experiments focus on two attack methods [87, 42] , since the accuracy-robustness trade-off exists when conducting vanilla AT to defend against them. We conduct the main experiments on POMO [38] with the attacker in [87] , and further demonstrate the versatility of the proposed framework on MatNet [39] with the attacker in [42] . More details on the experimental setups, data generation and additional empirical results (e.g., evaluation on large-scale instances) are presented in Appendix D. All experiments are conducted on a machine with NVIDIA V100S-PCIE cards and Intel Xeon Gold 6226 CPU at 2.70GHz. The source code is available at https://github.com/RoyalSkye/Routing-CNF.Baselines. 1) Traditional methods: we solve TSP instances by Concorde and LKH3 [25] , and CVRP instances by hybrid genetic search (HGS) [70] and LKH3. 2) Neural methods: we compare our method with the pretrained base model POMO (∼1M parameters), and its variants training with various defensive methods, such as the vanilla adversarial training (POMO_AT), the defensive method proposed by the attacker [87] (POMO_HAC), and the diversity training [32] from the literature of ensemble-based adversarial ML (POMO_DivTrain). Specifically, POMO_AT adversarially trains the models by first generating local adversarial instances in the inner maximization, and then minimizing their empirical risks in the outer minimization. POMO_HAC further improves the outer minimization by optimizing a hardness-aware instance-reweighted loss function on a mixed dataset, including both clean and local adversarial instances. POMO_DivTrain improves the ensemble diversity by minimizing the cosine similarity between the gradients of models w.r.t. the input. Furthermore, we also compare our method with CNF_Greedy by replacing the neural router with a heuristic greedy selection method, and another advanced ensemble-based AT method TRS [81] (see Appendix D.6). More implementation details of baselines are provided in Appendix D.1.Training Setups. CNF starts with a pretrained model, and then adversarially trains its M copies in a collaborative way. We consider two scales of training instances n ∈ {100, 200}. For the pretraining stage, the model is trained on clean instances following the uniform distribution. We use the open-source pretrained POMO for n = 100, and retrain the model for n = 200. Following the original training setups from [38] , Adam optimizer is used with the learning rate of 1e -4, the weight decay of 1e -6 and the batch size of B = 64. To achieve full convergence, we pretrain the model on 300M and 100M clean instances for TSP200 and CVRP200, respectively. After obtaining the pretrained model, we use it to initialize M = 3 models, and further adversarially train them on 5M and 2.5M instances for n = 100 and n = 200, respectively. To save the GPU memory, we reduce the batch size to B = 32 for n = 200. The optimizer setting is the same as the one employed in the pretraining stage, except that the learning rate is decayed by 10 for the last 40% training instances. For the mixed data collection, we collect B clean instances, M B local adversarial instances and B global adversarial instances in each training step.Inference Setups. For neural methods, we use the greedy rollout with x8 instance augmentations following [38] . We report the average gap over the test dataset containing 1K instances. Concretely, the gap is computed w.r.t. the traditional VRP solvers (i.e., Concorde for TSP, and HGS for CVRP). If multiple models exist, we report the collaborative performance, where the best gap among all models is recorded for each instance. The reported time is the total time to solve the entire dataset. We consider three evaluation metrics: 1) Uniform (standard generalization): the performance on clean instances whose distributions are the same as the pretraining ones; 2) Fixed Adv. (adversarial robustness): the performance on adversarial instances generated by attacking the pretrained model. It mimics the black-box setting, where the attacker generates adversarial instances using a surrogate model due to the inaccessibility to the current model and the transferability of adversarial instances; 3) Adv. (adversarial robustness): the performance on adversarial instances generated by attacking the current model. For a neural method with multiple (M ) models, it generates M K adversarial instances, from which we randomly sample 1K instances to construct the test dataset. It is the conventional white-box metric used to evaluate adversarial robustness in the literature of AT.The results are shown in Table 1 . We have conducted t-test with the threshold of 5% to verify the statistical significance. For all neural methods, we report the inference time on a single GPU. More- over, for neural methods with multiple (M ) models (e.g., CNF (3)), we develop an implementation of parallel evaluation on multiple GPUs, which can further reduce their inference time by almost M times. From the results, we observe that 1) traditional VRP methods are relatively more robust than neural methods against crafted perturbations, demonstrating the importance and necessity of improving adversarial robustness for neural methods; 2) the evaluation metrics of Fixed Adv. and Adv. are almost consistent in the context of VRPs; 3) our method consistently outperforms baselines, and achieves high standard generalization and adversarial robustness concurrently. For CNF, we show the performance of each model on TSP100 in Fig. 5 . Although not all models excel well on both clean and adversarial instances, the collaborative performance is quite good, demonstrating diverse expertise of models and the capability of CNF in reasonably exploiting the overall model capacity.We conduct extensive ablation studies on TSP100 to demonstrate the effectiveness and sensitivity of our method. Note that the setups are slightly different from the training ones (e.g., half training instances). The detailed results and setups are presented in Fig. 3 and Appendix D.1, respectively.Ablation on Components. We investigate the role of each component in CNF by removing them separately. As demonstrated in Fig. 3 (a), despite both components contribute to the collaborative performance, the neural router exhibits a bigger effect due to its favorable potentials to elegantly exploit training instances and model capacity, especially in the presence of multiple models.Ablation on Hyperparameters. We investigate the effect of the number of trained models, which is a key hyperparameter of our method, on the collaborative performance. The results are shown in Fig. 3(b) , where we observe that increasing the number of models can further improve the collaborative performance. However, we use M = 3 in the main experiments due to the trade-off between empirical performance and computational complexity. We refer to Appendix D.4 for more results.Ablation on Routing Strategies. We further discuss different routing strategies, including neural and heuristic ones. Specifically, given the logit matrix P predicted by the neural router, there are various ways to distribute instances: 1) Model choice with TopK (M-TopK): each model chooses potential instances with TopK-largest logits, which is the default strategy (K = B) in CNF; 2) Model choice with sampling (M-Sample): each model chooses potential instances by sampling from the probability distribution (i.e., scaled logits); 3-4) Instance choice with TopK/sampling (I-TopK/I-Sample): in contrast to the model choice, each instance chooses potential model(s) either by TopK or sampling.The probability matrix P is obtained by taking Softmax along the first and last dimension of P for model choice and instance choice, respectively. Unlike the model choice, instance choice cannot guarantee load balancing. For example, the majority of instances may choose a dominant model (if exists), leaving the remaining models underfitting and therefore weakening the ensemble effect and collaborative performance; 5) Random: instances are randomly distributed to each model; 6) Self-training: each model is trained on adversarial instances generated by itself without instance distributing. The results in Fig. 3(c ) show that M-TopK performs the best.In contrast to other domains (e.g., vision), the set of valid problems is not just a low-dimensional manifold in a high-dimensional space, and hence the manifold hypothesis [62] does not apply to VRPs (or COPs). Therefore, it is critical for neural methods to perform well on adversarial instances when striving for a broader out-of-distriburion (OOD) generalization in VRPs. In this section, we 2 , from which we observe that simply conducting the vanilla AT somewhat hurts the OOD generalization, while CNF can significantly improve it. Since adversarial robustness is known as a kind of local generalization property [22, 48] , the improvements in OOD generalization can be viewed as a byproduct of defending against adversarial attacks and balancing the accuracy-robustness trade-off.Benchmark Datasets. We further evaluate all neural methods on the real-world benchmark datasets, such as TSPLIB [58] and CVRPLIB [67] . We choose representative instances within the range of n ∈ [100, 1002]. The results, presented in Tables 9 and 10 , demonstrate that our method performs well across most instances. Note that all neural methods are only trained on n = 100.To demonstrate the versatility of CNF, we extend its application to MatNet [39] to defend against another attacker in [42] . Specifically, it constructs the adversarial instance by lowering the cost of a partial clean asymmetric TSP (ATSP) instance. When adhering to the vanilla AT, the undesirable trade-off is also observed in the empirical results of [42] . In contrast, our method enables models to achieve both high standard generalization and adversarial robustness. The detailed attack method, training setups, and empirical results are presented in Appendix B.3, D.1 and D.3, respectively. 
conclusion: 
 This paper studies the crucial yet underexplored adversarial defense of neural VRP methods, filling the gap in the current literature on this topic. We propose an ensemble-based collaborative neural framework to concurrently enhance performance on clean and adversarial instances. Extensive experiments demonstrate the effectiveness and versatility of our method, highlighting its potential to defend against attacks while promoting various forms of generalization of neural VRP methods. Additionally, our work can be viewed as advancing the generalization of neural methods through the lens of adversarial robustness, shedding light on the possibility of building more robust and generalizable neural VRP methods in practice.The limitation of this work is the increased computational complexity due to the need to synergistically train multiple models. Fortunately, based on experimental results, CNF with just three models has already achieved commendable performance. It even surpasses vanilla AT trained with nine models, demonstrating a better trade-off between empirical performance and computational complexity.Interesting future research directions may include: 1) designing efficient and effective attack or defense methods for other COPs; 2) pursuing better robustness with fewer computation, such as through conditional computation and parameter sharing; 3) theoretically analyzing the robustness of neural VRP methods, such as certified robustness; 4) investigating the potential of large language models to robustly approximate optimal solutions to COP instances. Intuitively, by distributing instances to suitable submodels for training, each submodel might be stimulated to have its own expertise. 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. The expertise of θ 0 lies primarily in handling clean instances, whereas θ 1 specializes in dealing with adversarial instances. Such diversity in submodels contributes to the collaborative efficacy of Θ and the mitigation of the undesirable trade-off between standard generalization and adversarial robustness, thereby significantly outperforming vanilla AT with multiple models.Why using Best-performing Model for Global Attack? The collaborative performance of our framework depends on the best-performing model θ b w.r.t. each instance, since its solution will be chosen as the final solution during inference. The goal of inner maximization is to construct the adversarial instance that can successfully fool the framework. Intuitively, if we choose to attack other models (rather than θ b ), the constructed adversarial instances may not successfully fool the best-performing model θ b , and therefore the final solution to the adversarial instance could still be good, which contradicts the goal of inner maximization. Therefore, to increase the success rate of attacking the framework and generate more diverse adversarial instances, for each instance, we choose the corresponding best-performing model θ b as the global model in each attack iteration.Divergence of Same Initial Models. We take POMO [38] as an example. During training, in each step of solution construction, the decoder of the neural solver selects the valid node to be visited by sampling from the probability distribution, rather than using the argmax operation. Even though we initialize all models using the same pretrained model, given the same attack hyperparameters (e.g., attack iterations), the adversarial instances generated by different models are generally not the same at the beginning of the training. Therefore, the same initial models can diverge to different models due to the training on different (adversarial) instances.Larger Model. In addition to training multiple models, increasing the number of parameters for a single model is another way of enhancing the overall model capacity. However, technically, 1) a larger model needs more GPU memory, which puts more requirements on a single GPU device. It is also more sophisticated to enable parallel training on multiple GPUs compared to the counterpart with multiple models; 2) currently, our method conducts AT upon the pretrained model, but there does not exist a larger pretrained model (e.g., larger POMO) in the literature. Despite the technical issues, we try to pretrain a larger POMO (i.e., 18 encoder layers with 3.64M parameters in total) on the uniform distributed data, and further conduct the vanilla AT. The performance is around 0.335% and 0.406% on clean and adversarial instances, respectively, which is inferior to the counterpart with multiple models (i.e., POMO_AT (3)). The superiority of multiple models may be attributed to its ensemble effect and the capacity in learning multiple diverse policies.Advanced AT Methods in Other Domains. In this paper, we mainly focus on the vanilla AT [48] . More advanced AT techniques, such as TRADES [85] , AT in RL [55] , and ensemble-based AT [65, 32, 53, 79, 81] can be further considered. However, some of them may not be applicable to the VRP domain due to their needs for ground-truth labels or the dependence on the imperceptible perturbation model. 1) TRADES is empirically effective for trading adversarial robustness off against standard generalization on the image classification task. Its loss function is formulated asL = CE(f (x), y) + βKL(f (x), f (x)), where CE is cross-entropy; KL is KL-divergence; x is a clean instance; x is an adversarial instance; f (x) is the logit predicted by the model; y is the ground-truth label; β is a hyperparameter. By explicitly making the outputs of the network (logits) similar for x and x, it can mitigate the accuracy-robustness trade-off. However, the above statement is contingent upon the imperceptible perturbation model, where the ground-truth labels of x and x are kept the same. As we discussed in Section 3.2, in the discrete VRPs, the perturbation model does not have such an imperceptible constraint, and the optimal solutions to x and x are not the same in the general case. Therefore, it does not make sense to make the outputs of the model similar for x and x. 2) Another interesting direction is AT in RL, where the focus is the attack side rather than the defense side (e.g., most of the design in [55] focuses on the adversarial agent). Specifically, it jointly trains another agent (i.e., the attacker or adversary), whose objective is to impede the first agent, to generate hard trajectories in a two-player zero-sum way. Its goal is to learn a policy that is robust to modeling errors in simulation or mismatch between training and test scenarios. In contrast, our work focuses on the defense side and aims to mitigate the trade-off between standard generalization and adversarial robustness. Moreover, this method is specific to RL while our framework has the potential to work with the supervised learning setting. Overall, it is non-trivial to directly apply this method to address our research problem (e.g., the trade-off). But it is an interesting future research direction to design attack methods specific to RL (e.g., by training another adversarial agent or attacking each step of MDP). 3) Similar to the proposed CNF, ensemble-based AT also leverages multiple models, but with a different motivation (e.g., reducing the adversarial transferability between models to defend against black-box adversarial attacks [79] ). Concretely, ADP [53] needs the ground-truth labels to calculate the ensemble diversity. DVERGE [79] depends on the misalignment of the distilled feature between the visual similarity and the classification result, and hence on the imperceptible perturbation model. Therefore, it is non-trivial to directly adapt them to the discrete VRP domain.DivTrain [32] proposes to decrease the gradient similarity loss to reduce the overall adversarial transferability between models, and TRS [81] further uses a model smoothness loss to improve the ensemble robustness. Technically, their methods are computational expensive due to the needs to keep the computational graph before taking an optimization step. We show their empirical results in Table 7 . Compared with others, their empirical results are not superior in VRPs. For example, for TSP100, POMO_TRS (3), which is adapted from [81] , achieves 0.098% and 0.528% on the metrics of Uniform and Fixed Adv., respectively, failing to mitigate the undesirable trade-off. We leave the discussion on defensive methods from other domains (e.g., language and graph) to Section 2.Attack Budget. As discussed in Section 3.2, we do not exert the imperceptible constraint on the perturbation model in VRPs. We further explain it from two perspectives: 1) different from other domains, there is no theoretical guarantee to ensure the invariance of the optimal solution (or groundtruth label), given an imperceptible perturbation. A small change on even one node's attribute may induce a totally different optimal solution. Therefore, we do not see the benefit of constraining the attack budget to a very small (i.e., imperceptible) range in VRP tasks. Moreover, even with the absence of the imperceptible constraint on the perturbation model, unlike the graph learning setting, we do not observe a significant degradation on clean performance. It reveals that we don't need explicit imperceptible perturbation to restrain the changes on (clean) objective values in VRPs. In our experiments, we set the attack budget within a reasonable range following the applied attack method (e.g., α ∈ [1, 100] for [87] ). Our experimental results show that the proposed CNF is able to achieve a favorable balance, given different attack methods and their attack budgets; 2) in VRPs (or COPs), all generated adversarial instances are valid problem instances regardless of how much they differ from the clean instances [20] . In this sense, the attack budget models the severity of a potential distribution shift between training data and test data. This highlights the differences to other domains (e.g., vision), where unconstrained perturbations may lead to non-realistic or invalid data. Technically, the various attack budgets can help to generate diverse adversarial instances for training.Considering the above aspects, we believe our adversarial setting, including diverse but valid problem instances, may benefit the VRP community in developing a more general and robust neural solver.With that said, this paper can also be viewed as an attempt to improve the generalization of neural VRP solvers from the perspective of adversarial robustness.Attack Scenarios and Practical Significance. Actually, there may not be a person or attacker to deliberately invade the VRP model in practice. However, the developers in a logistics enterprise should consider the adversarial robustness of neural solvers as a sanity check before deploying them in the real world. The adversarial attack can be viewed as a way of measuring the worst-case performance of neural solvers within the neighborhood of inputs. Without considering adversarial robustness, the neural solver may perform very poorly (see Fig. 1(c )) when the testing instance pattern in the real world is 1) different from the training one, and 2) similar to the adversarial one. For example, considering an enterprise like Amazon, when some new customers need to be added to the current configuration or instance, especially when their locations coincidentally lead to the adversarial instance of the current solver (i.e., the node insertion attack presented in Appendix B.2), the model without considering adversarial robustness may output a very bad solution, and thus resulting in unpleasant user experience and financial losses. Furthermore, one may argue that this robustness issue can be ameliorated by using other solvers, i.e., NCO alongside traditional heuristics. We would like to note that traditional solvers may be non-robust as well, as discussed in a recent work [42] . The availability of traditional solvers cannot be guaranteed for novel problems as well.The Selection Basis of Attackers. There are three attackers in the current VRP literature [87, 20, 42] .We select the attacker based on its generality. Specifically, 1) [20] is an early work that explicitly investigates the adversarial robustness in COPs. Their perturbation model needs to be sound and efficient, which means, given a clean instance and its optimal solution, the optimal solution to the adversarial instance can be directly derived without running a solver. However, this direct derivation requires unique properties and theorems of certain problems (e.g., the intersection theorem [9] for Euclidean-based TSP), and hence is non-trivial to generalize to more complicated VRPs (e.g., CVRP). Moreover, their perturbation model is limited to attack the supervised neural solver (i.e., ConvTSP [31] ), since it needs to construct the adversarial instance by maximizing the loss function so that the model prediction is maximally different from the derived optimal solution. While in VRPs, RL-based methods [37, 38] are more appealing since they can gain comparable performance without the need for optimal solutions. 2) [42] requires that the optimal solution to the adversarial instance is no worse than that to the clean instance in theory, which may limit the search space of adversarial instances. It focuses on the graph-based COPs (e.g., asymmetric TSP) and satisfies the requirement by lowering the cost of edges. Similar to [20] , their method is not easy to design for VRPs with more constraints. Moreover, they resort to the black-box adversarial attack method by training a reinforcement learning based attacker, which may lead to a higher computational complexity and relatively low success rate of attacking. Therefore, for better generality, we choose [87] as the attacker in the main paper, which can be applied to different VRP variants and popular VRP solvers [37, 38] . Moreover, we also evaluate the versatility of CNF against [42] as presented in Appendix D.3.Training Efficiency. As mentioned in Section 6, the limitation of the proposed CNF is the increased computational complexity due to the need to synergistically train multiple models. Concretely, we empirically observe that CNF requires more training time than the vanilla AT variants on TSP100 (e.g., POMO_AT (3) 32 hrs vs. CNF (3) 85 hrs). However, simply further training them cannot significantly increase their performance since the training process has nearly converged. For example, given roughly the same training time, POMO_AT achieves 0.246% and 0.278% while CNF achieves 0.118% and 0.236% on the metrics of Uniform and Fixed Adv., respectively. On the other hand, our training time is less than that of advanced AT methods (e.g., POMO_TRS (3) [81] needs around 94 hrs). The above comparison indicates that CNF can achieve a better trade-off to deliver superior results within a reasonable computational budget. Moreover, we find that the global attack generation consumes much more training time than the neural router (∼0.05 million parameters). During inference, the computational complexity of CNF only depends on the number of models, since the neural router is only activated during training, and is discarded afterwards. Therefore, all methods with the same number of trained models have the same inference time.Relationship between OOD Generalization and Adversarial Robustness in VRPs. Generally, the adversarial robustness measures the generalization capability of a model over the perturbed instance x in the proximity of the clean instance x. In the context of VRPs (or COPs), adversarial instances are neither anomalous nor statistical defects since they are valid problem instances regardless of how much they differ from the clean instance x [20] . In contrast to other domains (e.g., vision), 1) the attack budget models the severity of a potential distribution shift between training data and test data; 2) the set of valid problems is not just a low-dimensional manifold in a high-dimensional space, and hence the manifold hypothesis [62] does not apply to combinatorial optimization. Therefore, it is critical for neural VRP solvers to perform well on adversarial instances when striving for a broader OOD generalization. Based on experimental results, we empirically demonstrate that raising robustness against attacks through CNF favorably promotes various forms of generalization of neural VRP solvers (as shown in Section 5.3), indicating the potential existence of neural VRP solvers with high generalization and robustness concurrently.Robustness of Test-time Adaptation Methods. Test-time adaptation methods [26, 56, 82] 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 postprocessing 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. Furthermore, we conduct experiments on DIMES [56] and DeepACO [82] . The results are shown in Tables 3 and 4 , where we observe that 1) CNF 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 [77] , 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, attacking test-time adaption methods is a potential research direction, which we will leave to future work.  
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: Experiments compute resources are indicated in Section 5.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: This paper respects the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes]Justification: Please see Appendix E.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: Please see Appendix F.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: In this section, we first give a formal definition of adversarial instance in VRPs, and then present details of existing attack methods for neural VRP solvers, including perturbing input attributes [87] , inserting new nodes [20] , and lowering the cost of a partial problem instance to ensure no-worse theoretical optimum [42] . They can generate instances that are underperformed by the current model.We define an adversarial instance as the instance that 1) is obtained by the perturbation model within the neighborhood of the clean instance, and 2) is underperformed by the current model. Formally, given a clean VRP instance x = {x c , x d , σ}, where x c ∈ N c is the continuous variable (e.g., node coordinates) within the valid range N c ; x d ∈ N d is the discrete variable (e.g., node demand) within the valid range N d ; σ is the constraint, the adversarial instance x = {x c , xd , σ} is found by the perturbation model G around the clean instance x, on which the current model may be vulnerable. Technically, the adversarial instance x can be constructed by adding crafted perturbations γ to the corresponding attribute of the clean instance, and then project them back to the valid domain, e.g., xc = Π Nc (x c + α • γ xc ), where Π denotes the projection operator (e.g., min-max normalization); α denotes the attack budget. The crafted perturbations can be obtained by various perturbation models, such as the one in Eq. ( 7), γ xc = ∇ xc ℓ(x; θ), where θ is the model parameters; ℓ is the loss function. We omit the attack step t for notation simplicity. An illustration of generated adversarial instances is shown in Fig. 4 . Below, we follow the notations from the main paper, and detail each attack method. Figure 4 : An illustration of generated adversarial instances (i.e., the grey ones). (a) An adversarial instance generated by [87] on CVRP, where the triangle represents the depot node. A deeper color denotes a heavier node demand; (b) An adversarial instance generated by [20] on TSP, where the red nodes represent the newly inserted adversarial nodes; (c) An adversarial instance generated by [42] on asymmetric TSP, where the cost of an edge is in half.The attack generator from [87] is applied to attention-based models [37, 38] by perturbing attributes of input instances. As introduced in Section 4, it generates adversarial instances by directly maximizing the reinforcement loss variant (so called the hardness measure in [87] ). We take the perturbation on the node coordinate as an example. Suppose given the clean instance x (i.e., x(0) = x) and model parameter θ, the solution to the inner maximization can be approximated as follows:EQUATIONwhere x(t) is the (local) adversarial instances and θ (t) is the model parameters, at step t. Here we use N c to represent the valid domain of node coordinates (i.e., unit square U (0, 1)) for simplicity. After each iteration, it checks whetherx(t) = x(t) + α • ∇ x(t) ℓ(x (t) ; θ (t)) is within the valid domain N c or not. If it is out of N c , the projection operator (i.e., min-max normalization) is applied as follows:EQUATION)Note that it originally only focuses on TSP, where the node coordinates are perturbed. We further adapt it to CVRP by perturbing both the node coordinates and node demands. The implementation is straightforward, except that we set the valid domain of node demands as N d = {1, . . . , 9}. For the perturbations on node demands, the projection operator applies another round operation as follows:EQUATIONAn efficient and sound model is proposed by [20] , which, given the optimal solution y to the clean instance x sampled from the data distribution D, guarantees to directly derive the optimal solution ỹ to the adversarial instance x without running a solver. The attack is applied to the GCN [31] , which is a non-autoregressive construction method for TSP. It learns the probability of each edge occurring in the optimal solution (i.e., heat-map) with supervised learning. Following the AT framework, the objective function can be written as follows:EQUATIONwhere ℓ is the cross-entropy loss; G is the perturbation model that describes the possible perturbed instances x around the clean instance x; and h is used to derive the optimal solution ỹ based on (x, x, y) without running a solver. In the inner maximization, the adversarial instance x is generated by inserting several new nodes into x (below we take inserting one new node as an example), which adheres to below proposition and proof (by contradiction) borrowed from [20] :Proposition 1.Let Z / ∈ V be an additional node to be inserted, w(E) is an edge weight, and P, Q are any two neighbouring nodes in the original optimal solution y. Then, the new optimal solution ỹ (including Z) is obtained from y through inserting Z between P andQ if ∄(A, B) ∈ E \ {(P, Q)} with A ̸ = B s.t. w(A, Z) + w(B, Z) -w(A, B) ≤ w(P, Z) + w(Q, Z) -w(P, Q).Proof. Let (R, S) ∈ E \ {(P, Q)} to be two neighboring nodes of Z on ỹ. Assume w(P, Z) + w(Q, Z) -w(P, Q) < w(R, Z) + w(S, Z) -w(R, S) and the edges (P, Z) and (Q, Z) are not contained in ỹ (i.e., Z is inserted between R and S rather than P and Q).Below inequalities hold by the optimality of y and ỹ:EQUATIONEQUATIONTherefore, we have c(y) + w(P, Z) + w(Q, Z) -w(P, Q) ≥ c(ỹ) ≥ c(y) + w(R, Z) + w(S, Z) -w(R, S), (13) which leads to a contradiction against the assumption (i.e., w(P, Z) + w(Q, Z) -w(P, Q) < w(R, Z) + w(S, Z) -w(R, S)). The proof is completed.They use a stricter condition ∄(A, B) ∈ E \ {(P, Q)} with A ̸ = B s.t. w(A, Z) + w(B, Z)w(A, B) ≤ w(P, Z) + w(Q, Z) -w(P, Q) in the proposition, since it is unknown which nodes can be R and S in ỹ. Moreover, for the metric TSP, whose node coordinate system obeys the triangle inequality (e.g., euclidean distance), it is sufficient if the condition of Proposition 1 holds for (A, B) ∈ E \ ({(P, Q)} ∪ H) with A ̸ = B where H denotes the pairs of nodes both on the Convex Hull H ∈ CH(E) that are not a line segment of the Convex Hull. It is due to the fact that the optimal route ỹ must be a simple polygon (i.e., no crossings are allowed) in the metric space. This conclusion was first stated for the euclidean space as "the intersection theorem" by [9] and is a direct consequence of the triangle inequality.Based on the above-mentioned proposition, the optimization of inner maximization involves: 1) obtaining the coordinates of additional node Z by gradient ascending (e.g., maximizing l such that the model prediction is maximally different from the derived optimal solution ỹ); 2) penalizing if Z violates the constraint in Proposition 1. Unfortunately, the constraint is non-convex and hard to find a relaxation. Instead of optimizing the Lagrangian (which requires extra computation for evaluating f θ ), the vanilla gradient descent is leveraged with the constraint as the objective:EQUATION)where η is the step size. After we find Z satisfying the constraint, the adversarial instance x and the corresponding optimal solution ỹ can be constructed directly. Finally, the outer minimization takes (x, ỹ) as inputs to train the robust neural solvers. This attack method can be easily adopted by our proposed framework, where θ is replaced by the best model θ b when maximizing the cross-entropy loss (i.e., max x ℓ(f θ b (x), ỹ)) in the inner maximization optimization. However, due to the efficiency and soundness of the perturbation model, it does not suffer from the undesirable trade-off following the vanilla AT [20] . Therefore, we mainly focus on other attack methods [87, 42] .The attack method for graph-based COPs is proposed by [42] . It resorts to the black-box adversarial attack method by training a reinforcement learning based attacker, and thus can be used to generate adversarial instances for both differentiable (e.g., learning-based) and non-differentiable (e.g., heuristic or exact) solvers. In this paper, we only consider the learning-based neural solvers for VRPs. Specifically, it generates the adversarial instance x by modifying the clean instance x (e.g., lowering the cost of a partial instance) under the no worse optimum condition, which requires c(ỹ) ≤ c(y) if we are solving a minimization optimization problem. The attack is successful (w.r.t. the neural solver θ) if the output solution to x is worse than the one to x (i.e., c(τ |x; θ) > c(τ |x; θ) ≥ c(y) ≥ c(ỹ)).The training of the attacker is hence formulated as follows:EQUATIONwhere G(x, T ; θ) represents the deployment of the attacker G trained on the given model (or solver) θ to conduct T modifications on the clean instance x. It is trained with the objective as in Eq. ( 15) using the RL algorithm (i.e., Proximal Policy Optimization (PPO)). Specifically, the attack process is modelled as a MDP, where, at step t, the state is the current instance x(t) ; the action is to select an edge whose weight is going to be half; and the reward is the increase of the objective: c(τ (t+1) |x (t+1) ; θ) -c(τ (t) |x (t) ; θ). This process is iterative until T edges are modified. We use ROCO to represent this attack method in the remaining of this paper.ROCO has been applied to attack MatNet [39] on asymmetric TSP (ATSP). As shown in the empirical results of [42] , conducting the vanilla AT may suffer from the trade-off between standard generalization and adversarial robustness. To solve the problem, we further apply our method to defend against it. However, it is not straightforward to adapt ROCO to the inner maximization of CNF, since ROCO belongs to the black-box adversarial attack method, which does not directly rely on the parameters (or gradients) of the current model to generate adversarial instances. Concretely, we first train an attacker G j using RL for each model θ j , obtaining M attackers for M models (Θ = {θ j } M -1 j=0 ) in CNF. For the local attack, we simply use G j to generate local adversarial instances for θ j by G j (x, T ; θ j ). For the global attack, we decompose the generation process (i.e., modifying T edges) of a global adversarial instance x as follows:EQUATIONwhere x(t) is the global adversarial instance; θ is the attacker corresponding to θ(t) b , at step t ∈ [0, T -1].Since the model θ j is updated throughout the optimization, to save the computation, we fix the attacker G j and only update (by retraining) it every E epochs using the latest model. More details and results can be found in Appendix D.3.Without loss of generality, we take TSP as an example, where an instance consists of coordinates of n nodes. The attention-based neural router takes as inputs N instances X ∈ R N ×n×2 and a cost matrix R ∈ R N ×M , where M is the number of models in CNF. The neural router first embeds the raw inputs into h-dimensional (i.e., 128) features as follows:EQUATIONwhere F I ∈ R N ×h and F R ∈ R N ×h are features of instances and cost matrices, respectively; W 1 , W 2 are weight matrices; b 1 , b 2 are biases. The Mean operator is taken along the second dimension of inputs. Then, a single-head attention layer (i.e., glimpse [1] ) is applied:EQUATIONwhere [•, •] is the horizontal concatenation operator; Q ∈ R N ×h is the query matrix; K ∈ R M ×h is the key matrix; W Q , W K are the weight matrices; Emb(M ) ∈ R M ×h is a learnable embedding layer representing the features of M models. The logit matrix P ∈ R N ×M is calculated as follows:EQUATIONwhere the result is clipped by the tanh function with C = 10 following [1] . When the neural router is applied to CVRP, we only slightly modify Q by further concatenating it with the features of the depot and node demands, while keeping others the same.We attempt to briefly interpret the learned routing policy. We first show the performance of each model θ j ∈ Θ in CNF in the left panel of Fig. 5 , which is trained on TSP100 following the training setups presented in Section 5. Although not all models perform well on both clean and adversarial instances, the collaborative performance of Θ is quite good, demonstrating the diverse expertise of each model and the capability of CNF in reasonably exploiting the overall model capacity. We further give a demonstration (i.e., attention map) of the learned routing policy in the right panel of Fig. 5 .We take the first model θ 0 as an example, whose expertise lies in clean instances. For simplicity and readability of the results, the batch size is set to B = 3, and thus the number of input instances X for the neural router is 15. The neural router then distributes B = 3 instances to each model (if using model choice routing strategies). Note that the instances for different epochs are not the same, while the types remain the same (e.g., instances with ids 0-2 are clean instances). From the results, we observe that 1) the learned policy tends to distribute all types of instances to each model in a balanced way at the beginning of training, when the model is vulnerable to adversarial instances; 2) clean instances are more likely to be selected at the end of training, when the model is relatively robust to adversarial instances while trying to mitigate the accuracy-robustness trade-off.Setups for Baselines. We compare our method with several strong traditional and neural VRP methods. Following the conventional setups in the community [37, 38, 26] , for specialized heuristic solvers such as Concorde, LKH3 and HGS, we run them on 32 CPU cores for solving TSP and CVRP instances in parallel, while running neural methods on one GPU card. Below, we provide the implementation details of baselines. 1) Concorde: We use Concorde Version 03.12.19 with the default setting, to solve TSP instances. 2) LKH3 [25] : We use LKH3 Version 3.0.8 to solve TSP and CVRP instances. For each instance, we run LKH3 with 10000 trails and 1 run. 3) HGS [70] : We run HGS with the default hyperparameters to solve CVRP instances. The maximum number of iterations without improvement is set to 20000. 4) For POMO [38] , beyond the open-source pretrained model, we further train it using the vanilla AT framework (POMO_AT). Specifically, following the training setups presented in Section 5, we use the pretrained model to initialize M models, and train them individually using local adversarial instances generated by themselves. 5) POMO_HAC [87] further improves upon the vanilla AT. It constructs a mixed dataset with both clean instances and local adversarial instances for training afterwards. In the outer minimization, it optimizes an instancereweighted loss function based on the instance hardness. Following their setups, the weight for each instance x i is defined as: w i = exp(F(H(x i ))/T )/ j exp(F(H(x j ))/T ), where F is the transformation function (i.e., tanh); T is the temperature controlling the weight distribution. starts from 20 and decreases linearly as the epoch increasing. The hardness H is computed following Eq. (4). 6) POMO_DivTrain is adapted from the diversity training [32] , which studies the ensemblebased adversarial robustness in the image domain by proposing a novel method to train an ensemble of models with uncorrelated loss functions. Specifically, it improves the ensemble diversity by minimizing the cosine similarity between the gradients of (sub-)models w.r.t. the input. Its loss function is formulated as:L = ℓ + λ log( 1≤a<b≤M exp( <∇xℓa,∇xℓ b > |∇xℓa||∇xℓ b | )), where ℓ is the original loss function; M is the number of models; ∇ x ℓ a is the gradient of the loss function (on the a th model) w.r.t. the input x; λ = 0.5 is a hyperparameter controlling the importance of gradient alignment during training. 7) CNF_Greedy: the neural router is simply replaced by the heuristic method, where each model selects K hardest instances. We use [87] as the attack method in Section 5. For training efficiency, we set T = 1 in the main experiments. The step size α is randomly sampled from 1 to 100.Setups for Ablation Study. We conduct extensive ablation studies on components, hyperparameters and routing strategies as shown in Section 5. For simplicity, we slightly modified the training setups. We train all methods using 2.5M TSP100 instances. The learning rate is decayed by 10 for the last 20% training instances. For the ablation on components (Fig. 3(a) ), we set the attack steps as T = 2, and remove each component separately to demonstrate the effectiveness of each component in our proposed framework. For the ablation on hyperparameters (Fig. 3(b )), we train multiple models with M ∈ {2, 3, 4, 5}. For the ablation on routing strategies (Fig. 3(c )), we set K = B for M-TopK, where B = 64 is the batch size, and K = 1 for I-TopK. The other training setups remain the same.Setups for Versatility Study. For the pretraining stage, we train MatNet [39] on 5M ATSP20 instances following the original setup from [39] . We further train a perturbation model by attacking it using reinforcement learning. Concretely, we use the dataset from [42] , consisting of 50 "tmat" class ATSP training instances that obey the triangle inequality, to train the perturbation model for 500 epochs. Adam optimizer is used with the learning rate of 1e -3. The maximum number of actions taken by the perturbation model is T = 10. After the pretraining stage, we use the pretrained model to initialize M = 3 models, and further adversarially train them. We fix the perturbation model and only update it using the latest model every E = 10 epochs (as discussed in Appendix B.3). After the 10 th epoch, there would be M perturbation models corresponding to M models. Following [42] , we use the fixed 1K clean instances for training. In the inner maximization, we generate M K local adversarial instances and 1K global adversarial instances using the perturbation models. However, since the perturbation model is not efficient (i.e., it needs to conduct beam search to find edges to be modified), we generate adversarial instances in advance and reuse them later. Then, in the outer minimization, we load all instances and distribute them to each model using the jointly trained neural router. The models are then adversarially trained for 20 epochs using the Adam optimizer with the learning rate of 4e -5, the weight decay of 1e -6, and the batch size of B = 100.We follow the instructions from [37] to generate synthetic instances. Concretely, 1) Uniform Distribution: The node coordinate of each node is uniformly sampled from the unit square U (0, 1), as shown in Fig. 6 (a). 2) Rotation Distribution: Following [6] , we mutate the nodes, which originally follow the uniform distribution, by rotating a subset of them (anchored in the origin of the Euclidean plane) as shown in Fig. 6(b ). The coordinates of selected nodes are transformed by multiplying them with a matrix cos(φ) sin(φ) -sin(φ) cos(φ), where φ ∼ [0, 2π] is the rotation angle. 3)Explosion Distribution: Following [6] , we mutate the nodes, which originally follow the uniform distribution, by simulating a random explosion. Specifically, we first randomly select the center of explosion v c (i.e., the hole as shown in Fig. 6 (c)). All nodes v i within the explosion radius R = 0.3 is moved away from the center of explosion with the form of v i = v c + (R + s) • vc-vi ||vc-vi|| , where s ∼ Exp(λ = 1/10) is a random value drawn from an exponential distribution.In this paper, we mainly consider the distribution of node coordinates. For CVRP instances, the coordinate of the depot node v 0 is uniformly sampled from the unit square U (0, 1). The demand Opt. Gap (%) Clean Adv . Figure 7 : Ablation study on Components.We further conduct the ablation study on CVRP. For simplicity, here we only consider investigating the role of each component in CNF by removing them separately. The experiments are conducted on CVRP100, and the setups are kept the same as the ones presented in Appendix D.1. The results are shown in Fig. 7 , which still verifies the effectiveness of the global attack and neural router in CNF.Here, we consider several advanced ensemble-based AT methods, such as ADP [53] , DVERGE [79] , TRS [81] . However, as we discussed in Appendix A, it is non-trivial to adapt ADP and DVERGE to the VRP domain due to their needs for ground-truth labels or the dependence on the imperceptible perturbation model. Therefore, we compare our method with TRS [81] , which improves upon Div-Train [32] . Concretely, it proposes to use the gradient similarity loss and another model smoothness loss to improve ensemble robustness. We follow the experimental setups presented in Section 5, and show the results of TSP100 in Table 7 . We observe that TRS achieves better standard generalization but much worse adversarial robustness, and hence fail to achieve a satisfactory trade-off in our setting. Moreover, TRS is more computationally expensive than CNF in terms of memory consumption, since it needs to keep the computational graph for all submodels before taking an optimization step. The distribution of generated adversarial instances depends on the attack method and its strength. Here, we take the attacker from [87] as an example. We visualize clean instances and their corresponding adversarial instances in Fig. 8 , where we show distribution shifts of node coordinates and node demands on CVRP100, respectively.Recent works have highlighted the vulnerability of neural VRP methods to adversarial perturbations, with most research focusing on the generation of adversarial instances (i.e., attacking). In contrast, this paper delves into the adversarial defense of neural VRP methods, filling the gap in the current literature on this topic. Our goal is to enhance model robustness and mitigate the undesirable accuracy-robustness trade-off, which is a commonly observed phenomenon in adversarial ML. We propose an ensemble-based collaborative neural framework to adversarially train multiple models in a collaborative manner, achieving high generalization and robustness concurrently. Our work sheds light on the possibility of building more robust and generalizable neural VRP methods in practice. However, since our approach introduces extra operations upon the vanilla AT, such as the global attack in the inner maximization and the neural router in the outer minimization, the computation cost may not be friendly to our environment. Therefore, exploring more efficient and scalable attack or defense methods for VRPs (or COPs) is a worthwhile endeavor for future research. Justification: Main contributions and scope are accurately reflect in Abstract and Section 1.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.Note that in CO, there may not be an intentional attacker seeking to compromise the model in practice. In this paper, an "attacker" refers to a method of generating instances where the current model underperforms. 


Decision: After the rebuttal, reviewers think that their concerns have been mostly mitigated and they all agree that the paper has benefits. In particular, reviewers think that the paper tackles an important open problem of adversarial defense for routing problems and the effectiveness is outstanding. Therefore, AC will follow the reviewers' vote to accept the paper.

However, note that reviewers also mention some remaining issues that should be addressed in the revised version to further improve the paper. These include:

1. The paper lacks theoretical analysis and guarantee: please provide theoretical evidence for the following two arguments as authors mentioned in the rebuttal: "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" "The neural router empowers CNF to reasonably exploit the overall model capacity."

2. Please polish your description about the trade-off between generalization and transitional robustness as well as the intuition behind Figures 2 and Algorithm 1.

3. Please clarify the threat models and inference details in the main body.

Please take the above-mentioned comments into consideration in the next version of the paper.

Reviews: review: paper_summary: paper_summary: The paper proposes a Collaborative Neural Framework (CNF) to improve the robustness of neural methods for vehicle routing problems (VRPs) against adversarial attacks. CNF introduces two key innovations: first, a global attack strategy that generates diverse adversarial instances by attacking the best-performing model, in addition to the local attacks on individual models. Second, an attention-based neural router that effectively distributes instances to different models for training, achieving satisfactory load balancing and collaborative performance. Extensive experiments show the effectiveness and generalization ability of the proposed method against different attacks.
strength_weakness: strength_weakness: - The paper is primarily focused on the empirical evaluation of the proposed framework, without providing any theoretical analysis or guarantees on the robustness or generalization properties of the approach
questions: questions: Please see the weakness part.
limitations: limitations: Yes, the authors discuss the limitations in the conclusion section.
paper_summary: paper_summary: This paper develops a ensemble-based method CNF for adversarial training to enhance the robustness of NCO solvers. CNF demonstrates outstanding performance compared to all current adversarial training frameworks.
strength_weakness: strength_weakness: 1. The trade-off between generalization (on clean instances) and transitional robustness demonstrated in Figure is not clear.
2. Compared to the textual illustration of the proposed CNF, Figures 2 and Algorithm 1 are not intuitive enough.
questions: questions: 1. For CVRP, Is it possible to perform adversarial training on the demand values as well?
2. What's the setting of ablation models in the part Ablation on Components?
3. For TSP, is CNF equally effective in different network architectures (such as ELG [1])?
4. Can the neural router used to assign the testing datas to facilitate inference?
5. Minor questions: 
Line 82 should be 100% instead of 100. 
The notation $\tilde{x}$ and $\bar{x}$ is quite similar which may cause misunderstanding.
Section 2.2 should include more references, e.g., [2].
\theta{r} should be included as input in Algorithm 1.
What's the formula of b(x) in Eq. (4)?
﻿
[1] Gao, Chengrui, et al. ""Towards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy."" arXiv preprint arXiv:2308.14104 (2023).
[2] Goodfellow, Ian, et al. ""Generative adversarial nets."" Advances in neural information processing systems 27 (2014).
limitations: limitations: The discussion in article is comprehensive enough.
paper_summary: paper_summary: This paper presents an ensemble-based Collaborative Neural Framework for for vehicle routing problems to improve robustness. Multiple models are adversarially trained for better robustness against attacks and improve generalization, and a neural router routes instances to models for better load balancing and efficacy.
strength_weakness: strength_weakness: 1. The paper is not organized or written  well.
2. This paper is not technically sound.
questions: questions: 1. Figure 1 is not clearly explained and not referred in the paper.
2. During inference, "The best solution among them is returned", how can you tell which is the best solution?
3. What is "collaborative manner" exactly?
4. What distribution will the generated adversarial instances follow?
5. Does this paper focus on solving combinatorial optimization problems? How?
6. As an important part of evaluation, there is no discussion on Table 7 or 8.
limitations: limitations: Adequate.
paper_summary: paper_summary: This paper focuses on the robustness of neural combinatorial optimization and proposes a new framework to robustify neural models for routing problems. The core idea is to train a set of models and to let them collectively make the best predictions. The authors have conducted experiments to benchmark the proposed method against various baselines for TSP and CVRP.
strength_weakness: strength_weakness: W1: The proposed method is collaborative AT. Hence, a missing ablation study is *independent* AT, i.e., using AT to train $M$ models independently (say, under different seeds) and outputting the best solutions found by the $M$ models. 

W2: This paper did not describe the threat model considered in this work. There should be no guarantee of performance if arbitrary perturbations are allowed. Thus, it might be better if the authors can clearly state what types of perturbations the proposed method is robust against.

W3: This paper describes mainly the training procedure but barely the inference procedure. It might be better if the paper can elaborate more on the detailed inference procedure.

Minor issue: While the authors (as well as prior work) use "attack" throughout the paper, I personally do not think this is a precise term. The setting in this paper seems more like OOD than attacking because I am unable to come up with a real-world scenario where an attacker wants to perturb the instance only in order to make the model produce a worse solution for the *perturbed* instance.
questions: questions: Q1: How robust are test-time adaptation methods such as meta-learning [58] and neural-guided local search [89]? Since such methods do not solely rely on the pretrained model, they may be inherently robust. Hence, it might be better if this paper also compare with such test-time adaptation methods. 
- [58] Qiu et al. DIMES: A differentiable meta solver for combinatorial optimization problems. NeurIPS, 2022.
- [89] Ye et al. DeepACO: Neural-enhanced ant systems for combinatorial optimization. NeurIPS, 2023.

Q2 (regarding the limitation): Since it is observed that the proposed method takes more time to converge, is it possible to employ better training schemes to speed up the convergence of the proposed method? For example, [58] found that meta-learning can significantly speed up convergence (see their Figure 1).
limitations: limitations: The authors have clearly discussed the main limitation in Section 5. Although using multiple models potentially increases the computational burden in both training and inference phases, the authors found that three models typically suffice to achieve good performance. Thus, this does not seem to be a severe limitation. See also Q2.

Comments: title: Thanks for your feedback
Thanks for your prompt feedback
Thanks for your prompt feedback
References
comment: We sincerely appreciate the reviewer for acknowledging our response and raising the score!
Thanks for the authors' response, which clarified some points. I raised my ranking accordingly.
Dear Reviewer xLJf,

Thank you once again for your insightful comments and helpful suggestions. As the author-reviewer discussion will end soon (< 24 hours from now), we would greatly appreciate it if you could take a moment to review our rebuttal. Please let us know if you have any further questions or concerns. We sincerely appreciate your time and effort.

Best regards,  
Authors
Dear Reviewer DziC,

Thank you once again for your insightful comments and helpful suggestions. As the author-reviewer discussion will end soon (< 24 hours from now), we would greatly appreciate it if you could take a moment to review our rebuttal. Please let us know if you have any further questions or concerns. We sincerely appreciate your time and effort.

Best regards,  
Authors
Dear Reviewer xLJf:

The deadline for the author-reviewer discussion is approaching. Please kindly let us know if our response resolves your concerns and we appreciate it if you could give us any feedback. We thank you again for your precious time and effort.
We appreciate the reviewer for the prompt feedback and acknowledgment of our rebuttal!
Thank you for your response. I raised my score to 6.
We would like to thank the reviewer for the prompt feedback and raising the score!
Thanks for your detailed response, which adequately addresses my concerns. I have raised my score.
```
[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.
```