Unify ML4TSP: Drawing Methodological Principles for TSP and Beyond from Streamlined Design Space of Learning and Search
Authors: Yang Li
Jiale Ma
Wenzheng Pan
Runzhong Wang
Haoyu Geng
Nianzu Yang
Junchi Yan
Venue: ICLR 2025 Poster (2025)
Keywords: Neural Combinatorial Optimization
Travelling salesman problem
Primary area: datasets and benchmarks

Abstract: Despite the rich works on machine learning (ML) for combinatorial optimization (CO), a unified, principled framework remains lacking. This study utilizes the Travelling Salesman Problem (TSP) as a major case study, with adaptations demonstrated for other CO problems, dissecting established mainstream learning-based solvers to outline a comprehensive design space. We present ML4TSPBench, which advances a unified modular streamline incorporating existing technologies in both learning and search for transparent ablation, aiming to reassess the role of learning and discern which parts of existing techniques are genuinely beneficial and which are not. This further leads to the investigation of desirable principles of learning designs and the exploration of concepts guiding method designs. We demonstrate the desirability of principles such as joint probability estimation, symmetry solution representation, and online optimization for learning-based designs. Leveraging the findings, we propose enhancements to existing methods to compensate for their missing attributes, thereby advancing performance and enriching the technique library. From a higher viewpoint, we also uncover a performance advantage in non-autoregressive and supervised paradigms compared to their counterparts. The strategic decoupling and organic recompositions yield a factory of new TSP solvers, where we investigate synergies across various method combinations and pinpoint the optimal design choices to create more powerful ML4TSP solvers, thereby facilitating and offering a reference for future research and engineering endeavors.

Published as a conference paper at ICLR 2025
UNIFY ML4TSP: DRAWING METHODOLOGICAL PRIN- CIPLES FOR TSP AND BEYOND FROM STREAMLINED DESIGN SPACE OF LEARNING AND SEARCH
Yang Li Jiale M Wenzheng Pan', Runzhong Wang", Haoyu Geng',
Nianzu Yang', Junchi Y2n
1 Sch. of Artificial Intelligence& & Sch. of Computer Science, Shanghai Jiao Tong University
2 Shanghai Innovation Institute Maassachusetts Institute of Technology
petps://githat wtt.a//Tiiikaaaa--S///uaa.......
ABSTRACT
Despite the rich works on machine learning (ML) for combinatorial optimization (CO), unified, principled framework remains lacking. This study utilizes the Travelling Salesman Problem (TSP) as a major case study, with adaptations demon- strated for other CO problems, dissecting established mainstream learning-based solvers to outline a comprehensive design space. We present ML4TSPBench, which advances unified modular streamline incorporating existing technologies in both learning and search for transparent ablation, aiming to reassess the role of learning and discern which parts of existing techniques are genuinely beneficial and which are not. This further leads to the investigation of desirable principles of learning designs and the exploration of concepts guiding method designs. We demonstrate the desirability of principles such as joint probability estimation, symmetry solution representation, and online optimization for learning-base based designs. Leveraging the findings, we propose enhancements to existing methods to compensate for their missing attributes, thereby advancing performance and enriching the technique library. From higher viewpoint, we also uncover performance advantage in non-autoregressive and supervised paradigms compared to their counterparts. The strategic decoupling and organic recompositions yield a factory of new TSP solvers, where we investigate synergies across various method combinations and pinpoint the optimal design choices create more powerful ML4TSP solvers, thereby facilitating and offering a reference for future research and engineering endeavors.
INTRODUCTION
Combinatorial Optimization (CO) has been a central challenge with its inherent complexity (e.g., NP- hardness). Recently, machine learning (ML) has been actively introduced to address CO problems, i.c., ML4CO (Bengio et al., 2021; Cappart al., 2021), which brings practical advantages in both solving quality and speed especially when the instances are confined within certain distribution (Bengio al., 2021). Among CO problems, the Travelling Salesman Problem (TSP) has been representative one of the most intensely studied problems in both ML4CO and Operations Research (OR) communities with one the richest librarics of learning and search techniques (Hottung et al., 202 Fu et al., 2021; Min et al., 2023; Qiu et al., 2022; Hudson et al., 2022; Sun & Yang, 2023; Li et al., 2023b; Kool et al., 2018; Kwon et al., 2020; Kim et al., 2022). For solving CO problems, deep neural networks enjoy high parallel computing ability for speedup through one-shot inference. Meanwhile, ML. could automatically uncover heuristics through data (Kool et al., 2018; Luo et al., 2023) for improvement against existing handcrafted rules, especially for some new problems distributions that call for experts to develop tailored solving schemes.
instance
Recent advancements in learning- based solvers have significantly enhanced their solving performance and capacity to tackle larger-scale problems. These improvements have been propelled by a variety
"Correspondence author: yanjunchi @ sjtu.edu.cn. The SITU authors partly supported by NSFC (92370201), ), Shanghai Municipal Science and Technology Major Project (20215H2I//X0102),

---

Published as a conference paper at ICLR 2025
Trainring Stage
Solving Stage
Learning Model
I Leanning- Hlaed Search
Final Solution
Functionality
Learning
Training Objective
Instance Solving
Active Seurch
Naive Construction
Goodd Decading
Edge Prodiction
Superteed Sotution Paocunity
Chalken
Constructive Search
14
Unsapesised Seving Oltyetive
f Intermtdiatee Prodiction
Edge Regiot
Mets
Teams Search
Improvement- Blased Search Thoxkppe
Reitlerannnt
Objective
Sampling Dronding
Sdution Geramation
Fdgg Heamoo
Regett Provisity
Suqurrtial Node
Neuna Model
Twnddat Itelorte Allemation
Prddettes
Selation Ulttributionn Phoutrity
Hustrap
Kanti Cirro Ese Seach
Leurning-Based
Menristie-Bssel
Figure 1: Overview of our proposed ML4TSPBench! Blue and orange stand for training and testing processes, respectively. Dashed lines indicate the optional processes in pipelines.
of learning paradigms, encompassing supervised predictive modeling (Hottung et al., 2021b; Fu et al., 2021; Hudson et al., 2022), reinforcement learning (Qiu et al., 2022; Kool et al., 2018; Kwon et al., 2020; Kim et al., 2022), generative modeling (Sun & Yang, 2023; Li et al., 2023b), unsupervised learning (Min et al., 2023), meta learning (Qiu al., 2022), etc. In modern approaches, learning and search elements are often interleaved with each other, and common designs among existing learning- based solvers may manifest in varying implementations, making their effects and contributions less transparent, let alone their intricate interplay. Mcanwhile, the lack of crisp analysis of the whole ML,TSPP system (a representative example for MIACO) hinders the determination of the role of learning and the establishment of desirable principles for learning designs.
In this paper. we adopt higher-level perspective to consider the whole system and advocate the necessity of inspecting and aligning various existing methods. We endeavor to decompose established mainstream learning-based solvers to outline comprehensive design space and unify a modular streamline incorporating aligned learning and search technologies while minimizing disparities among methods, facilitating transparent ablation and systematic analysis. Fig. 1 presents the overview of our framework. Given instances and their (optional) labels c.g. reference solutions, the training stage involves different learning functionalities and training objectives to exploit the effective heuristics from data. Given instances, the solving stage follows complete (feasible) solution is generated first then it is improved through the improvement-basee search. The construction based on the intermediate predictions produced by the trained model, and baariing-based search is optionally applied to improve prediction quality by updating the parameters of the model or the intermediate predictions. Note the prediction results for auto-regressive methods using sequence models (Kool et al., 2018; Kwon et al., 2020) involve the interplay of neural models and construction methods to update the node heatmap prediction for different steps.
monstruction-refinemeee pipeline whereby
Based on this framework, we analyze the correlation between learning and solving objectives along with the efficacy of current ML4TSP endeavors within the outlined framework. This further leads to the summarization of the inherent desirable design principles among diverse learning methods and discerns key attributes that contribute to performance improvement. Specifically, minimized ablation studies performed demonstrating the desirability of design principles such as joint probability estimation, symmetry solution representation, online optimization, and search friendliness. Additionally, offer insights into how model predictions intervene with strong search methods like MCTS and highlight preferences in learning paradigms (e.g., supervised vs. unsupervised, autoregressive vs. nonautoregressive) regarding solving performance and scalability.
Leveraging our findings, we propose enhancements to existing methods to compensate for their miss- ing attributes, thereby advancing performance and enriching the technique library. Examples of novel methods include node-level normalization for one-shot solution predictions (Joshi et al., 2019), sym- metry introduction into the diffusion- based solvers (Sun & Yang, 2023; Li al., 2023b) and the rein- forcement solving objective of Qiu et al. (2022), the devised MCTS variants by decoupling the depen- dencies between solution initialization and local search within MCTS (Fu et al., 2021) and connecting its local search component with established constructive search methods, etc. Furthermore, we recom-
'The implementation is based ht / htt///gttttt httpgitth...o..o.eeeeoeomoooo nk1 1klab- S.TOO/M..COOOCO
2

---

Published as a conference paper at ICLR 2025
pose within the established technique library and propose a factory of solvers, among which the opti- mal ones achieve performance gains over previous SOTA. Beyond TSP, we also demonstrate adaptions of the framework to other CO problems and verify that the desirability of design principles discovered in ML4TSP evaluations still holds for other CO problems. Our implementation is carefully organized, featuring solver classes for various learning functionalities, facilitating easy development for further research and engineering practices. We aim for this work to streamline the development and evaluation process, offering a consistent implementation for verifying the effects of proposed methods efficiently.
2 PRELIMINARIES AND RELATED WORK
Graph Combinatorial Optimization and Travelling Salesman Problem (TSP). Following Karalias & Loukas (2020); Wang et al. (2022), we define G as the universe of CO instances by graphs G(V,E) E g. where V and E denote the node set and edge set respectively. Let x E {0.1] denote the optimization variable and Ω denotes the feasible set. A CO problem on G' aims to find feasible x E Ω that minimize the given objective function G): : Ω + Rzo- TSP is defined on an undirected complete graph G (V; F.,, where V represents cities and each edge F.. has non-negative weight Di, representing the distance hetween cities and j. The problem is to find Hamiltonian cycle of minimum weight in G. Here the dimension of the optimization variable N = n²" and we denote the solution as matrix X E {0, ] where X indicates whether E included x. The objective function is: f(: D X = E., Da. X..--
Related Works. This is early endeavor to rethink existing methodologies in ML4TSP while concurrently advancing the development of new techniques. It stands in contrast to Berto et al. (2023) which primarily focused on providing unified implementation and evaluation of RL-based models without delving into deeper analyses of learning paradigms and proposing new methods. Joshi et al. (2020) tries to analyze from the generalization perspective, yet the investigated methods are confined to naive pipelines (Kool et al., 2018; Joshi et al., 2019) which is a very partial subset of the current ML4TSP system, and no general design principles or new methods are provided. Geng et al. (2023) provides benchmark for the predictive combinatorial optimization. Pan et al. (2025) unifies set of CO problems by reducing them into the general TSP form featured by distance matrices. Our framework tries to integrate the mainstream efforts of constructive ML4TSP solvers. The comprehensive nature of our framework facilitates a higher-level integration and analysis, thereby facilitating the development of broader spectrum of research avenues within the community.
3 MODULAR FRAMEWORK FOR ML4TSP SOLVERS
3.1 DESIGN SPACE FOR TRAINING STAGE ALGORITHMS
The learning models generally receive input features from the instance graph, where the typical features optionally include node features indicating the 2D coordinates of the nodes, and edge features indicating the weight of the edges. The network backbones include GNN variants like Graph Convolutional Networks (GCN) (Kipf & Welling, 2016; Joshi et al., 2019), Graph Attention Networks (GAT) (Veličković et al., 2017; Kool et al., 2018), and Scattering Attention GNN (SAG) (Min et al., 2023). The algorithmic variances are reflected in the learning functionalities and training objectives presented below, where the correlations between these components presented in Fig. 1.
3.1.1 LEARNING FUNCTIONALITIES
Different learning functionalities are proposed to more efficiently utilize data for solving TSP, which involves what the neural models learn from pre-existing data.
Joshi et al. (2019); Fu et al. (2021); Qiu et al. (2022); Min et al. (2023) frame TSP solving as edge prediction task, where each edge is classified binary to determine whether it is in the solution. The prediction confidence of the edges (after softmax function) serves as a heatmap H denoting the probabilities of edges occurring in the tour, i... H = p(E.. E S*) where S* denotes the optimal solution represented in the matrix form.
Edge Prediction.
Edge Regret Prediction. The global regret is defined as the cost of fixing a certain edge in the solution relative to the cost of globally optimal solution (Hudson et al., 2022): R where R, denotes the regret of selecting Fi.j in the solution, St, denotes the optimal solution
s(s",; J( 1
3

---

Sequential Node Prediction. Instead of global prediction in one shot, sequence models (Kool et al., 2018; Kwon et al., 2020; Kim et al., 2022) decompose into n-step node predictions, where each step offers the prediction map of the next node selection based on the current state. The sequence models generally follow an attention based mecder- model where the encoder produces embeddings of all input nodes and the decoder produces the per-step node heatmap predictions Published as a conference paper at ICLR 2025
with E, fixed, and S" is the global optimal solution. This target contains more knowledge about how every edge benefits the optimizationn, especially for edges not included in the optimal solution, making it more conducive searching. However, it necessitates significantly more computational resources to acquire the supervision.
Solution Generation. Deviating from the prediction of single solution, generative modeling methods (Sun & Yang. 2023; Li et al., 2023b; Hottung et al., 2021a) endeavor to characterize a distribution of high-quality solutions for a given instance, i.e., estimating p(SIG). Solutions can be established by sampling from the distribution. This consideration of distributions makes predictions more diverse, thereby enhancing the search.
h P(T,, j| where h the j-th element of step i's prediction map and is the permutation representation of the solution.
3.1.2 TRAINING OBJECTIVES
Training objectives are proposed to achieve the learning functionalities in Sec. 3.1.1. This subsection discusses supervised and unsupervised methods sequentially. Supervised methods effectively leverage the readily available solved data, while unsupervised methods bypass the need to acquire supervision.
Supervised Solution Proximity. This objective encourages the model's prediction, e.g. heatmap H. [0, 1jmx,, to approximate the reference solutions obtained by alternative solver. Based on the binary classification for edges, the (weighted) binary cross-entropy loss is widely adopted:
L= Σ S., log,H.,, + - S.,) log(1 H.,)
(I)
where wo, wi are class weights since the classification task is unbalanced towards the negative class. Supervised Edge Regret Proximity. This objective encourages the model to predict reliable edge regrets R Rax= approximate the reference regrets R, by minimizing || R R|/2-
Solution Distribution Proximity. Prominent models for the generative objective encompass diffusion models (Sun & Yang, 2023; Li al., 2023b) and variational autoencoders (VAE) (Hottung al., 2021a), to maximize the conditional likelihood estimation E[log Do(S(G)) where 0 is the model parameters. The models are typically optimized through the evidence lower bound (ELBO), where is the posterior and Z is the latent variable.
log (S, Z G) 4Z
- (2(2/
2 log (o
Unsupervised methods typically optimize using the solving objective. However, the non-differentiable mapping from continuous, unconstrained space to discrete, highly constrained space suffers gradient truncation. Thus, unsupervised loss based on constraint penalty and reinforcement solving loss are employed, and meta- learning can be further adapted enhance generalization.
Unsupervised Solving Objective. Min et al. (2023) proposes penalties over the Hamiltonian cycle and no self-loop constraints to regularize the predicted assignment matrix T and heatmap H. T is
obtained by enforcing column-wise softmax to the network output, where T. [0, []x1 indicates
the next-node probabilities step, and H is calculated through H T T.
T.
L D., + Σ T., 1)2 H.. H.,..
3
The second and third term denotes the Hamilton cycle and no self-loop constraint, respectively.
Reinforcement Solving Objective. With the predicted probability distribution (5 G). we can sample solution tours. This objective optimizes the expectation of the tour length by gradient estimated by REINFORCE (Williams, 1992) with baseline b(G):
L = (p)() (S; G)]
and VL [Spo)) ((f(S; log)
4

---

Published as a conference paper at ICLR 2025
where the baseline function independently estimates the expected cost to reduce the variance of the gradients. The sampling construction method presented in Sec. 3.2.2 enables sampling solutions from the predicted edge heatmap and per-step node heatmaps achieve Po(S
Meta-Learning Objective. This objective (Finn et al., 2017; Qiu et al., 2022) aims to train models to acquire meta-knowledge from diverse problem instances, improving generalization when faced with previously unseen instances. In CO, model parameters and model predictions can be further updated during testing through a learning-based search in Sec. 3.2.1. The objective tries better predict model initialization or prediction that can achieve the best solving results after the learning- search in the solving phase. Suppose the edge heatmap H is optimized to H', then the meta-learning objective is L (..(S).. [f(S;G) where s-) denotes the sampling decoding function.
3.2 DESIGN SPACE FOR SOLVING STAGE ALGORITHMS
The solving stage does not involve any pre-existing data but tries to optimize the solutions or the predictions over unseen instances received on the fly, as shown in Fig.
3.2.1 LEARNING-BASED SEARCH
Motivated by the divergence between the training stage, which optimizes average performance across historical instances; and the solving stage that optimizes performance for each new instance, the work Hottung et al. (2021b); Qiu et al. (2022); Li et al. (2023b) design learning- based search in the solving stage to perform tailored optimization for testing instances, which improves prediction by updating the model parameters or the intermediate predictions.
Active Search. With objectives that do not require labels, active search (Hottung et al., 2021 b;; Qiu et al., 2022) further fine-tunes (partial) network parameters or intermediate model predictions, e.g. heatmaps, over each testing instance with solving objective updates of Eq. using gradient decent.
Gradient Search. Based on diffusion modeling (Sun & Yang, 2023), T2T (Li et al., 2023b) introduces objective guidance into the denoising process of diffusion, adjusting the denoising to objective- minimizing direction and rewriting the original learned denoising function pe (S:-1|S, SS, G) to
(S:-1 G, (p G) exp([-Vs.. G)] S.-1)
(5)
where y" is the optimal objective score given the instance G, I denotes the objective estimation function. This technique allows for further refinement of the predicted heatmaps by iteratively adding noise to the current solution and then denoising it to an expected better one.
3.2.2 CONSTRUCTION METHODS
Construction methods typically leverage the predictions and the graphs to decode a complete solution.
Greedy Decoding. As naive construction method, it sequentially inserts edges/nodes with the highest confidence the heatmap to the partial solution for feasible solution.
Sampling Decoding, It involves sampling edges or nodes based on their confidence scores in the heatmaps. Denoting the permutation representation of S, based on the edge heatmap H. the t-step
exp(Hi,,__mm) node heatmap prediction can also be estimated from the edge heatmap (1) Σ" exp(H+,.
Beam Search. At each step, beam search (Joshi et al., 2019) explores the heatmap by expanding the most probable edge connections among the nodes neighbors and saving the best b partial solutions for the next step. The final prediction is the tour with the highest probability among the b complete tours.
Random Initialization. For strong improvement-basee search methods like MCTS, random initial- ization of tours can also produce plausible results.
3.2.3 IMPROVEMENT- BASED SEARCH
On top of the constructed complete solutions, improvement- based search further iteratively refines solutions by exploring within limited neighborhood of the current solution.
Two-Opt and Relocate. Two-Opt swaps two nodes in the tour, dividing it into three segments, then reassembles the tour by reversing the middle segment. The relocate operator moves single node
5

---

Published as a conference paper at ICLR 2025
within the tour. The operators be performed the original solution to find lower-cost ones. These two operators can be combined by alternating between using either operator until no better solution can be found, which we call local search (LS) following Hudson et al. (2022) in the rest of the paper.
Monte Carlo Tree Search. The MCTS solver (Fu et al., 2021) iteratively proposes initial solutions and improves them to enhance solution quality. In each iteration, this process includes three compo- nents: 1) state initialization constructs a solution based on a given heatmap: 2) Two-Opt improvement explores a small neighborhood by Two-Opt until no improvements can be found; 3) MCTS based on K-Opt iteratively samples K-Opt operators based on the heatmap to improve the solution and update the heatmap for subsequent iterations. Typically, thousands of iterations of these steps are involved in an MCTS solver. However, we observed that increasing the number of outer iterations results in dimin- ishing marginal improvements heatmap updating. Thus, we reduce the number of outer iterations to one round, separating the construction phase and the improvement-basee search phase. We adopt the latter as design choice for improvement-bane search, which can be integrated with construction methods such as greedy, sampling, beam search, and random initialization generate MCTS variants.
Prediction Guidance. Improvement- -based search can guided by edge regret prediction (Hudson
Ru,,, where ni. is the number al., 2022), where the edge scores for penalizing is calculated as T+ms,,' of penalties assigned to E.g. The edges of maximum utility are penalized and the search is applied only to the penalized edge to maximize the chance of finding lower-cost solutions.
EMPIRICAL EVALUATION
This section tries to answer the following questions and proposes new techniques: Q1. How does learning benefit testing stage problem solving? Q2. What are the desirable design principles for ML4TSP methods? Q3. Which combination can enhance solving performance? The major empirical evaluation is conducted on TSP, yet Appendix C also shows examples of adapting the ML4TSP framework to other problems like Capacitated Vehicle Routing Problem (CVRP) and Maximum Independent Set (MIS) and verify whether conclusions drawn from TSP still hold for other problems.
4.1 EXPERIMENTAL SETUP
Datasets. A TSP instance includes N 2-D coordinates and reference solution. Instances are generated via uniformly sampling N nodes from the unit square [0, 1J2. Main experiments are performed on TSP on scales including 50, 100, and 500. We also include TSP-1000 and the real- world TSPLIB' dataset for generalization evaluation. The reference solutions for all problem scales are labeled by LKH-3 (Helsgaun, 2017). The test set for TSP-50/ 50/100 is taken from Kool et al. (2018) with 1,280 instances, and the test set for WSP-500/1000 is from Fu et al. (2021) with 128 instances.
Metrics. 1) Drop: the relative performance drop w.r.t. length compared to the optimal solutions (obtained by the exact solver Concorde (Applegate et al., 2006) in this paper): 2) Time: the average computational time per instance; 3) Length: the average total distance of the solved tours w.r.t. the corresponding instances i.e. the objective. Note the main paper omits this metric and indicates solution quality primarily by drop for clearness. Full results are presented in Appendix Table 9.
Method Indicator. We explore various combinations within the design space depicted in Fig. 1, making it impractical to label each variant individually. Thus, we directly list the design choices of the evaluated methods in the tables as indicators. Note the ablation may lead to convergence towards a subset of methods with common designs. In such cases, shared design choices are omitted from the table and explained in the caption for clarity. To correspond to prior methods, please refer to Table 9. To simplify method indication in experiments, we adopt the following abbreviations for certain design choices in our ML4TSP framework: 1) Learning Functionalities: Edge Prediction - Edge Pred, Edge Regret Prediction - Regret Pred, Solution Generation - Generation, Sequential Node Prediction + Sequential; 2) Training Objectives: Supervised Solution Proximity + SL. Supervised Edge Regret Proximity + SL Regret, Unsupervised Solving Objective
UL, Reinforcement Solving Objective - RL, Solution Distribution Proximity Generative.
hhttp:/ccompp.. 1fi, uni hei de berg. de/ http//otttaae///tee

---

Published as a conference paper at ICLR 2025
Table I: Joint probability estimation ablation based on methods with Edge Pred as the learning functionality, 8x Greedy: sample 8 heatmaps in parallel then enforce greedy.
Objective
Proh
Toini
Constraction
Solving Shage
Impr. Search
Drop,
TSP-50
Time
Dropl
TSP-100
Time
Dropl
TSP-500
Time
SL
Greedy
1,530%
7.6mms
7,078%
10.5ms
1222578
0.1s
Node
Greedy
0.6745
7.4ms
2.721%
10.1ms
B.496%
0.1s
Genernivee
Greedy
0.076%
0 1.2%%
0.186%
0.4s
6.695%
1.66
SL Node Nona Gonerative
Greedy
2-0gt
0.115%
7.6css
0.649%
12.0ms
2,089%
0.1s
Greedy
2-O
0.082%
7.4
0.292%
11.7ms
1.525%
0.1s
Greedy
2-0pt
0,046%
0.2s
0.077%
0.4s
0.883%
1.6s
SL. St. Node Norm
Beam (n-1280)
0.023%
1.1%
0.673%
2.34
23.629%
11.64
Besm (n=1 (n=1280) 1200)
0.016%
1.18
0.545%
2.24
21,678%
13.7%
Generntive
8x Greedy
0.007%
0.76
0.011%
2.56
1.443%
10.3s
SL
(1=1280)
2-Opi
0.015%
1.1s
2.34
2/318%
12.9%
SL Node Norm Generative
Beam (n= (n=1280)
2 2-Opt
0.01256
1.1s
0.156%
2.36
2.189%
14.0s
8x Greedy
2-Opt
0.006%
0.76
0.009%
2.55
0.320%
10:4s
4.2 LEARNING GENERALLY IMPROVES SOLVING WITH COMPATIBLE SEARCII ALGORITIIMS
This subsection endeavors to answer Q1. Apart from the training objectives that optimize the solving performance, the reference proximity objectives are not directly related to the solving target. Since the solving performance relies on the synergy of neural predictions and search strategies, the correlation between the estimation accuracy in training and the final solving performance remains unclear. To verify this, Fig. 2 provides the scatter plots for the correlation between solving performance and the learning loss across reference proximity objectives on 100-100 test sets
Overall, there exists a positive corre- lation between learning quality and problem-solving performance. How- ever, the introduction of a more robust search mechanism tends to mitigate the advantages of neural predictions. Moreover, once the learning loss surpasses a certain threshold (e.g.. Figure 2: Performance correlation of three reference proxim- ity objectives. GLS: guided local search.
Bege hrsieal
0.50
0L005
Louniing
Leaming Lote
less than 0.003 for the distribution ob- jective), the efficacy of translating improvements in neural predictions into enhancements in problem- solving quality may diminish. This suggests a potential bottleneck in the capacity of the learning phase to enhance the testing phase. Regarding the prediction of edge regret, we find that the accuracy of regret estimation minimally impacts improvement-bart based search methods without heatmap guidance, such as Two-Opt. More results of the effects of learning to MCTS are presented in Appendix E.8.
4.3 DESIRABLE DESIGN PRINCIPLES THAT BENEFITS ML4TSP SOLVING
This subsection delves into crucial design principles in learning algorithms to answer Q2. We generalize overarching design principles with wide applicability across various learning designs, serving as foundational guidance that inspires methodological proposals. Building upon these principles, we introduce novel designs seamlessly integrated into existing pipelines to boost solving performance and validate the effectiveness of adhering to these principles throughout the process.
4.3.1 JOINT PROBABILITY ESTIMATION HELPS CAPTURE VARIABLE CORRELATIONS
This subsection validates the importance of joint probability estimation over solution variables in loss design. In the learning functionality of edge prediction, the SL training objective (Joshi et al., 2019; Fu et al., 2021) generally enforces supervision over each edge's binary classification results. This is based on the assumption of mutual statistical independence of the individual solution parameters, such that the solution can be represented by a product of Bernoulli distributions for the individual solution variables Sanokowski et al. (2023). However, since the CO solutions are highly constrained with strong correlations among the solution variables, such an assumption can lead to a performance drop.
With GNN raw predictions F E g2xXx² which correspond to X n edges, prior methods utilize the softmax operation over the last dimension to ensure that the probabilities of positive and negative edges sum up to 1. The cross-entropy loss in Eq. 1 involves X edges' binary classification, lacking a general capture of joint probability over the solution variables. To this end, we propose node-wiss probability normalization, which normalizes the positive edge probabilities associated with each
7

---

Published as a conference paper at ICLR 2025
Table 2: Symmetry ablation based on meth- ods with Generative as training objective.
Table 3: Symmetry ablation based on methods with RL as the training objective. AS: active search.
Symmesy
Coneraation
Sulving Stage
Impe. Search
Dropi
TSP-300
Time
Faneturaity
Symmury
belsing
Depl
TSP:50
Tiee
Dopp
T5P-100
Tiee:
x
Gnuslyy
9.680%
1.2
Eigs
Baad Stnn
Nampiing
Sanpling
2.55%
72.7mm
11.4
4.80%
9,364%
0.14
Groedy
6.605%
Eigs
Saxplins
3.2
4.23%%
6.7
Guaedy
2-0g
1.5249
1.2s
Band Ston
Ali-loemping
8.22%
4%6
2009%%
9.36
Gronly
2.0g
0,883%
1.6
Segporiti
Conoty
X
4613/
MulliStad
Grealy
1.7ua
1641%
Ss. Groedly
1.43%
10.3
Sym Bsacies
Grandy
0.07%%
2,395
X
8% Groedy
2-0g
0.686/3
6.5%
Segreniici
-MitiStact
Kamphing
Sanpling
Groedy
2.0gc
0.330%
Sym. Bracing
Sampinng
2,509%
Table 4: Ablation on online optimization property, which can be achieved by learning- based search.
Funccionality
Objective
Sulving Suge
TSP-50
TSP-100
TSP-500
Learning Search
Constraction
Impr. Search
Drupi
Time
Dropi
Time
Dropl.
Time
Generative Gencrative
X
Greedy Greedl
0.076%
0.2s
0.186%
6.754%
1.6s
Grvdient Search
0.015%
0.023%
2.675%
3.74
Generation
Generative Generative
x
Greedy
2pt 2-0
0.046%
0.2s
0.077%
0.4s
0.811%
1.6s
Gradient Search
Greedy
0.012%
0.7%
0.023%
0.84
0.445%
3.86
Meta RL.
X
Sampling
4.310%
35.9ms
4.885%
0.1s
13,068%
1.3s
Edge Prod
Meta RL
Active Search
Sampling
3.006%
2%
3.940%
8.56
6.924%
274.8
Meta RL
X
Sampling Sampling
2-0gt 2-0
1.821%
0.1s
2.380%
6.228%
6.4s
Acrive Search
1.549%
2.176%
4.322%
277.0s
node sum up to 2 and the negative probabilities sum to n - 2: F
exp(F F...)
2
0
exp(F (. (.))
2
Then it clips the probability to (0.1]. The predicted heatmap is obtained by H F' (( 1].
Under the edge prediction functionality, we also include methods of solution distribution proximity objective into comparison, which considers a solution as the whole entity, allowing it to naturally adhere to the joint probability distribution. Table shows the ablation. Methods with joint probability estimation generally achieve lower drops, while relying solely on the proposed node-wise probability normalization can bring about significant performance improvement without any additional com- putational overhead. The generative objective can achieve much lower drops, albeit with the added computational cost of multistep inference in the diffusion model.
4.3.2 SYMMETRY SOLUTION REPRESENTATION INTRODUCES EQUIVALENCE AWARENESS
A tour solution holds symmetry or permutation invariance (Kwon et al., 2020). For instance, let tour л = (11, 12, U3, f4 be the optimal solution of some given 4-node TSP instance. Then tours with different starting points, e.g. n' {u2, U3, U4, F1 and tours in a counterelockwise direction, e.g. n" = {wa, 03, U2, Vi J. all represent the same optimal solution. Since CO aims to produce optimal solutions, the neural model expected to be aware of the equivalences among such sequences and should be optimized to consistently yield the same solution regardless of the variances in forms. This subsection endeavors introduce the symmetry solution representation attribute to methods lacking symmetry consideration within the framework, thereby enhancing problem-solving performance.
For Generation learning functionality with Generative training objective, Sun & Yang (2023); Li et al. (2023b) aim to generate directed graph representations (heatmaps) of solutions with directed graph supervision enforced in the optimization of Eq. 2. We replace the directed graph representation for learning with the undirected one, which naturally accommodates the symmetry, and discover a notable performance gain in Table 2. This does not explicitly increase computation during the learning process, but it introduces slight overhead during solution decoding.
For the RL objective, methods decode solutions sequentially during optimization. For instance, Qiu al. (2022) sequentially sample multiple solutions based the predicted edge heatmap, all starting from the same point, to estimate the route length expectations and the REINFORCE gradients, and sequence models (Kool et al., 2018) predict node sequence using per-step node heatmaps for optimization. To achieve symmetry, we propose to enforce a random starting point decoding policy in REINFORCE updates (in training and active search) for methods with Edge Pred functionality, and refer to Kwon et al. (2020) to optimize over diverse rollouts with multiple starting points as well as use symmetry baselines (Kim et al., 2022) for Sequential functionality. These techniques raise the model's 's awareness of symmetry. Table 3 presents solving results on TSP-50 and 100, showing notable performance gain by introducing symmetry, yet with additional computational overhead.
8

---

Published as a conference paper at ICLR 2025
4.3.3 ONLINE OPTIMIZATION COMPLEMENTS GENERALIZATION CAPABILITY
In order to bridge the gap between training for average performance and solving for performance in new instances, instance-specific optimization can be helpful. We verify the effectiveness of techniques that optimize in the testing phase in Sec. 3.2.1: the active search for methods with Edge Pred as the functionality and the gradient search for methods with Generation the functionality. Table 4 ablates learning-based search across different baselines, indicating a promising gain with Baaming-baset search, however at the cost of additional computation.
4.3.4 SEARCH FRIENDLINESS CONTRIBUTES TO LEARNING- -SARCH SYNERGY
Techniques that consider how better in- legrate learning with search can benefit problem-solving We verify the effective-
Table 5: Ablation on search friendliness property.
Funstionalty
Objective
Search Frod
Solving Stage
TSP-50
TSP-10
Insp
Time
ness of search friendliness designs includ-
Edgg Pred
X
Guided (x=1s)
0.1446
1.3s
3,319%
1.3
Regutt Frod
Regret
Guideel
1,05%
ing enhancing the informativeness of pre-
Edge
X
0.025
6000s
0.6
diction information (e.g. predicting edge
Rearet Fred
SL Roaret
Randons NCTS
0.000%
0.2x
0.179%
18
regrets), promoting diversity in the pre-
Reguoniial
Sequential
Mets + IRI.
x
Sumpiing
Sarppling
2.187%
72. Tmee
9.3648
4.899%
0.1
Smn
dicted solutions (e.g. modeling solution distribution), and incorporating the search
Segueniial
RL
AS*Surpling
3
3.36
4.234%
6.7%
Sequenial
Metu SRL
AS SSrSunggg
8.823%
4.5%
2.099%
0.36
process into optimization (e.g. through meta learning to learn optimal initialization for solving stage). Table 5 verifies the solving performance of providing more informative prediction and adopting meta learning, which may also introduce slight overhead. We notice that for MCTS, the performance gain of predicting edge regrets is minor, which may stem from the compatibility between the techniques. For the effectivvness of prediction diversity. Table 2 demonstrates significant improvement in solving performance achieved by employing multiple sampling, which is contributed by increased diversity.
4.4 STREAMLINING THE ML4TSP DESIGN SPACE DISCOVERS MORE POWERFUL SOLVERS
This section investigates Q2&3 by exploring potential recomposition among separable components in our framework, with the full results presented in Appendix Table 9.
Evaluation of Heuristic Search.
Table 6: Heuristic search ablation based on Edge Pred func- tionality and SL training objective.
We categorize search strategies out-
side learning as a construction- improvement paradigm, where con- structive search and improvement- based search are orthogonal. Ta-
Subving Stage
TSP-50
TSP-100
TSP-S00
Canstration
Impe Search
Danil
Time
Danil
Time
Doapl
Timm
Grusdy
L530's
7.6exs
7.078%
10.6ux
12.237%
(1-10))
1.35
0.177
Graady
Too-Ope
0.115%
5.6ext
0.695
12.0ma
2.09%%
0.1x
ble 9 shows that the most proper heuristic search strategy varies for
Gready
Guided LS (1-1s)
0.114%
1.15
3.319%
1.26
7.62%
45.55
Groady
MUTS
BUBB
5.4ms
IL1509
10.5ms
0X338
1.36
Boan (2-1)
Tyo-Dye
0.015%
1.1s
0.149%
2.3
2.431%
12.%
Heam (m=30)
METES
0.54
6.235%
$6.54
the specific learning functionalities and objectives. Interestingly, even
Sampling (a-50)
MCTS
0,022%
0.5s
0.021%
0.396%
58.1s
Randomn (s-10)
MCTS
17.5mz
$1,40s
0.5195
(em50))
0.002%
the more intricate MCTS method does not necessarily yield the best performance. In cases where the output heatmap closely approximates fcasible solutions and exhibits high discreteness (c.g. the Generative objective), the effectiveness of utilizing the heatmap guide the improvement search often falls short when compared to methods with smoother and more continuous heatmaps (e.g. SL and meta RL objectives for Edge Pred). Due to space limitation, Table 6 adopts the fundamental solution proximity objective for edge prediction as an example to illustrate the effectiveness and recomposing performance of heuristic search methods implemented in our framework. The de- coupled improvement MCTS can be combined with other construction methods to form variants like Greedy MCTS, Sampling MCTS, Beam MCTS, and Random MCTS, which utilize different constructive search for MCTS initialization, showing improvement in both solving performance and efficiency compared to the original MCTS solver (Fu et al., 2021). We use different time slices for varying problem scales, with the time for a single time slice denoted as t. We control the search process of MCTS by adjusting the number of time slices. More details are given in Appendix F.3.
Recomposing to the Optimal. We recompose the learning and search techniques in our framework to produce a factory of solvers Table 7 presents the best three method combinations for every learning functionality. The recomposed solvers achieve SOTA performance that reaches 0.000% for TSP-50, 0.001% % for TSP- 100, and O. 142% for TSP-500. We find that top- perffrronnnng methods remain closely tied to robust search such as MCTS, while generative models, specifically diffusion

---

Published as a conference paper at ICLR 2025
Table 7: Optimal recomposition of learning and search techniques. ": reference for drop estimation.
Trasing Stae
Selvire State
7SP-50
13R-100
1SP-340
Learing Panciccnllyy
Traning Obyezine
Lanin Sarch
Oresunaiin
lags Searh
Deep 194
Deep cli)
Tix
Drspriit
Tixs
(Apphapac
LaRS (rubedien thahaaas 2503)
0.000001000
0.5
0.5
0.322:2.176
0.7x
TK30 misas rietoge in 2017
100 100
1
0.072-9978
4.75
Bige Paal
SL. Nak:
Grenly
Mc75
0.001:00116 14
0.00160220 201
16330
1.3g
Node Nowrs
Bandem
METE
0.501 10
0.142 8.106
Roast (ual
sl, Regedt
Crealy
Guékad LS (mm10k)
0.504200885
10.30
0.48:222001
10.4s
Regit
MrTS
Rogwt Phod
Bandees
MUTS
0.800 8.mm
0.2s
0 1119100.01
1.5
Gcaminn
Ocscrated Sytt.
Grcolyy
Too
0.066:0 140
0.5
0 160
1.6
Gramsion
Ocneraing Sysz.
Gralien: Scauds
Six Guoaly
Tyo-Opi
0.062 /04
1.56
0.001:33222
5.6
0.18955135
25.66
Sapaxial
RL.
Sucpping, Maliitari
0.136m0 366
1.3ex
Sogastia
RL Syas. Badia:
Suapliin Mibiiitaii
Ton-Opi
0.110s00242 242
6.5
0. 0.22922535
1.5
Table 8: Generalization Results with models trained on TSP-500. *: reference for drop estimation.
Training Stage
Sulving Stage
TSP-1000
TSPLID 200-
100-1000
Leoming Functionality
Training Objective
Learning Search
Construction
Impr.
Deup
Dropl
Time
PyConcodd (Applegute al., 2006)
0,000%
54.4s
0.0035
10.64
Fdge Prod.
ST.
Cinady
MCTS
1,171%
1.416%
1.84
Edge Pred.
SL+ Node Norm
Creedy
MCTS
0.798%
6.1s
L,252%
1.8s
Edge Prud.
SL. Nude Norm
Sumpling (n=10)
MCTS
0.687%
53.5s
0.517%
17.9c
Edge Pred.
SL Node Norm
Random (o=10)
MC1S
0.603%
54.65
0.678%
17.35
Solution Genention
Genensiiee
Groady
Two-Qpt
1.819%
2.36
2.411%
1.64
Soluton Generatio
Generaive
Greedl
Two-Opt
1.735%
1.%%
18808
1.7s
Solution Genenaion
Generstvee Sym.
Gradient Search
Groedy
Two-Opt
1.293/
1.3378
Solution Generation
Generative Sym.
Greedy
Two-Opt
1.152%
22.46
1.01%
5.8s
models, excel in constructive solvers without heavy reliance on heavy search, achieving 0.002%, 0.003%. 0. 0.188 for TSP-50, 100 and 500. This highlights the potential for future development of more powerful solvers grounded in generative objectives and diffusion backbones. Considering the trade-off between solution quality and solving time, the best solutions are often achieved at the cost of higher computational expense. For comprehensiveness, Table has also selected, for each learning functionality, recompositions at different speed levels, including the fastest approach with stable solution quality for demonstration. This is to accommodate scenarios that prioritize speed or approximation quality over strict optimality, where RL methods stand out with the fastest speed.
Evaluation for Generalization. We reconduct ablations over top-performing models to verify the generalization performance of the framework and whether the claims still hold for generalization to larger scale TSP, i.e 1S0-1000, and TSPLIB instances with 200-1000 nodes. The verified models trained on TSP-500. Comparing methods in Table 8, we observe that the advantages of design principles such as joint probability estimation, symmetry solution representation, online optimization, and search friendliness persist across generalization. Additionally, the newly recomposed search method, Random MC7S, continues to demonstrate a performance advantage in generalization.
Regarding problem size, as observed in Table 9, the general trend is that the larger the scale, the worse the model's relative solving performance. We also find that learning strategies that play supportive roles (e.g. guiding MCTS) are less scale-sensitive, while end-to-end methods (e.g. generative and RL methods) are more affected. This may be because strong search methods mitigate the risk of reduced prediction quality by learning. However, we can also see that methods like generative models still perform well as the scale increases. On the other hand, when considering model complexity and training time, methods with shorter training times, like unsupervised learning, are relatively less affected by scale. This may be because the bottleneck is the model capacity or the amount of learnable information using unsupervised learning rather than task difficulty.
5 CONCLUSION AND FUTURE WORK
We design a principled modular framework that integrates existing ML4TSP practices, allowing for inspecting the current system. Based on this unification, we analyze the relationship between learning and solving objectives and show that learning generally improves solving with compatible search algorithms. We also analyze the effectiveness of current MLATSP efforts, identifying desirable design principles for ML solvers like joint probability estimation, symmetry solution representation, and online optimization. Additionally, we offer insights into how model predictions intervene with strong search methods like MCTS and highlight preferences in learning paradigms for ML4TSP. Leveraging our findings, we propose enhancements to existing methods to compensate for their missing attributes and recompose within the established technique library to establish factory of learning- based solvers, among which the optimal compositions achieve clear performance gains. Our implementation is carefully organized, facilitating easy development for further research and engineering practices.
10

---

Published as a conference paper at ICLR 2025
ETHICS STATEMENT
This research complies with ethical standards, utilizing datasets that are either synthetic or publicly available and contain no sensitive or personally identifiable information. involves no direct human subjects, nor does it present privacy security concerns. All methodologies and experiments were conducted in line with legal regulations and established research integrity practices. There are no conflicts of interest, external sponsorship influences, concerns regarding discrimination, bias, or fairness. Moreover, the research does not lead to any harmful insights or applications.
REPRODUCIBILITY STATEMENT
We have taken steps to ensure the reproducibility of the results presented in this paper. The ex- perimental settings, including datasets and model designs, are thoroughly described Section 4. Additional details, such as algorithm details and model configurations, provided in Appendix F. We provide full records of our experiments in Table and provide minimalistic code example for the implementation in A Appendix D. Source code will be made publicty available upon acceptance.
REFERENCES
SP Anbuudayasankar, K Ganesh, Sanjay Mohapatra, SP Anbuudayasankar, K Ganesh, and Sanjay Mohapatra. Survey of methodologies for tsp and vrp. Models for Practical Routing Problems in Logistics: Design and Practices, pp. 11-42, 2014.
David Applegate, Ribert Bixby, Vasek Chvatal, and William Cook. Concorde tsp solver, 2006.
Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne den Berg. Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 34:17981-17999 2021.
Tianyi Bao, Qitian Wu, Zetian Jiang, Yiting Chen, Jiawei Sun, and Junchi Yan. Graph out-of- distribution detection goes neighborhood shaping. ICML'24. JMLR.org, 2024.
Tianyi Bao, Xinyu Ye, Hang Ruan, Chang Liu, Wenjie Wu, and Junchi Yan. Beyond circuit connections: A non non-message passing graph transformer approach for quantum error mitigation. In The Thirteenth International Conference Learning Representations, 2025.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: methodological tour dhorizon. European Journal of Operational Research, 2021.
Federico Berto, Chuanbo Hua, Junyoung Park, Minsu Kim, Hyeonah Kim, Jiwoo Son, Haeyeon Kim, Joungho Kim, and Jinkyoo Park. RI4co: unified reinforcement learning for combinatorial optimization library. In NeurlPS 2023 Workshop: New Frontiers in Graph Learning, 2023.
Lorenzo Brusca, Lars CPM Quaedvlieg, Stratis Skoulakis, Grigorios Chrysos, and Volkan Cevher. Maximum independent set: self-training through dynamic programming. Advances in Neural Information Processing Systems, 36:40637 2023.
Quentin Cappart, Didier Chételat, Elias Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. arXiv preprint arXiv:2102.09544, 2021.
Xinyan Che, Yang Li, Runzhong Wang, and Junchi Yan. Mixsatgen: Learning graph mixing for instance generation. In The Twelfth International Conference on Learning Representations, 2024.
Omar Cheikhrouhou and Ines Khoufi. A comprehensive survey on the multiple traveling salesman problem: Applications, approaches and taxonomy. Computer Science Review, 40: 100369, 2021.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. Advances in Neural Information Processing Systems, 32, 2019.
11

---

Published as a conference paper at ICLR 2025
Ruoyu Cheng, Xianglong Lyu. Yang Li, Junjie Ye, Jianye Hao, and Junchi Yan. The policy-gradien placement and generative routing neural networks for chip design. In Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 16350-263622 Curran Associates, Inc., 2022a.
Ruoyu Cheng, Xianglong Lyu, Yang Li, Junjie Ye, Jianye Hao, and Junchi Yan. The policy-gradient placement and generative routing neural networks for chip design. Advances in Nearal Information Processing Systems, 35:26350-26362, 2022b.
Paulo R O Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akcay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Asian Conference on Machine Learning, pp. 465 460, 2020.
Paulo R de O da Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akcay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. arXiv preprint arXiv:2004.01600, 2020.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In International conference on machine learning. pp. 1126-1135. PMLR, 2017.
Zhang-Hur Hunng-Huauuee Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize a small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI Conference Artificial Intelligence, 2021.
Simon Geisler, Johanna Sommer, Jan Schuchardt, Aleksandar Bojchevski, and Stephan Günnemann. Generalization of neural combinatorial solvers through the lens of adversarial robustness. In International Conference Learning Representations, 2022.
Haoyu Geng, Hang Ruan, Runzhong Wang, Yang Li, Yang Wang, CHEN Lei, and Junchi Yan. Benchmarking pto and pno methods in the predictive combinatorial optimization regime. In The Thirty-eigh Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2023.
Katayoon Goshvadi, Haoran Sun, Xingchao Liu, Azade Nova, Ruqi Zhang, Will Grathwohl, Dale Schuurmans, and Hanjun Dai. Discs: a benchmark for discrete sampling. Advances in Neural Information Processing Systems, 36, 2024.
Ziao Guo, Yang Li, Chang Liu, Wenli Ouyang, and Junchi Yan. Acm-milp: Adaptive constraint modification via grouping and selection for mardness-preservve milp instance generation. In The Forty-first International Conference on Machine Learning, 2024.
Keld Helsgaun. An extension of the lin-kernighan-helseee salesman and vehicle routing problems. Roskilde: Roskilde University, pp. 24-50, 2017.
tsp solver for constrained traveling
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840-6851, 2020.
Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling, Argmax flows and multinomial diffusion: Learning categorical distributions. Advances in Neural Information Processing Systems, 34:12454- 2021.
André Hottung, Bhanu Bhandari, and Kevin Tierney. Learning latent search space for routing problems using variational autoencoders. In International Conference on Learning Representations, 2021a.
André Hottung, Yeong-Dae Kwon, and Kevin Tiemney Efficient active search for combinatorial optimization problems. In International Conference on Learning Representations, 2021b.
Qingchun Hou, Jingwei Yang. Yiqiang Su, Xiaoqing Wang, and Yuming Deng. Generalize learned heuristics to solve large-scale vehicle routing problems in real-time. In The Eleventh International Conference Learning Representations, 2023.
Benjamin Hudson, Qingbiao Li. Matthew Malencia. and Amanda Prorok. Graph neural network guided local search for the traveling salesperson problem. In International Conference on Learning Representations, 2022. URL https: wpwpeeveeeeeeeeeeeeeeeeeeee ew net forum 3
12

---

Published as a conference paper at ICLR 2025
Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.0122) 2019.
Chaitanya K Joshi, Quentin Cappart, travelling salesperson problem requires rethinking generalization. arXiv preprint arXiv:2006.07054, 2020.
Rousseau, and Thomas Laurent. Learning the
Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization graphs. Advances in Neural Information Processing Systems, 33: 6659-6672, 2020.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
Minjun Kim, Junyoung Park, and Jinkyoo Park. Learning to cross exchange to solve min-max vehicle routing problems. In The Eleventh International Conference Learning Representations, 2023.
Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-nco: Leveraging symmetricity for neural combinatorial optimization. arXiv preprint arXiv:2205.13209, 2022.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609 02907,, 2016.
Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn to solve routing problems! arXiv preprint wrXiv:180.008475 2018
Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances Neural Information Processing Systems, 33:21 1 88-88188,, 2020.
Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, and Renato F Werneck. Finding near-optimal independent sets at scale. In 2016 Proceedings of the eighteenth workshop on algorithm engineering and experiments (ALENEX), pp. 138-150, SIAM, 2016.
Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehicle routing. Advances in Neural Information Processing Systems, 34:26198 20-212221111 2021.
Yang Li, Yichuan Mo, Liangliang Shi, and Junchi Yan. Improving generative adversarial networks via adversarial learning in latent space. S. Koyejo, S. Mohamed, A. Agarwal, Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 8868-8881. Curran Associates, Inc., 2022.
Yang Li, Xinyan Chen, Wenxuan Guo, Xijun Li, Wanqian Luo, Junhua Huang, Hui-Ling Zhen, Mingxuan Yuan, and Junchi Yan. Hardsatgen: Understanding the difficulty of hard sat formula generation and strong stuuttre-hardness-ooe SIGKDD Conference on Knowledge Discovery and Data Mining, 2023a.
baseline. In Proceedings of the 29th ACM
Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. T2t: From distribution learning in training to gradient search in testing for combinatorial optimization. In Advances in Neural Information Processing Systems, 2023b.
Yang Li, Liangliang Shi, and Junchi Yan. lid-gan: an iid sampling perspective for regularizing mode collapse. In Proceedings of the 32nd International Joint Conference Artificial Intelligence, 2023c.
Yang Li, Jinpei Guo, Runzhong Wang, Hongyuan Zha, and Junchi Yan. Fast 12t: Optimization consistency speeds up diffusion based training-to to-tiningg- solving for combinatorial optimization. In The Thihty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Shen Lin and Brian W Kernighan. An effective heuristic algorithm for the traveling problm... Operations research, (1(2):99-5566 1973.
13

---

Published as a conference paper at ICLR 2025
Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. arXiv preprint arXiv:2310.07985, 2023.
Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. Advances in Neural Information Processing Systems, 36, 2024.
Yining Ma, Zhiguang Cao, and Yeow Meng Chee. Learning to search feasible and infeasible regions of routing problems with flexible neural k-opt. Advances Neural Information Processing Systems, 36, 2024.
Rajesh Matai, Surya Prakash Singh, and Murari Lal Mittal. Traveling salesman problem: overview of applications, formulations, and solution approaches. Traveling salesman problem, theory and applications, 1(1):1-25, 2010.
Yimeng Min, Yiwei Bai, and Carla P Gomes. Unsupervised learning for solving the travelling salesman problem. arXiv preprint arXiv:2303. 2.XXi:2303.10530 10538, 2023.
Yuichi Nagata and Shigenobu Kobayashi. A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem. INFORMS Journal on Computing, 25(2))346-363, 2013.
Wenzheng Pan, Hao Xiong, Jiale Ma. Wentao Zhao, Yang Li, and Junchi Yan. UniCO: On uni- fied combinatorial optimization via problem reduction to matrix-encoder general TSP. In The Thirteenth International Conference on Learning Representations, 2025.
Yun Peng, Byron Choi, and Jianliang Xu. Graph learning for combinatorial optimization: A survey of state-of-the-art. Data Science and Engineering. 6(2): 141, 2021.
Petrică C Pop, Ovidiu Cosma, Cosmin Sabo, and Corina Pop Sitar. A comprehensive survey on the generalized traveling salesman problem. European Journal of Operational Research, 2023.
Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. Dimes: A differentiable meta solver for combinatorial optimization problems. arXiv preprint arXiv:2210.044 0200 2022.
Sebastian Sanokowski, Wilhelm Franz Berghammer, Sepp Hochreiter, and Sebastian Lehner. Varia- tional annealing on graphs for combinatorial optimization. In Thirty-sevnnth Conference Neural Information Processing Systems, 2023.
Sebastian Sanokowski, Sepp Hochreiter, and Sebastian Lehner. A diffusion model framework for unsupervised neural combinatorial optimization. International Conference on Machine Learning, pp. 43346 43367. PMLR, 2024.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):4844455 2016.
Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. arXiv preprint arXiv:2010.02500 2020.
Zhiqing Sun and Yiming Yang. Difusco: bbaph diffusion solvers for combinatorial optimization. arXiv preprint 0822222302.08224, 2023.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10003. 2017.
Thibaut Vidal. Hybrid genetic search for the evrp: Open-source implementation and swap* neighbor- hood. Computers & Operations Research, 140: 105643, 2022.
Oriol Vinyals. Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in neural information processing systems, 28, 2015.
Haoyu Wang and Pan Li. Unsupervised learning for combinatorial optimization needs meta- meta-learning. arXiv preprint arXiv:2301.03) 2023.
14

---

Published as a conference paper at ICLR 2025
Haoyu Peter Wang and Pan Li. Unsupervised learning for combinatorial optimization needs meta learning. The Eleventh International Conference on Learning Representations, 2022.
Haoyu Peter Wang, Nan Wu, Hang Yang. Cong Hao, and Pan Li. Unsupervised learning for combinatorial optimization with principled objective relaxation. In Advances in Neural Information Processing Systems, 2022.
Runzhong Wang. Yunhao Zhang, Ziao Guo, Tianyi Chen, Xiaokang Yang, and Junchi Yan. Linsatnet: the positive linear satisfiability neural networks. In International Conference on Machine Learning. pp. 36605-36625, PMLR, 2023.
Frederik Wenkel, Yimeng Min, Matthew Hirn, Michael Perlmutter, and Guy Wolf. Overcoming oversmoothness in graph convolutional networks via hybrid scattering networks. arXiv preprint arXiv:2201.08932, 2022.
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8:229-256, 1992.
Huaijin Wu, Xinyu Ye, and Junchi Yan. Qvae-mole: The quantum vae with spherical latent vari- able learning for 3-d molecule generation. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Qitian Wu, Chenxiao Yang. Wentao Zhao, Yixuan He, David Wipf, and Junchi Yan. Dif- former: Scalable (graph) transformers induced by energy constrained diffusion. arXiv preprint arXiv:2301.09474. 2023.
Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuristics for solving routing problems. IEEE transactions on neural networks and learning systems, 33(9): 5057-5069, 2021.
Nianzu Yang, Huaijin Wu, Kaipeng Zeng, Yang Li, Siyuan Bao, and Junchi Yan. Molecule generation for drug design: a graph learning perspective. Fundamental Research, 2024.
Xinyu Ye, Ge Yan, and Junchi Yan. Towards quantum machine learning for constrained combinatorial optimization: a quantum qap solver. In Proceedings of the International Conference on Machine Learning), 2023.
Xinyu Ye, Hao Xiong, Jianhao Huang, Ziang Chen, Jia Wang, and Junchi Yan. On designing general and expressive quantum graph neural networks with applications to milp instance representation. In The Thirteenth International Conference on Learning Representations, 2025.
Yingqian Zhang, Laurens Blick, Paulo da Costa, Reza Refaci Afshar, Robbert Reijnen, Tom Catshock, Daniël Vos, Sicco Verwer, Fynn Schmitt- Ulmm, André Hottung, al. The first ai4tsp competition: Learning to solve stochastic routing problems. Artificial Intelligence, 319:103918 2023.
Xinhao Zheng, Yang Li, Cunxin Fan, Huaijin Wu, Xinhao Song, and Junchi Yan. Learning plaintext- ciphertext cryptographic problems via anf-based sat instance representation. Advances Neural Information Processing Systems, 2024.
Jianan Zhou, Yaoxin Wu, Wen Song. Zhiguang Cao, and Jie Zhang Towards omni-generaliizble neural methods for vehicle routing problems. International Conference on Machine Learning, pp. 42769 42789, PMLR, 2023.
15

---

Published as a conference paper at ICLR 2025
Appendix
CONTENTS
General Discussion of Design Choices
18
More Discussion of Related Work
19
C Adaptation of the Framework to Other CO problems
19
C.1 Guide for Cross-Problem Adaptation
19
C.2 ML4CO-Kit Library: Meta Framework
20
................................
C.3 Empirical Results
20
C.3.1
Experimental Setup
21
C.3.2
Joint Probability Estimation Helps Capture Variable Correlations.
C.3.3
Symmetry Solution Representation Introduces Equivalence Awareness
22
C.3.4
Online Optimization Complements Generalization Capability
22
C.3.5 Search Friendliness Contributes to Seamiig-SSeacll Synergy
22
D Minimalistic Code Example for ML4TSP Solvers
23
D.I
TSPSolver
23
D.2
Learning-based Solvers
23
D.3 TSPLKHSolver and TSPConcordeSolvvr
24
D.4
Evaluate on TSPLIB
24
Supplementary Experimental Results and Discussion
25
E.1 Full Recomposition Results
25
E,2
Generalization to Varying Distributions
26
E.3
Supplementary Results for Fig.
................................
26
E,4
Supplementary Results of runtime-drop curve.
26
E.5
Supplementary Results for Sec. 4.3.4
................................
26
E.6
Discussion of Unsupervised Objectives
................................
26
E.7 Discussion of Supervision Quality
................................
27
E.8
Discussion of MCTS
27
Supplementary Details of Incorporated Methods
29
F.1
Training Objectives
29
F.2
Learning-based Search
F3
Local Search
31
Network Architecture Details
32
G.1
Graph Convolutional Networks
32
16

---

Published as a conference paper at ICLR 2025
G.2 Graph Attention Networks
33
G.3 Scattering Attention GNN
33
H Discussion for the Synergy of Training and Solving for CO
34
I Experimental Details
36
I.1 Implementation and Hyperparameters
36
I.2 Detials of Experiments
37
J Limitations and Broader Impacts
37
17

---

Published as a conference paper at ICLR 2025
Table 9: Full Results of Learning and Searching Technique Recomposition for ML4TSP Solvers.
Tready Digake
Soursh
Souch
Longl:
Eregl
Tie
Lengla
T1:66
Lenghti
Drags
Tile
71.8
(1000)
18:33%
233809
11584
23.55
22-366
CANDAI Kolupeda (2133
5588
00375
410
3.565
0136
18.345
0.8005
UG0 vettrr Stritiggn 5017)
(1000%
1.014
0.305
0.115
4.17%
(2119)
12.37
Gamdy
Guale (a61
5723
1.80
1.011
3.30%
07.12
1.020
13333
18315
3136
13100
glning Tealts
165m
1380
150%%
3L
19715
115
15:00
13105
SXCSS
5380
1005
42390
(0015
155
13.00
1301
15155
A1ECK XF1)
MITTo (11))
1104
0034
1555
19377
1.039
11.0
Chenty
135
11590
4136
(200
1100
1108
1301
16:01
13235
0006
0003
135%
11:91
11.9%
163
3OTTS
000
1126
10.07
1301
16-153
MCTD Sacves
0008
1260
0007
100
1130
(3285
11.98
SKTS
3485
1035
350
4005
116-
KL
5985
114
140
03615
64566
19355
16.135
1AW%
Mal
1946
COMESSION
5003
2559
43355
1128
12.055
1.25%
1367
1101
10%
The
5351
137
137
1355
1110
15659
VETS
535
130%
123m
196
1506
1.8%
Uhe
1331
013
7386
175%
A.8%
43225
Actier
318/
1.0%
1756
Gouck
11.0
MI 4E:
The
0135
1.07
1396
115h
EDNNELS cildeeec 342
Clcckt
Ciato LS (HD0
5553
0085
1085
1.07
1985
132%
Guccf
3K15
(123)
2080
0136
DAP-3600 Taly 20331
5564
0.355
0386
1356
0231%
144%%
15.00
1.504%
1,204
3.53
1154
0117%
1.2%%
15.62
3.11%
4.3%%
ME--757
5562
0226
01865
1350
17.64
1STe
BS-4130
Goody
148%
15.99
1305
1.76
46-1153
MKT4
049h
0096
110
1986
1376
Scuch
Goody
01.6
11860
1996
16-152
Goody
MKTS
5.80
1286
0091
157
1500
1.55
1006
3E-155
Oorrdder 3ys
Graica
beack
2% Drand
SOCTS
5.85
00225
1394
1.50
(1001)
155%
13559
1.5%
35.5%
Seperiaa Prefecee
5397
1.81
23.3%
Clchf
The-
1387%
3.50
KL:
01616
1860
11m
Sanpting
KL
al
3.61
1.00
08100
Tou
Sye MOD
3002)
31.
Goody
5736
00776
15m
140
02
HEA15S
5555
18m
199%
1547
11.
1371
MU-Th
11. Syn foclee
Sunplng- 30.5
Thy- 5.64
01005
0.77%
1.00
0136
1905
A GENERAL DISCUSSION OF DESIGN CHOICES
With the recomposition results, we obtain the following observations regarding the general design solvers:
choices for ML4TSP solvers: 1) MCTS variants can significantly enhance the performance, while it is
not universally compatible with all learning designs. For adaptability, smoother and more continuous predictions tend to combine more easily with MCTS. With MCTS, the optimal combination in our framework is achieved when learning the solution proximity objective with node-wise normalization for edge prediction. This combination, together with the random MCTS solving strategy, achieves
18

---

Published as a conference paper at ICLR 2025
drops of 0.000%, 0.001% %, and 0.142% on TSP of sizes 50, 100, and 500, respectively. 2) Without relying on tailored heuristics like MCTS, the generative distribution proximity objective based on the symmetry representation achieves the optimal results when adopting gradient search, 8x Greedy, and Two-Opt for the solving stage, achieving drops of 0.002%. 0.003%, and 0.187% on TSP of sizes 50, 100, and 500, respectively. 3) Regarding the paradigms of learning-based solvers, we discover clear performance advantage of non-autoregressivve methods to autoregressive sequence models, and super- vised methods are significantly ahead of unsupervised methods, especially without the support of pow- erful heuristic search. For scalability, we notice that acquiring supervision for edge regret is extremely time-consuming, making it impractical for solving larger-scale problems like TSP-500. Meanwhile, RL-based sequence models also face challenges on larger-scale problems due to issues like sparse rewards and training instability, which also struggle to support training on larger-scale instances.
B MORE DISCUSSION OF RELATED WORK
Learning- -earning-based designs have advanced CO (Bengio et al., 2021; Cappart et al., 2021; Peng et al., 2021) leveraging graph learning (Bao et al., 2024; 2025; Wu et al., 2023). TSP has long been studied by the machine learning community since early works like (Vinyals et al., 2015; Khalil et al., 2017) and is one of the most extensively studied CO problems. Other CO problems like MIS (Brusca et al., 2023; Goshvadi et al., 2024; Wang & Li, 2023), CVRP (Ma et al., 2024; Hou et al., 2023; Kim et al., 2023) are also widely studied, which can sometimes share similar methodology designs. CO problems have found widespread applications in areas such as chip design (Cheng et al., 2022a), molecule generation (Yang et al., 2024; Wu al., 2024), and cryptography (Zheng et al., 2024).
Learning-basee CO solvers involve autoregressive methods (Khalil et al., 2017; Kool et al., 2018; Kwon et al., 2020; Hottung et al., 2021a; Kim et al., 2022) that directly construct solutions by sequen- tially determining decision variables until a complete solution is constructed, and non-autoregressive methods (Joshi et al., 2019; Fu al., 2021: Geisler et al., 2022; Qiu al., 2022; Sun & Yang. 2023; Zheng et al., 2024) that predict soft-constrained solutions in one shot and then perform post- processing to achieve feasibility. The neural predictions can also be leveraged to guide the local search process, which iteratively refines given solution (d O Costa et al., 2020; Wu et al., 2021; Chen & Tian, 2019; Li et al., 2021; Fu et al., 2021; Hudson et al., 2022). Recently, quantum machine learning has shown potential in solving these NP problems empowered inspired by quantum computing properties (Ye et al., 2023; 2025).
Generative models (Li ct al., 2022; 2023c) have been leveraged in CO to resolve data bottlenecks (Li et al., 2023a; Che et al., 2024; Guo et al., 2024) and have also shown promise in solving CO thanks to their strong representational capabilities and informative distribution estimation. It models the problem-solving task as a conditional generation task for learning solution distributions conditioned on given instances (Hottung et al., 2021a; Cheng et al., 2022b; Sun & Yang, 2023; Li et al., 2023b; Sanokowski et al., 2024; Li et al., 2024). The development line of diffusion-based solvers has achieved the current SOTA performance in neural CO solving. DIFUSCO (Sun & Yang, 2023) adapts the discrete diffusion models (Austin et al., 2021: Hoogeboom et al., 2021) in CO and has attained competitive performance solving TSP and MIS. The T2T framework (Li et al., 2023b) further introduces an objective-gus guided gradient search process in the diffusion model during solving to lever- age the learned distribution and has achieved the SOTA performance. DifUUCO (Sanokowski et al., 2024) optimizes the diffusion-based solver through an unsupervised learning approach. Recently, Fast T2T (Li et al., 2024) proposes a more powerful optimization consistency model for solving CO problems that achieves tens of times speedup compared to previous raw diffusion-bart based solvers.
C ADAPTATION OF THE FRAMEWORK TO OTHER CO PROBLEMS
C.1 GUIDE FOR CROSS-PROBLER ADAPTATION
The ML field has gone the farthest optimizing the TSP, and we consider TSP as one of the most extensively studied CO problems with the richest learning and searching techniques. Note numerous methods have been devised in ML4CO. While some of the best-performing methods show promising results, they still exhibit a gap compared to traditional methods. The very first motivation of this work is to reassess the role of learning for CO (or specifically TSP) and to discern which parts of existing
19

---

Published as a conference paper at ICLR 2025
techniques genuinely beneficial and which not. For this purpose. select TSP to incorporate and analyze learning and searching techniques as comprehensively as possible and, to the maximum extent, retain the potential for application to other problems.
This framework can be customized for other CO problems with the same modular organization and learning-based designs. The primary adaptions required would involve adjusting the optimization variables, e.g. replacing edges with nodes for node-decision problems such as Maximum Independent Set (MIS), as well as modifying the (optional) heuristic search designs that are problem-specific. Specifically, the pipeline for new problem can be still generally be organized by prediction-and- seach pipeline like TSP, where the learning models can be trained with learning tasks including 1) decision variable prediction, 2) variable regret prediction, 3) solution generation, and 4) sequential variable prediction, as well as training objectives including 1) supervised solution proximity, 2) unsupervised solving objective, 3) reinforcement solving objective, 4) supervised variable regret proximity, 5) solution distribution proximity, potentially with the support of 6) meta learning objective. Then in the solving stage, the neural prediction can be further improved by learning-base based search methods for specific problems, and the search phase can follow the construction-sean constructive search like Greedy and improvement- based search like local search.
pipeline with
Additionally, many parts our analysis, e.g., the study of the relationship between learning and solving objectives, the benefits of satisfying certain design principles like joint probability estimation, symmetry solution representation, online optimization, etc., indeed study the general learning designs and its synergy with search methods, maintaining the potential to have applicability beyond TSP in design. For example, for MIS, we can also consider achieving joint probability estimation by introducing a normalization other problems with sequential solutions, we can consider enforcing the symmetry property for solution representations. In general pipeline designs, we can also consider introducing optimization during the testing phase to enhance performance.
on the predicted node probabilities to enhance performance. For
C.2 ML4CO-KO KIT LIBRARY: META FRAMEWORK
To facilitate adaptation to other CO problems, we have developed a task-agnostic skeleton and common toolkit, which provides robust support for the development of learning based solvers across different tasks. This toolkit focuses on facilitating method development while leaving room for customizations of problem-specine implementations. Key features include:
1. A generic skeleton for organizing MI4CO frameworks;
2. Base classes to streamline method development;
3. Traditional solver baselines and reference solution acquisition;
4. Data generation for various distributions;
5. Problem and solution visualization tools;
6. Evaluators for multiple problem types;
7. Common post- processonn algorithms.
This toolkit enables the straightforward adaptation of our framework to new problems by inheriting base classes and adhering to the pre-defined project structure. The source code is publicly available https:://// gi t thub. com/ Thinklat SJTU/ CATU//LAC MML Kit- t. Based on this toolkit, we extend our framework design to CVRP and MIS problems, which include foundational classes for developing learning- based CVRP and MIS solvers. These frameworks currently implement several popular learning-bai based solvers and can be expanded to integrate additional methods using the same modular structure.
C.3 EMPIRICAL RESULTS
This subsection verifies the effectiveness of satisfying the discovered design principles in TSP to show the reference value of the ML4TSP analysis to other CO problems. Here, we verify the Capacitated Vehicle Routing Problem (VRP) and Maximum Independent Set (MIS) problems. Building upon the principles, we introduce novel designs seamlessly integrated into existing pipelines to boost solving performance and validate the effectiveness of adhering to these principles throughout the process.
20

---

Published as a conference paper at ICLR 2025
C.3.1 EXPERIMENTAL SETUP
CVRP Datasets. Following Ma et al. (2024), we samples with coordinates that are randomly uniformly distributed, demands that are random integers between and 9, and total capacity of 40 as our training and testing sets. The training size is 128000, with 100 training epochs. The testing set size is 10000, consistent with Ma et al. (2024). Note that when using neural networks for inference, the batch size is set to 100.
CVRP Metrics. We adopt three evaluation metrics to measure performance: 1) Length: the average total distance of the solved tours w.r.t. the corresponding instances; 2) Drop: the relative performance drop w.r.t. length compared to the nearly optimal solutions (obtained by the heuristic solver HGS (Vidal, 2022) in this paper): 3) Time: the average computational time per instance.
MIS Datasets. We use SATLIB2 as the dataset. Following Qiu et al. (2022); Sun & Yang (2023); Li al. (2023b), we use 39500 samples as the training set and 500 samples as the test set.
MIS Metrics. Following Qiu et al. (2022); Sun & Yang (2023); Li et al. (2023b), we adopt three evaluation metries measure model performance: 1) Size: the average size of the solutions w.r.t. the corresponding instances, i.c. the objective. 2) Drop: the relative performance drop w.r.t. size compared to the nearly optimal solutions (obtained by the heuristic solver KaMIS (Lamm et al., 2016) in this paper); 3) Time: the average computational time per instance.
C.3.2 JOINT PROBABILITY ESTIMATION HELPS CAPTURE VARIABLE CORRELATIONS
This subsection verifies whether the joint probability estimation property also benefits other CO problems. Here, adopt the MIS problem for evaluation. For MIS, the decision variable is the nodes in the given graph. In the learning functionality of node prediction, the SL. training objective generally enforces supervision over each node's 's binary classification results. This is based the assumption of mutual statistical independence of the individual solution parameters, such that the solution can be represented by product of Bernoulli distributions for the individual solution variables (Sanokowski et al., 2023). However, since the CO solutions are highly constrained with strong correlations among the solution variables, such an assumption can lead to a performance drop.
With GNN raw predictions, which correspond to n nodes, prior methods utilize the softmax operation over the last dimension to ensure that the probabilities of positive and negative edges sum up 1. The cross-entropy loss involves n nodes' binary classification, lacking general capture of joint probability over the solution variables. To this end, we propose relaxed probability normalization term achieved by LinSAT layer Wang et al. (2023), which projects the raw predicted probabilities to the constrained space, where the positive node probabilities within each node's ' adjacent node group to up less than the size of the adjacent group minus one. This is a largely relaxed constraint for the MIS problem, yet it provides the chance to connect among the node probabilities.
Under the node prediction functionality, we also include methods of solution distribution proximity objective into comparison, which considers a solution as the whole entity, allowing it to naturally adhere to the joint probability distribution. Table 10 shows the ablation. Methods with joint probability estimation generally achieve lower drops.
Table 10: Joint probability estimation ablation based on methods with Variable Prediction as the learning functionality for MIS
SATLIB
Objective
Joint Prob.
Solving Stage
Sizet
Drupā
Time
KaMIS (10s) (Lamm et al., 2016)
425.954
0.000
10s
SL
X
Greedy
421.692
1.004:10.5244
22.7ms
SL LinSAT Norm Generative
Greedy
422.098
0.907%10.473%
0.545s
Greody
424.496
0.394%0..29%%
1.101s
Phttps://www.r cs. ubc. http:///ww..eeeeeccaaarr////////
html
21

---

Published as a conference paper at ICLR 2025
C.3.3 SYMMETRY SOLUTION REPRESENTATION INTRODUCES EQUIVALENCE AWARENESS
Similar to TSP, CVRP tour holds symmetry or permutation invariance (Kwon et al., 2020). Since CO aims to produce optimal solutions, the neural model is expected to be aware of the equivalences among such sequences and should be optimized consistently yield the same solution regardless of the variances in forms. This subsection endeavors to introduce the symmetry solution representation attribute to methods lacking symmetry consideration within the framework, thereby enhancing problem-solving performance.
For the RL objective, methods decode solutions sequentially during optimization. To achieve symmetry, we refer to Kwon et al. (2020) optimize over diverse rollouts with multiple starting points as well as use symmetry baselines (Kim et al., 2022) for Sequential functionality, These techniques raise the model's ss awareness of symmetry. Table 1l presents solving results on CVRP-50, showing a notable performance gain by introducing symmetry.
Table 11: Symmetry ablation based on methods with RL as the training objective on CVRP.
Functionality
Symmetry
Sulving Stage
CVRP-50
Length
Dmop
Time
HGS (1s) (Vidal, 2022)
10.366
0.000=0.000%%
1.0s
Sequential
x
Greedy
11.138
7.479.2..553%
0.9ms
+ MultiStart
Greedy
10.605
1.305.11.14455
2.2mss
Sym. Baseline
Greedy
10.989
6.035.12.613%
0.9ms
Sequential
Sampling
11,201
8.093+3.1887%
0.9ms
+ MultiStart
Sampling
10.594
2. 2.195=1.1022
2.2ms
Sym. Baseline
Sampling
11.031
6.441=2.705%
0.9ms
C.3.4 ONLINE OPTIMIZATION COMPLEMENTS GENERALIZATION CAPABILITY
In order to bridge the gap between training for average performance and solving for performance in new instances, -pseiic optimization can be helpful. We verify the effectiveness of techniques that optimize in the testing phase in Sec. 3.2.1: the gradient search for methods with Generation as the functionality. Table 12 ablates learning- based search, indicating promising gain with learning-baad based search, however at the cost of additional computation.
Table 12: Ablation on online optimization property achieved by learning- search on MIS.
SATLIB
Functionality
Objective
Salving Stage
Size?
Dropl
Generation
Generative Generative
Greedy Gradient Scarch Greedy
424.496 425.006
1.101s 0.224+0.213%
0,34410.529%
2.380s
C.3.5 SEARCH FRIENDLINESS CONTRIBUTES TO LEARNING- LEARNING-SEARCH
SEARCH SYNERGY
Techniques that consider how to better integrate learning with search can benefit problem-solving This subsection verifies the effectiveness of search friendliness designs by promoting diversity in the predicted solutions (e.g. modeling solution distribution) and incorporating the search process into optimization (e.g. through meta learning to learn optimal initialization for solving stage). For the effectiveness of prediction diversity, Table 13 demonstrates the improvement in solving performance achieved by adopting meta learning and employing multiple sampling, which is contributed by increased diversity.
Table 13: Ablation on search friendliness property on MIS.
Functionality
Objective
Search Frnd.
Solving Stage
SATLIB
Size
Drop)
Time
Variable Prediction
RL
X
Sampling
408
4.104
27m34s
Variable Prediction
Meta e RI.
Sampling
410.596
3.607 1.607++28644
28m5s
Variable Prediction
Generative
X
Gready
424.496
0.344:00.29%
1.101s
Variable Prediction
Genenutive
Sx rredy
425.142
0.192-+0. 1989
5.324x
22

---

Published as a conference paper at ICLR 2025
D MINIMALISTIC CODE EXAMPLE FOR ML4TSP SOLVERS
D.1 TSPSOLVER
To accommodate diverse data types and facilitate the evaluation of solution quality, we provide TSPSolver base class that offers user-friendly approach for solving TSP. This class includes functionalities for data input and output, as well as an evaluation function. The solver supports different data imputs, such Numpy arrays and .DX7 and .rsp files. The outputs can be saved to corresponding types of files as needed. Additionally. the solver offers an evaluation function, by which users can quickly obtain the average tour length, average gap, and standard deviation of the test dataset. Below is an example of using TSPSolver to obtain the average tour length of the LKH test dataset, well its gap with standard deviation relative the Concorde test dataset.
>>> from ml4tsp import TSPSolver
Read the test file
>>> solver TSPSolver
>>> solver, fromm Sett_tttttttteeeeeeeeeeeeeeeeeee
Assign the ref_tour the tested solver as the solution path
>>> solver. rolver.read_toure (solver.rei_ttour)
Read the reference file
>>> solver.
(costs_avg, ref ref_costa_avge gap_avg, gap_std)
>>> wtt.ol/eer.ccllutttcccclllaaapae
(:6.548110417022276,, 16.545805334643322 0.0139392061675804 0.C28643127914336033
D.2 LEARNING-BASED SOLVERS
To enhance the modularization and cohesion within our proposed framework, we have extended the TSPSolver base class to support two highly integrated sorming-based solvers: ML4TSPNARSolver and RSoverr. These solvers can efficiently configure design choices be called to solve given instances. The following code snippet shows minimalistic code for TSP solving exemplified by solution proximity objective with greedy and MCTS as heuristic search:
from m14tsp import ve.
MI.TSSPAARENV
Create ML4TSPERV
>>> env MLATSPNAREIV
nodes_num-50n # the number of nodes aparse_factor=50 # KNN graph roprosentation
Create Solver
If "pretrained" is True and "pretraiiee__pahh is None, MI4TSP will automaticaily download the corresponding pre-trained file online.
>>> solver ML4TSPGNNSOLver
env-env, pocode_devilo==cccda,,
decoder="rardom",
decoder_kwargs--
(anbbrr_rwrrgg""aammlssee__ "samples_nnmt 50), Local_search= "m,ts",
23

---

Published as a conference paper at ICLR 2025
Loca_ limit" 1.0), scale-1,
pretrained-True,
Road data
>>> solver. from txt http::/www....aaa.o//o///////ott
Solve
>>> solver holver.solver solve (batch_size--
Encoding: 1008/---20 128/128 [00:05<00:00,
25.23it/s]
Encode Time: 9.426303148269653
Decoding: 100% ----| 128/128 [00:00<00:00, 650.48it/
Decode Time: 1. 1.578188419342041
Local Search: 1008 (008|----]] 6400/6400 [1:57:33<00:00,
1.10s/it]
Local Search Time: 7054.012353181839
Using the evaluate function obtain result
>>> solver. (ealuate Truu))
('6.59568398521005, 16.545805334443399, 0.30:42362569081776 c.15272430899596431)
Output and Save the soiution results
>>> solver.to_txt to_txt
txt")
D.3 TSPLKHSOLVER AND TSPCONCORDESOLVER
order to make the traditional C-based solvers, LKH and Concorde, more accessible to Python users, TSPLKHSolver and TSPConeordeSolver user-frice user-friendly interface that allows Python users to effectively utilize the powerful capabilities of LKH and Concorde for solving TSP. Here is simple example solved using the TSPLKHSolver:
built upon the TSPSolver framework, providing
>>> from m14tsp import DSPLXHSoLver
iikhmax_triall controls the maximum number of attempts in LKB 1kh_solver ISPLKHSolver (11h 1kh from_ettffroottx.. (Maaaa///mioooco//e////500.0.010
>>>
Usiin multi to speed the solution.
>>> 1kh_ solve (nun_ show_time-True
>>> ikh_solver to_txt (Mt htw.:///aaaaaooooooo/oo//////o/d
D.4 EVALUATE ON TSPLIB
We filter problems from the TSPLIB dataset with the number of nodes greater than or equal to 51 and less than equal to 1002, and with DOGE.WEIGHT.TYDD as EUC.2D. We then rescale the node coordinates to the range of 0 to globally. To facilitate future research endeavors on TSP, we use Concorde to precisely solve these problems and produce the corresponding text files. Furthermore,
24

---

Published as a conference paper at ICLR 2025
provide the ISPLIB4ML dataset, which can be used to quickly evaluate TSP solvers. In the experiments of this paper, we selected problems with the number of nodes ranging from 201 to 1002 as the test cases, and below is an illustrative evaluation example.
>>> from ml4tsp import :SPLIB4MEEvaluatorr MLATSPaNNSoLver
Create Evaluator >>> eval = TSPLIB:MEEaaluttor ()
Create Solver
env MLATSPNARENV (ar.aaaoooeappaaooaaaaaao-o--0
>>> solver XI4TSPGNNSoLver
env-env,
encode_devico=""ccaa""
decoder-"greedy"
Local_search="nctts,,,
evaluate
>>> eval. praluate Leci__oode_____e_ numm201, max modessodes_.. _00e_1022_
solved_costs
ref_costa
gaps
t&225
10.713846
10.553828
1.516214
tsp225
7.989420
7.895329
1.191729
pr226
5.290722
5.278835
0.225199
gi1262
12.054229
12.049518
0.039099
pr264
6.230572
6.200001
0,493082
a280
9.444607
9.238463
2.231368
pr299
6.730816
6.638419
1.391851
1in318
10.410730
10.169940
2.367660
rd400
15.408393
15.343968
0.419871
fL417
6.424722
6.285529
2.214497
pr439
9.492026
8.990802
3.574861
pcb442
13.469691
13.364091
0.790177
d493
9.474022
9.350242
1.323819
u574
12.127684
12.022998
0.870709
rat575
13.684484
13.619173
0.955546
p654
7.410115
7.195604
2,113133
d657
12.389867
12.211812
1,458056
u724
14.504233
14.436550
0.468836
rat/83
15.308325
15.246543
0.405221
pri002 002
704804
16.396624
1,879873
AVG
10.763168
10.624413
1,416140
E SUPPLEMENTARY EXpEriMENtAl RESULTS AND DISCUSSION
E. FULL RECOMPOSITION RESULTS
We show the full experimental results of learning and searching technique recomposition for ML4TSP solvers in Table 9, Recompositions that exactly correspond to prior methods are noted in the first column.
25

---

Published as a conference paper at ICLR 2025
E.2 GENERALIZATION TO VARYING DISTRIBUTIONS
Table 4 shows the generalization results of models trained on TSP-500 to varying distributions, e.g.. cluster (gaussian mixture), rotation, explosion etc., instead of uniform Zhou et al. (2023). We find that methods with more complex heuristic search methods and methods with online optimization designs may be less affected by distribution shifts. Meanwhile, different methods have their specialization on different data distributions, yet the ranking may not differ much due to their inherent powerfulness.
Table 14: Generalization results of models trained on TSP-500 to varying distributions, e.g., cluster (gaussian mixture), rotation, explosion etc., instead of uniform. The TSP data of different distributions are from Zhou et al. (2023).
Punctionality
Training Objective
Leurning
Construction
Impe. Seurch
Length
Drop
Greedy
TSP300 Clster
Geventton
Edge
Geserniie Symmeetr
Random (i-10)
Greedy
Twe-Apt
9.569
1,5005
0.617%
2.0166
Gevension
Genentive Symmeory
Gradien Search
8 Greidy
Twe-Opt
9.482
0.6295
10.563s
Edge Prod
SL Nods Norn
Greedy
MCTS
11.911
1,298%
1.245s
TSP500 Explosion
Generation
Fdge Prod
Generative Symmetry
St. Node Nam
Random (i=10)
Greedy
Two
MCTS
11.975
11.817
1815%
0.496%
11 11.677
0,857s
Gesention
Geserative Syumnetry
Grodiem Search
Greody
180026
Greedy Kandom (n=10)
TSP500-Rotation
Geenston
Edge
Symmetry
Greedy
Two-Dpt
12.472
1.299%
0.857s
11,833
Generation
SL + Symmeryy
Gradiemt Search
x Greedy
Two Opt
12.386
0.592%
17.844s
E.3 SUPPLEMENTARY RESULTS FOR FIG.
Fig. 3 serves as a supplementary figure to Fig. 2. providing the scatter plots for the correlation between solving performance and the learning loss across reference proximity objectives on TSP-50 sets.
Supervised Solution Proximity
Solution Distribution Proximity
Supervised Edge Regret Proximity
10
0.8
0.6
Drup (%)
0.4
Drop
0.05
0.10
0.15
0.0020 0,0000 0.0002 0.0034 0,0038 0,0000 Learning Loss
0.0000
0.0005
00010
Learning Loss
Learning Loss
Greedy
2rpp
Greedy+MCTS
Greedy+GLS
Figure 3: Correlation performance and learning loss across three reference proximity objectives on TSP50.
E.4 SUPPLEMENTARY RESULTS OF RUNTIME-DRE DROP CURVE.
Fig. shows the progress of solving within the heuristic search, showing the variation of the drop with respect to search time in the subsequent heuristic search conducted on predicted heatmaps.
E.5 SUPPLEMENTARY RESULTS FOR SEC. 4.3.4
To further illustrate the positive impact of prediction diversity on the solving performance, based on the solution distribution proximity objective, Fig. shows the effect of increasing the number of sampling in the estimated solution distribution during solving. As can be observed, with the diversity in neural predictions, the solving performance be improved through larger sampling number.
E.6 DISCUSSION OF UNSUPERVISED OBJECTIVES
In edge prediction learning functionality, although unsupervised loss provides seemingly reliable training objectives, observe that the effectiveness of these methods, including both unsupervised
26

---

Published as a conference paper at ICLR 2025
Greedy-Two-Opt
Greedy+MCTS
MCTS Solver
Drop (%)
1.0
1.5
Beam10 MCTS
Sampling10 MCTS
Drop
1.0
Random10 MCTS
0.5
Time
2
10
Time
Figure 4: Correlation of performance and runtime.
Search
Greedy
0.15
Greedy+2Opt
Drop (%)
0.10
0.05
10
Sampling Number
Figure 5: Correlation of performance and sampling number within the estimated distribution for the distribution proximity objective.
solving objective and reinforcement solving objective, relies heavily on heuristic search. Their performance often suffers when subjected naive construction methods like greedy decoding, with typical drops exceeding 10%. While reproducing these methods, we note that their original implementations heavily relied on the MCTS solver the search process, where their primary impact lies in providing overall guidance to MCTS. Therefore, incorporating alternative methods during the construction phase to introduce more diversity tends to yield better results. We observe that these methods perform better with Candom_MCTT and Bcam_MCTS. In particular, unsupervised solving objective relics on the Scattering Attention GNN (SAG) (Min et al., 2023) to take effect. Fig. 7 shows the effectiveness of SAG in producing sharper heatmaps, avoiding the over- smooth issue as observed in GCN. However, this SAG-learned heatmap still merely brings a greedy solving performance gain from 20% to 13%. Furthermore, the correlation between solving performance and learning loss within the framework of unsupervised training, as depicted in Fig. 6. However, it's disappointed find that decrease in learning loss did not result in an improvement in solving performance. Thus, it is crucial for edge prediction based unsupervised designs to develop more compatible heuristic search and pursue better integration.
verify that the
conducted an in-depth analysis of
E.7 DISCUSSION OF SUPERVISION QUALITY
We observe that the default setting of LKH3 (Helsgaun, 2017) does not generally produce the optimal solutions claimed by previous works (Qiu al., 2022; Sun & Yang, 2023). We experiment by adjusting the max_irials hyperparameter in LKH. We gradually increase it and observe that, for TSP-500, the solution quality continues improve even as we increase the number of trials from 10,000 to 50,000. In this paper, we utilize LKH3 as our source for supervised signals. We employ 500, 5000, and 50000 trials for 5SP-50, TSP-100, and TSP-500, respectively.
E.8 DISCUSSION OF MCTS
We make an intriguing observation investigating MCTS that the tour length before and after applying MCTS does not show straightforward proportional relationship. This observation serves as the
27

---

Published as a conference paper at ICLR 2025
TSF50 Unsupervised Solving Objective
TSP100 Unsupervised Solving Objective
12.5
10.0
Drop (%)
Drop (%)
10.0
7.5
7.5
5.0
5.0
2.5
2,5
12
14
16
18
20
20
25
30
35
Learning Loss
Learning Loss
Greedy
Greedy+2Opt
Greedy+MCTS
Figure 6: Correlation of performance and learning loss on the unsupervised solving objective.
0.000
3150
1120
0.06
40
00
0.04
3.75
3.50
5.000
(a) GCN learned heatmap
(b) SAG learned heatmap
Figure Edge heatmap prediction learned by different graph networks.
8.10
Randtom
13
NN
Beam
Ones
8.05
Sampling
Random
12
Your Langh After MCTS
8.00
Tour Length after
11
7.35
30
7.00
10
52
Tour Length Before NCTS
Tour Length Before MCTS
(a) Different decoding methods
(b) Different types of heatmap
Figure 8: Effects of different decoding methods and heatmap types on MCTS
motivation for us to investigate and develop a range of search methods rooted in MCTS, each incorporating distinct decoding strategies: Mondom_MCTS, Beam MCTS, and Sampling
Fig. (a) illustrates the variation in tour length before and after applying these different search methods. The experiments are conducted on the same TSP- instance utilizing the same heatmap generated by the model trained with solution proximity objective with node-wise normalization. Each method is sampled 100 times. Note Bean_MCTS, employing beam search the sampling strategy, achieves notably shorter average tour lengths before the heuristic search compared to the other two strategies. However, its performance after applying MCTS is found to be comparatively inferior
28

---

Published as a conference paper at ICLR 2025
to the other two strategies, as we consistently select the best result obtained from all the samples for each method. This finding aligns with the results presented in Table 9, where, with a sampling number of 50, Beam MCTS exhibits average drop of 0.013%, while the other two methods show drop of 0.003%, 0.002% respectively.
Furthermore, we investigate the impact of the predicted heatmaps on MCTS. Four types of heatmaps are examined: heatmaps generated by neural networks (NN), all-one heatmaps (Ones), random heatmaps (Random), and distance heatmaps (Distance). Fig. 8 (b) illustrates that the heatmap obtained from the neural network achieved the highest performance compared to the other types. This finding further confirms the significant role of machine learning in enhancing the MCTS method to solve TSP problems.
F SUPPLEMENTARY DETAILS OF INCORPORATED METHODS
F.1 TRAINING OBJECTIVES
Supervised Solution Proximity. In implementation, we adopt GCN for edge prediction, which receives the node coordinates as the input features and the output edge features would be further mapped by MIP to predict the probability of including this edge in the optimal solution. The weights of the weighted binary cross-entropy loss are given as wp- (n²-2n) and wi [2n)xx where c = 2 denotes the number of classes.
n²
Supervised Edge Regret Proximity. Using the same GCN+MLP network architecture, the model is trained with mean squared error loss to predict the regret associated with each edge. Due to the high computational complexity, obtaining the optimal solutions for calculating the corresponding regret is not tractable. Therefore, supervision signals are obtained through LKH3 (Helsgaun, 2017). The max .trials parameters for TSP-50 and 100 are set as 10 and 5, respectively. In this process, a global reference solution is computed, and the supervision for approximate regret is derived by fixing a particular edge and assessing the degradation in the reference solution caused by fixing that edge.
Solution Distribution Proximity. In this paper, we mainly implement the discrete diffusion mod- els (Sun& Yang, 2023; Li et al., 2023b) as the representative of generative model based solvers. Taking discrete diffusion models (Sun & Yang, 2023; Li et al., 2023b) as representation in this paper, which generates solutions S. E {0, 1)mXx by T-step denoising process from random noises Sy, and the latent variables include noised solution ST.7. For each entry, the model estimates Bernoulli distribution indicating whether this entry should be selected. In implementation, each entry of solution is represented by one-hot vector' such that So E {0, 1]=xxx2, Following the notations of Ho et al. (2020); Austin et al. (2021), the general framework of diffusion includes forward noising and reverse denoising Markov process. The noising process takes the initial solution So and progressively introduces noise to generate a sequence of latent variables S1.7. The denoising process is learned by the model, which starts from the final latent variable S7 and denoises S, at each time step to generate the preceding variables S based on the instance G, eventually recovering the target data distribution. The formulation of the denoising process is expressed as pe(So.r (G) = p(ST) pe (S,-1|S, G). The training optimization aims to align pe G))(G) with the data distribution G) using ELBO:
L -Eg
Σ DKL SS) po(St-1|Ss G)] - log pa S0. E>1
+
(6)
Specifically, the forward noising process is achieved by multiplying S, E [0, NxxN22 at step t with forward transition probability matrix Q [0, 1]22 where [Qu]i indicates the probability
B,
1- 3, (Austin et al., 2021), B,
of transforming E, in each entry to Ey. We set Q
1- 3.
where 3, E [0, 1] such that the transition matrix is doubly stochastic with strictly positive entries, ensuring that the stationary distribution uniform which is an unbiased prior for sampling. The noising process for each step and the t-step marginal are formulated as:
g S: Cat(Sr: p Q,) and (SS./So) Cat(S,; S.)
Faah entry with [0, indicates that it is included in S and [1, 0j indicates the opposite.
29

---

Published as a conference paper at ICLR 2025
where Cat(S:p) p) is categorical distribution over N one-hot variables with probabilities given by vector p and Q Q1 Q2 Qr- Through Bayes' theorem, the posterior can be achieved as:
1 Cat - S o SoQ
(S S. So)
(8)
(S.(Son)
SQQ.S
The neural network trained to predict the logits of the distribution Po(So)S,, G), such that the denoising process can be parameterized through q(St-1|S, So):
Po (S
Σ ((, (S.
So
Reinforcement Solving Objective. For edge prediction functionality, to calculate the gradient estimation by REINFORCE as presented in Eq. we follow Qiu al. (2022) to build the auxiliary distribution for TSP. Representing the solution as a permutation म, the auxiliary distribution can be formulated as:
exp(H
qa(m (x(T/)) = Σ n
q6 (T|mT = G.
Σ
II ao G)
II
E exp H 1
(10)
where H represents the estimated edge heatmap. With this auxiliary distribution, in each REIN- FORCE update, we sample 2,000 samples for TSP-50/100 and 120 samples for TSP-500 from qo (T]G) to estimate the gradients.
For the learning functionality of sequential node prediction, instead of establishing the per-step node heatmap from the estimated edge heatmap, sequence models decode each step's 's node heatmap sequentially. The attention based encoder-decoder model defines stochastic policy p(r[G) by modeling (T( Tr- G) each step. The encoder produces embeddings of all the nodes and the decoder takes the node embeddings, and context the current state as input, then it uses the attention mechanism to output the attention map the nodes. With visited nodes masked, the attention map over other unvisited nodes serves as the per-step node heatmap. The gradients are estimated by Eq. 4, where the auxiliary distribution is established upon node heatmaps.
The symmetric baseline on top of the sequential node prediction objective optimized with RL is implemented referring to Kim et al. (2022). The training objective leverages the symmetricities of CO by incorporating the regularization loss of invariant representation Lines the REINFORCE loss with solution symmetricity regularization C.s, and the REINFORCE loss with both solution and problem symmetricity regularization Cps. The final loss is written as Ciotel = Lps + aLinv + BL.s. Las regularizes the symmetric solutions to have the same objective values:
L.s - -E ( [[[T; G*]
K Σ K
(11)
VG,s
R( :G)
R(Te: G) log
where { /== are the solutions from (T Lps regularizes the problem symmetricity when two problems have identical optimal solution sets, which is obtained through rotation:
VL.. ~ Lps
-EQ'~ ((o())
[R(TT: G)]
K
L
(12)
[R( L.k G)
R(TLK Ge
LK
LK
where Q is the distribution of random orthogonal matrices, Q! is the thh sampled rotation matrix, and Lik is the 4tth sample solution of the 1th rotated problem. Livv regularizes the model to predict close hidden representations of symmetric problems:
MLP Line = Seas (MLP (ho(G)) MLP (he (Q(G)))
(13)
where Seos is the cosine similarity metric, hg is the neural feature projection, QGG) is the rotated problem, and MI. is projection head.
30

---

Published as a conference paper at ICLR 2025
F.2 LEARNING-BASER SEARCH
Gradient Search. Following T2T (Li et al., 2023b), the algorithm starts with an initial solution So and conducts several iterations to enhance the given solution. Each iteration involves adding certain degree of noise to disrupt the structure, denoising with objective gradient guidance to obtain lower-cost solution. The algorithm eventually reports solution with the lowest objective score. To introduce controlled degree disruption to the given solution, we employ SoQar to derive the distribution of the disrupted solution ((a) as N Bernoulli distributions, where a serves as a hyperparameter to control the degree of noise. Subsequently, the disrupted solution S. can be sampled from g(S.r\(p)) (So). From SaT, employ po [St, G, yy) to perform denoising, which aimed at recovering potentially lower-cost S.-
F.3 LOCAL SEARCH
TSP50
0,0225
0.20
Drop
0.0175
0.10
0.05
Time
0.00
0.000
0.005
0.010
0.015
0.020
0.025
0.030
Time
(a) TSP50
0.5
TSP100
2.0
1.5
Drop
0.3
Drop
0.2
0.01
0.02
Time
0.0
0.00
0.01
0.02
0.03
0.04
0.05
Time
(b) TSP100
2.0
TSP500
Drop (%)
1.5
Drop (%)
1.0
1.5
2.0
Time
4
(c) TSP500
Figure 9: The relationship between the solution quality and the search time of MCTS for different problem scales.
Two-Opt. For a TSP tour sequence #1...., Tp. Tp+1. .... Eg. Fg+1, suppose we select two nodes xp and 2g. and perform Twp-Opt operation by swapping the subsequence between them, the resulting path becomes Ii Pp: 2gy Ig-11... Ip+1, The difference between the path lengths before and after the swap is denoted reward Dpp+1 D Dpg D 1ttt, where Di. represents
31

---

Published as a conference paper at ICLR 2025
the distance between node i and node j. In each iteration, the two nodes that obtain the maximum reward are selected to perform the Twp-Opt operation. The iteration terminates when either no more improvements the maximum number of iterations has been reached. In the experiments of this paper, the maximum number of iterations was set to 5,000.
Monte Carlo Tree Search. In MCTS implementation, adopt the framework of the MCTS Solver (Fu et al., 2021) while refining certain design aspects.
The first improvement is the Two-Opt module. The MCTS Solver's Two-Opt strategy involves performing the swap immediately upon identifying a pair of nodes that can yield gain. In contrast, our approach aligns with the raw Two-Opt implementation, where select the optimal pair of nodes in each iteration.
The second aspect pertains our observation that the MCTS derived from the MCTS Solver underutilizes the allocated time slice. When a better solution cannot be found with the current random seed, the search terminates prematurely. Additionally, we discover that continuously replacing the random seed somewhat guides the search toward improved solutions, especially on large-scale problems like TSP500, where the gap of the model, which trains with solution proximity objective with node-wise normalization, is reduced from 0.900% to 0.578%.
Based on observation and improvement, we study the optimal search time for MCTS under different problem scales. We take the heatmap encoded by the GNN model and the tour obtained by greedy decoding of this heatmap as baseline for this investigation. The results are presented in Fig. Based on the results, we set the time limits for the MCTS on problems with 50, 100, and 500 nodes as 0.005, 0.020, and 1.000 seconds, respectively.
Note that although continuous search offers benefits for small-scale problems, the gains marginal when weighed against the extra time spent. Therefore, to improve the solving speed, we retain the original fixed random number scheme for the TSP50 and TSP100. However, for the TSP500 problem, we implement the optimized scheme to enhance efficiency.
G NETWORK ARCHITECTURE DETAILS
The network backbones include GNN variants like Graph Convolutional Networks (GCN) (Kipf & Welling, 2016; Joshi et al., 2019), Graph Attention Networks (GAT) (Veličković et al., 2017; Kool al., 2018), and Scattering Attention GNN (SAG) (Min et al., 2023). In the implementation of non- autoregressive methods, we employ GCN as the model backbone, while for autoregressive methods, use the transformer (Kool al., 2018) architecture serving as the essential network backbone. We ensure consistency in GCN and GAT implementations, including the number of layers and feature dimensions. In particular, for the unsupervised solving objectives for edge prediction, due to their reliance on the signal filtering capability of the SAG network, we utilize the SAG network in the implementation of this method, while again keeping its number of layers and feature dimensions consistent.
build the sequence model, with GAT
G.1 GRAPH CONVOLUTIONAL NETWORKS
Input Embedding Layer. Given node vector I E RRNx2 and weighted edge vector e E R", we compute the sinusoidal features of each input element respectively. The denoising timestep is optional, and it is required when using the diffusion model. Here, N denotes the number of nodes in the graph, and E denotes the number of edges, t E Ti,...,
i concat(ã.,o. Zt,1)
(14)
sin Tigj T
Fi.j Ta
Fig cos
Fi.j
Fi.j Ti.j
f..j concat
cos
sin
sin
COS
(15)
T
T
T
T
C;
Cj
C;
è concat
sin cos
sin
cos
sin
cOs
(16)
7
T
T
T
T
T
1
L
1
concat
sin
coS
sin
00S
sin
CO8
(17)
T
T
T
T
T
T
32

---

Published as a conference paper at ICLR 2025
where d is the embedding dimension, T is large number (usually selected as 10000), concat(-)
denotes concatenation.
Next, compute the input features of the graph convolution layer:
1; W
(18)
C, Whf
(19)
1 W?(ReLU(W?!)
(20)
where t R de is the time feature embedding dimension. Specifically, for TSP, the embedding input edge vector is weighted adjacency matrix, which represents the distance between different nodes, and e is computed above.
Graph Convolution Layer. Following Joshi et al. (2019), the cross-layer convolution operation is formulated as:
2 2 ReLU(BN(WW()) + Enly o Whas))
(21)
1+1 e + ReLU W E
(22)
a(ely)
(23)
where æ/ and clyy denote the node feature vector and edge feature vector layer 1, Wi,..., W5 Rhxh denote the model weights, n denotes the dense attention map. The convolution operation integrates the edge feature accommodate the significance of edges in routing problems.
For TSP, we aggregate the timestep feature with the edge convolutional feature and reformulate the update for edge features follows:
d+1 c'y + ReLU(BN(WL,, + Wha! + W + (ReL((P))
(24)
Output Layer. The prediction of the edge heatmap in TSP is follows:
Eij = Sottmex(porm((eLLlWWW
(25)
where L is the number of GCN layers and norm layer normalization.
G.2 GRAPH ATTENTION NETWORKS
Input Embedding Layer. Given node vector x E Nx2, we compute initial dimeimnnsi node embeddings h; (0) through learned linear projection with parameters W and 6": A. W" b
Attention Layer. Following Veličković et al. (2017); Kool et al. (2018), we denote with A the node embeddings produced by layer {I,..., })) and the attention layer operation is formulated as:
h BN' (n. (!-1) + (H (-1) ....,,h (...,,(-1))
(26)
h BN' + FF' h2)
(27)
where BN represents batch normalization, MHA denotes the multi-head attention layer, and FF refers the node-wise fully connected feed-forward layer.
G.3 SCATTERING ATTENTION GNN
Input Embedding Layer. Given node vector x E Nx2, we compute initial d, di-dimensional node embeddings HD through learned linear projection with parameters 4 and b": H = W" + ba
Diffusion Module. Following Min et al. (2023), the diffusion module consists a cascade of K N aggregation (or diffusion) layers with operations that are chosen for each node via attention
33

---

Published as a conference paper at ICLR 2025
Table 15: Design choices of existing major methods.
Method
Offinee Loatingg
Offine Solving
Paradign
Leunning Ftnciioaaity
Traniing Objectvv
Learning bated Search
Hearotic Search
Nonz
Orezay/ MC15
OCN etal.
Edge Prediction
Supersisel Solution Procuniy
None
DIMLS (Uis 2002)
Edge Prediction
Reieforcement
Objecthve
Greedy /Suplling MUTS
UTSP (Mis stal. 2003)
Eige Prodiction
sacupesiiae Selving Objeutive
Nenz
Bes-frw Lazal Lacal Seaech
GNNGUS (Hudon ctal. 2003)
1dge Regnet Preducion
Supervisdd lstge Regret Procinity
None
Guided Local Search
0
DIRLSCO (Sas & Yau,, 2023)
Soluiio Geacnuiio
Solation Distribuiin Prodinily
Nonz
Greeds Surgling MCTS
b)4)
Solation Commmation
Solation Desrihution Procinity
Gradiera Saarch
Gready Sampling METS
AM.Kost etal..
Socuential Prodiction
Reinfereement Solving Ohjeccive
Nonz
Sungling
/Sampling
2021b)
Sequential Node Prediction
Relaforcement Solring Objective
Cueedy
Sym NCO a10,
Sequential Node Prodiction
Relaforcemen Solring Objective
None
Greedy /Sumpling
mechanism. In each layer l, every node has access to node representations from a set of filters FF that contains a selection of low-pass and band-pas pass filters as follows:
Slowrr (H A" H'11
(28)
& (H/-1)- 1/ H'
(29)
where V E IR=x represents a wavelet (Wenkel et al., 2022) at scale 24
To assess the relevance of filter f to node data-driven scores sy (v) are computed. The variable H) represents the outcome of applying filter f to H'-1, These scores are determined using an attention mechanism, which can be defined as:
s (H) a'
(30)
where || denotes the concatenation operation and a' E Rdd denotes the attention vector.
Moreover, the scores are normalized across the filters using the softmax function, denoted as (v)(v) = (sytmaxx((((())) These normalized scores are stored in aty- Next, the node representations are updated through the following process:
Hago = EdoOH
(31)
FEF
where O is the element- wise multiplication (applied separately to each column of H3)
Output Layer. The formulas for the output layer as follows:
T= Softmax (Hagg))
(32)
where m² is the MLP: Rds -> Rdd where m' the MLP: Rd - RRd.. For the TSP problem, T represents the assignment matrix in the output, and subsequently, the edge heatmap will be obtained by TVTT.
H DISCUSSION FOR THE SYNERGY OF TRAINING AND SOLVING FOR CO
Recall that the solving process of traditional CO solvers primarily involves an online solving procedure based on manually designed heuristies, while the introduction of learning techniques has recently brought about paradigm shift in this field. In this section, we present the general formulation of CO and specifically TSP, well three paradigms for how existing CO solvers exploit machine learning, which serves as design guideline for our modular framework.
Pure Online Solving. This paradigm, as shown in Fig. 10 (a), typically comprises classic exact (Ap- plegate et al., 2006) and heuristic (Lin & Kernighan, 1973; Helsgaun, 2017; Fu et al., 2021; Silver et al., 2016) solvers, which operate a real-time manner without any prior offline learning phase. These solvers rely solely on the data received the fly according to some unknown distribution and do not leverage any pre-leamed knowledge or historical data. They make immediate decisions based on the features of the current problem instance and the objective is to minimize the objective cost for every encountered instance. This classic paradigm has been well-optimized and verified by the operation research community.
34

---

Published as a conference paper at ICLR 2025
Testing Data Gip
Online Solver o5
Solation - 0S(G.))
(a) Pure Online Solving
Training Dala [G,0]]
Receive
Offline Learning Algosithm
Predictive Model
Greedy Decoding
Testing Data Gz
Receive
Predictive Model
Predict
Preduction
Grdy(-)
H pulCir)
$ Grdy/H)
(b) Offline Learning for Direct Solving
Receive
Learn
Training Data (or
Offline Learning Algorithan
Predictive Model
Testing Data Gie
Receive
Predictive Model
Predict
Supporinng Prediction
pa(Cue)
Reveive
Receive
Online
Solve
Solution OS(G
(c) Offline Learning in Support of Online Solving
Figure 10: Solving paradigms for existing mainstream CO solvers. Blue and orange stand for offline and online processes, respectively.
However, instances in real-world applications are often from specific distribution with similar patterns and characteristics (Bengio et al., 2021), e.g. the scheduling of daily deliveries within particular region may exhibit commonalities. Since this paradigm learns nothing from the pre-existing data, the computation for each instance can be inefficiently repetitive when the data exhibits structural similarity.
Offline Learning for Direct Solving. In this paradigm as shown in Fig. 10 (b), the neural solver undergoes an offline learning phase where it learns from historical data before engaging in online solving. The offline learning algorithms produce predictive models that can directly predict solutions based on the given instance features. The primary goal is to learn the predictive models that produce solution predictions with the minimized average estimation eтror (for supervised learning) or average objective cost (for unsupervised learning) compared the optimal solutions.
However, following the classic machine learning mechanism, the neural network is optimized by minimizing the average objective score across the distribution of historical problem instances, diverging from the core target of CO of seeking optimal solutions for every newly encountered instance (Li et al., 2023b; Wang & Li, 2022). Without particular procedure of online search for the specific instance, the predictive model struggles to adapt quality solutions to newly encountered instances, and the typical local minima convergence limits further active search.
Offline Learning in Support of Online Solving. This paradigm, as shown in Fig. 10 (c), incorporates an offline learning phase that complements the online solving process. During the offline phase, the solver gathers insights from historical data, which are then leveraged to bolster and optimize the efficiency of the online groblem-solving procedures. The offline learning phase can provide valuable support to the online solver through various means, including solution initialization for online solving e.g. naive network prediction (Joshi et al., 2019; et al., 2021), solution distribution estimation e.g. generative modeling (Sun & Yang. 2023; Li et al., 2023b), and clues to searching for higher quality solutions e.g. regret estimation for local search (Hudson et al., 2022).
Overview. In general, offline learning data-driven process can serve as complement to the per-instance online solving process, such that the solver can excel in both efficiency in processing instances with similar structure and generalizing to every newly encountered instance with sufficient specialized search. Table 15 summarizes the current mainstream algorithms for the TSP problem and categorizes them into the above paradigms facilitate the follow-up detailed analysis.
35

---

Published as a conference paper at ICLR 2025
I EXPERIMENTAL DETAILS
All the experiments are performed on GPUs of NVIDIA RTX3090 and a CPU of AMD Ryzen Threadripper 3970X 32-Core Processor. All the test evaluations are performed on a single GPU.
I.1 IMPLEMENTATION AND HYPERPARAMETERS
Graph convolutional networks:
the dimension of the input features for implemented graph networks equals indicating the 2D coordinates of the nodes; the feature dimension of the intermediate layers is set as 256; The output channel dimensions of the networks are set as 2 for TSPGNN, TSPGNNWISE, and TSPDiffusion, and for TSPDIMES TSPGNN4REG and USTP.
Feature dimensions:
Number of layers: default be set as 12.
Sparse factor: for TSP500, in order reduce computational and GPU memory require- ments, the sparse factor is set as 50, which indicates that each node in the network only considers its nearest 50 nodes for computations. While for TSP50 and TSP100, sparse processing is typically not employed, hence their sparse factor is set as -1.
Graph attention networks:
Feature dimensions: the feature dimension of the intermediate layers is set as 128.
Number of layers: default be as
Number of heads: the number of heads for the attention is set 8.
Scattering attention GNN:
Feature dimensions: the feature dimension of the intermediate layers is set as 64.
Number of layers: default be set as 3.
Training objectives:
Solution distribution proximity: We implement the model with 50 inference steps for denoising, and the models are trained with 1000 denoising steps, i.c.. T = 1000. We additionally follow Sun & Yang (2023); Li al. (2023b) apply the technique of denoising diffusion implicit models (DDIMs) (Song et al., 2020) for accelerating inference and solution reconstruction.
Meta learning objective: The number of epochs for the inner optimization loop is set as 100, and the learning rate is 5e-2. The outer loop can be exactly viewed as the process of active search.
Unsupervised solving objective: The weights of the Hamiltonian cycle losses and the no self-loop constraints, i.e. A₁ and X2 in Eq. 3, are set as 10 and 0.1, respectively.
Learning-bee -baee search methods:
Gradient Search: ratio of noise adding in rewrite steps equals 0.4; the number of rewriting steps i.e. guided denoising steps is set as 5 for TSP-50 and 100, and 10 for TSP-500.
Active Search: as ss_ss is set as 100 and as_samlles is set as 1000.
Improved search methods:
Two-opt Search: The maximum number of iterations is set as 5000.
Guided LS: The maximum number of moves set as 100, and the maximum search time is limited to 10 seconds.
MCTS: The maximum search time is one-tenth of the total number of nodes, and the maximum search depth is 10.
36

---

Published as a conference paper at ICLR 2025
1.2 DETIALS OF EXPERIMENTS
Training Details. All models are trained with a cosine learning rate schedule starting from 2 x 10-4 and ending at O. For TSP-50, we generally use 1,280,000 random instances for training and train the models for 100 epochs. For TSP-100, we use 1,280,000 random instances and train the models for 50 epochs. We apply curriculum learning and initialize the models from TSP-50 checkpoints. For TSP-500, we use 128,000 random instances and train the models for 50 epochs. We also apply curriculum learning and initialize the models from TSP- 100 checkpoints.
Experimental Details of Fig. 2. To reflect the correlation between the solving performance and the offline learning quality, we show the scatter plots for the optimality drops with the corresponding learning objective values. During training, we equivalently sample 10 time points for recording and additionally sample the first 5 epochs for their importance as key representatives in the trends. The solid straight lines in the figures represent the fitted trend based the scatters.
Experimental Details of Fig. As the improvement-be -basee search continuously optimizes within the feasible solution space, we can output intermediate solutions any point to observe the trajectory of solution quality. our experiments, we set time slots for these improvement based algorithms to track the variation in solution quality at different running times. Given that 2-opt operates quite swiftly in practice, its descent process is rapid and almost appears as a straight line.
J LIMITATIONS AND BROADER IMPACTS
Limitations. The main limitation of this paper lies in the fact that our primary research revolves around ML4TSP and has not yet fully explored all other problems. While aim to provide insights into the entire 4CACO domain, on the other hand, we intend to thoroughly deconstruct the existing system to explore various aspects of the current major research. Therefore, we have chosen the widely studied and researched TSP problem for comprehensive decomposition and investigation. This also means that the workload of our work solely on ML4TSP already substantial. We believe that our exhaustive exploration of TSP could also provide valuable insights and reference points for the CO community. Moreover, the framework can be adapted to other CO problems, where the methods requiring reconstruction from scratch are primarily confined to problem-specife heuristic searches.
For the importance of studying ML4TSP and its reference value for other CO problems, we consider TSP as one of the most extensively studied CO problems with the richest learning and searching techniques, making this analysis representative for ML4CO. Note numerous papers like Fu et al. (2021); Min et al. (2023); Joshi et al. (2019); Hudson et al. (2022); da Costa et al. (2020) concentrate on TSP, and it also maintains its own surveys (Pop et al., 2023; Anbuudayasankar et al., 2014; Cheikhrouhou & Khoufi, 2021; Matai et al., 2010) and competitions like AI4TSP (Zhang et al., 2023), highlighting its significant importance. Meanwhile, any other NP problems can reduced to TSP in poly-time (since it is NP-hard) solve, and problems like VRP can directly be broken down to TSP (Luo et al., 2024).
Broader Impacts. The proposed principled and comprehensive framework for tackling combi- natorial optimization problems can address the lack of unification and offer guidance on crucial design principles for ML4TSP and can be generalized to ML4CO. The demonstrated advantages of specific techniques, along with the development of new solvers, are expected to inspire further research and innovation in the field. The strategic decoupling of existing methods and the unified modular framework that reproduces or even enhances the performance of existing methods can serve as the codebase and the methodology pool for further research and engineering practices. The paper's 's insights and observations underscore its potential to enhance the effectiveness of ML-based approaches solving complex optimization problems, ultimately benefiting various application domains that rely on combinatorial optimization.
37


Reviews:
[{"review_id": "gT1xOBlJfv", "reviewer": "Reviewer_7Hhi", "summary": "This paper explores machine learning-based methods for solving the Traveling Salesman Problem (TSP) and proposes a modular framework to streamline the design space of ML4TSP solvers. By systematically decomposing established learning-based TSP solvers, the authors develop a unified, modular approach that combines learning and search functionalities. This framework facilitates ablation studies, making it easier to assess the specific contributions of learning components and search strategies in current approaches. Key principles identified include joint probability estimation, symmetry solution representation, and online optimization, which enhance the efficiency and quality of ML4TSP solutions. The paper also proposes new combinations and enhancements to existing methods, improving performance and providing insights into optimal configurations for future ML-based combinatorial optimization research.", "questions": "Could the authors expand the comparison with traditional, non-ML solvers?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality: The paper presents a novel approach by developing a modular framework to dissect and streamline the design space of ML-based TSP solvers, which is a fresh and valuable perspective. \n\nQuality: The research is thorough, with a clear methodology that includes well-defined design principles, such as joint probability estimation, symmetry solution representation, and online optimization. The paper carefully analyzes these principles through comprehensive ablation studies, making the results robust and reliable. \n\nClarity: The paper is well-structured, with a clear and logical progression from problem background to framework design, implementation, and results. Each section explains the functionality and impact of various design components within the modular framework, making it easy for readers to follow. \n\nSignificance: The paper addresses a crucial gap in the field of ML for combinatorial optimization by providing a structured approach to analyze and optimize TSP solvers.", "weaknesses": "Lack of Theoretical Justification for Design Principles: While the paper empirically demonstrates the effectiveness of the proposed design principles (e.g., joint probability estimation and symmetry solution representation), it lacks a theoretical foundation to support it.\n\nLimited Exploration of Scalability: Although the framework is tested on TSP instances of varying sizes, there is limited discussion on its scalability to very large TSP instances or other complex combinatorial problems. \n\nLimited Generalization to Other Optimization Problems: Although the framework is designed with TSP in mind, the paper could benefit from explicitly discussing its adaptability to other combinatorial optimization problems (e.g., Vehicle Routing, Knapsack, or Job Scheduling).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "iSGhsZPeoy", "reviewer": "Reviewer_sguF", "summary": "This paper systematically explores the design space of machine learning-based approaches for the Traveling Salesman Problem (TSP) and introduces a unified framework for analyzing and enhancing these solutions. By decomposing existing methods into modular components of learning and search, the paper identifies key principles that improve solution quality, such as joint probability estimation, symmetry handling, and efficient exploration-exploitation strategies. Through a comprehensive set of ablation studies, the authors reveal the impact of each design choice and propose novel configurations that outperform current learning-based TSP solvers.", "questions": "In Tables 7 and 8, the results show that the best-performing configuration varies depending on the component and dataset combination. Could the authors clarify how these variations should be interpreted? Specifically, does this indicate that no single model consistently performs best across all scenarios, or are there insights into why certain components perform better with particular datasets? A clearer explanation here would help determine whether the findings suggest that different settings require tailored configurations rather than a universally optimal model.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The paper introduces a systematic framework for analyzing and enhancing ML-based TSP solvers by decomposing methods into modular components, offering new insights into the design space.\n\n- This paper shows extensive experimental study, thoroughly examining various component and dataset combinations and offering a comprehensive evaluation of the approach.\n\n- The implementation is well-structured, supporting straightforward development and extension for future research and engineering applications.\n\n- The paper is well-organized and clearly presents its findings.", "weaknesses": "- A primary concern is that the study’s conclusions are derived solely from experiments on the TSP, without sufficient exploration of their applicability to other routing problems or broader \bCO challenges. While TSP is a classic problem and valuable as a benchmark, part of its relevance comes from its potential to inform solutions for a variety of routing and CO problems via machine learning approaches. Given the extensive experiments conducted, the paper would be significantly strengthened by discussing how the findings and insights might generalize beyond TSP, suggesting implications or adaptations for other problem types. Without this, readers may question the broader utility of the proposed framework.\n\n- Another potential weakness is the study’s strict comparison of components based solely on optimality, without considering varying objectives that real-world applications may require. In some scenarios, the primary goal may be to find an optimal solution when sufficient time is available, while in other cases, the focus may be on obtaining a good approximate solution within a limited time frame. By focusing only on optimality, the comparisons risk being somewhat misleading, as certain components may be preferable in scenarios that prioritize speed or approximation quality over strict optimality. Acknowledging these different practical objectives and testing components under varying solution scenarios would give a more balanced and realistic view of each component’s strengths.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "pjE7tkHRH3", "reviewer": "Reviewer_i2ep", "summary": "This paper proposes a unified framework for learning-based approaches for the traveling salesman problem.  This paper identifies key algorithmic components of many recent ML4TSP algorithms, e.g., prediction, solution construction, and search.  \nThrough this lens, the authors propose a modular framework and implementation that streamlines the algorithmic choices for ML4TSP solvers.  The authors perform extensive numerical comparisons.", "questions": "**Questions**\n- How difficult is extending the existing library to other CO problems, i.e., VRP, or even CO problems not on graphs?  \n- Are there any methods in the ML4TSP space that do not fit into the implementation/view proposed?\n\n**Minor Remarks**\n- Some of the bolding in tables is missing or even incorrect, e.g., Table 6 has two different times bolded, which should not be the case.   In the final version of the paper, I would encourage the authors to review the tables/bolding carefully. \n- The length metric is not that useful.  Overall, it makes the tables harder to read.  At least in the main paper, I would encourage using a single metric to report solution quality, i.e., the gap to the best-known or reference solution.  \n- Some of the earlier papers on ML4TSP are not mentioned/discussed, i.e., [1,2,3]\n\n**References**\n\n[1] Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017.\n\n[2] Alex Nowak, Soledad Villar, Afonso S Bandeira, and Joan Bruna. A note on learning algorithms for\nquadratic assignment with graph neural networks. stat, 1050:22, 2017.\n\n[3] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in neural information\nprocessing systems, 28, 2015", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Overall, the paper is well-organized and easy to read.  One strength in this case is the reviewing, discussing, and modularizing of the related work and recent efforts on ML4TSP.\n- One significant contribution of this paper is the potential to lead to more streamlined and reproducible implementations of ML4TSP solvers.  \n- Extensive numerical comparisons.  As this paper is primarily computational, the authors extensively compare various algorithmic components in ML4TSP solvers and identify a few key elements that lead to reasonable quality solutions, i.e., MCTS.", "weaknesses": "- **Limitation in scope.** Perhaps the most significant weakness in the paper is the limitation in the scope of TSP.  Compared to other CO problems, e.g., the vehicle routing problem, TSP has more efficient specialized solvers, i.e., Concorde.  For this reason, the practical use case for a framework so specialized to TSP may not be impactful outside of studying the trade-off with learning-based methods. As such, one way to strengthen the contribution practically would be to expand beyond only TSP to include CO problems wherein state-of-the-art methods are not as scalable as those for TSP.  The authors do mention this as a limitation of the work.   Including more difficult CO problems with more complex structures would be much appreciated. \n- **Evaluation on \"Easy\" Instances.** Even the largest set of instances, i.e., TSP500, can be solved optimally in 18 seconds, with algorithms like LKH3 producing the same quality solutions in less than one second.  Given that the paper focuses explicitly on only TSP, evaluating more challenging instances would be helpful given the limitation in scope.  \n- **No Code to Review.** The authors mention that the code will be released upon submission.  However, given this paper is intended to give a modular view and implementation, the fact that no anonymized code is included in the submission makes reviewing the paper challenging.  For instance, based on the paper, it is impossible to tell how easy implementing other CO problems would be, or even other algorithmic components.   Assuming the implementation is well done, I would certainly be inclined to raise my score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "T40cXTZLjR", "reviewer": "Reviewer_Psci", "summary": "In this paper, a framework that puts the most meaningful works of ML for combinatorial optimization within a unified streamline is proposed. The aim is to provide a general view of the progress being made in the machine learning field for solving combinatorial optimization problems. The exercise is illustrated by taking as a case study the Travelling Salesperson Problem (TSP). Thanks to the unified view, the authors propose a series of modifications that permit the improvement of the performance of existing approaches.", "questions": "Any progress in the weaknesses noted above would be positive for the paper. In addition, I have some questions related:\n\nQ1. Being aware that at this stage it is difficult to add a new problem to the approach that is being taken... could the authors extend the work in this direction? If the authors can do this, I am willing to reconsider the score assigned.\n\nQ2. In Section 2, the authors state that the objective function is a function $f(\\cdot, G):\\{0,1\\}^N \\rightarrow \\mathbb{R}_{\\geq 0}$. However, the authors have also stated that $\\Omega$ denotes the feasible set of solutions, so I understand that f should be as follows: $f(\\cdot, G): \\Omega \\rightarrow \\mathbb{R}_{\\geq 0}$. Otherwise, I do not think it makes sense to map unfeasible solutions with the objective function. Please address this point.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. Giving a general view of the works done in the area is interesting, especially if connections between the different works are made, as is the case.\n\nS2.The paper is well written, although at times it becomes heavy to read—especially the abstract and the introduction. Later on, however, it becomes more readable.\n\nS3. Authors have proposed improvements for existing algorithms in the different stages of the streamlining, and they resulted in effective. This is a positive aspect since the paper is not merely a review of existing algorithms. In my opinion, this has value.", "weaknesses": "W1. The main problem of this paper is its case study. In my opinion, the ML field has gone too far optimizing the TSP and leaving aside other combinatorial problems. It seems that if you don't do the TSP your work is worthless, and curiously, the worthless one is the TSP, since real problems that resemble the TSP are minimal. Not so the VPR (among many others) which has almost direct applications. At the beginning of the abstract, it is made explicit that the TSP is used as a concrete case study, and it is suggested that this method that has been carried out is much more general. However, throughout the paper, no mention is made of any other problem, nor in the future work. Seen in this light, this paper looks like one more iteration of a loop that has been proposing ML models for TSP for years, increasingly better, but also increasingly isolated from real-world problems. \n\nW2. At the beginning of section 2, the authors gave the notation for CO problems, but I got confused. But I am not clear what the authors mean - do you mean that you focus on combinatorics problems that can be represented as graphs, or do you mean that all combinatorics problems can be represented as graphs? The former would make sense to me, although you should be more precise, which opens another door, and that is... What about those that are not graphs? The second of the options I am not sure, but I would say that at least naturally not all problems can be represented as graphs.\n\nW3. It almost goes unnoticed, but it should be noted that the reference solutions used have been obtained with LKH-3, a heuristic algorithm (if I am not mistaken), so we do not know the real solutions. At this point, the best thing to do would have been to use solvers. In the case of the TSP, Concorde is capable of arriving at optimal solutions for instances with thousands of cities. Moreover, in this line, it is also obvious that the ML models being developed for CO lag behind metaheuristic algorithms in terms of performance and execution time (if we take into account the training time). I understand that it is not the purpose of the authors to pretend to obtain SOTA results in this paper, but systematically obviating a whole family of algorithms that a priori is better than ML is not a good behavior. I think that incorporating metaheuristic algorithms as a reference would help to have a clearer view of the performance of the analyzed models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)