Neural Solver Selection for Combinatorial Optimization

Thank you for your positive review. We sincerely appreciate your agreement on the significance of our neural solver selection framework. Here are the detailed responses to your questions.

1. In Other Strengths And Weaknesses, weakness 1, “the number of collected models are not strictly consistent for different methods”.

   Thank you for raising your concerns. To demonstrate the effectiveness of our neural solver selection framework, we directly collect models of different methods from their released repositories and construct the solver pool according to the process introduced in Appendix A.3, where the redundant solvers are removed. Because some works have released multiple models (e.g., models trained on different scales of data, or models trained with different hyper-parameters), before collecting them we have made a simple but straightforward pre-selection. That is, we keep the models trained on different scales of data, since they usually show complementary performance. On the other hand, for models trained with different hyper-parameters, we only select the best one. Note that Table 1 is not aimed at ranking the previous methods but simply demonstrating the performance of typical collected single models. We will revise to clarify it. Thank you for your advice.

2. In Other Strengths And Weaknesses, weakness 2, “performance on instances of specific scales are expected”.

   Thank you for your suggestion. We will revise our paper to provide separate results on different scales of instances for a deeper investigation. The following tables demonstrate that our selection method consistently outperforms the single best solver across different problem scales on both TSP and CVRP datasets.

Separate results according to problem scale $N$ on the synthetic TSP dataset. We report the mean (standard deviation) optimality gap over five independent runs.

Separate results according to problem scale $N$ on the synthetic CVRP dataset.

4. In Other Strengths And Weaknesses, weakness 3, “ the implicit assumption of this paper is that computational resources are constrained, requiring neural solvers to operate sequentially”.

   Thank you for raising your suggestion. Take VPRs, which is one of the most popular combinatorial problems, as an example; the number of automatic routing requests can be extremely large every day. Compared to parallel operating all of the solvers, even though the saved cost of neural solver selection might be limited when handling one request, the totally saved cost of all the requests can be very considerable. We will revise to add more discussions on it to clarify its benefit. Thank you very much.

5. In Other Comments Or Suggestions, “The structure of the selection model can be visualized”.

   Thank you for your suggestion. As introduced in our paper, currently, we simply use an MLP as the selection model, where the instance features are the input, and each head of the output layer represents the logits of selecting a specific solver. Since this is a simple model (which already works well), we did not visualize it due to limited space, and directly described it in Section 3.2 of our paper. We will revise our paper to clarify it better. Thank you.

Thank you for your positive review and constructive comments. Below please find our responses. Corresponding experimental results can be found at link.

R1: How the model selection behaves on larger instances with up to 10,000 nodes

Thanks for your insightful comment. Scaling neural solvers to very large instances (e.g., 10,000+ nodes) is a challenging and active research area. Current neural solvers often struggle with such scales and extracting meaningful instance features from such large-scale instances also poses additional challenges.

As this paper is the first to explore solver selection in NCO, we focused on commonly studied instances (fewer than 1,000 nodes). Nevertheless, we also extended to 2,000 nodes in Appendix A.11 using additional solvers such as GLOP (Ye et al., 2024) and UDC (Zhang et al., 2024), and demonstrated that our proposed neural solver selection framework remains effective in this setting.

We believe that our framework holds potential for very large-scale instances (e.g., 10,000+ nodes) with the inclusion of an expanded solver pool and the development of advanced feature extraction methods. This represents an exciting avenue for future research. We will revise to include more discussions on this topic. Thank you again for your valuable feedback.

R2: The parameter counts of the different feature extractors

For a fair comparison, we actually adjust the depth of the hierarchical encoder referring to the naive graph encoder in our experiments. Specifically, the naive graph encoder uses 4 attention layers, while the hierarchical encoder has 2 blocks, each with an attention layer and an attention-based pooling layer. Their parameter counts are approximately the same, and it is more reasonable to attribute the improvements to the hierarchical design.

R3: The difference from graph attention

When graph attention is used on fully connected graphs like TSP, it works just like a Transformer without positional encoding.

R4: The hierarchical graph encoder seems a bit complex; try simpler pooling approaches that keep the hierarchical aspect

Thanks for your insightful comment. Our pooling method involves three steps: (a) structure-aware embedding computation via attention, (b) importance score calculation with a linear layer, and (c) top-k node selection and embedding updates. Although this process may seem somewhat complex, each step is conceptually grounded. Thanks to your suggestion, we tested a simpler pooling mechanism that skips step (a) and computes importance scores directly from node embeddings. While it benefits from the hierarchical design, this simpler method shows slightly degraded performance, as shown in Table S1. We agree that the hierarchical design plays a more critical role than the implementation of pooling. However, it is worth noting that advanced pooling implementations, such as the attention-based approach, also provide gains.

R5: Discussion on NFL Theorem and performance affected from changing the synthetic distribution

Thanks for your interesting question! When the distribution significantly shifts, the performance of selector may degrade substantially, i.e., the selector is fooled by the training distribution. This challenge—commonly referred to as the OOD problem—is inherent to all machine learning methods. To mitigate this issue, we have made several attempts in our methodology design: 1) Ranking loss, which can leverage the relationship of all solvers, thereby making the selection more robust; 2) Top-k selection, which increases the likelihood of including effective solvers, particularly under distribution shifts. 3) Hierarchical encoder, which extracts transferrable patterns; and 4) Diverse training data. As you described in Question 5, we have made many modifications to diversify the synthetic data. Without such diversity, the selector may easily overfit the training data. The selector cannot generalize well to TSPLIB and CVRPLIB if the training distribution is too simple, such as training on uniform datasets with $n=100$.

From a broader perspective, the development of strong neural solvers can benefit significantly from combining multiple solvers with a selection model. Compared to training a single neural solver to handle all possible problem distributions, training a selection model is more tractable for addressing the OOD challenge, as it only needs to identify patterns within instances rather than solve the problems directly. For this reason, we believe that selection-based methods represent a promising direction for advancing neural solvers, even though they also face OOD challenges.

In response to Question 5, we conducted new experiments using smaller-scale or simplified training data (see Table S2). The results indicate that generalization on TSPLIB degrades as training data becomes simpler.

Thank you for your valuable and encouraging comments. We sincerely appreciate your agreement on the effectiveness of the neural solver selection framework in our paper, which, we believe, has the potential to be a new branch of techniques for the application of NCO solvers. We summarize the concerns in your review. Here are the detailed responses.

1. In section Experimental Designs Or Analyses, about “putting the comparison with traditional selection methods in Appendix A.5 in the main paper”.

   Thank you for your suggestion. Limited by space, the current version of our paper only included the results of a typical traditional method (Smith-Miles et al., 2010), titled as “Manual” in Table 3, and left the details of implementation and the results of other methods in Appendix A.4 and Appendix A.5, respectively. We will revise our paper to clarify it better.

2. In weakness, "It seems that this paper only applies a general selection method to neural solvers for COPs".

   Thank you for raising your concerns. As we know, the general idea of solver selection (or algorithm selection) has been implemented in a variety of scenarios. However, how to adapt it in the context of neural solvers for COPs has never been explored before our work. Note that neural solvers themselves are quite different from traditional COP solvers. That is, they utilize neural network models (such as Transformers or Diffusion Models) as backbones, and generate solutions with the models in an end-to-end manner. Our work first investigated the instance-level performance of prevailing NCO solvers and found that they demonstrate clear complementarity. After that, we experimentally revealed that the change of problem distribution can change the dominance relationship of solvers. These two observations verify the potential benefit of neural solver selection for COPs. Inspired by these observations, we propose the first neural solver selection framework for COPs, which is the main contribution of this work and we believe can benefit the community and inspire future research in this area.

   On the other hand, the implementation of our neural solver selection framework has some advanced components. For example, we propose a new method of extracting instance features for NCO, which is different from previous works on classical algorithm selection for TSP. Firstly, we examined the manual features proposed in classical algorithm selection for TSP (https://tspalgsel.github.io/) and found that they can only achieve limited performance (in Table 3 of the original paper). To address this, we proposed a novel pooling-based hierarchical encoder designed to extract richer instance features, leading to significantly better generalization performance. We believe that such an instance feature extraction method may also be helpful for improving other NCO methods, not limited to our neural solver selection framework.

   Thank you again for your thoughtful comments. We sincerely hope the above clarification can address your concern.

3. Question 1 in Questions For Authors, "how to apply this framework to other COPs".

   Thank you for raising your concerns. Our paper aims to demonstrate the great potential of solver selection in the context of NCO (through observations in Figure 1(a)-(b)), and propose a general framework on neural solver selection for NCO, which consists of three components: feature extraction, selection model, and selection strategy. We believe the methods in the selection model and selection strategy can be easily adapted to a very wide spectrum of COPs. On the other hand, as we know, different kinds of COPs may possess different inherent characteristics, making it very challenging to obtain a general feature extraction method. In this work, we focus on TSP and CVRP, and propose to use graph attention for feature extraction. For other kinds of COPs, model structures may need to be specifically designed for feature extraction, e.g., MatNet (Kwon et al., 2021). General feature extraction methods (e.g., utilizing LLMs) are also interesting directions for future works. Besides, in this paper, we propose hierarchical pooling in feature extraction and show its effectiveness. We believe that the idea behind hierarchical pooling can benefit the design of feature extraction methods on other COPs. Thank you again for your suggestions. We will revise our paper to include more discussion.

   Thank you again for dedicating your time to reviewing our paper. We also welcome any further questions and discussions.

Thank you for taking the time to review our paper. We are delighted to learn that you generally appreciate the core idea of our work, and we sincerely value your insightful comments. However, we believe there may be some misunderstandings regarding certain aspects of the paper, which we would like to clarify.

We first want to emphasize that our main contribution is proposing neural solver selection in the community of Neural Combinatorial Optimization (NCO) for the first time and showing its effectiveness even with a very straightforward implementation. Inspired by the No-Free-Lunch theorem, we investigated the instance-level performance of prevailing NCO solvers and found that they demonstrate clear complementarity. This phenomenon emphasizes the potential of combining the advantages of state-of-the-art neural solvers and motivates our proposal of adaptively selecting suitable solvers for each instance. Since our work is supposed to be a pioneering attempt at neural solver selection, our main goal is to verify the possibility and benefits of solver selection for NCO. In our experiments, we found that even a straightforward method using hand-crafted features and MLP classification models can outperform the state-of-the-art neural solver, which strongly indicates that combining multiple neural solvers through solver selection is a promising direction for NCO. We believe our work can benefit the NCO community and inspire future research in this area.

In response to your concerns regarding technical novelty, we would like to highlight two key advancements in our work:

1. Handling dynamic neural solver pool through instance-solver matching. In Appendix A.7, we explore a novel feature extraction method for neural solvers, where an instance tokenizer and a two-layer transformer are utilized to summarize neural solvers' features from representative instances (i.e., those instances where a neural solver performs well). Based on these learned features, we train a matching network to compute compatibility scores between instance features and solver features. This architecture, detailed in Appendix A.7, is significantly more sophisticated than the MLP classifier used in our main experiments. Importantly, this instance-solver matching mechanism allows the framework to generalize to previously unseen solvers, enabling it to handle dynamic solver pool flexibly. Reviewer Qe6z recognized this aspect as "interesting." Moreover, we highlight that our work is the first to introduce the method of leveraging representative instances to extract solver features, further emphasizing its technical originality. Since your decision may have been made without reviewing the appendix in detail, we kindly refer you to Appendix A.7 for additional information.

2. Instance feature extraction through hierarchical encoder. While hierarchical encoding for COPs has been explored in prior work (e.g., Goh et al., 2024), existing methods primarily rely on cluster-based embedding aggregation. In contrast, our approach employs a pooling-based network design, which offers greater flexibility in identifying important but non-centric nodes (as illustrated in Figure 6). This flexibility enhances the model's ability to capture richer local patterns, thereby improving generalization. Compared to cluster-based aggregation, our method provides a novel and more robust solution for hierarchical feature extraction.

We hope these explanations can address your concerns regarding the technical contributions of our work. Additionally, we acknowledge your suggestion to improve the presentation and will carefully revise the paper accordingly. For example, we will enhance Figure 1 to include more details, such as the process of running the selected subset of solvers and obtaining the best solution from their results.

Once again, we greatly appreciate your time and thoughtful feedback. Please do not hesitate to reach out if you have further questions or suggestions.