Neural Solver Selection for Combinatorial Optimization
Authors: Chengrui Gao
Haopu Shang
Ke Xue
Chao Qian
Venue: ICML 2025 poster (2025)
Keywords: neural combinatorial optimization
Primary area: optimization->discrete_and_combinatorial_optimization
TL;DR: We demonstrate that neural combinatorial optimization solvers often exhibit complementary strengths and propose a general selection framework to coordinate multiple solvers for improved performance.

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 typical problems, Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP). Experimental results show that our 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.

Neural Solver Selection for Combinatorial Optimization
Chengrui Gao Haopu Shang
12
Ke Xue 12
Chao Qian
Abstract
1. Introduction
Combinatorial Optimization Problems (COPs) involve find- ing an optimal solution over set of combinatorial alter- natives, which has broad and important applications such as logistics (Konstantakopoulos et al., 2022) and manufac- turing (Zhang et al., 2019). To solve COPs, traditional ap- proaches usually depend on heuristics designed by experts, requiring extensive domain knowledge and considerable effort. Recently, machine learning techniques have been introduced to automatically discover effective heuristics for COPs (Bengio al., 2021; Cappart et al., 2023), leading to the burgeoning development of end-to-end neural solvers that employ deep neural networks to generate solutions for problem instances (Bello et al., 2017; Kool et al., 2019; Joshi et al., 2019). Compared to traditional approaches, these end-to-end neural solvers can not only get rid of the heavy reliance on expertise, but also realize better inference efficiency (Bello et al., 2017).
Machine learning has increasingly been employed to solve NP-hard combinatorial optimization prob- lems, resulting 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 typi- cally 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, selec- tion model, and selection strategy, aiming al- locate each instance to the most suitable solvers. To instantiate, collect several typical neural solvers with state-of-the-an performance as al- ternatives, and explore various methods for each component of the framework. We evaluated our framework on two typical problems, Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP). Experimental results show that our framework can effectively distribute instances and the resulting composite solver can achieve significantly better performance (e.g., re- duce the optimality gap by 0.88% on TSPLIB and 0.71 % on CVRPLIB) than the best individual neu- ral solver with little extra time cost. Our code is available solver-selection.
To enhance the capabilities of neural solvers, variety of methods have been proposed, with intensive effort on the design of frameworks, network architectures, and training procedures. For example, to improve the performance across different distributions, (Jiang et al., 2022) proposed adap- tively joint training over varied distributions, and (Bi et al., 2022) leveraged knowledge distillation to integrate the mod- els trained on different distributions. For generalization large-scale instances, (Fu et al., 2021) implemented a sivvdd-anddcongeee -nd--onnueereereeeeeeeeee strategy, (Luo et al., 2023) proposed a heavy-decoder structure to better capture the relationship among nodes, while (Gao et al., 2024) utilized the local transferability and introduced an additional local policy model. Diffusion models (Sun & Yang. 2023) have also been adapted generate the distribution of optimal solu- tions, demonstrating impressive results. More works include bisimulation quotienting (Drakulic et al., 2023), latent space search (Chalumeau et al., 2023), local reconstruction (Cheng et al., 2023; Ye et al., 2024; Zheng et al., 2024) and so on.
'Equal contribution 'National Key Laboratory for Novel Soft- ware Technology, Nanjing University, China "School of Artificial Intelligence, Nanjing University, China, Correspondence to: Chao Qian <qianc @ @nju.edu.en>.
As various neural solvers are emerging in the community, the state-of-the-an records for the overall performance on benchmark problems are frequently refreshed. However, the detailed comparison of these neural solvers on each instance has been rarely discussed. Here, we empirically ex- amined the performance of several prevailing neural solvers
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Neural Solver Selection for Combinatorial Optimization
COP
Open-source community
Solve
10
Scalorcoted capadly Capacty from trann tfangulrr dfrnguhrdzaffeuirss disrioutionss
Solver
Meboo
Infermtio::
Wineing
0.3
Optimality (5)
Solver
Feature extraction
Indermatie:: Difloder molil Triiin sall: 500
Selection model
0.
Selection strategy
Diverse solver pool
Selected
solvers
UEN0
5Q
BLG
omN
UERO
80
BLG
Onnil
(a) Percentages of Winning
Optimality Gap (Average)
(c) Our Framework
Figure I: (a), (b): Observation from the comparison of prevailing neural solvers at instance level. Details of the settings are provided in Section 4.1. (c): Our proposed selection framework.
on each instance, as illustrated in Figure ((a) and 1(b). As expected from the no-free-lunch theorem (Wolpert & Macready, 1997), we find that:
COPs, using only the most suitable individual solver pre- dicted by the selection model may fail. Therefore, it is important design robust selection strategies based on the confidence of the selection model.
As shown in Figure I(a), there exists no single neural solver that can dominate all the others on every instance, and different neural solvers win on different instances, demon- strating their complementary performance at instance level.
To verify the effectiveness of our proposed framework, we collect several prevailing open-source neural solvers and their released models with competitive performance in the community construct the pool of individual solvers, and provide several implementations for each component of the framework. For feature extraction, tention network (Veličković et al., 2018; 18; Kool et al., 2019) to encode COP instances, and further propose refined en- coder with pooling to leverage the hierarchical structures of COPs. For selection model, we train it from the perspective of classification and ranking, respectively. We also imple- ment several selection strategies, including top-k selection, rejection-base -basd selection, and on. Detailed descriptions are provided in Section 3. We conduct experiments on two widely studied COPs: Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP). Experi- mental results exhibit that our framework can generally se- lect suitable individual solvers for each instance to achieve significantly better performance with limited extra time con- sumption. Compared to the best individual solver, our frame- work reduces the optimality gap by 0.82% on synthetic TSP, 2.00% on synthetic CVRP, 0.88% on TSPLIB (Reinelt, 1991), and 0.71% % on CVRPLIB Set-X (Uchoa et al., 2017). As the first preliminary attempt on neural solver selection for COPs, we also analyze the influence of various imple- mentations of components, and discuss on future directions.
As shown in Figure 1(b), the modification of instance distribution almost reverse the domination relationship of neural solvers, which further verifies that different neural solvers are good at instances with specific characteristics due to their intrinsic inductive biases.
utilize the graph at-
These observations suggest that it may potentially bring impressive improvements to the overall performance, if multiple neural solvers are coordinated solve instances to- gether. In fact, recent works have already made preliminary attempts from the perspective of ensemble learning (Jiang et al., 2023) and population-basee training (Grinsztajn et al., 2023). However, their individual solvers share the same ar- chitecture, resulting in limited diversity. On the other hand, as of the individual solvers should run during inference, these methods can hardly achieve ideal efficiency.
Motivated by the observations above, we, for the first time, propose a general framework to coordinate end-to-end neu- ral solvers for COPs at the instance level by selecting suit- able individual solvers for each instance, as illustrated in Figure I(c). Specifically, our proposed framework consists of three key components, which are summarized as follows:
Feature extraction: For each problem instance, extract features for effectively identifying their characteristics.
2. Related works
Selection model: Based on the features of instances, train a selection model that can be utilized to identify suitable solvers for each instance.
2.1. End-to-end neural solvers for COPs
Traditional approaches for COPs have achieved impressive results, but they often rely on problem-specific heuristics
Selection strategy: Due the intricate structures of
2

---

Neural Solver Selection for Combinatorial Optimization
and domain knowledge by experts (Helsgaun, 2000; 2017). Instead, recent efforts focus on utilizing end-to-end learning methods. A prominent fashion is autoregression, which em- ploys graph neural networks in an encoder-decoder frame- work and progressively extends a partial solution until a complete solution is constructed (Vinyals et al., 2015; Bello et al., 2017; Kool et al., 2019). However, these methods tend to exhibit poor generalization performance across distribu- tions and scales (Joshi et al., 2022). To address the general- ization issue, considerable efforts have been dedicated from various perspectives, including meta-learning (Zhou et al., 2023), knowledge distillation (Bi et al., 2022), prompt learn- ing (Liu et al., 2024), rsstace-conditione adaptation (Zhou et al., 2024a), adversarial training ( (Wang et al., 2024) and nested local views (Fang et al., 2024).
Figure ((a) and I(b), we propose select suitable ones from pool of diverse individual solvers for each instance. Note that similar idea has been utilized in the area of algorithm selection (Kerschke et al., 2019; He et al., 2025) and model selection (Zhang et al., 2023), but has never been explored in the area of neural combinatorial optimization. By solver selection at instance level, any existing or newly constructed neural solver can be utilized, and only the selected individ- ual solvers need to be run in inference, thereby maintaining high efficiency.
3. The proposed framework
This section introduces our proposed framework of coordi- nating neural solvers for COPs. Our target is learning to select the suitable solvers for each problem instance. To address it, the framework comprises three key components:
Another popular kind of end-to-end learning methods is non-regressive, which predicts or generates the distributions of potential solutions. Typically, (Joshi et al., 2019; Ye et al., 2023) employed graph neural networks to predict the probability of components appearing in an optimal so- lution, represented with the form of heatmap. Diffusion models (Sun & Yang, 2023; Sanokowski et al., 2024) have also been adapted generate the distribution of optimal solutions, demonstrating better expressiveness than classical push-forward generative models (Salmona et al., 2022).
Feature extraction: To select the most suitable neural solvers for each instance, it is essential to extract the in- stance features, which is challenging as the COPs are usually intricate. In this work, we first utilize the graph attention encoder (Kool et al., 2019) to encode COP instances, and further propose refined graph encoder with pooling, which can leverage the hierarchical structures of COPs.
Selection model: We train a neural selection model with the graph encoder to identify the most suitable solvers. Specif- ically, we implement two loss functions from the perspec- tives of classification and ranking.
2.2. Solving COPs with multiple neural solvers
Recent studies have made preliminary attempts to integrate multiple neural solvers to enhance overall performance on COPs. For example, (Jiang et al., 2023) adopted ensemble learning, where multiple neural solvers with identical archi- tecture are trained on different instance distributions through Bootstrap sampling. During inference, the outputs of all the solvers are averaged at each action step. (Grinsztajn et al., 2023) proposed copulation-basel training method Poppy, where multiple decoders with a shared encoder are trained simultaneously as population of solvers, with re- ward targeting at maximizing the overall performance of the population. When solving a problem instance, each solver generates solutions independently, and the best solution is selected the final result. However, these works suffer from heavy cost as multiple solvers have to be run for each instance. Even they propose to share common encoder for each solver, experiments still demonstrate undesired in- ference time (Grinsztajn et al., 2023). On the other hand, different solvers share the same neural architecture, which may limit the diversity and thus the final performance.
Due to the complexity of COPs, it may be risky to rely solely on the selection model to iden- tify the best solver. To address this, we propose compromise strategies to allocate multiple solvers (if necessary) to sin- gle instance based on the confidence levels of the selection model, pursuing better performance with limited extra cost.
Selection strategies:
3.1. Feature extraction
For feature extraction, it depends on the COP to be solved. Here, we use the two most prevailing problems, TSP and CVPR, in the neural solver community for COPs (Kwon et al., 2020; Luo et al., 2023: Drakulic et al., 2023) as ex- amples, which will also be employed in our experiments. TSP and CVRP involve finding optimal routes over a set of nodes. For TSP, the objective is to find the shortest pos- sible route that visits each node exactly once and returns to the starting node. Each TSP instance consists of nodes distributed in Euclidean space. For CVRP, the goal is to plan routes for multiple vehicles to serve customer nodes with varying demands, starting and ending at depot node, while minimizing the total travel distance and satisfying vehicle capacity constraints (Dantzig & Ramser, 1959). Both TSP and CVRP instances can be represented as fully connected graphs, where nodes correspond to locations (cities or cus-
Consider that the burgeoning community has proposed many methods from various perspectives, resulting in diverse neu- ral solvers with different inductive biases. Properly coordi- nating them can potentially bring significant improvement on overall performance. Motivated by the observation in
3

---

Neural Solver Selection for Combinatorial Optimization
tomers). The graph representation makes them suitable for encoding using Graph Neural Networks (GNNs), which can effectively capture the structural information inherent in these problems (Khalil et al., 2017; Kool et al., 2019). In this paper, we design two types of GNN-based encoders tailored for TSP and CVRP instances as follows.
the graph attention layer computes score embeddings H gooee based on the current node embeddings H', which encode rich information about the graph structure and node features. These score embeddings H. are then mapped to scalar representative scores via linear layer. The complete process is shown as follows:
Graph attention encoder. We take the CVRP as an exam- ple describe the computation of the graph encoder. The raw features x E RNN33 of a CVRP instance are a set of nodes { Vs; m.)li E [N]] where (I', Mi) are the node coordinates, my is the node demand, N is the number of nodes, and [N] denotes the set (1, .,,,,...NN) First, a linear layer is employed on every node for initial node embed- dings, i.e., 70 = æW, where W E TRadd are the weights and d denotes the embedding dimension. Given initial em- beddings, multiple graph attention layers (Veličković et al., 2018; Kool et al., 2019) are applied to iteratively update the node embeddings as H' = AttentionLayer" (H' where E [L] and L is the number of layers. Since the graphs of TSP and CVRP are both fully connected, the graph attention layer covers every pair of nodes and ceff-connections, which becomes similar to the self-attention mechanism (Vaswani al., 2017). Details of the attention layer are in Appendix A.1. Finally, the node embeddings output by the last layer are averaged to form the instance representation, like most COP encoders (Khalil et al., 2017; Kool et al., 2019).
W H szore = AttentionLayer score (H'), Z' = o(H score score
where Z' E IE 'x1 are the representative scores of the N' nodes preserved in the (1- 1) block, a is a non-linear function (here we use the tanh function), and W score E [ are the parameters of the linear layer. Subse- quently, we sort the nodes according to their representative scores and select top-N' nodes (N < _ < N) to preserve. To make this pooling layer trainable via back- propagation (LeCun et al., 2002), we further combine the representative score together with the embeddings of their corresponding nodes as follows: ft' = H + Z 1, where E R is a vector with all the elements being 1. Intu- itively, this operation can separate the embeddings of high scored nodes from the embeddings of low scored nodes.
Figure 2 shows the complete encoder, where L blocks are stacked, and each block is formed by several graph atten- tion layers followed by a pooling layer. By successively applying L encoder blocks, the number of preserved nodes gradually decreases as N = a N (a is set to 0.8 in our experiments). This process constructs hierarchy of the original graph and its coarsened versions, enabling the encoder to capture multi-level structural information effec- tively. Within each block, we apply a readout layer that aggregates the embeddings after the graph attention layers by mean pooling and max pooling (Lee et al., 2019), i.e.,
Hierarchical graph encoder. Averaging the final node embeddings may result in sub-optimal instance represen- tations that are too flat to effectively capture the hier- archical structures inherent in COPs (Goh al., 2024).
Inspired by (Lee et al., 2019), we design a hier- archical graph attention encoder to address this limitation, which suc- cessively downsamples the graph of an instance using graph pooling, and aggregates features from each downsam- pling level to construct a comprehensive graph representation, as illus- trated in Figure 2. The hierarchical graph en- coder contains T. blocks.
COP' Instance
XL blocks
o' = === (Mean (1' (M' M|)
Graph attention
Hierarchical fenture
Readout
where Mean() computes the average embedding over the nodes, Max() computes the maximum along the column dimension, || denotes concatenation, and a is non-linear function. The result of provides the representation of the I-th coarsened graph. At the last layer, we also readout o from the final embeddings. To form the hicrarchical instance representation, we sum the representations of all levels Ei=
Pooling
Final feature ge
o² o2+ gf-1 Instance fentures
Figure 2: Illustration of the hi- erarchical graph encoder.
L+1 o'
3.2. Selection model
In each block, several graph attention layers are applied, and then the graph pooling layer selects representative nodes to form a coarsened graph that preserves important features. Consider the 1-th block, where the number of selected nodes denoted Nj. To quantify the representativeness of each node for graph pooling, an additional graph attention layer is introduced to compute representative scores. Specifically,
We employ a Multiple-Layer Perception (MLP) to predict the compatibility scores of neural solvers, where higher score indicates that it is more suitable to allocate the instance to the corresponding neural solver. This MLP model takes the instance representation and the instance scale N as input and outputs a score vector, where the value of each index is the score of the corresponding neural solver. In summary,
4

---

Neural Solver Selection for Combinatorial Optimization
the graph encoder and the MLP are cascaded compose selection model, which can produce the compatibility scores of solvers for the COP instances in an end-to-end manner. Advanced neural solver features can be incorporated for richer information, as discussed in Section 5. However, we find that even using fixed indices of neural solvers can be effective, which will be clearly shown our experiments. We train the selection model using a supervised dataset comprising thousands of synthetic COP instances. The objective values obtained by the neural solvers are recorded as supervision information. Intuitively, neural solver with a lower objective value (for minimization) has a higher compatibility score. To learn it, we employ two losses from the perspectives of classification and ranking.
This approach increases the likelihood of including the optimal solver but incurs additional computational overhead due to the execution of multiple solvers.
Rejection-based selection. To balance efficiency and effectiveness, we propose the rejection-based selection strategy, which adaptively selects greedy or top-k se- lection. Recognizing that the confidence of greedy se- lection varies between instances, an advanced strategy is to employ the top-k selection for low-confidence in- stances to enhance performance and utilize only greedy selection for high-confidence ones minimize compu- tational cost. To implement this strategy, we can use confidence measure to determine whether to accept or reject greedy selection. If the confidence in greedy se- lection is below a threshold, we reject it and apply the top-k selection to the instance. In this paper, we adopt the simple yet effective softmax response (Hendrycks & Gimpel, 2017) the confidence measure and de- fine the threshold by rejecting a certain fraction of test instances with the lowest confidence levels.
Classification. The selection problem is formulated as classification, where the most suitable neural solver for given instance serves as the ground truth label. By employ- ing classification loss functions such as cross-entropy loss in our experiments, we can train a selection model. How- ever, this approach focuses on identifying the optimal neural solver and ignores sub-optimal solvers, which may lead to unsatisfactory performance when the selection is inaccurate.
Top-p selection. We further propose top-p selec- tion strategy that selects the smallest subset of solvers with normalized scores sum up to at least p. It can adaptively determine the number of selected neural solvers by covering a certain amount of confidence, rather than relying on a fixed number k. The value of p is predefined adjusted according to time budget.
Ranking. The neural solvers can be sorted according to the objective values they obtain, thereby forming a ranking of the given solvers, denoted by ø : [M]] + [M]) where d(i) is the index of the rank-i solver and M is the number of solvers. We then train the selection model by maximizing the likelihood of producing correct rankings based on the computed scores (Xia al., 2008).
4. Experiments
exp(go(D))10)
To examine the effectiveness of our proposed selection framework, we conduct experiments on TSP and CVRP, investigating the following Research Questions (RQ): RQI: How does the proposed selection framework perform com- pared to individual neural solvers? RQ2: How does the proposed selection framework perform when the problem distribution shifts and the problem scale increases? RQ3: How do different implementations of components affect the performance of the framework? We introduce the experi- mental settings in Section 4.1 1 and investigate the above RQs in Section 4.2.
max E 0
log M Σj (x)())(())rt))
where go denotes the selection model with parameters 0, I denotes a problem instance, and Φ, is the ground-truth ranking on instance I. This ranking loss can leverage the dominance relationship of all neural solvers, including sub- optimal ones, which can make the selection more robust.
3.3. Selection strategies
Considering that the intricate structures of COPs may pose great challenges to the selection model, besides greedy se- lection (choosing the highest-scoring solver), we propose several compromise strategies that allow multiple solvers for a single instance based on the confidence level of the selection model, aiming to improve the overall performance with little extra cost.
4.1. Experimental settings
We generate synthetic TSP and CVRP instances by sam- pling node coordinates from Gaussian mixture distribu- tions (more details of the data generation are provided in Appendix A.2.1). For training, we generate 10, 000 TSP and CVRP instances and apply 8-fold instance augmen- tation (Kwon et al., 2020). For test, a smaller synthetic datasets with 1, 000 instances is used. Figures ((a) and 1(b) in Section depict results on the CVRP test dataset. To evaluate the distr--iittiitutio performance, we utilize
Top-k selection. The top-k selection method can be adopted for better optimality, where we select and ex- ecute the neural solvers with top-k scores for each in- stance, thus constructing a portfolio of multiple solvers.
5

---

Neural Solver Selection for Combinatorial Optimization
Two well-known benchmarks with more complex problem distributions and larger problem scales (up N = 1002): TSPLIB (Reinelt, 1991) and CVRPLIB Set-X (Uchoa et al., 2017). For TSPLIB, we select a subset of instances with N s 1002, and CVRPLIB Set-X includes instances ranging from N = 100 to 1000. These problem scales are larger than N E 500] in our training datasets. Notably, in Ap- pendix A.10, we also include experiments on larger scales up to N = 2000 for further evaluation.
best individual solver's gaps of 2.33% on TSP and 6.82% CVRP, achieved by DIFUSCO and Omni, respectively. Moreover, except utilizing the top-k strategy, our selection framework is nearly as efficient as running a single solver. In some cases, our framework can obtain better optimality gaps while consuming even less time. For instance, using rank- ing loss and greedy selection on TSP leads to the average optimality gap 1.86% with 1.33s, while the best individual solver DIFUSCO achieves 2.33% gap with I. 1.45s. In Table 1, Oracle (the fourth row) denotes the optimal performance for selection, which is obtained by running all individual solvers for each instance and selecting the best one. The best optimality gaps achieved by our selection framework (using ranking loss and top-k selection with k = 2) are close to Oracle, with gaps of 1.51% on TSP and 4.81% on CVRP, compared Oracle's gaps of 1.24% on TSP and 4.64% on framework can offer significant
Open-source neural solvers. We choose recent open- source neural solvers with state-of-the-art performance as the candidates, including Omni (Zhou et al., 2023),
BQ (Drakulic et al., 2023), LEHD (Luo et al., 2023),
DIFUSCO (Sun & Yang, 2023), T2T (Li et al., 2023),
ELG (Gao et al., 2024), INVIT (Fang et al., 2024) and MV-
MoE (Zhou et al., 2024b). More details about the realization can be found in Appendix A.2.2. Considering that some neural solvers contribute little to the overall performance, we iteratively eliminate the least contributive solver from the candidates, resulting in a more compact neural solver 700. This process reduces the zoo size to solvers for TSP and for CVRP. Further details of the elimination procedure are provided in Appendix A.3.
CVRP. Furthermore, speed advantages over Oracle, e.g., consuming an average time of 2.56s on TSP, whereas Oracle requires an average time of 8.93s. Note that complete results for all individual solvers are provided in Appendix A.
Extension of RQ1: Is the performance of the top-k se- lection better than the solver portfolio with the same size? The top-k strategy enhances the performance by running a selected subset of the solver zoo for each instance, which certainly costs more time than individual solvers. For a fair comparison, we benchmark our top-k selection method against a solver portfolio of the same size k. We construct this solver portfolio by exhaustively enumerating all possible subsets of size k and selecting the one with the best overall performance. As shown in Appendix A.6, our top-k selection consistently outperforms the size-k solver portfolio across k = 2,, 4} on all datasets, i.c., TSP, CVRP, TSPLIB and CVRPLIB Set-X, demonstrating the effectiveness of our selection model.
Hyperparameters. Limited by space, we provide the details of hyperparameters in our experiments in Ap- pendix A.2.3, including the hyperparameters of graph en- coders, hyperparameters of training, and hyperparameter of selection strategies.
Performance metrics. Following previous studies, we use the gap to the best-known solution (=(0)=er(a") as the per- formance metric, called optimality gap, where â is the solu- tion obtained by each method, a² is the best-known solution computed by extensive search of expert solvers (Helsgaun, 2017; Vidal, 2022), and cr() is the cost function of problem instance T. We also report the average time (including both the running of solvers and selection) to evaluate efficiency.
ey(a*)
RQ2: How does the proposed selection framework per- form when the problem distribution shifts and the prob- lem scale increases? We evaluate the generalization perfor- mance on two benchmarks, TSPLIB and CVRPLIR JIB Set-X, which contain out-of-distribttion and larger-scale instances. As shown in Table 2, all implementations of our selection framework generalize well, where the ranking model us- ing top-k selection improves the optimality gap by 0.88% (i.e., 1..5%-1107%%% on TSPLIB and by 0.71% (i.e., 6.% 5.39%) on CVRPLIB Set-X, compared to the best individual solvers T2T and ELG on these two benchmarks. These re- sults show that our selection framework is robust against the distribution shifts and increases in problem scale.
4.2. Experimental results
RQ1: How does the proposed selection framework per- form compared to individual neural solvers? In Table 1, we present the performance of several implementations of our selection framework on synthetic TSP and CVRP, along- side the results of the top-3 individual neural s We can observe that all implementations of our framework out- perform the best neural solver on both TSP and CVRP, demonstrating the effectiveness of our framework. For ex- ample, using ranking loss and the top-k selection strategy with k = 2, our framework achieves average optimality gaps of 1.51% on TSP and 4.82% on CVRP, surpassing the
RQ3: How do different implementations affect perfor- mance? We evaluate and compare different implementa- tions of the three components in our framework:
DIFFSCO and T2T have multiple trained models. We only report the best results of these models.
(1) Feature extraction methods. We compare the man-
6

---

Neural Solver Selection for Combinatorial Optimization
Table I: Empirical results on synthetic TSP and CVRP datasets, reporting the mean (standard deviation) over five independent runs. The top three individual solvers are included for comparison, and Oracle denotes the optimal performance for selection, which computed by running all individual solvers in the zoo for each instance and selecting the best one. The best individual solver and its results are underlined, and the best optimality gaps, excluding Oracle, are highlighted in boldface.
TSP
CVRP
Methods
Methods
Gap
Time
Gap
Time
BQ (3rd)
3.00%
1.40s
LEHD (3rd)
7.37%
1.01s
T2T (2nd)
2.40%
1.58s
BQ (2nd)
7.20%
1.59s
DIFUSCO (Ist)
2.33%
1.45s
Omni (1st)
6.82%
0.24s
Oracle
1.24%
8,93s
Oracle
4. 4.64%
4.38s
Selection by classification
Selection by classification
Greedy
1.94% (0.02%)
1.36s (0.01s)
Greedy
5.35% (0.02%)
0.64s (0.01s)
Top-k (k- = 2)
1.53% (0.01%)
2.52s (0.04s)
Top-k (k- = 2)
4.81% (0.01 %)
1.87s (0.03s)
Rejection (20%)
1881% (0.01%)
1.63s (0.01s)
Rejection (20%)
5.19% (0.03%)
0.77s (0.01s)
Top-p (p- = 0.5)
1.84% (0.03%)
1.55s (0.06s)
Top-p (p- 0.8)
5.16% (0.03%)
0.87s (0.08s)
Selection by ranking
Selection by ranking
Greedy
1.86% (0.01%)
1,33s (0.01s)
Greedy Top-k (k = 2)
5.31% (0.01%)
0.62s (0.01s)
Top-k (k= = 2)
1.51 % (0.02%)
2.56s (0.03s)
4.82% (0.01%)
1.90s (0.04s)
Rejection (20%)
1.75% (0.02%)
1.63s (0.01s)
Rejection (20%)
5.15% (0.02%)
0.74s (0.01s)
Top-p (p= = 0.5)
1.68% (0.02%)
1.86s (0.07s)
Top-p (p- 0.8)
4.99% (0.02%)
1.03s (0.03s)
ual features (Smith-Milke et al., 2010) (see Appendix A.4), graph attention encoder (Kool et al., 2019), and hierarchical graph encoder in Table 3. All methods are trained using ranking loss, and we report the optimality gap with greedy selection. As shown in Table 3, even the simplest manual features perform well, achieving better results than the best individual solver across three datasets - TSP, CVRP, and TSPLIB. This further validates the effectiveness of our selec- tion framework. Comparing the third and fourth columns, we observe that the graph attention encoder consistently outperforms manual features all datasets, verifying the superiority of learned features. More manual features are compared in Appendix A.5. Furthermore, by comparing the fourth and fifth columns, we find that while the graph atten- tion encoder has already been effective on synthetic datasets, introducing the hierarchical encoder can further improve generalization performance on -iitti--iitiittiionn datasets, TSPLIB and CVRPLIB Set-X, which is quite important in practice. This enhanced generalization capability may be attributed to the hierarchical encoder's 's ability to leverage the inherent hicrarchical structures in COPs. More ablation studies of the hierarchical encoder are in Appendix A.7.
optimal solvers.
(3) Selection strategies. Greedy selection efficient by selecting only the predicted best solver. Instead, top-k se- lection selects the best k solvers for better optimality gaps, but resulting in longer time. Rejection-basee and top-p se- lection provide trade-off between optimality gap and time. Here, we focus on the evaluation of rejection- and top-p selection. We tune their hyperparameters (e.g.. rejec- tion ratio, k and p) to obtain a range of results, provided in Appendix A.8. The results show that the rejection-based selection with smaller i (k- = 2 or 3) tends to achieve better trade-off. Comparing top-p and rejection-based selection, their performance has no obvious difference. This is ex- pected as their principles are both running more individual neural solvers when the confidence of the selection model is insufficient. However, the top-p selection may be preferable in practice since only one hyperparameter p is associated.
4.3. Exploration on neural solver features
To enable generalization to unseen neural solvers, we pro- pose a preliminary feature extraction method that leverages representative instances to characterize each neural solver. Specifically, for a given neural solver, we sort those in- stances where the neural solver performs the best in ascend- ing order according to the ratio of the objective value that the solver obtains to the runner-up objective value and select the top 1% as its representative instances. Then, we use an instance encoder to obtain embeddings for representative instances as their token vectors. A two-layer transformer model further processes these token vectors to learn a sum-
(2) Loss functions to train the selection model. We can clearly observe from Tables 1 and 2 that the model trained with ranking loss generally outperforms that trained with classification loss, particularly when employing top-p selec- tion or under dutrof-distrbbution settings. We also compare their accuracy of selecting the best single individual, which is similar as shown Appendix A.9. Thus, the benefit of ranking loss over classification loss shows the importance of incorporating the dominance relationships among sub-
7

---

Neural Solver Selection for Combinatorial Optimization
Table 2: Generalization results to TSPLIB and CVRPLIB Set-X datasets, which contain real-world out-of-distribution instances with larger scales.
TSPLIB
CVRPLIB Set-X
Methods
Methods
Gap
Time
Cap
Time
BQ (3rd)
3.04%
1.44s
BQ (3rd)
10.31 %
2.60s
DIFUSCO (2nd)
2.13%
1.44s
Omni (2nd)
6.21 %
0.38s
T2T (Ist)
1.95%
1.74s
ELG (Ist)
6.10%
1.31s
Oracle
0.89%
9.14s
Oracle
5.10%
6.81s
Selection by classification
Selection by classification
Greedy
1.54% (0.05%)
1.33s (0.02s)
Greedy
5.96% (0. (0.1
1.06s (0.08s)
Top-k (k- = 2)
1.22% (0.10%)
2.47s (0.02s)
Top-k (k- = 2)
5,44% (0.08%)
2.40s (0.25s)
Rejection (20%)
1.42% (0.11%)
1.54s (0.03s)
Rejection (20%)
5.83% (0. 12%)
1.31s (0.09s)
Top-p (p- 0.5)
1.49% (0.11%)
1.37s (0.028)
Top-p (p 0.8)
5.79% (0.09%)
1.42s (0.17s)
Selection by ranking
Selection by ranking
Greedy
1.33% (0.06%)
1.28s (0.03s)
Greedy
5.76% (0.04%)
1.31s (0.10s)
Top-k (k = 2)
1.07% (0.03%)
2.48s (0.02s)
Top-k (k: = 2)
5.39% % (0.06%)
2.56s (0.13s)
Rejection (20%)
1.26% (0.03%)
1.51s (0.04s)
Rejection (20%)
5.63% (0.05%)
1.60s (0.08s)
Top-p 0.5)
1.28% (0.04%)
1.46s (0.06s)
Top-p (p 0.8)
5.61% (0.03%)
1.72s (0.08s)
Table 3:
Mean (standard deviation) of optimality gaps of different feature extraction methods. All the models are trained using ranking loss, and employ greedy selection.
Datasets
Best solver
Manual
Attention encoder
Hierarchical enedoer
TSP
2.33%
1.97% (0.01%) ()
1.87% (0.02%)
1.86% (0.01 %-) 5.31% (0.01%) ())
CVRP
6.82%
5.49% (0.08%)
5.30% (0.01 %)
TSPLIB
1.95%
1.83% (0.03%)
1.45% (0. 1%) 5.87% (0.06%)
1.33% % (0.06%) 5.76% % (0.04%)
CVRPLIB
6.10%
6.35% (0.06%)
marized feature, which serves as the feature representation of the neural solver.
sentation. We apply two attention layers for this purpose. The first layer is a self-attention mechanism applied over all tokens (including the summary token), enabling interactions among them. The second attention layer uses only the sum- mary token as the query and all tokens keys and values, effectively aggregating information from all tokens into the summary token. The final embedding of the summary token is then output as the neural solver's representation.
To integrate a newly added neural solver, we first identify its representative instances from synthetic dataset and employ the aforementioned networks to compute its feature repre- sentation. The selection model can then leverage the newly added solver by considering its feature during selection, without the need for any fine-tuning. The implementation details of each component are described as follows.
Selection model with neural solver features. The se- lection model integrates both the instance features and the neural solver features output score for each instance- solver pair. We employ MLP to compute these scores. For each instance, the scores across all neural solvers are normalized to derive the probability distribution.
Instance tokenization. We use hierarchical graph coder as the tokenization encoder to generate embeddings for each representative instance. To stabilize the instance to- kens during training, we update 0' using a momentum-baste moving average of the parameters 0 of the instance feature encoder: 0' <- m-0' + (1 - (1mmm))mmmm m)-0, -0, where m E [0, 1) is a mo- mentum coefficient (We set m 0.99 in experiments). Only the parameters 0 updated via back-propagation. This momentum update ensures that 0' evolves more smoothly than 0, resulting in stable instance tokenization.
To evaluate the effectiveness of this method, we remove the second-best neural solver from the current solver zoo, train the selection model using the supervision information over the pruned solver zoo, and reintroduce the removed solver during testing. Figure 3 presents the top-k selection per- formance with and without the newly added (extra) solver. The results show that the performance with the newly added solver is generally better than the performance without it, demonstrating that the selection model can leverage the
Transformer architecture. For each neural solver, we utilize the tokens of its representative instances along with a learnable summary token to compute a summary repre-
8

---

Neural Solver Selection for Combinatorial Optimization
TSPLIB
Section 4.3, we design preliminary method for extracting features of neural solvers to facilitate generalization un- seen solvers. The results show that it enables generalization to unseen neural solvers, where adding an extra solver can improve the selection performance. For future improve- ments, some approaches may be worth exploring, such as utilizing large language models to encode the neural solvers from their codes and descriptions (Wu et al., 2024), or learn- ing representations from their trained parameters (Kofinas et al., 2024), which can involve internal solver information and potentially bring improvements.
1.8
1.3-
1.6
1.2
1.1
1.44
1.0
1.2
Top k (With extra solver)
Top-k
Figure 3: Performance of introducing an extra neural solver based on the neural solver feature. The results of top-k selec- tion with and without extra neural solver are presented. The horizontal axis represents the number of selected solvers.
Runtime-aware selection for learn-to-seach solvers. In this paper, since the average runtime of most individual neu- ral solvers short (approximately 1-2 seconds), we ignored their time difference during the training of the selection model, and only used the objective values obtained by the neural solvers as supervision information (by classification or ranking). However, if there are some time-consuming learn-to-search solvers, such as NeuOpt (Ma et al., 2021; ; 2023) and local reconstruction methods (Kim et al., 2021; Ye et al., 2024), in the solver pool, the runtime should be considered in the performance ranking, In such cases, de- veloping runtime-aware selection method to balance com- putational time and solution optimality would be necessary.
information of unseen solvers without any finetuning. In other words, the selection model can generalize to unseen solvers. However, we observe a slight decrease in top-1 per- formance, indicating that the current feature design is not accurate enough for the most precise top-1 selection. This highlights the need for further refinement and optimization to our preliminary feature extraction method.
5. Conclusion and discussions
Enhance the neural solver zoo by training. As shown in Figure 6, current neural solvers can exhibit complementary performance over instances without any modification, which has motivated our framework of neural solver selection. In- spired by the population- based training (Grinsztajn et al., 2023), we can further enhance their complementary ability through finetuning, i.e., each neural solver is finetuned on those instances where it performs the best. We can also train new solvers from scratch by maximizing their performance contribution to the current solver zoo and iteratively add such new solvers for enhancement. Moreover, to facilitate the training and deployment of neural solver zoo, is es- sential to develop unified platform that provides interfaces for executing and training diverse neural solvers, such as an extension to the existing RIACO (Berto et al., 2024).
In this paper, we propose general framework for neural solver selection for the first time, which can effectively select suitable solvers for each instance, leading to signif- icantly better performance with little additional computa- tional time, as validated by the extensive experiments on two well-studied COPs, TSP and CVRP. Besides TSP and CVRP, our proposed selection framework is adaptable to other prob- lems. For new problems, one only needs to customize the feature extraction component. For instance, when adapting our framework to scheduling problems, one can adjust the graph attention encoder according to MatNet (K woo et al., 2021) (i.e., add edge embeddings). We hope this preliminary work can open a new line for neural combinatorial optimiza- tion. Within the proposed selection framework, we prelimi- narily investigate several implementations of the three key components: Feature extraction, training loss functions, and selection strategies. Techniques such hierarchical graph encoder, ranking loss, rejection-basee selection, and top-p selection notably enhance overall performance. Beyond the techniques presented, we discuss several promising avenues for further research under this framework.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Feature extraction for neural solvers. Our method, which uses fixed indices for neural solvers, assumes static neural solver 700 and cannot directly utilize any newly added neu- ral solvers during deployment. To enable zero-shot general- ization to unseen neural solvers, it is essential to construct a smooth feature space for solvers, where those with similar preferences and biases are positioned closely together. In
A Acknowledgement
This work was supported by the Science and Technol- ogy Project of the State Grid Corporation of China (5700- 202440332-2211-2X1,
9

---

Neural Solver Selection for Combinatorial Optimization
References
Cheng, H., Zheng, H., Cong, Y., Jiang, W., and Pu, S. Se- lect and optimize: Learning aolve large-scale TSP instances. In Proceedings of the 26th International Con- ference on Artificial Intelligence and Statistics (AISTATS), pp. 1219-1231, Valencia, Spain, 2023.
Bachlechner, T., Majumder, B. P.,. Mao, H. H.,, Cottrell, G., and McAuley, J. J. Rezero is all you need: fast convergence at large depth. In Proceedings of the 37th Conference on Uncertainty in Artificial Intelligence (UAI), pp. 1352-1361, Virtual, 2021.
Dantzig, G. B. and Ramser, J. H. The truck dispatching problem. Management Science, 6(1):80-91 11880-91,-0 1959.
Bai, Y., Zhao, W., and Gomes, C. P. Zero training overhead portfolios for learning to solve combinatorial problems. arXiv:2/02.03002 2021.
Drakulic, D., Michel, S., Mai, F., Sors, A., and Andreoli, J.- M. BQ-NCO: Bisimulation quotienting for generalizable neural combinatorial optimization. In Advances in Neural Information Processing Systems 36 (NeurIPS), pp. 77416- 77429, New Orleans, LA, 2023.
Bello, I,, Pham, H., Le, Q. V., Norouzi, M., and Bengio, S. Neural combinatorial optimization with reinforce- ment learning. In Proceedings of the 5th International Conference on Learning Representatioss (ICLR), Toulon, France, 2017.
Fang, H., Song, Z.,, Weng, P., and Ban, Y. INVIT: A general- izable routing problem solver with invariant nested view transformer. In Proceedings of the 41 International Con- ference on Machine Learning (ICML), pp. 12973-12992, Vienna, Austria, 2024.
Bengio, Y., Lodi, A., and Prouvost, A. Machine learning for combinatorial optimization: A methodological tour d'horizon. European Journal of Operational Research, 290(2):405-421, 2021.
Fu, Z.-H., Qiu, K.-B., and Zha, H. Generalize small pre-trained model to arbitrarily large TSP instances. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pp. 7474-7482, Virtual, 2021.
Berto, F., Hua, C., Park, J., Luttmann, L., Ma. Y., Bu, F., Wang, J., Ye, H., Kim, M.. Choi, S., Zepeda, N. G., Hottung, A., Zhou, J., Bi, J., Hu, Y., Liu, F., Kim, H., Son, J., Kim, H., Angioni, D., Kool, W., Cao, Z., Zhang, J., Shin, K., Wu, C., Ahn, S., Song, G., Kwon, C., Xie, L., and Park, J. RL4CO: An extensive reinforce- ment learning for combinatorial optimization benchmark. arXiv:2306.1711 2024. https: / /ttth/g.ttt/ttt//// com/ a ai4co/r1 1cc.
Gao, C., Shang. H., Xue, K., Li, D., and Qian, C. To- wards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy. In Proceedings of the 33rd International Joint Conference Artificial Intelligence (IJCAI), pp. 6914-69223 Jeju, Korea, 2024.
Goh, Y. L., Cao, Z., Ma, Y., Dong, Y., Dupty, M. H., and Lee, W. S. Hierarchical neural constructive solver for real- world TSP scenarios. In Proceedings of the 30th ACM SIGKDD Conference Knowledge Discovery and Data Mining (KDD), pp. 884-895, Barcelona, Spain, 2024.
Bi, J., Ma. Y., Wang. J., Cao, Z., Chen, J., Sun, Y., and Chee, Y. M. Learning generalizable models for vehicle routing problems via knowledge distillation. In Advances in Neural Information Processing Systems 35 (NeurIPS), pp. 31226-312222 1238, New Orleans, LA, 2022.
Grinsztajn, N., Furelos- Blannoo D., Surana, S., Bonnet, C., and Barrett, T. Winner takes it all: Training per- formant RL populations for combinatorial optimization. pp. 48485-48509, New Orleans, I.A, 2023.
Campello, R. J. G. B., Moulavi, D., and Sander, J. Density- based clustering based on hierarchical density estimates. In Proceedings of the 17th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), pp- 160-172, Gold Coast, Australia, 2013.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, Las Vegas, NV, 2016.
Cappart, Q. Chételat, D., Khalil, E. B., Lodi, A., Morris, C., and Veličković, P. Combinatorial optimization and rea- soning with graph neural networks. Journal of Machine Learning Research, 1613
He, X., Shang, H., and Qian, C. How to train algorithm selection models: Insights from black-box continuous optimization. In 15th Workshop on Evolutionary Com- putation for the Automated Design of Algorithms at GECCO 25, Málaga, Spain, 2025.
Chalumeau, F., Surana, S., Bonnet, C., Grinsztajn, N., Pre- torius, A., Laterre, A., and Barrett, T. Combinatorial optimization with policy adaptation using latent space search. In Advances in Neural Information Processing Systems 36 (NeurIPS), pp. 7947-7959, New Orleans, LA, 2023.
Heins, J., Bossek, J., Pohl, J., Seiler, M., Trautmann, H.,, and Kerschke, On the potential of normalized TSP features for automated algorithm selection. In Proceedings of the
10

---

Neural Solver Selection for Combinatorial Optimization
16th ACM/SIGEVO Workshop on Foundations of Genetic Algorithmss (FOGA), pp. 1-15, Virtual Event, Austria, 2021.
Kofinas, M., Knyazev, B., Zhang, Y., Chen, Y., Burghouts, G. J., Gavves, E.,, Snoek, C. G., and Zhang, D. W. Graph neural networks for learning equivariant representations of neural networks. In Proceedings of the 12th Interna- tional Conference on Learning Representations (ICLR), Vienna, Austria, 2024.
Helsgaun, K. An effective implementation of the lin- kernighan traveling salesman heuristic. European Journal of Operational Research, (26(1):106-1) 2000.
Konstantakopoulls, G. D., Gayialis, S. P., and Kechagias, E. P. Vehicle routing problem and related algorithms for logistics distribution: A literature review and classifica- tion. Operational Research, 22(3):2033-206) 2022.
Helsgaun, K. An extension of the lin-kernighan kernaghannhellgaunn TSP solver for constrained traveling salesman and vehicle routing problems. Technical report, 2017.
Hendrycks, D. and Gimpel, K. A baseline for detecting misclassified and out-of-distribution examples in neu- ral networks. In Proceedings of the 5th International Conference on Learning Representations (ICLR), Toulon, France, 2017.
Kool, W., van Hoof, H.. and Welling, M. Attention, learn to solve routing problems! In Proceedings of the 7th International Conference on Learning Representations
(ICLR), New Orleans, LA, 2019.
Kwon, Y.DD., Choo, J., Kim, B., Yoon, I., Gwon, Y., and Min, S. POMO: Policy optimization with multiple op- tima for reinforcement learning. In Advances in Neural Information Processing Systems 33 (NeurIPS), pp. 21 188- 21198, Virtual, 2020.
Jiang, Y., Wu, Y., Cao, Z., and Zhang, J. Learning to solve routing problems via distributionally robust optimization. In Proceedings of the 36th AAAI Conference Artificial Intelligence (AAAI), pp. 9786-9794, Virtual, 2022.
Jiang, Y., Cao, 7., Wu, Y., Song, W., and Zhang, J. Ensemble-bar based deep reinforcement learning for vehicle routing problems under distribution shift. In Advances in Neural Information Processing Systems 36 (NeurIPS), pp- 531 13112-53125, New Orleans, LA, 2023.
Kwon, Y.-D., Choo, J., Yoon, I., Park, M., Park, D., and Gwon, Y. Matrix encoding networks for neural combina- torial optimization. volume 34, pp. 5138-510 5149, Sydney, Australia, 2021.
LeCun, Y., Bottou, L., OrT, G. B., and Müller, K.-R. Effi- cient backprop. In Neural networks: Tricks of the trade, volume 7700, pp. 9-48, 2002.
Joshi, C. K., Laurent, T., and Bresson, X. An efficient graph convolutional network technique for the travelling salesman problem. arXiv:1906.011 2019.
Joshi, C. K., Cappart, Q., Rousscau, L., and Laurent, T. Learning the travelling salesperson problem requires rethinking generalization. Constraints, 27(1-2):70-98, 2022.
Lee, J., Lee, I., and Kang. J. Self-attention graph pooling. In Proceedings of the 36th International Conference on Machine Learning (ICML), pp. 1734-3743 Long Beach, California, 2019.
Kerschke, P., Hoos, H. H., Neumann, F., and Trautmann, H. Automated algorithm selection: Survey and perspectives. IEEE Transactions on Evolutionary Computation, 27(1): 2019.
Li, Y., Guo, J., Wang, R., and Yan, T2T: From distribution learning in training to gradient search in testing for combi- natorial optimization. In Advances in Neural Information Processing Systems 36 (NeurlPS), pp. 10020-50040,, New Orleans, LA, 2023.
Khalil, E. B., Dai, H., Zhang, Y., Dilkina, B., and Song, L. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems 30 (NeurIPS), pp. 6348-6358, Long Beach, CA, 2017.
Liu, F., Lin, X., Liao, W., Wang, Z., Zhang, Q., Tong, X., and Yuan, M. Prompt learning for generalized vehicle routing. In Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI), pp. 6976 6984, Jeju, Korea, 2024.
Kim, M., Park, J., and kim, j. Learning collaborative poli- cies to solve NP-hard routing problems. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems 34 (NeurIPS), pp. 10418-10433 2021.
Luo, F., Lin, X., Liu, F., Zhang, Q., and Wang. Z. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In Advances in Neural Infor- mation Processing Systems 36 (NeurIPS), pp. 8845-8864, New Orleans, LA, 2023.
Kingma, D. and Ba, J. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Representations (ICLR), San Diego, CA, 2015.
Ma, Y., Li, Cao, Z., Song, W., Zhang, L., Chen, Z., and Tang, J. Learning to itcratively solve routing problems with dual- dual-aspect collaborative transformer. In Advances

---

Neural Solver Selection for Combinatorial Optimization
in Neural Information Processing Systems 34 (NeurIPS), pp. 11096-11100 11107, Virtual, 2021.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, t.., and Polosukhin, I. Atten- tion is all you need. In Advances in Neural Information Processing Systems 30 (NeurIPS), pp. 1998-6008 Long Beach, CA, 2017.
Ma, Y., Cao, Z., and Chee, Y. M. Learning search feasible and infeasible regions of routing problems with flexible neural k-Opt. In Advances in Neural Information Pro- cessing Systems 36 (NeurIPS), pp. 49555-49578, New Orleans, LA, 2023.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks. In Pro- ceedings of the 6th International Conference on Learning Representations (ICLR), Vancouver, Canada, 2018
Manchanda, S., Michel, S., Drakulic, D., and Andreoli, J.-M. On the generalization of neural combinatorial op- timization heuristics. In Proceedings of the 33rd/26th Joint European Conference on Machine Learning and Knowledge Discovery in Databases (ECML PKDD). Pp.
Vidal, T. Hybrid genetic search for the CVRP: Open-source implementation and swap* neighborhood. Computers & Operations Research, 140: 105643,, 2022.
426-442, Grenoble, France, 2022.
Vinyals, O., Fortunato, M., and Jaitly, N. Pointer networks. In Advances in Neural Information Processing Systems 28 (NeurlPS), pp.
Nazari, M., Oroojlooy, A., Takáč, M., and Snyder, L. V. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems 31 (NeurIPS), pp. 9861-9871, Montréal, Canada, 2018.
Montreal, Canada, 2015.
Wang. C., Yu, Z., McAleer, S., Yu, T., and Yang, Y. ASP:
Learn a universal neural solver! IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(6))4102-
Reinelt, G. TSPLIB- A traveling salesman problem library. ORSA Journal on Computing, 3(4):376-384, 1991.
4114, 2024.
Wolpert, D. H. and Macready, W. G. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1):67-22, 1997.
Salmona, A., De Bortoli, V., Delon, J., and Desolneux, A. Can purb-forward generative models fit multimodal distri- butions? In Advances in Neural Information Processing Systems 35 (NeurIPS), pp. 10766-10779, New Orleans, LA, 2022.
Wu, X., Zhong, Y., Wu, J., Jiang, B., and Tan, K. C. Large language model-enhanced algorithm selection: Towards comprehensive algorithm representation. In Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI), pp. 5235-5244, Jeju, Korea, 2024.
Sanokowski, S., Hochreiter, S., and Lehner, S. diffusion model framework for unsupervised neural combinatorial optimization. In Proceedings of the 41st International Conference on Machine Learning (ICML), Vienna, Aus- tria, 2024.
Xia, F., Liu, T.-Y., Wang, J., Zhang, W., and Li, H. List- wise approach to learning to rank: Theory and algorithm. In Proceedings of the 25th International Conference on Machine Learning (ICMI.), pp. 1192-1199, Helsinki, Fin- land, 2008
Seiler, M., Pohl, J., Bossek, J., Kerschke, P., and Trautmann, H. Deep learning as a competitive feature- free approach for automated algorithm selection on the traveling sales- person problem. In Proceedings of 16th International Conference Parallel Problem Solving from Nature (PPSN), pp. 48-64, Leiden, The Netherlands, 2020.
Yc, H., Wang. J., Cao, Z., Liang, H., and Li, Y. DeepACO: neural-enhancee ant systems for combinatorial optimiza- tion. Advances in Neural Information Processing Systems 36 (NeurIPS), pp. 43706-43722 2023.
Smith-Miles, K., Van Hemert, J., and Lim, X. Y. Understand- ing TSP difficulty by learning from evolved instances. In Proceedings of the 4th International Conference on Learning and Intelligent Optimization (LJON), pp. 266- 280, Venice, Italy 2010.
Ye, H., Wang. J., Liang, H., Cao, Z., Li, Y., and Li, F. GLOPP: Learning global partition and local construction for solving large-scale routing problems in real-time. In Proceedings of the 38th AAAI Conference on Artificial Vancouver, Canada, 2024.
Sun, Z. and Yang, Y. DIFUSCO: Graph-based diffusion solvers for combinatorial optimization. In Advances in Neural Information Processing Systems 36 (NeurIPS), pp. 3706-3731, New Orleans, LA, 2023.
Intelligence. pp.
Zhang, J., Ding, G., Zou, Y., Qin, S., and Fu, J. Review of job shop scheduling research and its new perspectives under industry 4.0. Journal of Intelligent Manafacturing, 30:1809-1838 2019.
Uchoa, E., Pecin, D., Pessoa, A., Poggi. M., Vidal, T., and Subramanian, A. New benchmark instances for the ca- pacitated vehicle routing problem. European Journal of Operational Research, 257(3):845-885) 858, 2017.
Zhang, Y.-K., Huang, T.-J., Ding, Y.-X., Zhan, D.-C., and Ye, H.J. Model spider: Learning to rank pre-trained
12

---

Neural Solver Selection for Combinatorial Optimization
models efficiently. Advances in Neural Information Pro- cessing Systems 36 (NeurIPS), pp. 13692213779, 2023.
Zheng, Z., Zhou, C., Xialiang, T., Yuan, M., and Wang, Z. UDC: A unified neural aeride-and-conquer frame- work for large-scale combinatorial optimization problems. 1xX0:24477.00312.. 2024.
Zhou, C., Lin, X., Wang, Z., Tong, X., Yuan, M., and Zhang, Q- Instance-conditioned adaptation for large- scale generalization of neural combinatorial optimization. arXiv:2405.0 00055.00066... 2024a.
Zhou, J., Wu, Y., Song. W., Cao, Z., and Zhang. J. Towards omni-generalizable neural methods for vehicle routing problems. In Proceedings of the 40th International Con- ference on Machine Learning (ICML), pp. 42769-42789, Honolulu, HI, 2023.
Zhou, J., Cao, Z. Wu, Y., Song, W. Ma, Y., Zhang, J., and Xu, MVMoE: Multi-task vehicle routing solver with mixture-of-experts. In Proceedings of the 39th Inter- national Conference on Machine Learning (ICML), pp. 61804-61824, Vienna, Austria, 2024b.
13

---

Neural Solver Selection for Combinatorial Optimization
A. Appendix
A.1. Graph attention layer
The graph attention layer is composed of two sub-layers: a multi-head attention sub-layer (Vaswani et al., 2017) and a ferd-forward sub-layer. Each sub-layer is equipped with residual connection (He et al., 2016) and ReZero normaliza- tion (Bachlechner et al., 2021) for stable convergence of training. Denote the embedding of the i-th node h2 (i.e., the i-th row of H). Since the graphs TSP and CVRP are typically considered be fully connected, the graph attention layer is calculated as
1 h. 1-- + a (H n/2 ,..., ...l)
h = h aoFFhF)(
where ( is the layer index, i is the node index, a' is learnable parameter used in the ReZero normalization, MHA and FF are short for the multi-hear attention and the feed-forward network, respectively. For the implementations of the basic components MHA and FF, we refer to (Vaswani et al., 2017) for details. Specifically, following the common settings of previous works, we set the dimension of h to 128, the number of heads in MHA to 8, and the hidden dimension of FF to 512.
A.2. Supplement of experimental settings
1. DATA GENERATION
Synthetic TSP and CVRP instances are generated for training, where the node coordinates, demands, and vehicle capacities are all sampled from manually defined distributions. The scale of each instance is sampled from [50, 500] randomly. Details of node coordinates, vehicle capacity, and node demands are introduced as follows.
Node coordinates To generate diverse training instances, we utilize Gaussian mixture distributions to sample the node coordinates for both TSP and CVRP, which common in previous works (Manchanda et al., 2022; Zhou et al., 2023) and demonstrates effectiveness on approximating various node distributions with different hardness levels (Smith-Miles et al., 2010). First, we randomly select the number of Gaussian components distribution) and partition the nodes randomly into groups, one for each component. For each Gaussian component, we sample the mean coordinates = (I yu) by I (0, 1) and Uy ~ (0, 1), and sample the variances var, and var, uniformly from [1, 100]. The covariance cov is sampled uniformly from |-v var, vary, var, var,). forming the
(0, 15) (when = 0, we use the uniform
covariance matrix Σ varz
cov
Node coordinates are sampled from the N Σ) and then scaled to the square of
Cov
vary
y,y E [0, 1]. Unlike conventional Gaussian mixture distributions (Manchanda et al., 2022; Zhou et al., 2023), which often use an identity covariance matrix, our approach employs randomized covariance matrices Σ. This modification can produce more diverse instances by introducing more variability in the node distributions.
Vehicle capacity and node demands We employ two vehicle capacity distributions to generate CVRP instances: (1) Scale-related distribution (Zhou al., 2023): The vehicle capacity is proportional to the scale N, defined as Q - 30 + N (2) Triangular distributions (Uchoa et al., 2017): The parameters of the triangular distribution include the upper limit ub. mode m, and lower limit 1b, which are randomly sampled in succession as follows: ub ~ U200, N) m (5, ub), and lb ~ U3, m). The triangular distribution T(b,, m, ub) is then used to generate vehicle capacities, resulting in more diverse CVRP instances compared to the fixed capacity setting (Nazari et al., 2018). Each capacity distribution is selected with equal probability. Node demands m. are sampled uniformly from (1, and normalized by dividing by Q.
A.2.2. DETAILED SETTINGS OF OPEN SOURCE SOLVERS
We choose recent open-source neural solvers with state-of-the-att performance the candidates, including Omni (Zhou et al., 2023), BQ (Drakulic al., 2023), LEHD (Luo al., 2023), DIFUSCO (Sun & Yang, 2023), T2T (Li et al., 2023), ELG (Gao et al., 2024), INVIT (Fang et al., 2024) and MVMoE (Zhou et al., 2024b). Greedy decoding is used for all the methods to avoid stochasticity. We set the pomo size to 100 and the augmentation number to 8 for the methods based on POMO (Kwon et al., 2020). The number of denoising steps is set to 50 and the number of 2-opt iterations set to 100 for diffusion-basee methods. These individual solvers constitute a neural solver zoo. Ideally, if we can always select the best solver from the zoo for each instance, the optimal performance achieved, which also the performance upper bound
14

---

Neural Solver Selection for Combinatorial Optimization
of our selection model. Considering that some neural solvers contribute little the overall performance, we iteratively eliminate the least contributive solver from the candidates, resulting in a more compact neural solver 200, which reduces the 200 size to 7 solvers for TSP and 5 for CVRP. Further details of the elimination procedure are provided in Appendix A.3.
A.2.3. DETAILED SETTINGS OF HYPERPARAMETERS
(1) Hyperparameters of graph encoders. For the graph attention encoder, we set the number of layers to 4. For the hierarchical graph encoder, we use 2 blocks where each block has 2 attention layers. The embedding dimension is set to 128. Other details of encoders can be found in Appendix 1. (2) Hyperparameters of training. The Adam optimizer (Kingma & Ba, 2015) is employed for training, where we the learning rate The number of epochs is set to 50. The final model is chosen according to the performance on validation dataset with 1, 000 synthetic instances. We train 5 selection models using different random seeds and report the mean and standard deviation of their performance. (3) Hyperparameters of selection strategies. For the top-k strategy, we set k = 2. For the rejection-basee based strategy, we reject the 20% of instances with the lowest confidence levels (i.e., the highest selection probability of all individual solvers), and apply top-2 selection to these rejected instances. For the top-p strategy, we set p = 0.5 for TSP and p 0.8 for CVRP.
10-4 and the weight decay to 10-6,
A.3. Eliminate useless neural solvers
The preserved neural solvers should have distinct strengths in certain problem instances, ensuring that they can bring significant improvements in overall performance. Motivated by this, we propose a simple yet effective heuristic strategy to build the neural solver zoo based on the assessment of their contribution the overall performance.
Given the alternative neural solvers S = {si, $2, ".... we assess the contribution of specific solver 8, S by the degradation of performance after removing it. That is, the assessment of s, can be formalized as
A(s:) E, (Pr(S) P((())
E,
where (-) denotes the performance of a neural solver 700 on instance Here we use the percentage of the optimality gap to define (-) and employ validation set for the estimation of expectations. According to this criteria, we can estimate the alternative solvers and remove the one with the lowest assessed contribution from S. This process repeats iteratively until for all 8, E S, A(s.) surpasses the predefined threshold 6, indicating the significance of each alternative neural solver. In practice, we collect the prevailing competitive neural solvers in the community to compose the original S and set 5 as 0.01%.
The neural solver zoos before and after climination are listed in Table 4. Note that for DIFUSCO and T2T, multiple models are released. We collect both the models trained on the N = 100 dataset and the N = 500 dataset as alternatives simultaneously.
Table 4: The neural solver zoo before and after elimination.
Stage
Neural solver zoo for TSP
Neural solver 700 for CVRP
BQ, LEHD, Omni, ELG, INVIT. DIFUSCO (N=100), DIFUSCO (N=500), T2T (N=100), T2T (N=500)
Before elimination
BQ, LEHD, Omni, ELG. INVIT, MVMoE
BQ, LEHD, ELG, DIFUSCO (N=100), DIFUSCO (N=500), T2T (N=100), T2T (N=500)
After elimination
BQ, LEHD, Omni, ELG, MVMoE
A.4. Manual features
We reproduce the manual features proposed by (Smith-Miles et al., 2010), which use statistical information and cluster analysis results to describe the characteristics of TSP. In this paper, we adopt these features: the standard deviation of the distances, the coordinates of the instance centroid, the radius of the TSP instance, the fraction of distinct distances, the variance of the normalized nearest neighbour distances (nNNd's), the coefficient of variation of the nNNd's, the ratio of
15

---

Neural Solver Selection for Combinatorial Optimization
the number of clusters to the number of nodes (Here we use HDBSCAN algorithm (Campello et al., 2013) to generate clusters), the ratio of number of outliers to nodes, and the mean radius of the clusters. For CVRP, we further add the mean and standard deviation of node demands to the features.
A.5. Comparisons with traditional algorithm selection methods
To further demonstrate the effectiveness of our proposed techniques, provide additional comparison results between proposed method and existing algorithm selection methods for non-neural TSP solvers (Smith-Miles et al., 2010; Seiler et al., 2020), as shown in Table 5. In fact, the method of using features from (Smith-Miles et al., 2010) and our ranking model was also compared in Table 3. The R package salesperson" provides the up-to-now most comprehensive collection of features for TSP and is widely used in algorithm selection methods (Seiler et al., 2020; Heins et al., 2021). Based on the feature set of salesperson, we reproduce an advanced algorithm selection method (Seiler et al., 2020) following the pipeline that computes hand-crafted features, conducts feature selection, and applies random forest for classification, where employ the univariate statistical test to select important features. Besides, also combine the salesperson features with our ranking model for ablation, denoted by "(Seiler et al., 2020) Ranking" in Table 5.
Table 5: Comparison experiments with algorithm selection methods for TSP. We report the mean (standard deviation) over five independent runs.
Synthetic TSP
TSPLIB
Methods
Gap
Time
Gap
Time
Single best solver Oracle
2.33%
1.45s
1.95%
1.74s
1,24%
8.93s
0.89%
9.14s
Algorithm selection methods
(Smith-Miiee al., 2010) Ranking
1.97% (0.01%) (%) 2.12% (0.04%)
1.37s (0.01s)
1.83% (0.03%)
1.32s (0.05s)
(Seiler al., 2020)
1.35s (0.00s)
1.56% (0.01%)
1.34s (0.05s)
(Seiler et al., 2020) + Ranking
1.95% (0.01%) %)
1.33s (0.03s)
1.55% (0.03%)
1.27s (0.06s)
Our selection method using ranking
Greedy Top-k (k- 2)
1.86% (0.01%)
1.33s (0.01s)
1.33% (0.06%)
1,28s (0.03s)
L.51% (0.02%)
2.56s (0.03s)
1.07% (0.03%
2.48s (0.02s)
Rejection (20%)
1.75% (0.02%)
1.63s (0.01s)
1.26% (0.03%)
1.51s (0.04s)
Top-p (p- 0.5)
1.68% (0.02%)
1.86s (0.07s)
1.28% (0.04%)
1.46s (0.06s)
The experimental results in Table 5 indicate that our proposed method can achieve superior performance than advanced algorithm selection methods on both synthetic TSP and TSPLIB. Comparing the fifth and sixth rows, our proposed hierarchical encoder demonstrates superior performance over the salesperson features, especially on the out-of-distribution benchmark TSPLIB. Additionally, the comparison of the fourth and fifth rows shows that our deep learning- ceaniing-based ranking model achieves better results than traditional classification methods. Furthermore, the results of the last three rows illustrate that our proposed adaptive selection strategies effectively enhance optimality with minimal increases in time consumption.
A.6. Results of top-k selection.
We compare the performance of our top-k selection and the solver portfolio with the same size k on four datasets, including TSP, CVRP, TSPLIB and CVRPLIB Set-X. As shown in Figure 4, our top-k selection consistently outperforms the size-k solver portfolio across i E 21, 3, 4). We also observe that the performance of our top-k selection is close to the Oracle when A = 4. Moreover, it is expected that the performance improvement of our top-k selection gradually diminishes as k increases, since the performance of solver portfolio is also approaching the Oracle (the gray line).
Related works, such as ZTop (Bai et al., 2021), employ a fixed set of neural solvers to construct portfolio for all instances, resembling the static portfolio approach compared in this study. In contrast, our top-k selection strategy dynamically constructs instance-specifie portfolios, offering greater flexibility and a higher potential for performance improvement. As demonstrated in Figure 4, our method consistently outperforms the static portfolio approach across all portfolio sizes.
hhtpps//gi thub. httpu//cmm..kkooooseeaaaaaeeeeee
16

---

Neural Solver Selection for Combinatorial Optimization
TSP
TSPLIB
CVRP
CVRPLIB Set-X
2.0
2.2
1.8
6.5-
Optimaityy gap
6.0
1.8
1.4
5.5
1.6
1.2
5.0
1.0
1.2
OPT
Solver portfolio with size k
Top-k selection
Figure 4: Comparisons of the proposed top-k selection and the solver portfolio with size k.
A.7. Ablation of the hierarchical graph encoder.
The proposed hierarchical graph encoder utilizes graph pooling to downsample the instance graph and aggregates features obtained from multiple levels of the downsampled graphs. A graphical illustration of the downsampling process is provided in Appendix A. where we can find some consistent patterns which are intuitively reasonable. To evaluate the effectiveness of the graph pooling, we employ a graph encoder that aggregates the features from multiple layers for comparison, which is a clear ablation study since the main difference is that does not have the graph pooling operation.
The results in Table 6 show that using our hierarchical graph encoder outperforms the encoder that simply accumulates multi-layer features, especially in terms of the generalization performance CVRPLIB Set-X. This demonstrates the effectiveness of the graph pooling operation.
Table 6: Ablation study of hierarchical graph encoder. We report the mean and standard deviation of five independent runs. All the models are trained using ranking loss, and employ greedy selection.
Datasets
Attention encoder
Multi-layer features
Hierarchical encoder
TSP
1.87% (0.02%)
1.87% (0.01%)
1.86% (0.01 %
CVRP
5.30% (0.01% %)
5.30% (0.02%)
5.31% % (0.01 %)
TSPLIB
1.45% (0.11%)
1.35% (0.05%)
1.33% (0.06%)
CVRPLIB
5.87% (0.06%)
5.86% (0.08%)
5.76% (0.04%)
To evaluate the computational efficiency of the hierarchical encoder, provide detailed comparisons of the computation cost and optimality between hierarchical encoder and typical graph encoder. The results shown in Table 7, which includes the inference time per instance on TSPLIB, training time per epoch, and the average optimality gap on TSPLIB.
Table Comparisons of the computation cost and optimality between our hierarchical encoder and typical attention encoder.
Inference time selection model
Inference time of neural solvers
Training time each epoch
Methods
Optimality gap
Naive attention encoder Hierarchical encoder
0.0054s
1.2600s
1m40s 2m30s
1.54%
0.0070s
1.2961s
1.37%
We can observe from the second column that the introduction of our hierarchical encoder will increase the inference time of the selection model a little bit, e.g., from 0.0054s to 0.0070s. However, as shown the second and third columns, the
17

---

Neural Solver Selection for Combinatorial Optimization
inference time of the selection model is orders of magnitude shorter than that of the neural solvers, so the inference efficiency of the selection model is less of concern. The fourth column shows that the training time per epoch of the na've encoder and the hierarchical encoder are Im40s and 2m30s, respectively. Although the hierarchical encoder slows the training, the total runtime for 50 epochs is still only 2 hours, which is acceptable in most scenarios. Therefore, the performance metric (i.e., optimality gap) of different encoders is more crucial, especially the generalization performance. If the encoder learns robust representations, we can directly transfer the selection model to different datasets in a zero-shot manner, saving the time for fine-tuning and adaptation. Considering the better generalization (e.g., the optimality gap decreases from 1.54% to 1.37%), we believe that the proposed hierarchical encoder is better choice.
A.8. Detailed comparisons of selection strategies
According to the mechanisms of the four selection strategies, they have different preferences the trade-off of efficiency and optimality. Generally, for efficiency. Greedy > Rejection = Top-p > Top-k. for optimality, Top- Rejection = Top-p Greedy. Meanwhile, the hyper- syper-parameters of them can be used for balancing efficiency and optimality well. As result, the choice of different selection strategies can be decided by the users according to their preference, and we suggest using Top-p or Rejection as the default choices since they can adaptively select solvers based on the confidence.
The bjase selection and top-p selection are both designed to achieve better performance with little additional time consumption. To evaluate them in detail, we tune their parameters (e.g., rejection ratio, k, and p) to obtain a range of results. For the rejection-based selection, we use E (2, 3, 4} and vary the rejection ratio from 0.05 to 0.85 in increments of 0.05. For the top-p selection, we adjust the value of p from 0.40 to 0.95 in increments of 0.01. The results of the optimality gap and time consumption are provided in Figure 5. As shown in the figures, the rejection strategy with smaller k tends to achieve better optimality gaps using the same time consumption. Therefore, we recommend k = 2 or 3 when using rejection-basee based selection. Comparing top-p selection and rejection- eejeetion-based selection, we can not definitively conclude which strategy is superior, which is expected since they share a similar idea of utilizing confidence levels to decide whether to employ multiple solvers. However, the top-p selection may be preferable in practice due to its simplicity, where only a single hyperparameter p requires tuning.
Average time (s) per Instance
TSP
TSPLIB
CVRP
CVRPLIB
6
3
4-
2
5)
2-
1
2
1.4
1.6
1.8
1.0
1.2
1.4
1.6
4.8
5.0
5.2
5.2
5.4
5.6
Optimality (%))
Optimality gap (%)
Optimality gap (9)
Optimality gap (%)
Top
Rejection (k=2)
Rejaction (k=3)
Rejection (km4)
(a) Selection by classification
time Fer Ingtrrce
TSP
TSPLIB
CVRP
CVRPLBB
3
2
L.6 Optimiltyy (8)
1.0
Optimility (S)
Optimality [S]
Optimaltyy gap (S)
Top-p
Rejection (k=21
Rojeztion (k-3)
Rajection (c-4)
(b) Selection by ranking
Figure 5: Performance of the rejection- based and top-p selection.
18

---

Neural Solver Selection for Combinatorial Optimization
A.9. Selection accuracy
We present the accuracy of selecting the optimal neural solver in Table 8. The results show that the ranking model and classification model generally have similar selection accuracy, except that the ranking model achieves better accuracy than the classification model CVRPLIB.
Table 8: Accuracy of models trained by different losses using greedy selection. We report the mean and standard deviation of five independent runs.
Metrics
Classification
Ranking
Accuracy on TSP
36% (1%)
35% (1%)
Accuracy on CVRP
61 % (1%)
62% (0%)
Accuracy on TSPLIB Accuracy on CVRPLIB
40% (3%)
40% (7%)
52% (2%)
56% (3%)
A.10. Additional results for more neural solvers and larger-scale datasets
We add two divide-and-conques solvers, GLOP (Ye et al., 2024) and UDC (Zheng et al., 2024), to our solver pool, increase the problem scale from N E [50, 500] to N E [500, 2000] to conduct new experiments. The results shown in Table demonstrate that our framework can be compatible with more neural solvers and can also improve performance over the single best solver on larger-scale instances.
Table 9: Experimental results on the larger-scale instances with N E [500, 2000]. We report the mean (standard deviation) over five independent runs.
Synthetic TSP with E
[500, 2000]
Methods
Gap
Time
Single best solver
6.104%
8.369s
Ours (Greedy)
5.540% (0.038%)
8.322s (0.036s)
Ours (Top-k, k
5.369% (0.003%
15.566s (0.085s)
Single best of new solver pool
3.562%
5.274s
Ours with new solvers (Greedy)
3.126% (0.002%)
6,892s (0.006s)
Ours with new solvers (Top-k; 2)
2.955% (0.005%)
13.713s (0.036s)
19

---

Neural Solver Selection for Combinatorial Optimization
A.11. Illustration of the nodes sampled by hierarchical graph encoder
We illustrate the retained nodes after downsampling. Surprisingly, can find some consistent patterns which are intuitively reasonable. We summarize them three main points:
Cluster nodes. As illustrated in Figures 6(a) and 6(b), when instances contain certain clusters, the hierarchical encoder tends to select subset of "representative" nodes from each cluster, efficiently describing the entire spatial distribution.
Specific blocks, As illustrated in Figures 6(c) and 6(d), when instances contain specific complex geometric patterns like squares (Figure 6(c)) and arrays (Figure 6(d)), the hierarchical encoder can capture the nodes of these important areas identify their characteristics.
Boundary nodes. For instances without clear sub-components, the hierarchical encoder tends to focus on boundary nodes that describe the global shape, as illustrated in Figures 6(e) and 6(f).
(a)
(b)
(c)
(d)
(e)
(I)
Figure 6: Illustrations of nodes selected by the hierarchical encoder. Each sub-figure represents instance of TSP. The blue nodes represent the original instance, and the red nodes represent the retained nodes after down-sampling by the hierarchical encoder.
A.12. Complete results with all neural solvers
The complete experimental results with all individual solvers presented in Table 10 and Table 11, where the average objective values are provided for further comparisons.
20

---

Neural Solver Selection for Combinatorial Optimization
Table 10: Empirical results synthetic TSP and TSPLIB datasets, reporting the mean (standard deviation) over five independent rums. All individual solvers included for comparison. The suffixes '-N100' and '-N500" indicate models trained on datasets with N=100 and N=500, respectively. Ohj denotes the average objective value on the dataset.
TSP
Methods
Obj
Gap
Time
BQ
8.13
3.00%
1.61s
ELG
8.18
3.70%
0.45s
LEHD
8.17
3.57%
0.86s
T2T-N100
8.08
2.48%
1.71s
T2T-N500
8.08
2.40%
1,98%
DIFUSCO-N100
8.11
2.84%
1 1,46s
DIFUSCO-N500
8.07
2.33%
1.45s
Oracle
7.99
1.24%
8.93s
Selection by classification
Greedy
8.04 (0.00)
1.94% (0.02%)
1.36s (0.01s)
Top-k (k: = 2)
8.01 (0.00)
1.53% (0.01%)
2.52s (0.04s)
Rejection (20%)
8.03 (0.00)
1.81% (0.01%)
1.63s (0.01s)
Top-p (p 0.5)
8.03 (0.00)
1.84% (0.03%)
1.55s (0.06s)
Selection by ranking
Greedy
8.04 (0.00)
1.86% (0.01%)
1.33s (0.01s)
Top-k (k- = 2)
8.01 (0.00)
1.51% (0.02%)
2.56s (0.03s)
Rejection (20%)
8.03 (0.00)
1.75% (0.02%)
1.63s (0.01s)
Top-p (p- 0.5)
8.02 (0.00)
1.68% (0.02%)
1.86s (0.07s)
TSPLIB
Methods
Obj
Gap
Time
BQ
8.29
3.04%
1,44s
ELG
8.29
3.05%
0,40s
LEHD
8.26
2.57%
0.88s
T2T-N100
8,22
2.09%
1.76s
T2T-N500
8.21
1.95%
1.74s
DIFUSCO-N100
8.23
2.25%
1,44s
DIFUSCO-N500
8.22
2.13%
1.44s
Oracle
8.12
0.89%
9.14s
Selection by classification
Greedy
8.17 (0.00)
1.54% (0.05%)
1.33s (0.02s)
Top-k (k 2)
8.15 (0.01)
1.22% (0.10%)
2.47s (0.02s)
Rejection (20%)
8.16 (0.01)
1.42% (0.11%)
1.54s (0.03s)
Top-p (p 0.5)
8.17 (0.01)
1,49% (0.11%)
1.37s (0.02s)
Selection by ranking
Greedy
8.16 (0.00)
1.33% (0.06%)
1.28s (0.03s)
Top-k (k 2)
8.14 (0.00)
1.07% (0.03%)
2.48s (0.02s)
Rejection (20%)
8.15 (0.00)
1.26% (0.03%)
1.51s (0.04s)
Top-p (p 0.5)
8.15 (0.00)
1.28% (0.04%)
1.46s (0.06s)
21

---

Neural Solver Selection for Combinatorial Optimization
Table 11: Empirical results synthetic CVRP and CVRPLIB Set-X datasets, reporting the mean (standard deviation) over five independent runs. All individual solvers are included for comparison. Obj denotes the average objective value on the dataset.
CVRP
Methods
Obj
Gap
Time
BQ
18.39
7.20%
1.59s
ELG
18.49
7.81%
0.82s
LEHD
18.42
7.37%
1.01s
MVMoE
19.48
13.56%
0.70s
Omni
18.32
6.82%
0.24s
Oracle
17.95
4.64%
4.38s
Selection by classification
Greedy
18.07 (0.00)
5.35% (0.02%)
0.64s (0.01s)
Top-k (A: = 2)
17.98 (0.00)
4.81 % (0.01 %)
1.87s (0.03s)
Rejection (20%)
18.04 (0.01)
5.19% (0.03%)
0.77s (0.01s)
Top-p (p 0.8)
18.04 (0.01)
5.16% (0.03%)
0.87s (0.08s)
Selection by ranking
Greedy
18.06 (0.00)
5.31 % (0.01%)
0.62s (0.01s)
Top-k (k: = 2)
17.98 (0.00)
4.82% (0.01%)
1.90s (0.04s)
Rejection (20%)
18.04 (0.00)
5.15% (0.02%)
0.74s (0.01s)
Top-p (p 0.8)
18.01 (0.00)
4.99% (0.02%)
1.03s (0.03s)
CVRPLIB Set-X
Methods
Obj
Gap
Time
BQ
71.21
10.31%
2.60s
ELG
68.50
6.10%
1.31s
LEHD
73.40
13.70%
1.60s
MVMoE
74.59
15.54%
0.90s
Omni
68.57
6.21%
0.38s
Oracle
67.85
5.10%
6.81s
Selection by classification
Greedy
68.41 (0.08)
5.96% (0.12%)
1.06s (0.08s)
Top-k (k = 2)
68.07 (0.05)
5.44% (0.08%)
2.40s (0.25s)
Rejection (20%)
68.32 (0.08)
5.83% (0.12%)
1.31s (0.09s)
Top-p (p = 0.8)
68.30 (0.06)
5.79% (0.09%)
1.42s (0.17s)
Selection by ranking
Greedy
68.28 (0.03)
5.76% (0.04%)
1.31s (0.
Top-k (k: = 2)
68.04 (0.04)
5.39% (0.06%)
2.56s (0.
Rejection (20%)
68.19 19 (0.03)
5.63% (0.05%)
1.60s (0.08s)
Top-p (p = 0.8)
68.18 (0.02)
5.61% (0.03%)
1.72s (0.08s)
22


Reviews:
[{"review_id": "dk0DKAqDt3", "reviewer": "Reviewer_4HPV", "summary": "This submission introduces a framework for intelligently coordinating multiple neural solvers to tackle combinatorial optimization problems (COPs).  The core idea involves feature extraction from problem instances, training a selection model to identify the most suitable solver, and employing robust selection strategies to balance performance and efficiency. The framework's components include extracting features that characterize problem instances, a model to select the optimal solver, and a method that selects one or more solvers to address the problem.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nWe 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. \n\nIn response to your concerns regarding **technical novelty**, we would like to highlight two key advancements in our work:\n\n1. **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. \n\n2. **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.\n\nWe 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.\n\nOnce again, we greatly appreciate your time and thoughtful feedback. Please do not hesitate to reach out if you have further questions or suggestions.", "claims_and_evidence": "The submission’s claims are well supported by experimental results. \nFor example, the reason the authors developed a multi-solver selection framework is that there exists no single neural solver that dominates all others on every instance, and instance distribution shifts can also significantly affect the solvers’ performance relationship. These claims are supported by Figure 1.\nIn addition, the paper claims the proposed framework has achieved significantly better results than individual solvers. The claim is again supported by experimental results: the framework reduces the optimality gap by 0.82% on synthetic TSP, 2.00% on synthetic CVRP, 0.88% on TSPLIB, and 0.71% on CVRPLIB Set-X compared to the best individual solver.", "methods_and_evaluation_criteria": "The problem is stated in the introduction section of the submission: no individual solver is dominantly better at solving all instances. \nTo this end, this paper proposes a solver selection framework that incorporates feature extraction, solver selection model and selection strategies, which dedicated to select the best few solvers to solve the COP problems.\nThe benchmark involves best individual solvers and solver portfolios, which are some good examples to compare with. The evaluation also considers generalization problems: the framework is tested on out-of-distribution datasets (TSPLIB and CVRPLIB Set-X) and larger-scale instances.\nOverall, the problem, the proposed methods and the selected benchmarks remain consistent throughout the submission and make sense for the problem.", "theoretical_claims": "na", "experimental_designs_or_analyses": "Experiments on Traveling Salesman and Capacitated Vehicle Routing Problems demonstrate the framework's effectiveness in selecting appropriate solvers. The framework leads to improved solution quality and comparable time consumption compared to using the best individual neural solver alone. The work also explores future research directions such as incorporating solver features, addressing runtime awareness, and enhancing the collection of neural solvers.", "relation_to_broader_scientific_literature": "na", "essential_references_not_discussed": "na", "other_strengths_and_weaknesses": "I generally like the idea proposed in this paper, where each instance can be assigned to the most appropriate solver. However, the technical novelty is limited. The authors just use a MLP to calculate the compatibility scores of neural solvers. There is still room to improve.\n\nThe authors are advised to improve their presentation as well, especially figure 1. In addition, authors can include how the selected solvers work cooperatively to solve the instance, which could be an essential part of the framework.", "other_comments_or_suggestions": "na", "questions_for_authors": "na", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6dQ6NDIXK3", "reviewer": "Reviewer_mJAJ", "summary": "The paper proposes a framework to coordinate neural solvers for combinatorial optimization problems (COPs), addressing the complementary performance of individual solvers across instances. It introduces a three-component framework: (1) feature extraction using graph attention networks or hierarchical encoders, (2) a selection model trained via classification or ranking losses, and (3) selection strategies (e.g., top-k, rejection-based) to balance performance and efficiency. Experiments demonstrate that the framework reduces optimality gaps over state-of-the-art individual solvers on synthetic and real-world benchmarks. The results highlight the benefits of coordinating diverse neural solvers, particularly under distribution shifts and larger problem scales.\n\n## Update after rebuttal\nI acknowledge the author’s responses to the questions raised and recommend a weak accept for this paper.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n1. In section Experimental Designs Or Analyses, about **“putting the comparison with traditional selection methods in Appendix A.5 in the main paper”**.\n    \n    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.\n\n2. In weakness, **\"It seems that this paper only applies a general selection method to neural solvers for COPs\"**.\n\n    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.\n\n    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.\n\n    Thank you again for your thoughtful comments. We sincerely hope the above clarification can address your concern.\n\n3. Question 1 in Questions For Authors, **\"how to apply this framework to other COPs\"**.\n    \n    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.,\n    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.\n\n    Thank you again for dedicating your time to reviewing our paper. We also welcome any further questions and discussions.", "claims_and_evidence": "The claims are well supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes, the evaluation criteria is reasonable for learning-based methods for COPs.This is an empirical work and does not have any theoretical claims that need to be checked.", "theoretical_claims": "This is an empirical work and does not have any theoretical claims that need to be checked.", "experimental_designs_or_analyses": "It would be better to compare the proposed learning-based selection method with some traditional selection methods. Although they are presented in Appendix A.5, I think it would be better to put them in the experiments section to highlight the effectiveness of the proposed method.", "relation_to_broader_scientific_literature": "This paper applies the algorithm selection to neural solvers for COPs and shows promising results.", "essential_references_not_discussed": "I think the related works are well discussed.", "other_strengths_and_weaknesses": "Strengths:\n\n1.\tThe experiments are solid and clearly show the superiority of the learning-based solver selection method.\n2.\tThe presentation of the paper is well organized.\n\nWeaknesses:\n\n1.\tThe link between the selection method and the architecture of COPs is unclear. It seems that this paper only applies a general selection method to neural solvers for COPs.", "other_comments_or_suggestions": "In the references, it seems that there is a typo in “Learning to aolve large-scale TSP instances”.", "questions_for_authors": "1.\tThis paper claims a general solver selection framework. However, it seems that for each type of the COPs, we need to carefully design a feature extraction component. Can you explain how to apply this framework to other COPs, besides TSP and CVRP? Does there exist a more general approach?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hIunncrkRI", "reviewer": "Reviewer_Qe6z", "summary": "The authors propose to train a neural network that selects the most appropriate solver to use on a given instance. They tested their method on TSP and CVRP problems using a pool of state-of-the-art neural solvers. This solver selection is effective and allows a better tradeoff between computation-time and optimality. Multiple modelling approaches are explored.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review and constructive comments. Below please find our responses. **Corresponding experimental results** can be found at [link](https://anonymous.4open.science/api/repo/9356_rebuttal-D4F5/file/addtional_results_9356.pdf).\n\n**R1: How the model selection behaves on larger instances with up to 10,000 nodes**\n\nThanks 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.\n\nAs 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.\n\nWe 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.\n    \n**R2: The parameter counts of the different feature extractors**\n\nFor 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.\n\n**R3: The difference from graph attention**\n\nWhen graph attention is used on fully connected graphs like TSP, it works just like a Transformer without positional encoding.\n\n**R4: The hierarchical graph encoder seems a bit complex; try simpler pooling approaches that keep the hierarchical aspect**\n    \nThanks 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.\n    \n**R5: Discussion on NFL Theorem and performance affected from changing the synthetic distribution**\n    \nThanks 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$. \n\nFrom 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. \n\nIn 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.", "claims_and_evidence": "The claims are supported by comparisons between two baselines:\n1. The oracle which knows for each instance which solver to use\n2. The single overall best solver.\n\nThey close the gap between the oracle and the single overall best solver by 77% on average while using only two solvers instead of the full pool of solvers required by the oracle. Other selection strategies are tested and they all are strictly better than the single overall best solver in terms of optimality and computation time.\n\nThey also produce ablation studies on the choice of the loss function and the feature extraction method. They compare the performance of a classification loss with a ranking loss. The ranking loss is shown to be overall better. They compare two learnable feature extractor and show that the hierarchical one generalizes better to new and bigger instances.\n\nThe trained model are evaluated on TSPLIB and a subset of CVRPLIB on relatively small graphs only. It would have been nice to see how the model selection behaves on bigger instances with up to 10000 nodes.", "methods_and_evaluation_criteria": "The method is well designed. While the hierarchical feature extractor is a bit complicated, it shows better adaptivity to bigger instances than the more standard graph attention encoder. The selection strategies are the one you would expect and the evaluation criteria is appropriate.", "theoretical_claims": "There is no theoretical claim in this work.", "experimental_designs_or_analyses": "The final method achieves a nice tradeoff between optimality and computation time. This is what we expect from such approach and the results are sound.", "relation_to_broader_scientific_literature": "The idea of selecting which solver to use for a given instance has already been explored in the past, but usually the model selection is done with metaheuristics approaches or different machine learning techniques other than neural networks. In this work the proposed model selection is done with neural networks and features are extracted from the raw instances directly, leading to less biases and potentially better performance.", "essential_references_not_discussed": "To the best of my knowledge, all essential references are cited.", "other_strengths_and_weaknesses": "While selecting the right solver is not new, the idea of using a fully neural approach is interesting, and not limited to neural solvers.\n\nIt seems that the loss function is not so important here. The authors could have kept the ranking loss function and explore further the design of the selection strategies.", "other_comments_or_suggestions": "- Numbers are not percentages in Fig 1, y axis. \n- L302: extra comma\n- Table 3: \"encdoer\"\n- L434: \"seach\"", "questions_for_authors": "- What are the parameter counts of the different feature extractors? It might explain the difference in performance.\n- The hierarchical graph encoder seems a bit complex. Have you tried simpler pooling approaches that keep the hierarchical aspect? I would expect a simpler model to work just as well.\n- The citation of Velickovic et al., 2018, for feature extraction, may be inaccurate, since their architecture (graph attention network) is different from the transformer one you use. Do you agree? \n- When you mention the No-Free-Lunch Theorem, this also affects your overall selection procedure. From my understanding, your selection tends to guarantee that the resulting solver will typically be as good as the best one in the pool, but one could argue the existence of a distribution that fools its selection. Can you comment on this? \n- How is the performance on TSPLIB and CVRPLIB affected from changing the synthetic distribution (e.g. varying the number of components c, the scale of the instances, or removing the covariances and considering the classical identity covariance matrix)?  \n- Why didn't you consider larger instances?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SzMNJAvTVk", "reviewer": "Reviewer_MmHR", "summary": "This paper proposes an ensemble framework to select appropriate neural solvers from the solver pool for each instance to solver. This framework includes a feature extraction step to extract instance-level features. Based on the features, a selection model alongside several selection strategies is proposed to select dedicated neural solvers to solve the corresponding instance. This framework improves the overall performance of current state-of-the-art neural solvers through extensive experiments on TSP and CVRP on small to large scales.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n1. In Other Strengths And Weaknesses, weakness 1, **“the number of collected models are not strictly consistent for different methods”**.\n    \n    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.\n    \n3. In Other Strengths And Weaknesses, weakness 2, **“performance on instances of specific scales are expected”**.\n    \n    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. \n\nSeparate results according to problem scale $N$ on the synthetic TSP dataset. We report the mean (standard deviation) optimality gap over five independent runs. \n\n| Methods | $50\\le N \\le 200$ | $200< N \\le 300$ | $300< N \\le 400$ | $400< N \\le 500$ |\n| --- | --- | --- | --- | --- |\n| Single best solver | 0.96% | 2.34% | 2.78% | 2.98% |\n| Oracle | 0.39% | 1.19% | 1.70% | 2.18% |\n| Ours (Greedy) | 0.84% (0.03%) | 2.01% (0.02%) | 2.43% (0.02%) | 2.71% (0.03%) |\n| Ours (Top-k, k=2) | 0.61% (0.02%) | 1.53% (0.03%) | 1.99% (0.03%) | 2.41% (0.05%) |\n| Ours (Rejection, 20%) | 0.75% (0.04%) | 1.86% (0.04%) | 2.33% (0.03%) | 2.62% (0.02%) |\n| Ours (Top-p, p=0.5) | 0.71% (0.02%) | 1.70% (0.02%) | 2.24% (0.04%) | 2.57% (0.04%) |\n\nSeparate results according to problem scale $N$ on the synthetic CVRP dataset. \n\n| Methods | $50\\le N \\le 200$ | $200< N \\le 300$ | $300< N \\le 400$ | $400< N \\le 500$ |\n| --- | --- | --- | --- | --- |\n| Single best solver | 3.95% | 6.06% | 7.76% | 9.24% |\n| Oracle | 2.17% | 4.33% | 5.74% | 7.40% |\n| Ours (Greedy) | 2.85% (0.03%) | 4.87% (0.02%) | 6.47% (0.05%) | 8.09% (0.01%) |\n| Ours (Top-k, k=2) | 2.32% (0.02%) | 4.54% (0.02%) | 5.91% (0.03%) | 7.55% (0.03%) |\n| Ours (Rejection, 20%) | 2.64% (0.02%) | 4.70% (0.03%) | 6.22% (0.02%) | 7.91% (0.03%) |\n| Ours (Top-p, p=0.8) | 2.36% (0.02%) | 4.70% (0.04%) | 6.21% (0.05%) | 7.81% (0.02%) |\n    \n4. 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”**.\n    \n    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. \n    \n5. In Other Comments Or Suggestions, “**The structure of the selection model can be visualized**”. \n    \n    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.", "claims_and_evidence": "Yes, the claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes, it does make sense.", "theoretical_claims": "There are no theoretical claims.", "experimental_designs_or_analyses": "I have checked the experimental design in Section 4.1, the experimental analyses in Section 4.2, and some discussions in Section 5. They are sound.", "relation_to_broader_scientific_literature": "This paper relates multiple advanced NCO models to solve VRPs in an ensemble way at an instance level and improves current state-of-the-art performance.", "essential_references_not_discussed": "To my knowledge, no related works that are essential to understanding are missing.", "other_strengths_and_weaknesses": "Strengths:\n\n(1) This paper is well-motivated and is clear to understand.\n\n(2) The method is simple yet efficient, improving the performance on the top of advanced neural solvers in both small-scale (Table 1) and large-scale (Table 9) scenarios.\n\n(3) The ablation study (RQ3, A.5, and A.8) and hyperparameter study (A.9) are detailed, providing a clear illustration of the effect of different components and hyperparameters.\n\nWeaknesses:\n\n(1) For DlFUSCO and T2T, this paper collects both the models trained on the N = 100 and 500 datasets, but only a single model is used for the other methods, which may make it inappropriate to rank the methods in Table 1 on TSP.\n\n(2)  This work primarily reports the summary results on diverse problem instances with significantly varying distributions and scales, while the detailed performance on instances with specific characteristics (e.g., instances with the same scale) is less analyzed. This may restrict the scope of performance evaluation for the proposed method.\n\n(3)  An implicit assumption in this paper is that computational resources are constrained, requiring neural solvers to operate sequentially. This assumption highlights the runtime efficiency of solver selection. While I acknowledge the high cost of computational resources and generally appreciate the contributions of the proposed selection framework, the scenario of adequate computational resources is possible and important and should be discussed in the paper.", "other_comments_or_suggestions": "The model structure of the selection model can be visualized for better understanding.", "questions_for_authors": "see weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper has the following identified issues:  
- Limited Technical Novelty  
- Generalization to Other COPs  
- Evaluation Scope  
- Baseline Consistency and Fairness  

However, the following points are positively evaluated, and considering these factors comprehensively, the recommendation is Weak Accept:  
- Novel and impactful contribution to the NCO field  
- Demonstrates strong improvements in optimality gaps and robustness  
- Modular and general design with potential beyond TSP/CVRP
Decision: Accept (poster)