Neural Solver Selection for Combinatorial Optimization

Authors: Chengrui Gao, Haopu Shang, Ke Xue, Chao Qian
Primary area: other topics in machine learning (i.e., none of the above)
Keywords: learn to optimize

Abstract:
Machine learning has increasingly been employed to solve NP-hard combinatorial optimization problems, resulting in the emergence of neural solvers that demonstrate remarkable performance, even with minimal domain-specific knowledge. To date, the community has created numerous open-source neural solvers with distinct motivations and inductive biases. While considerable efforts are devoted to designing powerful single solvers, our findings reveal that existing solvers typically demonstrate complementary performance across different problem instances. This suggests that significant improvements could be achieved through effective coordination of neural solvers at the instance level.
In this work, we propose the first general framework to coordinate the neural solvers, which involves feature extraction, selection model, and selection strategy, aiming to allocate each instance to the most suitable solvers. To instantiate, we collect several typical neural solvers with state-of-the-art performance as alternatives, and explore various methods for each component of the framework. We evaluated our framework on two extensively studied combinatorial optimization problems, Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP). Experimental results show that the proposed framework can effectively distribute instances and the resulting composite solver can achieve significantly better performance (e.g., reduce the optimality gap by 0.88\% on TSPLIB and 0.71\% on CVRPLIB) than the best individual neural solver with little extra time cost.

Decision: reject
Reviewer scores: 6, 6, 6, 5

Reviews and discussion:
<thread>
creation date:
1729787031152

thread_type:
official_review

<thread_object>
creator: reviewer_sapt

<content>
summary:
This paper introduces a framework for selecting the most appropriate neural solvers for TSP and CVRP at instances level. The framework enhances performance by allocating each problem instance to the most suitable solvers from a pool of available neural solvers via graph encoding and tailored selection model and strategy.

strengths:
The paper is generally well-structured and easy to follow. The writing is clear and the presentation of the idea is concise. The idea of selecting neural solvers at instance level is interesting and of practical significance.

weaknesses:
1. The novelty of this work is somewhat limited because the idea of ranking different existing solvers for individual instances is not technically innovative, and the framework seems to highly rely on previous solvers, graph encoders, as well as established losses and selection strategies.
2. To gain the supervision for training requires executing multiple solvers on the same training set, which is probably time-consuming. Furthermore, given such computational overhead, it is believed that a tediously sequential performing of them on the targeted dataset can have been already done for simple selection of the optimal result. Thus, further clarification is needed on the necessity of this proposal.
3. The OPT in the evaluation is somewhat misleading. I suggest the authors solving the test instances with exact solvers or powerful heuristics like Gurobi, LKH3, HGS, etc, as reference solution for the computation of optimality gaps, which also better aligns with previous works. 
4. Additionally, adding such heuristics (in point 3) in your selection zoo is worth considering for further experimental results. If the neural solvers achieve comparable performance as the learning-free methods, the significance of this work is further strengthened.
5. More mainstream solvers should be included, such as [1-7]. They are a set of representing (but not limited to) neural works for routing problem solving, including supervised-, reinforced-, unsupervised-, meta-reinforced-, divide-and-conquer-, and neural-heuristic-mannered approaches. It is acceptable the authors include a subset of them into the framework, but this would benefit the completeness for your empirical evaluation.
6. The authors are also suggested to evaluate their framework on the conventionally used uniform TSP dataset (like those consistent test files through [1,2,4,5,7, etc.]). And please report the origianal objective for the COPs in addition to currently only the gap.
7. The claim in the title is broader than what is done within the paper. If the framework is to be a neural solver selection of combinatorial optimization, can it be readily applied to more complex problems beyond TSP and CVRP? And what is the solution at larger-scaled (e.g., $N\ge 1000$) instances where most neural solvers struggle to produce satisfactory results compared to the traditional heuristics?

**References:**

[1] DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems.

[2] An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem.

[3] Unsupervised Learning for Solving the Travelling Salesman Problem.

[4] Graph Neural Network Guided Local Search for the Travelling Salesperson Problem.

[5] Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances.

[6] GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time.

[7] Attention, Learn to Solve Routing Problems!

questions:
Please see the weaknesses part for questions and suggestions.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730607657012

thread_type:
official_review

<thread_object>
creator: reviewer_pbug

<content>
summary:
This work proposes a neural solver selection framework to efficiently select a subset of suitable neural combinatorial optimization (NCO) solvers to handle each problem instance at the inference time. Three key components (feature extraction, training loss, and selection strategies) have been proposed and investigated in detail for solver selection. Experimental results show that the proposed framework can achieve promising performance on the traveling salesman problem (TSP) and the capacitated vehicle routing problem (CVRP) with little extra time cost.

strengths:
+ This paper is well written and easy to follow.

+ Algorithm selection is an important strategy for classic (combinatorial) optimization, and it has not yet been well studied for NCO. This work is a timely contribution to this important research direction.

+ The proposed algorithm selection framework can achieve promising performance on different TSP and CVRP instances.

weaknesses:
**1. Connection to Neural Combinatorial Optimization (NCO) and Novelty**

Although this work's main motivation is to propose a neural solver selection framework for NCO, it seems that the proposed solver selection approach is actually agnostic to NCO. It is more like an independent learning-based solver selection method that can be used for other solvers, including the traditional ones. What makes the proposed method specific for NCO?

On the other hand, algorithm selection is already a popular research direction in the optimization community. As correctly mentioned in this paper, many (learning-based) algorithm/solver selection methods have already been proposed and widely used in practice (for example, see [1] for TSP algorithm selection). Many of them can be easily adapted to select NCO solvers. What is the novelty/contribution of the proposed framework over the existing algorithm selection methods?

[1] https://tspalgsel.github.io/

**2. Discussion/Comparison with Existing Algorithm Selection Methods**

I think the claim "[the traditional method] has never been explored in the area of neural combinatorial optimization" is far from enough to truly distinguish the proposed method from the traditional algorithm selection method. A detailed discussion/comparison with traditional algorithm selection methods is needed. 

What are the advantages/disadvantages of the proposed method compared with existing (learning-based and non-learning-based) algorithm selection methods? What is the performance of existing algorithm selection methods with NCO solvers? What is the performance of the proposed method with classic solvers?

**3. Novelty of the Key Components**

The proposed framework has three key components, namely feature extraction, selection model, and selection strategies. However, it seems that these components and the proposed structures are quite common in the NCO and algorithm selection community. The novelty and unique contribution of these components should be highlighted with solid evidence.  

**4. Generalization Performance**

Although experimental results show the proposed framework has good performance with problem distribution/scale shifts, it is unclear why it can achieve good out-of-distribution generalization performance as a learning-based method. 

**5. Experiments**

In the experiments, only a single summary table is provided for each comparison. I think a complete table with separate results for different instances (e.g., with different numbers of nodes), as widely used in other NCO papers, could be very helpful to better understand the performance of the proposed method.

As mentioned above, a detailed comparison with existing (learning-based and non-learning-based) algorithm selection methods is also needed.

questions:
See weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730612318230

thread_type:
official_review

<thread_object>
creator: reviewer_kqip

<content>
summary:
This paper proposes a novel framework for selecting the most suitable neural solver for different instances of combinatorial optimization problems (COPs). The framework effectively combines graph feature extraction through attention mechanisms and hierarchical encoders, as well as multiple solver selection strategies, including Greedy, Top-k, and Rejection-based approaches. The experimental results demonstrate the superiority of the proposed method over traditional approaches on tasks like TSP and CVRP. Overall, the paper offers valuable insights to instance-specific solver selection.

strengths:
1. The paper introduces a novel combination of hierarchical graph encoders and multiple selection strategies, which together enhance solver performance for different combinatorial optimization problem instances.
2. The experimental results cover a range of combinatorial optimization tasks and demonstrate improvements in performance compared to using a single solver.
3. The proposed Adaptive Solver Selection Framework for selecting solvers based on instance characteristics is flexible.

weaknesses:
1. The current selection strategies include Greedy selection, Top-k, Rejection-based, and Top-p. While these strategies have demonstrated effectiveness in different experimental settings, the basis for choosing the most suitable strategy for different types of instances is not clear. For example, what kind of instances would make Top-k more suitable than Top-p? 
2. The paper could benefit from including more graphical representations.

questions:
1. The paper mentions that the hierarchical encoder can better leverage the hierarchical structural features in COPs. However, the intuitive interpretation of these hierarchical features is unclear. How do these structures correspond to specific instance properties of problems such as TSP or CVRP?
2. The paper mentions the use of graph features and instance scale as inputs for the selection model, while the specific features of different neural solvers are not directly involved in the learning process. Would the absence of these solver-specific features limit the generalization ability of the selection model?
3. During the score calculation phase, how exactly does the MLP relate to different solvers? In other words, how are the features of different solvers reflected in the MLP, and how does this ensure that the classification results are correlated with the solvers' features?
4. In the Top-p selection strategy, the paper defines a threshold probability $p$ to decide which solvers to retain. Is this threshold set adaptively based on the problem's features, allowing for optimal performance? 
5. The introduction of a hierarchical encoder adds complexity to the model. How does this impact the overall training efficiency and inference speed of the model? Is there any quantitative analysis showing the trade-off between the hierarchical encoder's added complexity and the model's performance improvements?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730656471690

thread_type:
official_review

<thread_object>
creator: reviewer_n15x

<content>
summary:
This paper considers a new perspective on solving the Combinatorial Optimization (CO) problem using deep learning. Given an instance, a deep learning framework is trained to select the best suitable solver for this instance from a state-of-the-art solver pool. The general idea is (1) feature extraction of the input instance, (2) selection based on several criteria, e.g., top k, and the output of a trained classifier/ranking model.  (3) run the instance on the select solver(s). 

The experiment results show that the proposed method can improve the current single solver performance with few efforts. It also shows the ability to generalize. The key idea behind this paper is similar to this paper: Bai Y, Zhao W, Gomes C P. Zero Training Overhead Portfolios for Learning to Solve Combinatorial Problems[J]. arXiv preprint arXiv:2102.03002, 2021. Since the CO problems are typically too hard, so a single sovler cannot capture the entire problem structure. So, different solvers have their own advantages, then we can leverage this to improve the performance.

strengths:
(1) Since the CO problems are typically too hard, a single solver cannot capture the entire problem structure. Different solvers have their own advantages, which we can leverage to improve performance.
(2) The experiment results show the ability to generalize.

weaknesses:
See questions.

questions:
(1) Do you have any results on TSP-10000 or large instances? Trying to train your selection model on TSP-1000 and see how it can be generalized to TSP-10000 is critical.
(2) Are the instances training the selection model generated from the same distribution of the testing instances?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732271018789

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General response to all reviewers

comment:
We are very grateful to the reviewers for carefully reviewing our paper and providing constructive comments and suggestions. We have revised the paper carefully according to the comments and suggestions. The changed and newly added parts are colored in blue in the new version. Our response to individual reviewers can be found in the personal replies, but we would also like to make a brief summary of revisions for your convenience.

1. According to the suggestion of Reviewer N15x and SaPT, we conduct new experiments on larger-scale instances (N up to 2000) with newly added divide-and-conquer neural solvers, detailed in Appendix A.12. The additional results demonstrate that our proposed method can be compatible with more neural solvers and can also improve performance on larger-scale instances.
2. According to the suggestion of Reviewer PbuG, we conduct comparison experiments with advanced algorithm selection methods for non-neural TSP sovlers, showing the superiority of our implementation. Details can be found in Appendix A.13.
3. According to the suggestion of Reviewer kQip, we provide graphical illustrations of how the hierarchical encoder works in Appendix A.15, where we find some intuitively reasonable down-sampled patterns.
4. We provide more detailed results of our method.

   (1). According to the suggestion of Reviewer PbuG, we present separate results with different problem scales in Appendix A.11, demonstrating that our method consistently outperforms individual neural solvers across different problem scales.

   (2). According to the suggestion of Reviewer kQip, we add comparisons of computational costs between our hierarchical encoder and a typical graph encoder in Appendix A.6. These results further validate the efficiency and superiority of our hierarchical encoder.

   (3). According to the suggestion of Reviewer SaPT, we now include the results of objective values in Tables 8 and 9 for more detailed comparisons. 
5. We add some discussions according to the reviewers' comments.

   (1). As suggested by Reviewer kQip, we have expanded the discussion on the advantages of our proposed selection strategies in Appendix A.7, highlighting their impact on optimality and efficiency;

   (2). In Appendix A.14, we have added explanations for our dataset choices as suggested by Reviewer SaPT, clarifying how the dataset aligns with the scope and goals of our work; 

   (3). In Section 5, we have included a discussion on the versatility of our framework, as also recommended by Reviewer SaPT, emphasizing its potential applicability to different combinatorial optimization problems;

   (4). Following Reviewer N15X's suggestion, we discuss a new related work in Appendix A.5 to provide a more comprehensive context for our contributions.


**We hope that our response has addressed your concerns, but if we missed anything please let us know.**
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposed a learning based solver selection method for neural vehicle routing models. It involves feature extraction, selection model, and selection strategy, aiming to allocate each instance to the most suitable solver from a pool of neural VRP models. Reviewers agreed that the proposed method is interesting and neural solver selection is of practical meaning. However, they also raised several key concerns including 1) insufficient discussion and comparison to existing algorithm selection methods; 2) insufficient link to NCO; and 3) insufficient technical novelty. I particularly agree with the first point. Algorithm selection is a classic topic with many mature methods that can easily be applied to select neural VRP solvers, but this paper lacks a systematic discussion of the literature, as well as proper comparison to SOTA methods. In addition, the link to NCO is indeed not strong, as it appears to be a neural algorithm selection method that can be applied to other algorithms. So overall, this paper is interesting, but still requires major improvement to reach the acceptance threshold.