Purity Law for Neural Routing Problem Solvers with Enhanced Generalizability
Authors: Wenzhao Liu
Haoran Li
Congying Han
Zicheng Zhang
Anqi Li
Tiande Guo
Venue: NeurIPS 2025 poster ()
Keywords: Routing Problem
Generalization
Universal Structural Principle
Policy Optimization
Primary area: optimization

Abstract: Achieving generalization in neural approaches across different scales and distributions remains a significant challenge for routing problems. A key obstacle is that neural networks often fail to learn robust principles for identifying universal patterns and deriving optimal solutions from diverse instances. In this paper, we first uncover Purity Law, a fundamental structural principle for optimal solutions of routing problems, defining that edge prevalence grows exponentially with the sparsity of surrounding vertices. Statistically and theoretically validated across diverse instances, Purity Law reveals a consistent bias toward local sparsity in global optima. Building on this insight, we propose Purity Policy Optimization (PUPO), a novel training paradigm that explicitly aligns characteristics of neural solutions with Purity Law during the solution construction process to enhance generalization. Extensive experiments demonstrate that PUPO can be seamlessly integrated with popular neural solvers, significantly enhancing their generalization performance without incurring additional computational overhead during inference.

Purity Law for Neural Routing Problem Solvers with Enhanced Generalizability
Wenzhao Liu'
Haoran Li!
Congying Han
Zicheng Zhang?
Anqi Li
Tiande Guo
School of Mathematical Sciences, University of Chinese Academy of Sciences JJD.com
School of Mathematical Sciences, Nankai University
{1 (1iuwenzhao22, 1aroo2,,,,ihhcae 1ihaoran2211 (aaimn22@mmaalll. @mails.l......a..aa....am. Cmmails.uaasee....... www.ucc..aa.. ac. cn, hancyducas... acc..ccss.c..................... ac cn zhangzicheng600 com, anqili@nankai. edu. en, tdguolucas.
Abstract
Achieving generalization in neural approaches across different scales and distri- butions remains significant challenge for routing problems. A key obstacle is that neural networks often fail to learn robust principles for identifying universal patterns and deriving optimal solutions from diverse instances. In this paper, we first uncover Purity Law, a fundamental structural principle for optimal solutions of routing problems, defining that edge prevalence grows exponentially with the sparsity of surrounding vertices. Statistically and theoretically validated across di- instances, Purity Law reveals consistent bias toward local sparsity in global optima. Building on this insight, we propose Purity Policy Optimization (PUPO), novel training paradigm that explicitly aligns characteristics of neural solutions with Purity Law during the solution construction process to enhance generalization. Extensive experiments demonstrate that PUPO be seamlessly integrated with popular neural solvers, significantly enhancing their generalization performance without incurring additional computational overhead during inference. The code is available at httpt:://// /tttps://githut github.......ie com/Ke] Kejun0677/PUPO
Introduction
Routing problems, such as Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP), are fundamental combinatorial optimization (CO) problems with broad applications operations
research and computer science fields, including scheduling [8 B] circuit compilation [6] 9. and
computational biology [25] [5). Due to their NP-hard nature, even the most advanced exact solver [2] could not efficiently find the optimal solution for large-scale instances within reasonable time frame. As result, approximate heuristic algorithms, such as LKH3 [66] 17] and HGS 42), have been developed to find near-optima with improved efficiency. However, these approaches still face significant computational overhead owing to their iterative search processes for each instance.
Deep learning, particularly deep reinforcement learning, holds significant promise for developing fast and advanced neural routing problem heuristics. Learning-basee approaches generally fall into two categories: methods that learn to construct solutions step by step 44 24 26 18], and learn to search for better solutions iteratively 30 7 [T] Among these, neural constructive methods excel in faster inference and higher performance, enabling real-time applications. However, they often struggle with generalization and exhibit limited performance on large-scale or heterogeneous instances.
"Corresoondng author: hancy @ ucas.ac.cn
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

The primary challenge behind this weak generalizability lies in the tendency of neural models to overfit to specific patterns tied to particular training settings. To address this, some approaches have focused on simplifying the decision space, such as restricting the feasible action set [10] [2] and employing -nncnu-and-oo strategies |2|(37 [.] While these methods improve the performance, they inherently reduce the potential optimality of the solutions. More importantly, they lack guidance from the universal structural properties of routing problems, which prevents neural solvers from directly learning consistent and applicable patterns across various instances during training.
In this paper, we first explore generalizable structural patterns in routing problems, then leverage them to guide the learning process of neural solvers. To begin with, we define edge purity order as a measure of vertex density around edges, where sparser neighborhoods yield lower purity orders. We reveal Purity Law, fundamental principle for routing problems stating: the proportion of different edges in the optimal solution follows negative exponential law based on their purity orders across various instances. This indicates that edges with lower purity orders are more prevalent in optimal solutions, with their frequency increasing exponentially as the order decreases. Purity Law demonstrates its potential to capture universal structural information in two key ways. First, it is ubiquitously present in optimal solutions in various instances, underscoring its strong connection to optimality. Second, the parameters of its negative exponential model remain statistically invariant across varying instance scales and distributions, proving that the sparsity-driver edge dominance law is intrinsic rather than data- sataa-peciific.
Based on the universal presence of Purity Law, we propose PUrity Policy Optimization (PUPO), a novel training framework that incorporates this generalizable structural information into the policy optimization process. PUPO guides the solution construction process by encouraging the emergence of Purity Law. Specifically, it modifies the policy gradient to balance the purity metrics of solutions at different decision stages. By aligning with Purity Law, PUPO helps models learn consistent patterns independent of specific instances, thereby improving their ability to generalize to different distributions and scales, without altering the underlying network architecture. Notably, PUPO can be easily integrated with a wide range of existing neural solvers. Extensive experiments show that PUPO significantly enhances the generalization ability of these solvers, without increasing computational overhead during inference. Our contributions include:
Law as a fundamental principle that reliably characterizes optima across various instances, offering a novel perspective to comprehend common structural patterns in routing problems.
We identify Purity
We propose PUPO, novel training approach that explicitly encourages alignment with Purity Law during the solution construction process, helping models to learn consistent patterns across instances.
We demonstrate through extensive experiments that PUPO can be seamlessly integrated with popu- lar neural routing problem solvers considerably improve their generalization, without increasing computational cost during inference.
2 Related Work
According to the way the solutions are generated, neural approaches can488 generally be divided into two classes: learning to directly construct and learning to iteratively improve solutions. Discussions on classical neural solvers are provided in Appendix [A] Traditional Neural methods often struggle
with poor generalization 19) Recently, some works have attempted to improve the generalizability of
neural routing problem solvers. UTSP [35] applies unsupervised learning by leveraging permutation properties of TSP; but fails to scale to instances larger than 2000 vertices. HTSP [37 improves efficiency for large-scale TSP by employing hierarchical reinforcement learning. LEHD 3T and
GL.PP 45 continuously refine solutions through divide-and--ooquerr strategies via neural models.
Following local reconstruction, SIL [32) proposes self-improved training, utilizing the pscudo-labels of previous partial solutions, which boosting the scalability of NCO methods. INVIT [10] simplify the decision space by restricting actions to local neighborhoods, nested view transformer, to improve generalization. ELG [12] ensembles a global policy and local policies, whose outputs are aggregated with a pre-fixee rule. The local policies also utilizing k- nearest neighbors to promote cross-size generalizability. More detailed discussions are provided in Appendix A However, these approaches inherently trade off the optimality of solutions in favor of generalization. Despite progress, no research has explored universal structural principles of routing problems to guide neural learning, leaving the challenge of identifying consistent instance patterns unsolved.
well enforcing the invariant
2

---

3 Preliminary
3.1 Routing Problems
In this paper. we focus on the Euclidean routing problems in two-dimensional space. Given instance, let G = (x,E) represents an undirected graph, X = {a;|1 I i i | is the vertex set, and 3 = {Ci (Iz, [;) S i,j S [X]} is the edge set, where |. is the number of vertices. In the Euclidean routing problems, G is fully connected and symmetric, with each vertex 2; E X represented by coordinate (x).=;) scaled to the unit square [0, 1]. Each edge Cij & is assigned a visit cost o(T,, 2ty), typically the Euclidean distance between the vertices I; and æj. A feasible solution (TI, . TN) ) is index sequence of length N that satisfies all the constraints. The objective is to find the optimal one with the minimum total cost among all feasible solutions, where the total cost of T is formulated as follows:
((T) c(ETN Fnn) E c(T 1...))
The constraints vary according specific routing problems. For example, in TSP, the constraint is that feasible solutions are Hamiltonian cycles which visit each vertex exactly once. In CVRP, each vertex z; has demand d; to fulfill, and depot node Zg is introduced for the vehicle to replenish when it rums out of its capacity. The vehicle is constrained to visit vertices except depot strictly once while not exceeding capacity limit.
3.2 Policy Learning for Routing Problems
Policy learning is the dominant paradigm in deep reinforcement learning for solving routing problems. Given an instance X, a feasible solution t is autoregressively generated through the neural policy:
po(T x)) (a x) II (T
(2)
where 0 are the parameters of the policy network, trained by minimizing the expected total cost:
C( X') EE (o [))
REINFORCE 44 is the cornerstone of policy-based reinforcement learning methods, which com- putes the gradient (()))) in the context of routing problems as the following:
(I(T) b(x)) Σ Vlog (1lgp1(1)1
Epo(r|a))
(4)
where b(X)) baseline for variance reduction.
Purity Patterns for Generalization
In this section, we first explore the structural patterns closely tied generalization in optimal solutions of routing problems. We observe that edges surrounded by sparse vertices consistently prevail across different instances. To capture this relationship, we propose the concept of purity order, which quantifies the density of vertices around an edge. Based on this, we uncover the Purity Law, an empirical phenomenon that reveals a universal structural principle optimal solutions of routing problems.
4.1 Purity Order in Routing Problems
We first introduce the concept of purity order to formulate the vertex density around each edge. Definition 4.1 (Purity Order). The covering set Ne and purity order Kp of an edge Cij = (Ix 2,)) defined as:
No(ew) = E (x; - (x, - < 0}. x)
(5a)
Kp(ew) = Kp(zn,2)) = [No(et))).
(5b)
3

---

kp(4,))) =0
e2
R (x,x,)
e1
X1
Figure 1: Example of edge purity orders with the same length.
Geometrically, the covering set an edge corresponds to the vertices lying within a circle, whose diameter is defined by this edge, and the purity order is the cardinality of this set. It is not difficult to obtain that the computational complexity required to calculate the purity order for all nodes is ((121)). The purity order reflect the local density of vertices surrounding edge. A lower purity order indicates a more sparse and "pure" configuration of vertices around the edge. For convenience, refer to edge with purity order k k-order pure edge.
Additionally, we investigate the topological properties of O-order pure edges with the lowest redun- dancy (details and proofs shown in Appendix [B. Specifically, we establish the existence of O-order pure neighbors for any vertex, laying the groundwork for our optimization paradigm. We then prove the connectivity of the subgraph formed by O-order pure edges, indicating that these edges capture global structural properties. Furthermore, we demonstrate that the polyhedron formed by the 0-order pure neighbors of any vertex is convex, highlighting its structural integrity and stability. This insight suggests the potential for efficient computational methods. We also design the purity order for
non-Euclidean problems, which can be referred to Appendix C
Intuitive Example Analysis. Measuring vertex redundancy around an edge, purity order can also capture topological information beyond edge length. Even among edges of equal length, those with lower purity orders typically exhibit more favorable structural properties. As shown in Fig. [ consider two edges, él and e2, formed with vertices and 22 from vertex Despite of the same length, their purity orders are 4 and O, respectively. The edge ei passes through a denser region of vertices, which negatively affects the subsequent connections, making it harder to form cohesive structure. In contrast, 62, surrounded by sparser vertices, has minimal negative impact on the underlying connectivity of others, suggesting more conducive to well-structured solution. These observations suggest that solutions with more lower-order pure edges may have a greater potential for optimality.
4.2 Purity Law in Optimal Solutions of Routing Problems
We quantitatively investigate the distribution of purity orders optimal solutions across various instance scales and distributions, leading to the concept of the Purity Law.
Purity Law
The distribution of edges in optimal solutions follows a negative exponential law based on their purity orders across various instances.
To validate the Purity Law, we conduct extensive statistical experiments instances with varying scales and distributions. The following discussions focus on TSP, while the Purity Law also exists in CVRP despite more constraints, with verification and analysis presented in Append. D Specifically, we create datasets from 84 instance types with scales ranging from 20 to 1000, sampled from four classical distributions. The corresponding optimal solutions are computed using the LKH3 algorithm [7 A detailed description the dataset is provided Append.
For each instance type, we calculate the purity order of every edge in the optimal solution and then statistic the proportion y of edges with given purity order k. which is defined as:
v(k) Entooeer I(Kp(Ti k) k 10
2].
(6)
N

---

Pulb
Expledoo
Impleson
Figure 2: Purity Law curves under varying scales and distributions.
23
Meas dee
Properier booder of Eare
Mean Ou ded of Pare Edges
kmn
Cluszedd
825
Explosis
52
2200
Figure 3:
Mean purity order, proportion of 0-order pure edges, and average order of non-O-order pure edges for varying instance.
where N the length of solution, 75)) is the edge the optimal solution r", and T(-) is the indicator function. Next, we fit the proportions to negative exponential function:
yog 33k + loga,
and present statisties of fitted parameters a, 8, and fitting errors in Table 7 of Appendix FF And all detailed fitting results for each instance type are also available in Appendix F The remarkably low mean and variance of fitting errors statistically underscore that the negative exponential law reliably and universally applies across different instance scales and distributions.
The negative exponential relationship reveals that purity orders of edges and their proportions in the optimal solution decrease exponentially, confirming our earlier comprehension. To better understand the decay rate, we visualize the fitted curves for different instance types in Fig. 2 where we plot the logarithm of y for clarity. seen in Fig. the coefficient a is invariant for both scales and distributions, with different curves nearly overlapping at the vertical axis intersection. The decay rate slightly increases with instance scale, indicating that, for larger-scale instances, the proportion of each purity order decreases more rapidly.
Theorem 4.2. For edge ezp assume that K (e(ez)) evenly distributed both sides of exyy and the probability of each node being selected follows uniform distribution. Then, the probability of ewy being at the optimal solution holds the following inequality:
an positive even number, 2, E Ne(Cog)
k!!
Plezy E TOPT]
2 2.4 + 1)!!
For the random Euclidean routing problem, theoretically prove that under certain conditions, there is an upper bound about the probability an edge with purity order & being at the optimal solution, which is shown in Theorem 4.2 The proof of Theorem 4.2 can be referred Appendix G Notably, this upper bound decreases monotonically with increasing k. This means that edges of higher purity order have lower probability of forming the optimal solution, consistent with findings. Furthermore, the negative exponential form of this upper bound indirectly confirms the purity law we propose.
4.3 Consistent Dominance of Lowest-order Pure Edges
The rapid decay of the negative exponential function ensures that edges with lower purity orders dominate the optimal solution, while edges with higher purity orders are seldom present. To concretely
5

---

illustrate this property, we calculate the mean purity order, the proportion of O-order pure edges, and the average order of non-O-order pure edges in optimal solutions for each instance type. The results, shown in Fig. highlight the consistent dominance of O-order pure edges.
The variations in these metries exhibit a steady trend across different instance scales and distributions, further reinforcing the universality and stability of the Purity Law. The mean purity order stabilizes around 0.1, indicating that the optimal tours consistently maintain quite low level of overall purity order. Furthermore, the proportion of O-order pure edges consistently stays around 92%, reflecting their dominant presence in optimal solutions. This proportion also aligns with the fitting parameter a. For -on-O-order pure edges, which have minimal purity order of 1, the mean purity order remains around 1.15. This suggests that, even among non-O-order pure edges, low-order pure edges are predominant, with higher-order pure edges being quite rare. Notably, all these proportions remain nearly invariant when the instance scale exceeds 300, underscoring the remarkable and dominant consistency of low-order pure edges. These quantitative characteristics indicate that, compare with the well-known k-nearest prior, Purity Law can reflect additional structural information. Further discussions connection with k-nearest prior are available in Appendix H
5 Policy Learning Inspired by Purity Patterns
In standard neural learning for routing problems, the total cost, as defined in Eq. (4). typically the only objective for policy optimization. However, relying solely on this reward signal, neural networks often fail to capture inherent structural patterns present across different instances. Despite efforts to modify the architecture of policy networks and learning modules in previous research, the absence of guidance from generalizable structural principles, limits effective learning of universal patterns, resulting in poor generalization. Fortunately, the widespread and stable presence of purity patterns in optima presents a promising avenue for improving generalization. Motivated by this, we introduce two key concepts-puid purity availability and purity cost-to characterize purity patterns for neural learning. By incorporating these into the policy training, we propose PUrity Policy Optimization (PUPO) to encourage alignment with the Purity Law, enhancing generalization in neural solvers.
5.1 Purity Availability and Purity Cost
In the Markov model of routing problems, the state time consists of the unvisited vertex set U4, and the current partial solution T which includes the visited vertex set Vz. The action corresponds to the vertex Tr selected for the next visit.
Definition 5.1 (Purity Availability).
The purity availability d()) of the unvisited vertex set Ue is defined as the average minimum available purity order, given by:
((U)) Ex,e4 mina,euus Eliisi K (1)))
1stsN.
(9)
[e
The purity availability ((4)) measures the potential purity order of future edges that can be formed by the unvisited vertices. We demonstrate that the & is supermodular, meaning the absolute value of marginal gain in purity availability diminishes as the set Ue increases. The proof in Appendix !
Proposition 5.2 (Supermodularity of Purity Availability). The set function Φ 2 + R. defined on subsets of the finite set X, supermodular. Specifically, for any subsets A B C and any vertex E X B, the following holds:
$(Au (x}) +(A) s o(B U (z)) 6BB).
(10)
This indicates that, as the solution construction progresses, the absolute value of marginal improve- ment in purity availability becomes more significant on smaller unvisited sets. Definition 5.3 (Purity Cost). The purity cost C(U,, T for selecting an action T++1 time t is defined as:
(TT + +(U--) - ((2{), for t < N,, for t = N.
(11)
TT),
The purity cost C(ui, T141) includes both the purity order of the new edge formed by 7. and T and the difference in purity availability before and after the action T++1- This formulation captures

---

both the contribution of action T--1 to the purity order of the current partial solution and its impact on the purity potential of the remaining unvisited vertices.
5.2 Policy Optimization with Purity Weightings
To improve generalization, we integrate purity costs into policy optimization process, aligning model with the Purity Law. This encourages the learning of structural patterns that are consistent across varying instances. To assess the potential of the current state-action pair fostering a low-purity structure for future solution construction, we introduce the purity weighting based on purity costs.
Definition 5.4 (Purity Weightings). Let d be a discount factor. The purity weighting W W(,; Te+1) is defined as:
N Σ TH1,
W(U, T+1) = 7+1)
(12)
J=
Building on this characterization, we propose the purity policy gradient V (O)) as follow:
Epp(rp (L(T) - b(x1) Σ
(13)
The complete description of the PUPO framework is presented in Appendix And we also provide an theoretical analysis on optimization error of PUPO in Appendix K PUPO establishes upon the REINFORCE algorithm with POMO baseline, incorporating generalizable purity patterns into the modified policy gradient. At each stage of the solution construction, PUPO employs a discounted purity cost that reflects the purity potential of both the current partial solution and the unvisited vertex set, encouraging the model to favor actions with lower purity orders during training. This approach helps the model to learn consistent, cross-instance patterns that align with the Purity Law, thereby enhancing its generalization capability. Notably, PUPO is flexible and can be integrated with various popular constructive neural solvers, without any alterations the network architecture. Further discussion on the derivation process and explanation of PUPO are provided in Appendix L
6 Numerical Experiments
To validate the effect of PUPO on enhancing generalization, we compare the performance of both vanilla policy optimization and PUPO across several state-of-the constructive neural solvers. Additionally, we conduct a comprehensive evaluation of generalization performance and purity metrics on well-known public datasets.
6.1 Experimental Setups
Dataset. To ensure the adequacy of the experiments, we validate the model's performance on two categories of datasets. The randomly generated dataset used in this paper is the same that in INViT 10]. which is widely adopted to testify existing DRL. approach. The real-world dataset we used is More details about dataset we used are presented in Appendix N
TSPLIB 39 and CVRPLIB 40
Comparison Methods. Although PUPO can be integrated with any DRL-based neural constructive model, we select four representative SOTA methods with high recognition for experiments. This section mainly present the results on two latest and advanced neural solvers ELG [2] and INVIT [00] We also conduct experiments on two classical neural solvers POMO 26 and PF (18), whose results can be seen in Appendix M For each method, we conduct training on scales of 50 and 100.
We report three widely adopted performance metrics to evaluate the general- izability each comparison method, including the average total cost of solutions, the average gap to the optimal solutions, and the average solving time. The gap characterizes the relative difference between the output solution of neural models and the optimal solution, which calculated as the following:
Evaluation Metrics.
gap = modell - (pT
x 100%
(14)
L(Topt)
7

---

We also present three metrics to reflect the ability of the model to perceive purity information: the average purity order (APO (all) for short). the proportion of O-order pure edges (Prop-O (%) for short), and the average order of non-O-order pure edges (APO (non-0) for short) for each solution.
Experimental Settings. All the numerical experiments are implemented RTX 3090 GPU with 24 GB of memory, paired with a 12th Gen Intel(R) Core(TM) 19-12900 CPU. We train each model using the vanilla method and PUPO, respectively. In each training paradigm, we use the original network architectures and hyper-parameters provided in the source code, without any modifications to modules. Due to the different magnitude the policy gradient between the two, we only adjust the learning rates during PUPO. Details about the learning rates of each model are available in Appendix O All models are trained on random instances from a uniform distribution.
NVIDIA GeForce
6.2 Generalization Performance Analysis
Table 1: The experimental results of average gap (%) on the randomly generated TSP dataset with different distributions and scales after training each model using both the vanilla and PUPO methods, where means out of memory, bold formatting represents superior results, Blue highlights the relative decrease ratio (%) in the gap, while Red indicates its relative increase ratio (%).
BLG-30
BLG 100
INVIT-50
INVIT-1ON 100
Instance
Vanila
PUFO
Vanilla
PUPO
Vanilla
PUPO
Vanilla
PUFO
U-100
6.60
7.10
7.662
5.86
6.39
19.13
2.14
2.17
2.61
2.35
9.92
U-1000
20.81
19.47
166.0
17.95
17.49
2.58
7.27
7.17
.1.43
7.41
6.26
15.45
U-5000
31.50
26.84
14.78
29.22
23.77
18.66
9.41
9.09
13.37
9.39
8.05
14.25
U-10000
7,89
7.63
3.39
7.51
6.25
16.74
C-100
10.05
8.98
10.60
11.50
9.37
18.45
2.90
2.86
1.55
3.59
3.22
10.23
C-1000
27.14
24.13
11.09
27.06
21.13
21.90
8.44
8.00
5.25
8.37
7,20
13.93
C-5000
38.89
35.63
J. 8.39
40.44
29.29
27.58
9.90
9.45
1.551
9.65
8.55
11.35
C-10000
10.85
10.09
6.92
10.47
9.11
13.00
E-100
6.83
7.23
3.644
7.28
7.19
L 1,22
2.15
2.11
2.23
2.70
2.41
10.88
E-1000
24.55
23.77
4.3.21
24.01
21.57
10.16
9.61
9.18
14.99
9.61
8.77
8.76
E-5000
35.67
28.88
19.03
34.77
26.26
24.47
12.44
11.65
6.36
11:45
10.41
9.03
E-10000
10,96
12.24
[-100
6.66
7.23
1 88669
6.64
6.60
J 0.556
2.44
2.38
2.22
2.77
2.62
5,46
I-1000
21.30
20.54
3.55
18.62
18.52
J. 0.57
7.56
7.50
0.70
7.81
6.90
11.65
I-5000
30.40
27.64
1. 9.07
30.70
24.64
19.76
9.20
8.86
3.60
9.44
8.96
I-10000
8.36
7.68
8.10
8.27
6.78
18.05
Table 2: The experimental results of average gap (%) on the randomly generated CVRP dataset with different distributions and scales after training each model using both the vanilla and PUPO methods.
ELG-50
ELG-100
INVT-550
INVIT-100
Instance
Vanilla
PUPO
Vanilla
PUPO
Vanilla
PUPO
Vanilla
PUPO
U-50
7.45
8.15
19.45
8.32
9.09
9.36
4.25
4.58
7.83
4.75
5.06
6.44
U-500
15.48
10.97
1 29.14
8.91
8.84
0.73
10.75
9,83
8.55
9.67
8.37
13.50
U-5000
22.75
8.31
63.47
5.97
5.14
13.85
9.67
7.26
24.98
7.90
4.72
40.18
C-50
7.45
7.28
2.36
7.40
8.03
1 8.82
4.50
4.84
T 7.38
4.64
4.97
7,20
C-500
16.47
10.21
37.98
8.82
7.92
10.118
9.79
8.79
9.22
7.51
18.56
C-5000
20.45
8.72
57.36
7.10
5,43
23.50
8.49
7.07
1 16.72
7.66
4.51
41.107
B-50
7.58
8.13
1.332
8.57
9.13
6.799
4.56
4.94
7 8.52
4,88
5.37
9.98
B-500
15.86
11.12
29.88
9.32
8.68
6.99
10.48
6.26
9.82
13.27
E-5000
27.10
8.52
68.58
8.26
6,33
23.36
9.64
7.71
20.08
8.47
5.17
39,03
I-50
7.77
8.22
5.85
8.34
8.67
3.94
4.41
4.77
8.26
4.78
3.08
6.29
I-500
15.76
10.83
31.29
8.97
8.83
1.53
10.15
6.48
9.34
8.28
11.35
I-5000
19.43
7.05
63.73
6.01
5.24
12.91
8.23
6.87
16.48
7.35
4.58
37.66
Performance on Randomly Generated Dataset. Table [ [ the performance on the
randomly generated TSP and CVRP dataset, trained using both the vanilla and PUPO methods. The experimental results for total cost, statistics of gap and solving time are provided in Appendix [P] It can be observed that PUPO training enhances the performance across nearly all instance types both TSP and CVRP. Notably, the PUPO-trained INVIT- accomplishes a gap of 4.51% on C-5000 of CVRP, whereas the Vanilla-trained model can only reach gap of 7.66%.
From the perspective of test scale, PUPO training significantly improves model generalization performance on larger instances. For example, INVIT-100 achieves 18 18.05% relative enhancement on I- 1-10 of TSP, 40.18% 18% and 41.07% on U-5000 and C-5000 of CVRP. And ELG-50 shows significantly 68.58% and 63.73% gain on E-5000 and I-5000 of CVRP. On scales closer to the training scale, diverse phenomena can be observed. INViT- accomplishes an 9.92% uplift on U- 100 of TSP, while most other PUPO-trained solvers experience negative performance changes on the
8

---

U-500
U-5000
C-50
C-500
C-5000
E:50
E-500
E-5000
1-500
1-5000
30.00
25.00
Relative Deviation (%)
20.00
10.00
1111
-5.00
ELG.50
ELG-100
MVIT-50
INVIT-100
-15.00
Figure 4: The bar chart of relative deviations (%) solving time between Vanilla- and PUPO-trained models, where positive values indicate that PUPO-trained models hold shorter solving times.
same scale. This suggests that PUPO may involve in a trade-off, sacrificing accuracy on smaller-scabe instances while learning patterns more suited to larger scales. This trade-off is linked to the implicit regularization feature of PUPO, which discussed in the subsequent part. From distributional perspective, PUPO leads to positive average relative improvements across all distributions, indicating an enhancement in generalizability with respect to distributions.
Performance on Real-world Dataset. Table presents the performance on TSPLIB, further demonstrating that PUPO enhances the generalization ability on real-world data. For example, PUPO-trained ELG-50 achieves 31.6% relative enhancement on CVRPLIB 501 ~ 1000. Similar to
the experimental results random datasets, PUPO training leads better performance large-scale instances, but there are still some unimproved instances at small scale.
Table 3: Performance of average gap (%) on TSPLIB and CVRPLIB after training each model using both the vanilla and PUPO methods.
Instance
Vanilla
PUPO
Vanilla
PUPO
HLG-50
BL.G-100
TSPLIB 1~ 100
4.25
4.57
7.577
4.91
4.90
10.10
TSPLIB 101~1000
10.81
10.21
5.55
9.47
10.16
7.27
TSPLIB 1001~5000
22.88
20.24
11.55
23.45
18.69
$ 20.27
CVRPLIB 1~~200
9.84
9.52
4.3.32
8.30
8.62
3.81
CVRPLIB 201~-500
13.11
11.26
14.13
9.73
9.55
1.90
CVRPLIB 501~~1000
16.25
11.12
31.60
10.18
9.96
2.18
INVIT-50
IN 100
TSPLIB 1~~100
1.71
1.84
7.78
2.43
2.16
10.9T
TSPLIB 101~1000
4.97
4.67
6.01
5.60
4.97
J 11.15
TSPLIB 1001~5000
9.65
8.49
12.00
9.32
8.68
4 6.87
CYRPLIB 1~-200
8.93
9.00
0.78
8.72
9.57
9.84
CVRPLIB 201~5500
12.61
12.31
2.36
12.05
11.34
5.88
CVRPLIB 501~1000
13.31
12.59
$ 5.45
12.31
11.28
8.37
6.3 Computational Efficiency Analysis
Figure illustrates the relative deviations in solving time between Vanilla-trained and PUPO-trained models on CVRP, where positive values indicate that PUPO-trained models hold shorter solving times. Following the figure, most of the relative deviations are within 10%, suggesting negligible differences between the two, even the PUPO-trained models tend solve faster most cases. The possible reason may derive from that PUPO acts as an implicit regularization, which may have positive impact on the computation the model during the forward inference phase. Since PUPO only provides guidance during the training phase, it does not introduce additional time overhead during inference. Due to tensorizable computation of PUPO, training time does not increase greatly.
6.4 Learning Mechanisms Analysis
Purity Perception. To further explore the role PUPO during the training process, Table presents three metries that evaluate the purity of tours obtained by INVIT- 100. Numerical results of purity

---

metrics for all models are available in Appendix PP The table demonstrates that PUPO trained models consistently generate solutions with more outstanding purity.
Table 4: The experimental results of Vanilla- and PUPO-trained model on three purity evaluation
metrics, where bold formatting represents more pure results.
Prop-O (%)
APO (all)
APO (non-O)
Vanilla
PUPO
Vanilla
PUPO
Vanilla
PUPO
100
80.02
80.53
0.13
0.12
1.16
1.12
1000
85,46
86.48
0.23
0.19
1.81
1.66
5000
43.36
43.95
0.31
0.24
2.52
2.10
10000
87.17
88.27
0.54
0.55
4.28
4.86
Uniform
74.36
75.23
0.17
0.14
1.44
1.33
Clustered
73.82
74.65
0.34
0.33
2.76
3.02
Explosion
73.91
74.71
0.48
0.42
3.85
3.64
Implosion 73.91
74.64
0.21
0.20
1.74
Compared to vanilla training, PUPO enhances the Prop-O metric across all types, and lead to reduction in the kinds of APO metric across nearly all types. Notably, the largest average improvement in Prop-O occurs at the scale of 10,000, with a 1. % increase, which also corresponds to the scale where INVIT- 100 achieves its promoted generalization performance. These results suggest that PUPO facilitates the emergence of Purity Law during training, leading to enhanced model generalization.
Implicit Regularization. Furthermore, we calculate the sum of the Frobenius norm of the parameter matrices for each model after different training, presented in Table It can be observed that PUPO training reduces the sum of the parameter norms, acting as an implicit regularization mechanism. In contrast, also perform explicit regularization training by directly incorporating the sum of the norms into the reward function, but it does not result in improved generalizability. This suggests that PUPO effectively mitigates overfitting on the specific training set, encouraging the model to learn more generalizable structural patterns.
Table The sum of Frobenius norm of the parameter matrices for each model after different training, where bold formatting represents lower value.
ELG-50
ELG-100 100
INViT-50
INViT-100
Vanilla
336.44
336.24
430.83
429.78
PUPO
335.8
335.67
425.26
425.19
Conclusion
In this paper, reveal Purity Law, fundamental structural principle for optima of routing problems, which defines that edge prevalence grows exponentially with the sparsity of surrounding vertices. And we propose Purity Policy Optimization (PUPO) explicitly promote alignment with Purity Law during the solution construction process. Extensive experiments demonstrate that PUPO can be seamlessly integrated with popular neural solvers, significantly enhancing their generalization perfor- mance without incurring additional computational overhead during inference. Purity Law provides a novel perspective on routing problems, revealing systematic bias toward local sparsity in global optima validated across diverse instances statistically. While improving large-scale generalization, maintaining high accuracy for small-scale scenarios still limitation PUPO needs to improve. In future work, we plan to explore more effective training methods for leveraging Purity Law, and design network architectures that integrate Purity Law promote the perception it, thereby achieving greater generalizability.
Acknowledgments
This paper is supported by the National Key R&D Program of China project (2021 YFA 1000403), and the National Natural Science Foundation of China (Nos. 12431012, U23B2012).
10

---

References
[1] Alckh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, 32:96, 2019.
[2] David L. Applegate, Robert E. Bixby, Vašek Chvátal, William Cook, Daniel G. Espinoza. Marcos Goycoolea, and Keld Helsgaun. Certification of an optimal tsp tour through 85,900 cities. Operations Research Letters, 37(1):11-155 2009.
[3] Tapan P Bagchi, Jatinder ND Gupta, and Chelliah Sriskandarajah. A review of tsp based approaches for flowshop scheduling. European Journal of Operational Research, 169(3):116 854, 2006.
[4] Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combina- torial optimization with reinforcement learning. arXiv preprint arXiv:1611 1,1.0990, 2016.
[5] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d' d'horizon. European Journal of Operational Research, 2902))405-421, 2021.
[6] Jieyi Bi, Yining Ma. Jiahai Wang, Zhiguang Cao, Jinbiao Chen, Yuan Sun, and Yeow Meng Chee. Learning generalizable models for vehicle routing problems via knowledge distillation. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 11226-31222 Curran Associates, Inc., 2022.
[7] Paulo da Costa, Jason Rhuggenaath, Yingqian Zhang, Alp Akcay, and Uzay Kaymak. Learning 2-opt heuristics for routing problems via deep reinforcement learning. SN Computer Science, 2, 09 2021.
[8] Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Mare Andreoli. Bq-nco: Bisimulation quotienting for efficient neural combinatorial optimization. In A. Oh, T. Naumann, A. Globerson. K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 77416-77429. Curran Associates, Inc., 2023.
[9] Ekrem Duman and Or. Precedence constrained tsp arising in printed circuit board assembly. International Journal of Production Research, 42(1):67-78, 2004.
[10] Han Fang, Zhihao Song, Paul Weng, and Yutong Ban. INVIT: A generalizable routing problem solver with invariant nested view transformer. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceed- ings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 12973-12992 PMLR, 21-27 Jul 2024.
[11] Zhang-Huz -ua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 7474-7482, 2021.
[12] Chengrui Gao. Haopu Shang. Ke Xue, Dong Li, and Chao Qian. Towards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy. In Kate Larson, editor, Proceedingy of the Thirty-Third International Joint Conference on Artificial Intel- ligence, IJCAI-24, pages
International Joint Conferences on Artificial Intelligence Organization, 2024. Main Track.
[13] Simon Geisler, Johanna Sommer, Jan Schuchardt, Aleksandar Bojchevski, and Stephan Günne- mann. Generalization of neural combinatorial solvers through the lens of adversarial robustness. arXiv preprint arXiv:21 10..22111.1924.. 2021.
[14] Tiande Guo, Congying Han, Siqi Tang, and Man Ding. Solving combinatorial problems with machine learning methods. Nonlinear Combinatorial Optimization, pages 207-229, 2019.
[15] Dan Gusfield. Integer linear programming in computational biology: Overview of ilp, and new results for traveling salesman problems in biology. Bioinformatics and Phylogenetics: Seminal Contributions of Bernard Moret, pages 373-404, 2019.

---

[16] Keld Helsgaun. An effective implementation of the lin kernighnn traveling salesman heuristic. European journal of operational research, 126(1):106-13))) 2000.
[17] Keld Helsgaun. An extension of the fnn-kemigghanbbelgamm tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University. 12:966 98060 2017.
[18] Yan Jin, Yuandong Ding, Xuanhao Pan, Kun He, Li Zhao, Tao Qin, Lei Song, and Jiang Bian. Pointerformer: Deep reinforeed multi-pon pointer transformer for the traveling salesman problem. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 132--814,, 2023.
[19] Chaitanya K Joshi, Quentin Cappart. Louis-Martin Rousseau, and Thomas Laurent. Learning tsp requires rethinking generalization. International Conference on Principles and Practice of Constraint Programming, 2021.
[20] 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.
[21] 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.
[22] Minsu Kim, Jinkyoo Park, and joungho kim. Learning collaborative policies to solve np-hard routing problems. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 10418- 10430. Curran Associates, Inc., 2021.
[23] Minsu Kim, Jiwoo Son, Hyeonah Kim, and Jinkyoo Park. Scale-conditioned adaptation for large scale combinatorial optimization. In NewrlPS 2022 Workshop on Distribution Shifts: Connecting Methods and Applications, 2022.
[24] Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn solve routing problems! arXiv preprint 1003:0880008877 2018.
[25] C. Korostensky and G. Gonnet. Near optimal multiple sequence alignments using traveling salesman problem approach. In 6th International Symposium on String Processing and Informa- tion Retrieval. 5th International Workshop on Groupware (Cat. No.P00026)), pages 105-114, 1999.
[26] Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning, Advances in Neural Information Processing Systems, 33:21 188-118-11 198, 2020.
[27] Yeong-Dae Kwon, Jinho Choo, Iljoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. Advances in Neural Informa- lion Processing Systems, 34:5133 11:5138-5149 2021.
[28] Langley. Crafting papers on machine learning. In Pat Langley, editor, Proceedings of the 17th International Conference on Machine Learning (ICML 2000), pages 1207-1216, Stanford, CA, 2000. Morgan Kaufmann.
[29] Wenzhao Liu, Congying Han, Tiande Guo, Haoran Li, and Zicheng Zhang. Fusion of multi-level information: Solve large-scale traveling salesman problem with an efficient framework. In International Conference on Neural Information Processing, pages 80-103. Springrr, 2024.
[30] Hao Lu, Xingwen Zhang, and Shuang Yang. A learning-based iterative method for solving vehicle routing problems. In International conference on learning representations, 2019.
[31] Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances Neural Information Processing Systems, volume 36, pages 1845-8864. Curran Associates, Inc., 2023.
12

---

[32] Fu Luo. Xi Lin, Yaoxin Wu, Zhenkun Wang, Tong Xialiang, Mingxuan Yuan, and Qingfu Zhang. Boosting neural combinatorial optimization for large-scale vehicle routing problems. In The Thirleenth International Conference on Learning Representations, 2025.
[33] Yining Ma, Jingwen Li, Zhiguang Cao. Wen Song, Le Zhang, Zhenghua Chen, and Jing Tang. Leanning to steratively solve routing problems with dual-aspect collaborative transformer. Advances in Neural Information Processing Systems, 34:1 1096-11107, 2021.
[34] Sahil Manchanda, Sofia Michel, Darko Drakulic, and Jean-Mare Andreoli. On the generalization of neural combinatorial optimization heuristics. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 426-442. Springer. 2022.
[35] Yimeng Min, Yiwei Bai, and Carla P Gomes. Unsupervised learning for solving the travelling salesman problem. Advances in Neural Information Processing Systems, 36, 2024.
[36] Alexandru Paler, Alwin Zulehner, and Robert Wille. Nisq circuit compilation is the travelling salesman problem on a torus. Quantum Science and Technology, 6(2):025016, mar 2021.
[37] Xuanhao Pan, Yan Jin, Yuandong Ding, Mingxiao Feng. Li Zhao, Lei Song, and Jiang Bian. H-tsp: Hierarchically solving the large-scale traveling salesman problem. Proceedings of the AAAI Conference on Artificial Intelligence 37(8):9345-955 -9353, Jun. 2023.
[38] Jean-Claude Picard and Maurice Queyranne, The time-dependent traveling salesman problem and its application the tardiness problem in one-machine scheduling. Operations research, 26(1 26(1):66-110, 1978.
[39] Gerhard Reinelt. Tsplib traveling salesman problem library. OR Software, 1991. Available httt:://www iwr uni head-eeedebbrrggg.... /ttp/////////o////ototo/////////
[40] Eduardo Uchoa, Diego Pecin, Artur Pessoa, Marcus Poggi, Thibaut Vidal, and Anand Subrama- nian. New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257(3)8845-858, 2017.
[41] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[42] Thibaut Vidal. Hybrid genetic search for the evrp: Open- implementation and swap* neighborhood. Computers Operations Research, 140:100643, 2022.
[43] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in neural information processing systems, 28, 2015.
[44] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforce- ment learning. Machine learning, 8:229-22 256. 1992.
[45] Haoran Ye, Jiarui Wang, Helan Liang, Zhiguang Cao, Yong Li, and Fanzhang Li. Glop: Learning global partition and local construction for solving large-scale routing problems in real-time. Proceedings of the AAAI Conference on Artificial Intelligence, 28018)20024-20222 Mar. 2024.
[46] Dongxiang Zhang, Ziyang Xiao, Yuan Wang, Mingli Song, and Gang Chen. Neural tsp solver with progressive distillation. Proceedings of the AAAI Conference on Artificial Intelligence, 11410)42147-12114, Jun. 2023.
[47] Jianan Zhou, Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Towards amni-generalizable neural methods for vehicle routing problems. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardtt Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 42769942789, PMLR, 23-29 Jul 2023.
13

---

A More Discussion on Related Works.
With the rapid progress in deep learning, various neural approaches to combinatorial optimization have emerged. Overviews of these methods can be found in Guo et al. [4] and Bengio et al. [5].
Classical Neural Solvers. According to the way the solutions are generated, neural approaches can generally be divided into two classes: learning to directly construct and learning to iteratively improve solutions. For constructive methods, Vinyals et al.
45 introduce the Pointer Network, which solves routing problems end-to-end utilizing Recurrent Neural Networks to encode vertex embeddings, trained via supervised learning. Kool et al. 24 first introduce the Transformer architecture [41] to solve routing problems. Kwon et al. [26] further propose the policy optimization with multiple optima (POMO), which improves the performance by exploiting solution symmetries. Meanwhile, some works based on graph learning [21 20] also show potential to solve routing problems. Pointer- former [8] enhances memory efficiency by adopting a reversible residual network in the encoder and a multi-pointer network in the decoder. For iterative methods, DRL-2opt 7 trains a DRL policy to select appropriate 2-opt operators for refining solutions. Ma et al. 33 design dual-aspect collabo- rative Transformer to learn embeddings for the node and positional features separately, iteratively solving routing problems. GCN+MCTS [11] integrates graph decomposition and Monte Carlo Tree Search to handle large-scale instances effectively but mone-consuming.
Next, we will supplement more related work on improving generalization of neural routing problem solvers. AMDKD [6] introduces knowledge distillation to tackle the cross-distribution generalization concerns in the routing problem. Specifically, it leverages knowledge from teachers trained on exemplar distributions to yield a generalist student model. Also along with knowledge distillation, PDAM (46] adopts curriculum learning train TSP samples in increasing order of their problem size and progressively distilling high-level knowledge from small models to large models via a distillation loss. SCA [23] designs plugged network mix scale information into the original representation vector, which can help the pre-trained model adapt the policy to larger-scale tasks. By studying adversarial robustness, Geisler [3] derives perturbation models for SAT and TSP to enhance the expressiveness of the model with perturbations. Zhou [47) proposes a generic meta-learning framework enhance the ability of the initialized model fast adapt to new tasks during inference and conduct extensive experiments on VRPs. Sahil (34) Formalizes solving a CO problem over a given instance distribution as separate learning task and investigates meta-learning to optimize the capacity of the model to adapt to new tasks. Reformulating the Markov Decision Process of the solution construction in combinatorial optimization problems, BQ-NCO 8 proposes a novel Bisimulation Quotienting method for generalizable neural solver. GDMF 29 proposes an divideanddconquee
framework via fusing multi-level feature for large-scale TSP.
B Topological Properties of O-order Pure Edges
As the class of edges with the lowest degree of redundancy, 0-order pure edges are demonstrated by the following propositions to possess a series of favorable topological properties.
Proposition B.1. Given an instance X. for any vertex E X, there exists at least one vertex that can form 0-order pure edge with x.
Proof. We prove the proposition by contradiction.
Assume that for any x E X, we choose
v(*) arg min | y/
Since no vertex can form 0-order pure edge with x, have that
Kp( v(x)) > 0, Vz E X.
Therefore, there must exist point z(x) such that
(x - x=)) - =(x)) O.
14

---

Then we can derive that
y())ll2
o =0x) =(x) 22))
a =<x)]] (1z(() - u(x)1l -2x 2(x =(x))) - z(x))
2 x =(x)]]² ||((z) - y(²)1l
2 1 =<<:)]?
which means that the distance between =(x) and a smaller than the distance between y(z) and x. Therefore, it contradicts the assumption that y(x) is the nearest neighbor of x.
Proposition B.2. Given an instance X, the subgraph Go = (X, En) is connected, where En is the edge set of all O-order pure edges.
Proof. We prove the proposition by contradiction.
Suppose the subgraph Go is not connected. Without loss of generality, assume that Go has two connected components, denoted as Fi and F2. Let Si E Fi and f2 E F2 be such that
dist( f1, f2) dist(Fi, F2)
min min dist(a, b). aE beF2
Since es & Go. we have that
Kp(fi.f21 f2) > 0.
Therefore, there must exist point f3 such that the following inequality holds:
(/1 - f3) fs) < <.
which means that the distance between /3 and Si is smaller than the distance between f2 and fi- Regardless of whether f3 Fi f' F2, this leads contradiction with the assumption that the distance between /1 and f2 is the shortest distance between Fj and F2.
Proposition B.3, Given an instance X, for any vertex x E X, the polyhedron by its 0-order pure neighbors Dj is convex.
Proof. Consider any three adjacent O-order pure neighbors A, B, and C of point X. We have that
LABC LABX + LXBC.
Since A and C are 0-order pure neighbors of X, it follows that
LABX, BX < π 2
and thus LABC < n.
Due to the arbitrariness of A, B, and C, the polyhedron formed by its 0-order pure neighbors DV is convex.
Proposition B.1 establishes the existence of 0-order pure neighbors for any point, providing foundation for subsequent analysis. While proposition B.2 demonstrates that the subgraph formed by O-order pure edges possesses overall graph structural properties. And proposition B.3 describes the intrinsic topological features the O-order neighbor set for any given point. The three propositions above characterize the mathematical properties of purity order theoretically.
15

---

C Purity Order Form for Non-Euclidean Problems
In non-Euclidean problems, there is longer direct connectivity between vertices, and the metric given a priori by the edge cost matrix. Given G = =(V, E), we define purity order (e(Ci)) in
non-Euclidean routing problems as follow:
Kp(eis)= maXm, 15m,, maxM, 183m,]
(15)
where M, = [mlargmac m.l(Sim;)s "eag) (( Sim, is the shortest path from vertex U/ to Um.
To understand it intuitively, we first need find the shortest path starting from the two endpoints, which does not exceed half the length of the edge and has the largest length, and then define the purity order two end points as the average the maximum number of nodes take an instance of the non-Euclidean TSP dataset of size 50 in [27] as an example and calculate the pure order according to the above definition. The purity order distribution is as follows:
shortest path. We
D Verification of Purity Law on CVRP
Although different routing problems face distinct constraints, the common goal of VRPs is to minimize the sum of the total tour cost, which is typically characterized by the spatial relationships between nodes. The Purity Law describes a universal local structure of spatial relationships. which are highly relevant to the common goal of VRPs. We also verify the Purity Law on CVRP. Using the dataset from the original paper of INVIT [10,, we computed the proportion (%) of edges with purity orders 0 10 in the optima. The result shown in the table6 can be observed that the negative exponential law still obviously holds. And lowest-order pure edges still keep dominance in the optimal solutions, while the concentration is slightly reduced due to capacity constraints.
Table 6: The verification result of Purity Law on CVRP.
CVRP-50 Uniform
CVRP-500 Uniform
Purity Order
Clustered
Explosion
Implosion
Clustered
Explosion
Implosion
78.3
76.5
78.2
78.4
66.6
65.8
67.3
66.8
13.2
12.9
13.3
13.2
11.3
11.2
11.2
11.3
5.5
5.6
5.5
5.3
4.3
4,4
4.3
4,4
3.1
3.1
3.0
3.1
2.4
2.5
2.3
2.4
2.1
2.2
2.0
2.1
1.6
1.6
1.5
1.6
1.5
16
1.6
1.5
1.1
1.2
1.1
1.1
1.2
1.3
1.3
1.2
0.9
L0
0.9
0.9
L.0
1.0
1.0
1.0
0.7
0.7
0.7
0.7
0.9
0.9
0.7
0.6
10
0.7
0.6
0.5
0.5
0.5
0.5
E Detailed Description of Statistical Dataset
To construct the dataset in statistical experiments, we first generate 21 different scales within the range of 20 to 1000, with intervals of 50 except 20. For each scale, we consider four widely recognized classical distributions, which is uniform, cluster, explosion and implosion, resulting in 84 different instance types totally. For instance types with scales under 500, 256 instances are randomly sampled to form the dataset, while for those with sizes of 500 or above, the number of instances is reduced to 128, which is due to the fact that optimal solutions of large-scale instances require excessive amount time. The optimal solutions for all instances are solved by LKH-3 [16] 17], which the SOTA heuristic capable of producing optimal solutions even for large-scale instances.
F Detailed Fitting Result
The mean and variance fitted parameters a and 3, along with fitting errors are shown in Table And the detailed values of the fitting error, a and / for each instance type are listed in Table g According to the table, the low mean and variance of the fitting errors demonstrate the reliability and university of the fitting results across different instance scales and distributions.
7
16

---

Table 7: Fitting results of the exponential function in Eq.
FITTING ERROR
/
MEAN
2.23E-05 8.45E-10
0.92 1.57E-04
2.63 1.49E-02
VARIANCE
Table 8: The fitting errors, coefficients or and 33 in Sec. 4.2
Fitting Eruu Explosion
Uniform
Clasterod
Implosicn
Unifform
Clustered
Explosion
Implosion
Uniform
Clusterad
Explosion
Implasion
6.58E-05
2.455004
1.01F-04
5.71E-08
0.8860
0.8554
2,0800
2.2483
2.2630
50
5.42E-05
7.90E-05
3.90E-05
5.05E-05
0.9115
0.8919
0.90127
0.9002
25106
2.3295
2.4152
2.3923
100
2.41E 05
3.75E-05
LSSE-05
3.61E-05
0.9204
0.9124
0.9091
0.9137
2.5974
2,5133
2.4567
2.5286
150
2.54F-05
2.57F-05
2.96--05
1.78F-05
0.9236
0.1888
0.9150
0.9184
2,610
2,5782
2.5412
2.5681
200
2.18E-08
2.20B-05
2.62E-05
1.638005
0.9236
0.9211
0.9197
0.9302
26384
2.6192
2,6002
2.5887
1.35E-05
2.38B-05
2.42E-05
2.6337
300
1.26E-60 05
1.495-05
2.06E-05
2.08E-05
0.9259
0.9258
0.9211
0.9224
266335
2.6578
2.6057
2.6201
350
1.39E-40 05
10E-05
16615-05
1.71E-05
0.9273
0.9263
0.9236
0.9224
2.6622
2.6621
2,6318
2,6166
400
1.33E 05
1.54E-05
1 1.00E-05
10052-06
0.9278
0.9200
0.9241
0.9255
1.814
2.6918
2.6430
2,6206
450
1.0EE
1.12E-05
1.61E-05 05
1.52E-05 05
0.9280
0.9288
0.9234
0,9260
66005
2.6947
2.6289
2,6633
1155-0
1.1SE-05
1.28E-05
2,6536
350
1.04-005
496-05
1 1944--55
1.31E-U5
0.9306
09298
0.9277
0,9267
7
2,7186
2,6615
2,6673
600
7.55E 06
1OSE-00
LASE--05
1.262-05
0.9294
09306
0,9259
0.9275
2.6911
2.7207
2.6591
2.6803
650
1.13E-68 05
L337--05
9.63E-06
1.79E-05
0.9297
0,9310
0.9262
0.9263
2.7058
2.7293
2.6535
2,6689
700
1,34E-05 05
10BE-05
40EE-U5
1.77E-0S
0.9280
0,9006
0.9277
0.9256
16855
2.7175
2,6877
266663
1.22F-05
1.36F-05
0.9264
2.6930
1.22E-05
296-00
97F--06
1.19E-0K
0.9294
09311
2,7040
2.7323
2.6750)
850
1.30E-05
126--0
506-00
1.33E-05
0,9300
0.9305
0.9276
0.9271
2.7151
2.7181
2.6409
2,6707
900
1.33E-05
103E-05
1 006--0
466--1
0.9309
0.9366
0.9276
0.9281
2.7296
2.7357
2.6790
2.6906
950
1.33E-05
38F-01
44F-05
1.41--05
0.9299
0.9314
019284
0.9277
2,7132
2.7376
2,6951
2,6851
1000
1.515.08
1.215-05
1.268005
1.248-05
09318
0.9282
0,9289
2.7340
2.6890
2.6978
G Proof of the upper bound
Theorem G.1. For edge Erg. assume that K (el(ea)) is an positive even number, 2; E NN(ezy) evenly distributed both sides of exy, and the probability of each node being selected follows uniform distribution. Then, the probability of exy being at the optimal solution holds the following inequality:
k!
Plezy E TOPT] S
(16)
2. 1)!!
2
Proof. Let Way denote the Hamilton Path formed by edge exy and vertices 2; E Ne(ery). Then, the following inequality holds:
Plezy E TOPT] PPeedges in Way do not cross].
(17)
Next, We will analyze the probability that no edges in Way cross and obtain an upper bound. We prove this theorem by induction.
When A 2, there zı, #2 Ne(esy) evenly distributed on both sides of eay- At this time, there are six possible cases for Way: (21, v. 22), (22, o, V, 21). (z1, 22, v. y). (21, 22, y, v)) (x, žı, 22, y). (y, 21, a)). Among them, (Z1, 22) and (z2, y, =1) have edge intersection, so
1
2!!
Pleay E TOPT] S Pledges in Way do not cross]
(18)
3
2 4"!!!
Now, we assume that when Kp(Exy) k, the following equation holds:
k!!
Pledges in Way do not cross] 4 (I + 1)!!
(19)
means that among all (k + 1)! combinations of Ways there are (k!!)
- situations where the edges
of Wzy do not cross. When (ey))) = l + 2, first, there are totally (k + 3)1 combinations of situations
(k!!)²
Way. Next, we consider the con-intersection structure based on case k. For every 4
17

---

where the edges of Way do not cross, consider one side of Cay first. If adding point still leaves no intersection, there are + possible addition positions. Considering both sides symmetrically. there are (5 +1 (k+2) non-intersection cases. Therefore, it can be obtained that
(k!))
(k+2)
(k: 2)!! 4(x+2)/2 ((k: + 2) + 1)!!
Pledges in Way do not cross]
45/2-T
(20)
(k + 3)!
Hence,
k!!
Plesy E TOPT]
S
(21)
4 - 1)!!
H
Connection between Purity Law and k-Nearest Prior
The k-nearest prior in routing problems refers to the observation that in optimal solutions, the next city visited is frequently among the & nearest neighbors of the current city, where k ttpicaaly small value. Purity Law and the k-nearest prior are both local phenomena that are commonly observed in optimal solutions of routing problems. However, the Purity Law reflect more topological information.
First, the k-nearest neighbor with smaller values of that exhibit good structural quality tend to have lower purity orders for the edges they form. Second, the purity order reflects local structural information that the k-nearest prior not capture. For example, in Fig. [ both and 22 5-NN of z, and they are equivalent under the k-NN metric. However, under the purity order metric, they distinguished. The neighbor 21 with lower purity order is more ideal candidate for connecting to & compared to 22, due to its more coherent local structure. Thus, Purity Law not only contains distance information but also incorporates the structural information of the node distribution around the edges. This richer information carried by Purity Law allows it to contribute more effectively generalization.
I Proof of the supermodularity of Purity Availability
Proposition L1. The set function & 2X defined on the subsets of the finite set X is su- permodular, that is, for any subset A C B X and any x E X B, the following inequality holds:
-AA -BB)..
Proof. Given subsets U C X and any 01 X U, we prove the equivalent definition of supermodular functions:
d(U ((U -(( s(U (1), +2))+ 6(U).
(22)
18

---

First, we have
Σ min Kp(T,. 2.EU ipi
x(U) =
U
Σ
min 25E0(((o)) (z) + min kz)) 2yEt
#iE jfz
10++1 (y()
Σ
min
+ min (y()) 25E0
NEU 25 jps
@UU (v2))
U kp(1;,33)) +
Σ 2iEU
min m) 171
min xz) + min kz((2, ayE(((1z)
Φ(U U (21,
IU +2
By the following relations, we partition U into three parts, denoted as Uo, U1, U2, respectively.
Uo arg min Ky y) E U}
{
U1 { arg min Kp y) v1
U2 = {or arg min K (3ic v) =02)
Then, prove that the following expression is non-positive from three parts:
(&(U u (mi)) x(U u (v2))) (s(U U (vI, + o(U)).
Part 1
min K (3) zjEU E.EDo
Σ
+
+
100
10| +
-1
min K ()), z,EU s, E.E
Σ
50
[UK[U] + 1)( 2)
Part 2
minz, EU Kp(x5.27) ming,eu EU Kp(xe. +
K Kp(de, U1) 10 +
10
[U]
UU+11
R,EU,
minazeu Kp(zz,01)
EuUuuu) Kp(zz.01)
|1|+1
U1++2
minz,eu Kp(0),35)
K Kg(H;, U1)
ming,e0 EU Kp(zz, U1) +
Σ
1U((U++1)
[ + +2)
(IU) + +)[[U+++
Kp(I;, 21) +1 [U((U1+1)
Kp(zi,01)
min et Kn(zij,1) v1)
< Σ
(1U) + 1)(UU]+ +2)
(1U)+ 1] + 2)
x,E0,
1
-2 Σ K,(,,,0) + +10|
min K Kn 01) - UUKKUU + +2) 2,e0
VI([U 1)(1U) + +2)
2yE0,
1
1 + 1)( + 2)
2 min Ky(r,, Z
+ U min Kp(a,, |U1((U] + 2) ayEU
(-2 - 2(U1 0
1)(10++2
19

---

Part 3
minazev (x()
minayeu Ky Kp(wi,
K Kp(se,,15 v2)
Ky Kp(ri; U2)
))
Σ
101+1
[01
[0] +1
10 + 2
min (2)
EUUfo) Kg(Iz, 02)
[U| +1
[U| +2
ming,e EU (z((())z))
Ky(zi, v2)
ming,eD EU Kp(zz, U2)
Σ
[U((U++1)
(1U) 1)(1U) +
(IU) 1)( + +2)
24 2
Kplaz, U2)
Kp U2)
ming, EU K2 Kp(z),02 v2)
<
Σ
[U((U++11 +1)
(U + 1)(UU +
(IU 1) +
x,E02
1
-2 Σ
Kp(I,; 02) + U0]
min K [.. 02) - |22|UU1 +2) 2yE0
[0[[U]+ (IQUU(+)((U++)) +)(
Ty EU2
1
S 1)(1U + 2)
-2|U/ min K, (Iz,, v2) + |0| zyEU
min Kp(z,, 02) |021(1U] + +2) 2GEū
$ 1
(-2 - 2) S
The gain consists of three parts, each of which is non-positive. Therefore, the overall gain is non-positive, and the supermodular property is thus proven.
J The Whole PUPO Algorithm
The whole algorithm of PUPO is presented in Algorithm PUPO is established upon the REIN- FORCE with baseline, incorporating Purity Law information into the modified policy gradient. At different stages of solution construction, PUPO introduces discounted cost information that reflects the purity potential of the partial solution and the unvisited vertex set, which encourages the model to take actions with lower purity orders at each step during the training process. This approach helps the model to learn consistent patterns with the Purity Law prior, an information that is independent of specific instances, thereby enhancing its generalization ability. Notably, PUPO can be easily integrated with arbitrary existing constructive neural solvers, without any alterations to network architecture.
K Theoretical analysis on optimization error of PUPO
Theorem K.1. Assume that for all 0, VPa is 8-smooth and bounded V.. Suppose the variance is bounded as follows: B|IlVVrs VVP [|] s a². For t. 3(V v(0))/o2, suppose
constant stepsize of n 1/3, and thereafter, we use 17: (3T) For all T, we can obtain:
23(V* V(O))
20
min B|l (1 3
+
(23)
T
T
N Σ where VVP= = E (L(T)-b(x))
w W( (1) Po log
VVP
- -(x)) (1
and the update rule of gradient ascent al-
gorithm is f.41 02 + VVP..
The proof method is similar to I And these optimization error theorem confirms that our proposed algorithm can converge to stationary points.
20

---

Algorithm PUPO Training
Input:
number of epochs E, steps per epoch M, batch size B, scale of training instances N,
discount factor 7,, learning rate 5
Init 8, 0 <-
for epoch = ..... do
for step ..... M do
E 1.2.... ..2..... B}
8 Random/nstance()
T' f SampleRollout( (s,, pe)
T. GreedyRolloutie Poaz)
UB + 8
for time =1 ......
N U. + U 7
do
((U)) + Σ min Ky 8, beUt
deti bya
((1)-1)
o(U))
C(U), - KKp 1141 s;) +
10/+1l
10H1
Wit1 t 1 Σ "-CUJ T)+2)
j=t
end for
VG B L(7h))
- SVL
end for BL. t UpdateBaseline(4 (.)
end for
(a)
(U,,)
(b)
((U,) 0
the vertex in unvisted vertex set
the vertex in current partial tour
Figure 5: Example of two purity potential.
L Further Discussion on Derivation Process and Explanation of PUPO
In this section, We will discuss the derivation process and explanation of PUPO more detail. For convenience, Wei denotes the shorthand for W (14, 7++1).
each step is essential for learning policy with strong generalization capability. For intuitive understanding, we plot a specific example shown in Fig. 5 In this figure, policy (a) selects myopic local optima the earlier decision stages. In the later stages, constrained by the requirement to select vertices only from the unvisited vertex set, forced to connect some "bad" edges with higher purity orders (see red edges). In contrast, strategy (b) constructs tour with higher overall purity level. For solving instances of the same
Enhancing the purity potential of the unvisited vertex
21

---

type during training, the tour lengths obtained by strategies (a) and (b) may not differ significantly. However, when generalized to other instances, myopic strategies like (a), which result in poor purity in the later stages, are more likely to lead to tours of lower quality.
Inspired by supermodularity, we design purity weights to assess the potential purity of states at each time step for future decision under different policies. We constructed a Purity Availability metric with supermodular properties to measure the purity potential of the unvisited vertex set. On one hand, since Purity Availability represents the average minimum available purity order, higher values indicate that the state will not be able to generate highly pure structures in the future. For example. in the figure above, the Purity Availability of strategies (a) and (b) at the current state are and O. respectively. It means that policy (b) possess ability to construct purer structures in the future. On the other hand, constrained by the necessity to select nodes only from the unvisited vertex set, later decision stages often lead to states that are unfavorable for generalization and difficult to distinguish under tour length metrics. Due to supermodularity, the marginal benefit of Purity Availability, 6(44) o(4,1), is greater at later stages, making the purity measure in the later decision phases more significant. Inspired by supermodularity, we designed the purity cost based on the marginal benefit of state and the purity order of the actions. Furthermore, we designed purity weights based on the concept of future discounting to comprehensively assess the future purity potential of intermediate states during policy transitions.
Through analysis of upper and lower bounds and experimental analysis, PUPO encourages the exploration of higher-quality states under the purity measure. First, we present a pair of upper and lower bounds for Eq. (12). Since W, 2 1, the following inequality holds:
N
L(T)
v log poggoanal
<pp((Tix)
L(T)
Σ
W,
1=2
N
<Epu(T|X)
L(T))
Σ
W
log (oggo(t(
The left-hand side of the inequality represents the original policy gradient with tour length as the
reward, while the right-hand side represents the policy gradient with Σ We L(T) as the reward.
In this reward, the purity weights act as multiplicative factors on the tour length. It means that the overall purity of the tour is also incorporated into the reward information. The policy gradient of PUPO lies between the two, applying each We to the logarithm of action probabilities at each time step. This more subtle approach encourages the exploration of strategies that can transition to states with higher quality under the purity measure.
M Numerical Result on Two Classical Solvers
We also conduct experiments on two classical neural solvers POMO and PF. Table 9 show the results on random dataset of TSP. It can be observed that PUPO training enhances the performance of four classical models across nearly all instance types. In particular, AM-100 and PF-100 demonstrate superior performance across all distributions and scales compared to those trained with the vanilla. Table [0] also shows the results on TSPLIB, and Table [T] shows the result on random dataset of CVRP. It can be observed that for CVRP, PUPO training enhances the performance more significantly. Although PUPO also enhanced the generalizability of AM and PF, their global perception and decision modules remain vulnerable, resulting in larger performance gaps as the scale increases. This observation abstracts us to focus on developing network architectures that incorporate Purity Law in future work.
22

---

Table 9: The experimental results of average gap (%) on the randomly generated dataset with different distributions and scales of TSP after training two classical model using both the vanilla and PUPO methods, where bold formatting represents superior results.
POMO-50
POMO-100
PF-50
PF-100
Instances
Vanilla
PUPO
Vanilla
PUPO
Vanilla
PUPO
Vanilla
PUPO
U-100
5.21
5.35
5.07
4.61
4.16
4.31
3.64
3.39
U-1000
35.51
34.01
31.23
30.16
41.00
39.10
30.57
29.93
U-5000
67.99
65.12
80.64
68.42
113.55
104.09
80.59
77.53
C-100
7.75
8.03
7.66
6.07
7.67
7.71
7.24
6.90
C-1000
41.14
39.82
37.99
33.84
51.04
49.58
47.50
44.11
C-5000
77.78
75.93
76.37
70.03
137.51
131.61
137.15
121.79
E-100
5.01
5.18
5.04
4.71
4.98
5.12
4.74
4.65
E-1000
35.57
35.07
32.97
30.20
46.04
45.34
41.60
37.73
E-5000
71.95
66.66
74.55
66.33
133.99
129.02
120.96
110.16
I-100
5.02
5.17
5.12
4.64
4.71
4.91
4.49
4.35
I-1000
37.38
37.12
32.44
30.94
46.54
44.83
36.11
34.47
I-5000
78.57
74.05
72.87
66.58
151.37
138.71
120.67
103.74
Table 10: Performance of average gap (%) on TSPLIB after training two classical model using both the vanilla and PUPO methods.
POMO-50
POMO-100
PF-50
PF-100
Vanilla
PUPO
Vanilla
PUPO
Vanilla
PUPO
Vanilla
PUPO
I 100
5.82
5.17
4.98
4.48
7.42
8.37
7.82
7.16
101~1000
17.39
16.14
14.12
12.17
25.96
24.77
23.37
22.68
1001~5000
48.41
46.48
43.33
40.46
75.57
72.58
66.05
60.86
Table 11: The experimental results of average gap (%) on the randomly generated dataset with different distributions and scales CVRP after training POMO model using both the vanilla and PUPO methods, where bold formatting represents superior results.
POMO-50
POMO-106
Instance
Vanilla
PUPO
Vanilla
PUPO
U-50
4.6
5.704
6.146
6.769
U-500
16.379
14.311
14.843
13.383
U-5000
22.846
16.122
20.599
18.067
C-50
5.204
6.346
6.388
6.384
C-500
14.997
13.21
12.837
12.279
C-5000
15.803
11.694
13.172
13.376
E-50
4.624
5,851
6.042
6.704
E-500
16.227
14.622
14.249
13.525
E-5000
22.761
17.148
21.638
17.673
I-50
4.57
5.794
6.117
6.911
I-500
15.744
14.239
14.033
13.16
I-5000
19.703
14.64
16.513
16.214
N Detailed Description of Dataset in Comparative Experiments
To ensure the adequacy of the experiments, we validate the model's performance two categories of datasets. The randomly generated dataset used in this paper is the same that INVIT [0], which is widely adopted to testify existing DRL approach. For TSP, it contains 16 subsets and correspond- ing (optra) solutions for TSP. including distributions (uniform, clustered, explosion, and implosion, denoted U, C, E, 1) and 4 scales (100, 1000, 5000 and 10000). For CVRP, it contains 12 subsets and corresponding (near-)oppima, solutions for CVRP, including distributions (uniform, clustered, explosion, and implosion, denoted as U, C, E, and scales (50, 500 and 5000).
23

---

The real-world dataset we used is TSPLIB and CVRPLIB. TSPLIB is well-known TSP library [39 that contains 100 instances with various nodes distributions and their optimal solutions. These instances come from practical applications with scale ranging from 14 to 85,900. In our experiment, we consider all instances with more than 10000 nodes. For CVRP, we include all instances in CVRPLIB Set-X [40], containing 100 instances varying in scale from 100 to 1000.
O Detailed of the Learning Rates of Models
Specifically, for TSP, the learning rates are set to 0.0001, 0.00015, 0.0001, 0.00017, 0.0001, 0.00012, 0.00011, 0.00012 for POMO-50, POMO-100, PF-50, PF-100, ELG-50, ELG-100, INViT-50, and INViT-100, respectively. For CVRP, the learning rates are set to 0.0001, 0.00006, 0.0001, 0.0001, 0.00005, 0.0001 for POMO-50, POMO-100 100, ELG-50, ELG-100, INViT-50, and INViT-100.
P Detailed Experimental Result
Table 12 shows the training time per epoch with different methods. We can see that the training time of PUPO does not increase significantly owing the tensorizable computation.
Table 12: The numerical results of training time (minutes) per epoch during different training.
POMO-50
POMO-100
INVIT-50
INVIT-100
Vanilla 3.05
4.49
7.72 11.598
15.75
PUPO
5.95
14.20
21.40
The experimental results of the specific tour length is presented in Table [3] Table illustrates the solving time of Vanilla-trained and PUPO-trained models on randomly generated dataset. Following the table, it can be observed that there is almost no difference between Vanilla and PUPO. The numerical results of purity metrics for all models are presented in Table T5] Following the table, PUPO-trained models possess the ability to generate solutions with more outstanding purity. Detailed results of ELG and INVIT are provided in Table to Table 27
Table 13: The length of tours generated from each model after different training on randomly generated dataset of TSP.
POMO-50
POMO- 100
PF-50
PF 100
INVIT-50
INVIT: 100
Vanilla
PUPO
Vanilla
PUPO
Vanilla
PUPO
Vanilla
PUPO
Vanilla
PUPO
Vanilla
PUPO
Uniform
8.07
8.05
1000
31.47
31.12
30.47
30.22
32.74
32.30
30.32
30.17
24.91
24.88
24.94
24.67
10000
79.07
78.88
78.79
77.87
Clustered
5.50
1000
19.82
19.65
19.39
18.80
21.26
21.05
20.78
20.30
15.25
15.19
15.24
15.07
10000
44,88
44.58
44.72
44.17
Explosion
6.68
1000
21.90
21.84
21.47
21.03
23.50
23.36
22.72
22.10
17.67
17.60
17.67
17.53
36.88
10000
43.28
43.05
43.18
42.66
Implosion
7.30
1000
27.61
27.57
26.63
26.33
29.39
29.04
27 28
26.95
21.64
21.63
21.69
21.51
44.78
10000
72.24
71.79
72.17
71.18
24

---

Table 14: The solving time for each model with different training methods on randomly generated
dataset of TSP.
POMO-50
POMO-100
PF-50
PF-100
INVIT-50
INViT-100
Vanilla
PUPO
Vanilla
PUPO
Vanilla
PUPO
Vanilla
PUPO
Vanilla
PUPO
Vanilla
PUPO
U-100
0.20
0.22
0.21
0.22
2.02
1.97
1.00
1.02
0.85
0.80
1.07
0.91
U-1000
2.35
2.34
2.41
2.40
23.67
24.08
13.57
14.18
13.24
12.88
17.83
17.34
U-5000
19.68
19.10
20.00
19.57
246.65
246.12
205.14
204.15
91.20
89.44
120.07
119.87
U-10000
224.99
223.69
288.44
287.11
C-100
0.21
0.21
0.21
0.21
2,08
2,13
0.97
0.98
0.84
0.80
1.04
1.17
C-1000
2.35
2.35
2.44
2.43
25.28
26.11
14.05
15.28
13.00
12.77
17.57
16.56
C-5000
19.16
19.38
19.99
19.35
275.68
274.49
212.36
211.68
88.23
118.63
117.31
C-10000
222.47
222.32
288.67
288,90
E-100
0:21
0.21
0:20
0.22
2.18
2.17
0.97
1.09
0.82
0.83
1.05
0.94
E-1000
2.38
2.46
25.44
24.53
13.94
13.05
17.70
E-5000
19.30
18.67
19.98
19.57
410.08
411.22
213.01
212.39
89.58
89.93
118.93
118.34
E-10000
223.24
223.03
288.86
288.32
I-100
0.21
2.89
1.00
1.05
I-1000
2.37
2.45
2.45
2.45
20.84
21.01
14.08
13,99
12.91
12.73
17.60
17.31
I-5000
19.95
19.28
19.84
19.30
445.75
444.87
186.14
186.05
89.92
88,30
118.87
118.69
1-10000
221.72
289.39
Table 15: The numerical results of purity evaluation for three models on TSP after different training.
Varilla APO
AAOO
APO
(5))
(all)
APO
Prop-O
APO
U-100
75.65%
0:15
1.31
75.29%
0.15
1.11
76.81%
0.15
1.12
79.45%
0.14
1.17
11-100
62.5158
(164
1.06
64. 64.12%
0.62
1.92
63.67%
0.52
1.75
57 7072
1155
1.56
U.5000
24.9156
1.36
2.97
25.39%
1.33
3.05
24.54%
1.50
3.13
26 15.64%%
1.23
2.74
70.1316
0.50
2.19
0.65
C-500
1.53
255
1.64
3,33
23.50%
1.45
C-10000
E:100
73.7256
0.17
1.15
74.35%
0.17
1.14
75.24%
0.17
1.17
77.77%
0.17
1.22
5-1000
62 9758
2.0%
61 559
0.67
2.0
67.12%
0.60
189
1.57
1.84
E55000
25.0995
1.53
3.27
23,99%
1.41
3.05
24.20%
1.55
3.13
26.04%
1.30
2.52
1.95
35000
1.53
25.708
24.22%
25.309
1.46
1-10000
19:30
PI-100
Vanillo ATO Gilly
PUPO APO (alb)
Vasilla APO (all)
PUPO
Pmg--0(0)
ATO (ncn-0)
Prop-O
APO (nun-4)
Prop-O (9))
APO (mun-0)
Prog-0 (9)
APO Gall)
APO (nom-)))
11-00
77.656
0:14
1.09
77.57%
0.15
1.10
80.0%%
0.12
80 911
0.13
1.06
1000
S906855
0.74
2.00
60.73%
0.70
1.1
05.0655
0.56
1.78
56 00.05
0.54
1.75
20.045
3.65
1.40
71.41%
71.53%
0.25
1.20
73.64/2
0.23
1.28
C-100
52
2000
56.515
1.57
C.5000
15.055
4.52
6.54
15.42%
4.36
5.95
16.00%
4.20
6.3
19%
3.13
4.93
C-10000
E:100
74.92%9
0.19
1.36
7482%
0.18
1.17
76.63%
0.17
1.17
77 17.44
0.16
1.16
9-1000
55.05%
0.06
2.34
5.10
2.73
B-10000
73.76%
0.34
1.28
75.6%%
0.22
1.20
3-1000
1.00
1/42
1.13
355000
15.18%
8.14
10.81
15.00%
5.46
11.50
17.79%
7.46
10.38
18.35%
6.02
3.58
1-10000
3NV
I0V
Vantilla APO (ill)
PUTO APO (alt)
Vanilla APO (ali(
PUPO APO (all))
Piop u
JAPO (ncn-0)
Phop 195)
APO (pos.
Phop O
APO (aon 0)
Prog 1
APO /
1.04
0.10
E-10000
0.17
1.50
E2000
0.90
0.33
1.17
1.20
111.4
1.39
C-1000
$6.025
0.22
1.58
0.56
0.19
1.63
83.56%
0.23
1.83
0.87
0.18
1,61
C-5000
657725
11:00
1.51
0.64
0.18
1.55
41.170 1775
0.37
2.30
0.46
1.17
1.5
C-10000
0.54
6.1
0.58
0.58
7.34
87.15%
0.71
5.74
0.38
0.27
7,37
0.12
E-5000
1-10000
8.38
0.55
L-000
79 0355
0.12
1.12
0.80
0.12
1.12
70.77%
0.14
1.17
0.80
0.13
1.13
17000
15 6995
1.19
1.54
0.8
0.18
1.54
0.21
1.64
0.85
1115
1.55
1,5000
45.55 39.99%
0.23
1.58
0.44
0.22
181
43.35%
0.24
199
0.44
0.19
1,56
1-10000
0030
7.47
0.81
0.29
2.39
87.10%
2.18
0.38
0:30
7,62
25

---

Table 16: Detailed results of ELG-TSP-50 [Vanilla] on random dataset.
Instance
Mean Time (8)
Mean Length
Mean Gap (%)
Min Gap (%)
Max Gap (%)
Std
U-50
0.167
8,385
6.599
I.095
13.377
0.019
U-500
1.638
28.051
20.805
16.915
25.198
0.017
U-5000
21.006
67.121
31.496
30.52
32.456
0.009
C-50
0.17
5,838
10.047
3.552
20.179
0.03
C-500
2.027
17.867
27.142
19.898
34.527
0.034
C-5000
19.721
41.468
38.888
35.129
42,994
0.03
E-50
0.169
6,97
6.848
1.456
19.511
0.024
E-500
2.079
20.064
24.554
17.191
32.079
0.036
E-5000
19.915
45.129
35,672
32.112
42.508
0.045
I-50
0.167
7.591
6.655
1.143
14.219
0.021
I-500
1.96
24.401
21,303
17.254
25.035
0.02
1-5000
19.832
53.693
30.403
28.01
32.592
0.018
Table 17: Detailed results of ELG-TSP-50 [PUPO] on random dataset.
Instance
Mean Time (s)
Mcan Length
Mean Gap (%)
Min Gap (%)
Max Gap (%)
Std
U-50
0.163
8,425
7.102
0.73
13.637
0.018
U-500
1.667
27.742
19.474
15,497
22.476
0.015
U-5000
21.34
64.744
26.84
24.991
28.767
0.015
C-50
0.169
5,783
8.982
2.337
17.056
0.026
C-500
2.012
17.461
24.132
18.047
29.298
0.024
C-5000
19.84
40.475
35.625
34.174
38.202
0.016
E-50
0.171
6.996
7.234
0.849
15.83
0.022
E-500
2.139
19.941
23.767
18.862
30.275
0.032
E-5000
19.73
42.989
28.882
26.586
32.44
0.022
I-50
0.172
7.629
7.233
1.79
19.087
0.023
I-500
2
24.238
20.544
16.96
25.203
0.019
I-5000
19.781
52.342
27.644
25.039
30.885
0.021
Table 18: Detailed results of ELGGTSPP-000 [Vanilla] on random dataset.
Instance
Mean Time
Mean Length
Mean Gap (%)
Min Gap (%)
Max Gap (%)
Std
U-50
0.17
8.327
5.859
1,414
10.455
0.017
U-500
1.714
27.389
17.954
15.157
21 21.448
0.016
U-5000
21.802
65.96
29.223
27.378
30.284
0.011
C-50
0.18
5,912
11.495
3.5
33.416
0.041
C-500
2.135
17.842
27.057
17.086
53.627
0.059
C-5000
20.303
41.904
40.44
35.008
53.044
0.073
E-50
0.177
6.991
7.277
1.466
32,814
0.037
E-500
2.164
19.952
24,007
15,306
34.444
0.046
E-5000
20.288
44.711
34.771
28.244
53.191
0.104
I-50
0.181
7.582
6.639
1.27
53.637
0.037
I-500
2.129
23.869
18.621
13.569
23.293
0.021
I-5000
20.454
53.499
30.701
28.03
37.713
0.04
Table 19: Detailed results ELG-TSP- [PUPO] on random dataset.
Instance
Mean Time (s)
Mean Length
Mean Gap (%)
Min Gap (%)
Max Gap (%)
Std
U-50
0.169
8,416
6.394
1.544
11.726
0.018
U-500
1.642
27.513
18.491
15.788
21.281
0.013
U-5000
21.291
63.176
23.769
22,484
24.722
0.008
C-50
0.168
5,803
9.374
3.302
19.165
0.027
C-500
2.028
17.033
21.131
15.879
26.933
0,022
C-5000
19.813
38.576
29.285
27.614
30.616
0.011
F-50
0.17
6.993
7.188
1.913
15.156
0.022
E-500
2,094
19,599
21.568
16,944
27.233
0.025
E-5000
19.835
42.083
26.262
23.14
29.791
0.025
I-50
0.171
7.657
7.602
1.684
16.868
0.023
I-500
1.978
24.035
19,515
14.306
23.205
0.017
I-5000
19.735
51.01
24.636
21.293
28.75
0.031
26

---

Table 20: Detailed results of ELG-VRP-50 [Vanilla] on random dataset.
Instance
Mean Time (8)
Mean Length
Mean Gap (%)
Min Gap (%)
Max Gap (%)
Std
U-50
0.182
10.597
7,446
2.438
15.163
0.024
U-500
1.702
79.532
15.478
10.783
20.443
0.027
U-5000
41.938
729.196
22.753
12.2
31.278
0.069
C-50
0.192
9.228
7.451
1.417
19.272
0.032
C-500
1.788
64.274
16,468
10.468
25.644
0.035
C-5000
31.429
681,954
20.448
14.562
29.403
0.063
E-50
0.189
9,461
7.577
1.767
16.394
0.026
E-500
1.783
60.506
15,855
11.473
26.178
0.032
E-5000
31.684
437.246
27.103
15.508
48.303
0.126
I-50
0.191
10.086
7.766
1.961
19.897
0.028
I-500
1.797
73.173
15.762
10.151
22.652
0.03
1-5000
31.711
700.698
19.427
15.743
28.109
0.051
Table 21: Detailed results of ELG-VRP-50 [PUPO] on random dataset.
Instance
Mean Time (s)
Mcan Length
Mean Gap (%)
Min Gap (%)
Max Gap (%)
Std
U-50
0.186
10.665
8.15
2.483
21.006
0.027
U-500
1.694
76.488
10.968
8.122
15.112
0.016
U-5000
31.128
647.568
8.312
7.469
10.66
0.013
C-50
0.189
9.21
7.275
1.289
20.119
0.029
C-500
1.759
60.866
10.214
6.542
15.321
0.02
C-5000
30.684
615.111
8.72
4.76
16.811
0.048
E-50
0.189
9,513
8.132
2.725
17.49
0.027
E-500
1.748
58.13
11.117
8,009
17.598
0.02
E-5000
30.737
373.572
8.516
6.827
11.048
0.018
I-50
0.187
10.127
8.22
2.307
17.804
0.028
I-500
1.767
70.051
10,83
7.665
14.91
0.016
I-5000
30.623
629.346
7.046
4.803
9,885
0.021
Table 22: Detailed results of ELG-VRP-100 [Vanilla] on random dataset.
Instance
Mean Time
Mean Length
Mean Gap (%)
Min Gap (%)
Max Gap (%)
Std
U-50
0.195
10.685
8.315
I.049
19.544
0.028
U-500
1.843
75.079
8.907
6.067
13.065
0.015
U-5000
33,265
631.606
5.969
4.003
8.587
0.018
C-50
0.199
9,22
7.395
1.519
21.493
0.032
C-500
1.856
60.128
8.818
4,944
13.067
0.018
C-5000
31.53
609.493
7.103
5.912
8.039
0.01
E-50
0.2
9,547
8,566
2.14
23.925
0.031
E-500
1.865
57.156
9.322
7.064
15.291
0.019
E-5000
31.831
372.201
8.259
6.408
9.693
0,013
I-50
0.201
10.144
8.344
1.643
20.51
0.031
I-500
1.888
68.729
8.97
5.076
14.439
0.017
I-5000
31.839
622.795
6.013
5,351
6.99
0.007
Table 23: Detailed results of ELG- 100- [PUPO] on random dataset.
Instance
Mean Time (s)
Mean Length
Mean Gap (%)
Min Gap (%)
Max Gap (%)
Std
U-50
0.178
10.811
9.093
2.543
22.455
0.031
U-500
1.673
75.034
8.842
6.207
11.874
0.015
U-5000
31.197
626.848
5.142
3.314
7.476
0.016
C-50
0.189
9,359
8.047
1.617
23.159
0.038
C-500
1.757
59.604
7.92
5,273
13.105
0.015
C-5000
30.857
597.049
5,434
2.846
6.627
0.016
E-50
0.19
9.647
9.148
1.991
23.308
0.034
E-500
1.757
56,838
8.676
6,645
12.068
0.015
E-5000
30.796
365.526
6.33
4.875
7.202
0.009
I-50
0.189
10,262
8.673
1.927
23.732
0.036
I-500
1.758
68.808
8.833
6.697
14.897
0.014
I-5000
30.911
617.372
5.237
3.594
6.488
0.011
27

---

Table 24: Detailed results of INVIT-VRP-50 [Vanilla] on random dataset.
Instance
Mean Time (8)
Mean Length
Mean Gap (%)
Min Gap (%)
Max Gap (%)
Std
U-50
0.836
10.286
4.251
0.544
8.944
0.016
U-500
8.903
76.366
10.747
9.049
13.794
0.012
U-5000
137.071
654.376
9.672
8.218
10.969
0.01
C-50
0.74
8,978
4.5
0.718
15.507
0.024
C-500
8.035
60.676
9.786
7.865
11.631
0.008
C-5000
131.165
615.721
8.492
7.421
9.728
0.011
E-50
0.769
9,199
4.555
0.296
11.336
0.018
E-500
8,044
57.801
10,475
7.92
15.046
0.015
E-5000
131.033
376.968
9.641
8.73
10.735
0.009
I-50
0.743
9.775
4,408
0.427
12.283
0.019
I-500
7.756
69.659
10.148
7.872
12.083
0.01
1-5000
128.097
635.588
8.229
7.275
9.21
0.008
Table 25: Detailed results of INVIT-VRP-50 [PUPO] on random dataset.
Instance
Mean Time (s)
Mcan Length
Mcan Gap (%)
Min Gap (%)
Max Gap (%)
Std
U-50
0.797
10.329
4.584
0.572
9.606
0.016
U-500
7.909
75.738
9.828
7.848
12.912
0.011
U-5000
128.458
639.748
7.256
6.153
9.235
0.012
C-50
0.789
9.008
4.841
0.553
15.779
0.025
C-500
7.947
60.189
8.926
7.654
11.551
0.009
C-5000
127.466
608.262
7.072
6.281
7.985
0.007
E-50
0.795
9,233
4,943
0.531
10,928
0.019
E-500
8.012
57.44
9.819
7.607
14.179
0.014
E-5000
132.614
370.181
7.705
6.471
9.107
0.012
I-50
0.846
9.819
4.872
0.481
14.009
0.02
I-500
8.1
69.219
9,49
7.007
12.117
0.012
I-5000
130.251
627,491
6.873
6,444
7.233
0.003
Table 26: Detailed results of INVIT-VRP-101 [Vanilla] on random dataset.
Instance
Mean Time (s)
Mean Length
Mean Gap (%)
Min Gap (%)
Max Gap (%)
Std
U-50
0.778
10,319
4.75
0.235
10.179
0.017
U-500
7.906
75.658
9.672
8.112
11.936
0.009
U-5000
130,972
643.717
7.896
6.829
9,479
0.01
C-50
0.77
8,989
4.639
1.182
15.259
0.024
C-500
7.903
60.362
9.223
7.537
11.981
0.009
C-5000
126.556
611.67
7.655
7.229
7.876
0.003
E-50
0.777
9.227
4.878
0.587
11.05
0.019
E-500
7.915
57.486
9,82
7.829
12.352
0.01
E-5000
127.763
372.908
8.472
7.441
9.643
0.01
I-50
0.779
4.782
0.707
13,409
0.021
I-500
7.941
69.15
9.336
7.609
11.371
0.009
I-5000
127.558
630.358
7.353
6.908
7.836
0.004
Table 27: Detailed results of INVIT-VRP- [PUPO] on random dataset.
Instance
Mean Time (s)
Mean Length
Mean Gap (%)
Min Gap (%)
Max Gap (%)
Std
U-50
0.776
10,365
5.055
0.369
9.866
0.017
U-500
7.796
74.755
8.366
7.137
10.577
0.008
U-5000
127.661
625. 141
4.723
4.172
5.306
0.005
C-50
0.775
9,017
4.973
0.651
17.35
0.026
C-500
7.754
59.417
7.511
5,883
9,331
0.007
C-5000
127.345
593.798
4.511
4.173
4.826
0.003
F-50
0.783
9.27
5.365
0.804
12.195
0.021
E-500
7.903
56.784
8.517
7.271
12.073
0.01
E-5000
127.504
361.641
5.165
4.653
5,629
0.004
I-50
0.793
9.856
5.283
0.473
13.671
0.021
I-500
7.891
68.487
8.276
6.14
10.157
0.008
I-5000
126.872
614.135
4.584
4.223
4.953
0.003
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims made in the abstract and introduction can accurately reflect the contributions and scope of our paper, and are supported by theoretical analysis or empirical results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We have discussed the limitations of the work the section 7
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
29

---

Answer: [Yes]
Justification: The proof of all the theorems appeared in the main text is provided in the Appendix | and B
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The procedure of our algorithm PUPO is outlined Algorithm I with details provided in Appendix!!
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
30

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: Since we have conducted extensive experiments on several environments and implemented several algorithms, providing detailed scripts is intricate. The code will be made available upon acceptance the article.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
souuidee/CooeSumiisstt
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
wtaplli/ggiiee//eee Sawelee//oooSSbbmiiiaa SonpoddeummsssiooPPe.. wwriiisssioppiiioioo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: In the numerical experiments section of the main text. present brief introduction to experimental settings. More details about the experimental setting can be found in Appendix N and
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We have reported the variance of fitting results of the exponential function in tab 7 And report standard variance of gap at comparative experiments in Appendex P
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
31

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have reported the compute resources in the experimental settings part of section ??.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't itdn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htttpss//eeurips.cccpbb.i... cen.eiieeeeecccccceeeeeeeeee
Answer: [Yes]
Justification:
The research conducted in this paper adheres to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in their jurisdiction)
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This article mainly focuses theoretical analysis and algorithm design, and does not directly involve particular applications. Therefore, does not discuss the potential societal impacts.
Guidelines:
32

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societAal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e-g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work does not involve the release of models or datasets with high risk of misuse. Therefore, no special safeguards were required.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All datasets and code libraries used in this work are properly cited. We give clear credit to the original authors and fully comply with their license terms (e.g., MIT, CC-BY).
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
33

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, snperswithcode com comddatasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This work does not involve crowdsoureing experiments or research involving human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
34

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMS as any important, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy hatt:p///earrrppccc/ooooeereeee/ /c/////oeeeeeecc///22////.. for what should or should not be described.
35


Reviews:
[{"review_id": "7ZAjLggYil", "reviewer": "Reviewer_8oG4", "summary": "The paper proposes an empirical observation for routing problems in a metric space, introducing the concept of purity, which roughly measures the number of vertices in the neighborhood of an edge within the optimal solution of a minimum-cost routing problem (e.g., TSP or CVRP). Observing empirically that optimal solutions tend to have low purity on synthetic instances, the authors propose incorporating purity as a reward signal for reinforcement learning. Experiments on both synthetic and standard datasets for TSP and CVRP suggest that adding purity to the reward improves over vanilla REINFORCE.", "questions": "Do the authors have any sense of whether the purity phenomenon could be formally proven, at least for random Euclidean TSP? It seems plausible that one could rigorously show that cost-optimal solutions generally avoid long edges spanning densely populated regions.", "limitations": "Yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: Identifying reward signals that improve reinforcement learning in routing problems is a valuable contribution. The notion of purity is simple yet elegant, and the underlying intuition — that a cost-minimizing tour is unlikely to use edges spanning densely populated regions — is sound. That this observation can be transformed into a useful reward signal helps shed light on what kinds of dense, structured rewards are more amenable to policy gradient methods. This kind of insight may well generalize beyond routing to other combinatorial settings.\n\nWeakness: The main weakness is that REINFORCE itself is a relatively weak baseline. While I appreciate the simplicity of evaluating the method with REINFORCE on TSP and with a random graph baseline, this evaluation alone may not fully demonstrate the potential of the proposed reward shaping. I encourage the authors to also consider how their method compares against classical solvers such as concorde.  It's ok to lose, but it's informative to know by how much.", "was_revised": true, "final_justification": "The paper is substantially improved with theoretical results that prove its primary claim.  That a provable property of euclidean, random, routing problems can be demonstrated to offer consistent improvements over a vanilla baseline is conceptually clear and elegant.  The comparisons are now thorough.  As such, I've decided to increase my score.", "rebuttal": "Thank you very much for your time and effort in reviewing our work. We feel glad to know you acknowledge our work is a valuable contribution, find notion of purity is a sound underlying intuition, simple yet elegant, and believe this work would be insightful for the community.\n\nWe will address each of your concerns in detail as follow.\n\n--Q1: Integration with REINFORCE.\n\nThank you for raising this concern. First, the proposed PUPO can be combined with any policy-based method. Due to the fundamental role of REINFORCE in NCO, we first combined PUPO with it and found that after PUPO-training, the model's cross-distribution and large-scale generalizabilities were significantly improved. Furthermore, we conducted experiments combining PUPO with imitation learning, and the results were further improved. (Please see our response to Reviewer Kzrh.)\n\nIn the field of neural routing problems, REINFORCE is a principal training method for neural constructive approaches, due to its ease of instance generation for the routing problems and its efficient sample utilization for reward computation. It is still adopted by the latest and most advanced works, such as [1-7].\n\nTraditional reinforcement learning environments require CPU-based trajectory data generation, which is very time-consuming and slow. Therefore, advanced algorithms such as PPO are needed to improve sample utilization efficiency. However, in the neural routing problems, instance generation is very simple and easy to parallelize on GPUs, and reward computation can efficiently utilize samples. At the same time, [8] demonstrates that the complex hyper parameter tuning of PPO may slightly hurt performance. Also [8] shows that REINFORCE-trained model performs even better than PPO-trained on mDPP. Therefore, REINFORCE is a vital baseline for neural routing problem solvers training.\n\n--Q2: Comparison against concorde.\n\nThank you for this suggestion. The test datasets used in this paper is from [6]. In the datasets with multi-distribution, TSP-100 is solved by Gurobi, an exact solver, so the solutions are guaranteed to be truly optimal. TSP-1000, TSP-5000 and TSP-10000 are solved by a SOTA heuristic algorithm LKH3, which can output near-optimal solutions.\n\nTo settle down your concerns, we use concorde to resolve three large datasets. We report the gap between LKH3 and concorde on TSP-1000 as follow, where negative gap means concorde performs better than LKH3.\n\n|           | Uniform      | Clustered    | Explosion   | Implosion    |\n|-----------|--------------|--------------|-------------|--------------|\n| Cost      | 23.164  | 14.095  | 16.052 | 20.169   |\n| Gap(\\%) | -0.248 | -0.016 | -0.073 | -0.102  |\n\nIt can be observed that LKH3 can reach the optima very nearly. However, due to unacceptable time consumption (one instance need more than 20 hours), concorde fails on the TSP-5000 and TSP-10000. \n\nIn the future, we will make the concorde-solved optimal values and solutions of each of 200 instances with four distributions in TSP-1000 all open source.\n\n\n--Q3: Formal proof for purity phenomenon.\n\nThank you for raising this important concern. For the random Euclidean TSP, we theoretically prove that under certain conditions, the probability of an edge with purity order $k$ being at the optimal solution is bounded by $\\frac{k!!}{4^{\\frac{k}{2}-1}(k+1)!!}$. Notably, this upper bound decreases monotonically with increasing $k$. This means that edges of higher purity order have a lower probability of forming the optimal solution, consistent with our findings. Furthermore, the negative exponential form of this upper bound indirectly confirms the purity law we propose. If the paper is accepted, the theorem and detailed analysis and proof will be added to the paper.\n\n\nTHEOREM: For edge $e_{xy}$, assume that $K_p(e_{xy})=k$ is an positive even number, $z_i \\in N_c(e_{xy})$ evenly distributed on both sides of $e_{xy}$, and the probability of each node being selected follows a uniform distribution.\nThen, the probability of $e_{xy}$ being at the optimal solution holds the following inequality:\n\n$P[e_{xy} \\in \\tau_{OPT}] \\leq \\frac{k!!}{4^{\\frac{k}{2}-1}(k+1)!!}.$\n\n Let $\\omega_{xy}$ denote the Hamilton Path formed by edge $e_{xy}$ and vertices $z_i \\in N_c(e_{xy})$, $\\tau_{\\omega_{xy}}$ denote the Hamilton Circle including $\\omega_{xy}$. Then, the following inequality holds:\n\n $P[e_{xy} \\in \\tau_{OPT}] \\leq P[$ edges in $\\tau_{\\omega_{xy}}$ do not cross $] \\leq P[$edges in $\\omega_{xy}$ do not cross $]$. \n\nIn the following, We will analyze the probability that no edges in $\\omega_{xy}$ cross and obtain an upper bound. We prove the theorem by induction.\n\nWhen $K_p(e_{xy})=k=2$, it can be proven by enumeration method.\n\nNow, we first assume that when $K_p(e_{xy})=k$, the following equation holds:\n\nP[ edges in $\\omega_{xy}$ do not cross $] = \\frac{k!!}{4^{k/2-1} (k+1)!!}$.\n\n\nIt means that among all $(k+1)!$ combinations of $\\omega_{xy}$, there are  $\\frac{(k!!)^2}{4^{{k/2}-1}}$ situations where the edges of $\\omega_{xy}$ do not cross.\n\n\nWhen $K_p(e_{xy})=k+2$, first, there are totally $(k+3)!$ combinations of $\\omega_{xy}$. Next, we consider the non-intersection structure based on case $k$.\nFor every $\\frac{(k!!)^2}{4^{{k/2}-1}}$ situations where the edges of $\\omega_{xy}$ do not cross, consider one side of $e_{xy}$ first. If adding a point still leaves no intersection, there are $k/2+1$ possible addition positions. Considering both sides symmetrically, there are $(k/2+1)^2=\\frac{(k+2)^2}{4}$ non-intersection cases. Therefore,\n\nP[ edges in $\\omega_{xy}$ do not cross $] = \\frac{\\frac{(k!!)^2}{4^{{k/2}-1}} \\cdot  \\frac{(k+2)^2}{4}}{(k+3)!} = \\frac{(k+2)!!}{4^{(k+2)/2-1} ((k+2)+1)!!}$.\n\nHence, we have finished the proof of \n$P[e_{xy} \\in \\tau_{OPT}] \\leq \\frac{k!!}{4^{\\frac{k}{2}-1}(k+1)!!}$.\n\nReference:\n\n[1] CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention, ICML 2025\n\n[2] SHIELD: Multi-task Multi-distribution Vehicle Routing Solver with Sparsity and Hierarchy, ICML 2025\n\n[3] Rethinking Light Decoder-based Solvers for Vehicle Routing Problems, ICLR 2025\n\n[4] PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimization, ICLR 2025\n\n[5] UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems, NeurIPS 2024\n\n[6] INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformer, ICML 2024\n\n[7] Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policy, IJCAI 2024\n\n[8] RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark"}, {"review_id": "0Ip4FgcsiZ", "reviewer": "Reviewer_iRH9", "summary": "This paper introduces Purity Law, a principle revealing that edge prevalence in optimal solutions of routing problems grows exponentially with the sparsity of surrounding vertices. The authors propose Purity Policy Optimization (PUPO) that aligns NCO solvers with this law to enhance the generalization ability. On TSP and CVRP tasks, they show that PUPO integrates seamlessly with popular neural solvers (e.g., ELG, INViT) to improve performance on large-scale and heterogeneous problems without increasing inference costs.", "questions": "1. How does the proven supermodularity property guide the algorithm design? Could you explain this in more detail? Furthermore, can this supermodularity property lead to theoretical approximation ratios?\n2. Can the purity cost be directly incorporated into the reward? Although the current purity cost method considers multi-step accumulation, the lack of a baseline or critic may result in high variance. Would integrating purity cost as part of the reward yield better results?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n1. The motivation of this paper is clear. The author first observed a common purity pattern in large-scale TSP instances and was inspired by this to propose a purity cost to guide policy training, encouraging the policy to favor solutions with a smaller overall purity order, achieving improvements in generalization performance in experiments.\n2. The proposed algorithm is novel and effective. The key technical contributions lie in uncovering a universal structural pattern and leveraging it to guide policy learning, demonstrating significant generalization gains in empirical evaluations. It make sense to me.\n\nWeaknesses\n1. Many experimental data in the paper are inconsistent with those in related works. For example, in the TSP100 data,  INViT reports a 0.95% gap and ELG reports a 0.22% gap, which differ significantly from the 5.86% and 2.61% shown in Table 1 of this paper. After comparing most of the experimental results in Table 1 and Table 2, I found substantial discrepancies with existing results. \n2. Based on the current experimental results, the proposed method appears to impair performance on small-scale problems. \n3. Although the paper proposes some theoretical aspects, they provide limited guidance for algorithm design. In particular, it lacks theoretical analysis of relevant performance metrics, such as the algorithm’s approximation ratio, sample complexity analysis related to reinforcement learning, or classical generalization error analysis, which limits the theoretical contributions of the paper. I would like to see more discussion related to algorithm design.", "was_revised": true, "final_justification": "Some of my concerns have been addressed. I decide to weakly accept it.", "rebuttal": "Thank you very much for your time and effort in reviewing our work. We feel glad to know you acknowledge our work is novel and effective, and believe our presenting and motivation are clear.\n\nWe will address each of your concerns in detail as follow.\n\n--Q1: Inconsistence between experimental data in this paper with those in related works?\n\nThanks for your thorough review. In our experiments, to ensure fairness, we conduct each training process for the model under the same hardware conditions and parameters (except for the learning rate). In the original INViT paper, all numerical experiments are performed on an NVIDIA RTX 4090. While in the original ELG paper, models are trained on NVIDIA RTX 6000 Ada with 48GB memory, tested on one NVIDIA RTX 4090. Whereas our experiments are implemented on an NVIDIA RTX 3090. Additionally, the selection of the starting point for the tour is random. These factors may account for the slight differences observed when compared to the results in related works. If the paper is accepted, we will make all the code and detailed training logs open source.\n\n\n\n--Q2: Performance decline on small-scale problems.\n\nThanks for your thorough review. The slight performance decline on small-scale problems derives from the underlying mechanism of implicit regularization of PUPO. Shown in Table 5, we can observe that the PUPO training reduces the sum of the parameter Frobenius norms. It results in an expected but reasonable trade-off on small, identically distributed datasets.\n\nWhen the scale and distribution of training data is limited and completely same with the test data, PUPO-trained model may underfit the specific patterns and noise of the training set. This is because regularization prevents the model from excessively memorizing \"details\" of the training data, which might be important for decision-making in a small, same-distributed setting. Vanilla-trained models are more likely to achieve near-optimal fit to the training set in this \"ideal\" small, same-distributed setting.\n\nHowever, during vanilla training, tour length serves as the sole reward signal. Lacking guidance from generalizable structure, the model often overfits to these specific patterns in the small training set, resulting in weak generalization. PUPO introduces purity information into the model training process, allowing the model to focus on generalizable patterns even in the small training set, significantly improving cross-distribution and larger-scale generalizability, which is potentially more challenging and relevant in the real world.\n\nOn multiple large-scale datasets (1000, 5000, and 10000), our algorithm achieves significant and consistent enhancements compared to vanilla training. In particular, as shown in Table 2, the PUPO-trained ELG-50 achieves a 68.58% improvement on the E-5000 of CVRP. On the distribution-shifted test sets (C, E, I, TSPLib and CVRPLib), the PUPO-trained model also achieves significant cross-distribution generalization, demonstrating the effectiveness of the implicit regularization introduced by PUPO in addressing data distribution-shifted generalization.\n\nIn future work, to balance the model's performance on small datasets, we will introduce a tuning parameter $\\alpha \\geq 0$ and generalize the Purity Weightings to $\\hat{W}(U_t, \\tau_{t+1}) = W^{\\alpha}(U_t, \\tau_{t+1})$ to adjust the implicit regularization degree. When $\\alpha$ reaches 0, PUPO degenerates to a vanilla policy gradient.\n\n\n--Q3: More discussion related to algorithm design.\n\nThank you for this suggestion. We supplemented the theoretical analysis on optimization error of PUPO. First, we denote \n$\\nabla V^{p_{\\theta}} = E_{p_{\\theta}(\\tau | \\mathcal{X})} \\Biggl[   \\sum \\limits_{t=2}^{N} \\left( L(\\tau) - b(X) \\right) W(U_{t-1}, \\tau_{t}) \\nabla \\log p_{\\theta}(\\tau_{t} | \\tau_{1:t-1}, X)  \\Biggr]$, \n\nand $\\widehat{\\nabla V^{p_{\\theta}}} = \\sum \\limits_{t=2}^{N} \\left( L(\\tau) - b(X) \\right) W(U_{t-1}, \\tau_{t}) \\nabla \\log p_{\\theta}(\\tau_{t} | \\tau_{1:t-1}, X) $.\n\nThe update rule of gradient ascent algorithm is $\\theta_{t+1} = \\theta_t + \\eta_t \\widehat{\\nabla V^{p_{\\theta}}}$.\n\n\nLet us say a function $f$ is $\\beta$-smooth if $||\\nabla f(\\theta)-\\nabla f(\\theta')|| \\leq \\beta||\\theta-\\theta'||$, where the norm $||\\cdot||$ is the Euclidean norm.\nAssume that for all $\\theta$, $V^{p_{\\theta}}$ is $\\beta$-smooth and bounded $V_{\\star}$. Suppose the variance is bounded as follows: \n$E [ ||\\widehat{\\nabla V^{p_{\\theta}}}-\\nabla V^{p_{\\theta}}||^2 ] \\leq \\sigma^2$.\nFor $t \\leq \\beta (V^*-V^{(0)})/\\sigma^2$, suppose we use a constant stepsize of $\\eta_t = 1/\\beta$, and thereafter, we use $\\eta_t = \\sqrt{2/(\\beta T)}$. For all $T$, we can obtain:\n\n$\\min\\limits_{t \\leq T} E[||\\nabla V^{(t)}||^2] \\leq \\frac{2 \\beta (V^*-V^{(0)})}{T} + \\sqrt{\\frac{2\\sigma^2}{T}}$\n\nThe proof method is similar to [1]. And this optimization error theorem confirms that our proposed algorithm can converge to stationary points.\n\nHowever, due to the black-box nature of neural networks, proving the approximation ratio and generalization error of learning methods is extremely difficult. The gap evaluation metric in this paper can experimentally reflect the function of the approximation ratio, showing the gap ratio between model performance and the optimal solution. In future work, we hope to provide more comprehensive algorithm design analysis from a theoretical perspective. The above optimization error analysis will be added to the appendix of this paper.\n\n--Q4: Guidance role of supermodularity property to algorithm design.\n\nThank you for raising this concern. In the late stages of the neural constructive solver's decision-making process, the set of unvisited nodes is quite narrow. Because the agent's early stages occupy underlying better future node selection options, it is likely to choose poor ones that are detrimental to generalization. However, in vanilla training, tour length is the only reward signal, which fails to identify this impact of late-stage decisions. These late-stage decisions, made within a narrow feasible set, are crucial for generalization. The increasing marginal returns of the supermodular function, Purity Availability, effectively capture this tail effect.\n\nInspired by this motivation, we constructed a Purity Availability metric with supermodular properties to measure the purity potential of the unvisited vertex set. On one hand, since Purity Availability represents the average minimum available purity order, higher values indicate that the state will not be able to generate highly pure structures in the future. For example, in the Figure 5 in appendix, the Purity Availability of strategies (a) and (b) at the current state are 1 and 0, respectively. It means that policy (b) possess ability to construct purer structures in the future. On the other hand, constrained by the necessity to select nodes only from the unvisited vertex set, later decision stages often lead to states that are unfavorable for generalization and difficult to distinguish under tour length metrics. \n\nDue to supermodularity, the marginal benefit of Purity Availability, $\\phi (U_t) - \\phi (U_{t-1})$, is greater at later stages, making the purity measure in the later decision phases more significant. Inspired by supermodularity, we designed the purity cost based on the marginal benefit of state and the purity order of the actions. Furthermore, we designed purity weights based on the concept of future discounting to comprehensively assess the future purity potential of intermediate states during policy transitions.\n\n\n--Q5: Incorporating purity cost directly into the reward.\n\nThank you for this suggestion. We use the sum of the pure orders of the edges in the tour as a regularization term and design the following modified loss function: $\\hat{L}(\\tau) = L(\\tau) + \\lambda \\sum_{(\\tau_i, \\tau_j) \\in \\tau}K_p(\\tau_i, \\tau_j).$\nBased on INViT-50-TSP, while maintaining the same experimental settings as in our paper, we trained the model with $\\lambda$ set to 1, 0.1, and 0.01. A larger $\\lambda$ indicates a higher importance of purity information in the loss function. The test results are as follows.\n\n|         | $\\lambda$ = 0.01   | $\\lambda$ = 0.1    | $\\lambda$ = 1      |         | $\\lambda$ = 0.01   |$\\lambda$ =  0.1    | $\\lambda$ = 1       |\n|---------|--------|--------|--------|---------|--------|--------|---------|\n| U-100   | 2.37   | 3.26   | 5.01   | E-100   | 2.37   | 3.18   | 4.69    |\n| U-1000  | 7.77   | 10.26  | 14.38  | E-1000  | 9.92   | 12.31  | 16.83   |\n| U-5000  | 9.88   | 13.03  | 18.69  | E-5000  | 12.51  | 15.14  | 20.99   |\n| U-10000 | 8.31   | 11.62  | 17.12  | E-10000 | 11.31  | 14.74  | 19.59   |\n| C-100   | 3.04   | 3.51   | 4.75   | I-100   | 2.59   | 3.30   | 4.72    |\n| C-1000  | 8.89   | 11.01  | 14.24  | I-1000  | 8.14   | 10.44  | 14.53   |\n| C-5000  | 10.56  | 14.16  | 17.98  | I-5000  | 10.16  | 13.41  | 18.82   |\n| C-10000 | 11.08  | 14.04  | 18.73  | I-10000 | 8.85   | 12.67  | 18.47   |\n\n\nWe can see that the test results for all three models are worse than those obtained with PUPO training. The degree of deterioration increases with increasing $\\lambda$. Explicitly incorporating purity information into the loss function can lead to a mix of purity information and length information, which can lead to situations where the degree of purity improves but length deteriorates, making it impossible to distinguish well between them. This prevents the model from effectively perceiving purity information during training.\n\n\n\nReference:\n\n[1] Reinforcement Learning: Theory and Algorithms. Alekh Agarwal, Nan Jiang, Sham M. Kakade, Wen Sun"}, {"review_id": "Hb3sxG6MQv", "reviewer": "Reviewer_VRAr", "summary": "This paper proposes the purity law for neural routing solvers. Based on the purity law, the authors introduce purity policy optimization (PUPO) to enhance the generalization of the neural routing solvers. Experiments demonstrate that PUPO can be integrated into popular solvers and improve the generalization ability in routing problems, including TSP and CVRP.", "questions": "1.\tCompared to Vanilla RL, PUPO uses purity weights in the loss function. I wonder whether the concept of purity law and purity weights can be applied to supervision-learning-based neural solvers.", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "This paper proposes a novel insight and an effective algorithm to solve combinatorial optimization. I would like to support the acceptance if the authors can address my concerns.\n\nStrengths：\n\n1.\tThe concept of purity law is impressive and interesting. The purity law is related to the generalizable structural patterns in routing problems, which is a novel insight.\n\n2.\tThe proposed PUPO can be easily integrated with a wide range of existing neural routing solvers. \n\n3.\tThe authors propose a solid theoretical analysis on the algorithm, introducing two key concepts purity availability and purity cost.\n\n4.\tThe writing of the paper is good.\n\nWeaknesses:\n\n1.\tThe authors may want to include more baselines in the experiments. The performance of traditional solvers, such as LKH3 and Concorde, should be considered.\n\n2.\tIn Tables 1 and 2, I find PUPO's performance worse than Vanilla. Since PUPO is trained on instances with scales 50 and 100, PUPO performs worse in the in-distribution instances. I encourage the authors to give a deeper explanation of the mechanism of implicit regularization.", "was_revised": true, "final_justification": "The authors have addressed my concerns on the performance comparison with traditional solvers and deeper insights into the purity law.   I would like to remain the score.", "rebuttal": "Thank you very much for your time and effort in reviewing our work. We feel very glad to know you acknowledge our purity is novel and impressive, find the theoretical analysis is solid, and believe that our paper is well written.\n\nWe will address each of your concerns in detail as follow.\n\n--Q1: Including concorde in the experiments.\n\nThank you for raising this concern. The test datasets used in this paper is from [1]. In the datasets with multi-distribution, TSP-100 is solved by Gurobi, an exact solver, so the solutions are guaranteed to be truly optimal. TSP-1000, TSP-5000 and TSP-10000 are solved by a SOTA heuristic algorithm LKH3, which can output near-optimal solutions.\nTo settle down your concerns, we use concorde to resolve three large datasets. We report the gap between LKH3 and concorde on TSP-1000 as follow, where negative gap means concorde performs better than LKH3.\n\n|           | Uniform      | Clustered    | Explosion   | Implosion    |\n|-----------|--------------|--------------|-------------|--------------|\n| Cost      | 23.164  | 14.095  | 16.052 | 20.169   |\n| Gap(\\%) | -0.248 | -0.016 | -0.073 | -0.102  |\n\n\nIt can be observed that LKH3 can reach the optima very nearly. However, due to unacceptable time consumption (one instance need more than 20 hours), concorde fails on the TSP-5000 and TSP-10000. In the future, we will make the concorde-solved optimal values and solutions of each of 200 instances with four distributions in TSP-1000 all open source.\n\n\n--Q2: Deeper explanation of the mechanism of implicit regularization.\n\nThank you for this concern. The slight performance decline on small-scale problems derives from the underlying mechanism of implicit regularization of PUPO. Shown in Table 5, we can observe that the PUPO training reduces the sum of the parameter Frobenius norms. It results in an expected but reasonable trade-off on small, identically distributed datasets.\n\nWhen the scale and distribution of training data is limited and completely same with the test data, PUPO-trained model may underfit the specific patterns and noise of the training set. This is because regularization prevents the model from excessively memorizing \"details\" of the training data, which might be important for decision-making in a small, same-distributed setting. Vanilla-trained models are more likely to achieve near-optimal fit to the training set in this \"ideal\" small, same-distributed setting.\n\nHowever, during vanilla training, tour length serves as the sole reward signal. Lacking guidance from generalizable structure, the model often overfits to these specific patterns in the small training set, resulting in weak generalization. PUPO introduces purity information into the model training process, allowing the model to focus on generalizable patterns even in the small training set, significantly improving cross-distribution and larger-scale generalizability, which is potentially more challenging and relevant in the real world.\n\nOn multiple large-scale datasets (1000, 5000, and 10000), our algorithm achieves significant and consistent enhancements compared to vanilla training. In particular, as shown in Table 2, the PUPO-trained ELG-50 achieves a 68.58% improvement on the E-5000 of CVRP. On the distribution-shifted test sets (C, E, I, TSPLib and CVRPLib), the PUPO-trained model also achieves significant cross-distribution generalization, demonstrating the effectiveness of the implicit regularization introduced by PUPO in addressing data distribution-shifted generalization.\n\nIn future work, to balance the model's performance on small datasets, we will introduce a tuning parameter $\\alpha \\geq 0$ and generalize the Purity Weightings to $\\hat{W}(U_t, \\tau_{t+1}) = W^{\\alpha}(U_t, \\tau_{t+1})$ to adjust the implicit regularization degree. When $\\alpha$ reaches 0, PUPO degenerates to a vanilla policy gradient.\n\n\n\n\n--Q3: More discussion on supervision-learning-based neural solvers.\nThank you for this suggestion. For the supervision-learning-based neural solvers, their loss function of imitation learning is as follows:\n$l = - \\frac{1}{N} \\sum_i (y_i \\mathop{\\log} p_i + (1-y_i) \\mathop{\\log} (1 - p_i) )$, where $y_i$ is optimal label.\n\nFollowing the PUPO in our paper, we propose the modified loss function as follow:\n$\\hat{l} = - \\frac{1}{N} \\sum_i (y_i C(U_{i-1}, \\tau_i) \\mathop{\\log} p_i + (1-y_i) C(U_{i-1}, \\tau_i) \\mathop{\\log} (1 - p_i) ).$\n\nWe then compare the two training methods using LEHD [2] as an example, testing them on a few instances of TSPLib. The results are shown below.\n\n|          | PUPO   | Vanilla |        | PUPO   | Vanilla |         | PUPO   | Vanilla  |\n|----------|--------|---------|--------|--------|---------|---------|--------|----------|\n| a280     | 6.41   | 5.41    | d2103  | 15.33  | 19.11   | u1060   | 14.77  | 15.11    |\n| berlin52 | 0.04   | 0.02    | eil51  | 2.29   | 1.44    | u1432   | 11.53  | 10.93    |\n| bier127  | 6.84   | 6.54    | eil76  | 3.25   | 3.17    | u1817   | 13.71  | 13.87    |\n| ch130    | 2.83   | 2.77    | eil101 | 4.77   | 4.16    | u2152   | 20.14  | 25.58    |\n| ch150    | 11.68  | 8.99    | fl417  | 10.93  | 9.93    | u2319   | 6.38   | 7.27     |\n| d198     | 11.03  | 11.01   | fl1400 | 23.40  | 25.81   | vm1084  | 11.14  | 13.67    |\n| d493     | 9.16   | 9.76    | fl1577 | 23.65  | 28.23   | vm1748  | 17.55  | 18.11    |\n| d657     | 9.84   | 11.21   | gil262 | 2.73   | 2.75    | fl3795  | 44.19  | 48.12    |\n| d1291    | 15.26  | 19.32   | u159   | 1.79   | 1.66    | fnl4461 | 25.71  | 29.08    |\n| d1655    | 19.47  | 23.08   | u574   | 7.18   | 7.81    | pcb3038 | 17.64  | 21.74    |\n\nAs can be seen, PUPO-training improves the model's generalization ability on larger scales, but may exhibit a trade-off on smaller instances. It's worth noting that due to limited time, neither method was fully trained. We believe that thorough training would further improve the performance of both models. A performance comparison of the two models after full training will be supplemented in the appendix.\n\nReference:\n\n[1] INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformer, ICML 2024\n\n[2] Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization, NeurIPS 23"}, {"review_id": "1uBxK3LH8r", "reviewer": "Reviewer_Kzrh", "summary": "The authors propose PUrity Policy Optimization (PUPO), a novel training framework that incorporates the Purity Law, a consistent structural pattern observed in routing problem solutions, into the policy optimization process. PUPO modifies the policy gradient to encourage the emergence of this structure during training, improving generalization across distributions and problem sizes without changing the model architecture. It is compatible with some existing neural solvers and enhances their performance without adding inference overhead.", "questions": "1. Is it possible to make a similar law for non-Euclidean problems, which are much more interesting and more important, because almost all real-life routing problems belong to this class?\n\n2. The statistical properties of the proposed measure of optimal solutions (purity order) appear remarkably stable across the four instance distributions considered. However, since this remains a heuristic observation, could it be possible to characterize the class of distributions for which the purity law holds? Alternatively, could one learn or design a distribution of instances that maximally violates the purity law?\n\n3. Given the apparent generality of the law, it is regrettable that it is leveraged only in a specific class of NCO algorithms (based on Reinforce). Another approach could be to incorporate purity orders as edge features in the instance input representation, making them accessible in an algorithm-agnostic way, whether REINFORCE-based or not, and even beyond RL? This could allow the algorithm to learn how best to exploit the proposed heuristic. \n\n4. Related to the above, there is an alternative NCO approach known as the 'heavy-decoder/no-encoder' paradigm ([1, 2] and a few following works), which is known for its excellent generalization capabilities and relies on imitation learning. Is it possible to apply your method to such types of learning algorithms?\nWhen talking about this paradigm, why did you not consider these works as baselines, especially given that they use the same experimental setup as your paper (training on TSP/VRP-100 and evaluating generalization)? Although they do not play with different instance distributions, comparisons on TSPLib and CVRPLib suggest they perform significantly better.\n\n5. You trained the method on problems of size 50 and 100, but can you confirm that you trained 4 different policies for every distribution (U, C, E, I)? NCO methods claim to generalize to distribution shift, and it would therefore have been interesting to measure the deterioration of performance of, say, INViT-50 trained on U and tested on C, compared to INViT-50 trained on U and tested on U, especially to view how this deterioration evolves when adding PUPO. One would expect it to diminish with PUPO.\n\n\n[1] Luo et al. Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization, NeurIPS 23\n\n[2] Drakulic et al. BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization, NeurIPS 23", "limitations": "This work has two main limitations: it is applicable to Euclidean routing problems with the REINFORCE learning algorithm.", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The proposed measure is intuitive, but original in the area of NCO\n- The statistical analysis is thoroughly conducted\n- The paper is well written,  logically structured, and presents an interesting perspective.\n\nWeaknesses:\n- The proposed measure is limited to Euclidean problems and involves not only Euclidean distance but also the scalar product.\n- The integration into the Reinforce algorithm is ad-hoc.", "was_revised": true, "final_justification": "During the rebuttal, the authors addressed both of my concerns and demonstrated that this work is applicable beyond the cases described in the initial submission.\n\nI clearly support its acceptance.", "rebuttal": "Thank you very much for your time and effort in reviewing our work. We feel very glad to know you acknowledge our work is intuitive and original, find the statistical analysis is thoroughly conducted, and believe that our paper is well written, logically structured, and presents an interesting perspective.\n\nWe will address each of your concerns in detail as follow.\n\n--Q1: Similar law for non-Euclidean problems?\n\n   Thank you for raising this important concern. In non-Euclidean problems, there is no longer direct connectivity between vertices, and the metric is given a priori by the edge cost matrix. Given $G=(V, E)$, we define purity order $K_p(e_{ij})$ in non-Euclidean routing problems as follow: \n\n$K _ p(e _ {ij}) = \\frac{max _{m _ i \\in M _ i} |\\xi _ {im _ i}| + max _ {m _ j \\in M _ j} |\\xi _ {jm _ j}|}{2} $\n, where $M _ i $ consists of all $ m _i =  \\arg\\max _ {m, l(\\xi _ {im}) \\leq l(e _ {ij})/2}  l(\\xi _ {im}) $, \n\nand $\\xi_{im}$ is the shortest path from vertex $v_i$ to $v_m$.\n\nTo understand it intuitively, we first need to find the shortest path starting from the two endpoints, which does not exceed half the length of the edge and has the largest length, and then define the purity order of the two end points as the average of the maximum number of nodes in the shortest path. We take an instance of the non-Euclidean TSP dataset of size 20 in [1] as an example and calculate the pure order according to the above definition. The purity order distribution is as follows:\n\n\n\n| Purity Order | Frequency | Purity Order | Frequency  |\n|--------------|-----------|--------------|------------|\n| 0            | 35        | 4            | 1          |\n| 1            | 11        | 5            | 0          |\n| 2            | 3         | 6            | 0          |\n| 3            | 0         | 7            | 0          |\n\n\nWe can observe that the purity order still exhibits a negative exponential law on non-Euclidean TSP instances. In the future, we will calculate the purity order distribution of optimal solutions for more non-Euclidean TSP instances and add them to the appendix of this paper.\n\n\n\n--Q2: More theoretical discussion on purity law.\n\n  Thank you for this suggestion. Regarding your first point, we also find the stability of the purity law under different distributions interesting. We speculate that certain types of vertex distributions in instances may satisfy persistent homology in the field of topology, under measured by the \"purity order on the optimal solution.\" However, we have not yet achieved a formal theoretical proof. In future work, we plan to explore more theoretical proofs of this relationship from the perspective of topological data analysis.\n\nYour second point is also interesting and inspiring. Taking the TSP as an example, for instances consisting of regular N-gon endpoints, the negative exponential law is not strictly satisfied. Because the purity order of the edges in the optimal solution is all 0. However, this can be viewed as a limiting case of the negative exponential law. Furthermore, we speculate that there should be special instances that theoretically violate the negative exponential law. In future work, we plan to theoretically construct such special instances or generate them through learning-based methods.\n\nFurthermore, we have rigorously proved an upper bound on the probability that an edge of purity order $k$ is located on the optimal solution under certain conditions. If you are interested, please refer to our response to Reviewer 8oG4.\n\n\n\n--Q3: Incorporating purity orders as instance input representation.\n\n  Thank you for this suggestion. On one hand, purity order can be incorporated as an edge feature into graph representation learning, such as Graph Convolutional Neural Networks architecture. On the other hand, purity order can be generalized from edges to certain vertex attributes to reflect the purity information of nodes in instances. In future work, we will explore more methods for incorporating purity information into representation learning.\n\n\n--Q4: Discussion on PUPO combined with heavy-decoder paradigm. \n\n  Thank you for this suggestion. The LEHD and BQ-NCO you mentioned are both excellent works, which use imitation learning for training. The loss function of imitation learning is as follows:\n$l = - \\frac{1}{N} \\sum_i (y_i \\mathop{\\log} p_i + (1-y_i) \\mathop{\\log} (1 - p_i) )$, where $y_i$ is optimal label.\n\nFollowing the PUPO in our paper, we propose the modified loss function as follow:\n$\\hat{l} = - \\frac{1}{N} \\sum_i (y_i C(U_{i-1}, \\tau_i) \\mathop{\\log} p_i + (1-y_i) C(U_{i-1}, \\tau_i) \\mathop{\\log} (1 - p_i) ).$\n\nWe then compare the two training methods using LEHD as an example, testing them on a few instances of TSPLib. The results are shown below.\n\n|          | PUPO   | Vanilla |        | PUPO   | Vanilla |         | PUPO   | Vanilla  |\n|----------|--------|---------|--------|--------|---------|---------|--------|----------|\n| a280     | 6.41   | 5.41    | d2103  | 15.33  | 19.11   | u1060   | 14.77  | 15.11    |\n| berlin52 | 0.04   | 0.02    | eil51  | 2.29   | 1.44    | u1432   | 11.53  | 10.93    |\n| bier127  | 6.84   | 6.54    | eil76  | 3.25   | 3.17    | u1817   | 13.71  | 13.87    |\n| ch130    | 2.83   | 2.77    | eil101 | 4.77   | 4.16    | u2152   | 20.14  | 25.58    |\n| ch150    | 11.68  | 8.99    | fl417  | 10.93  | 9.93    | u2319   | 6.38   | 7.27     |\n| d198     | 11.03  | 11.01   | fl1400 | 23.40  | 25.81   | vm1084  | 11.14  | 13.67    |\n| d493     | 9.16   | 9.76    | fl1577 | 23.65  | 28.23   | vm1748  | 17.55  | 18.11    |\n| d657     | 9.84   | 11.21   | gil262 | 2.73   | 2.75    | fl3795  | 44.19  | 48.12    |\n| d1291    | 15.26  | 19.32   | u159   | 1.79   | 1.66    | fnl4461 | 25.71  | 29.08    |\n| d1655    | 19.47  | 23.08   | u574   | 7.18   | 7.81    | pcb3038 | 17.64  | 21.74    |\n\n\nAs can be seen, PUPO-training improves the model's generalization ability on larger scales, but may exhibit a trade-off on smaller instances. It's worth noting that due to limited time, neither method was fully trained. We believe that thorough training would further improve the performance of both models. A performance comparison of the two models after full training will be supplemented in the appendix.\n\n\n\n\n--Q5: More specific details on training.\n\n  Thank you for raising this concern. In this paper, all models are trained on a uniform distribution and then directly tested on the U, C, E, and I distributions. The test results in this paper reflect the performance changes caused by the distribution shift you mentioned. From Table 1 and Table 2 in this paper, PUPO-training improves the model's generalization ability to distribution shift and scale increase.\n\n\nReference:\n\n[1] Matrix Encoding Networks for Neural Combinatorial Optimization, NeurIPS 2021"}]

Author rebuttal:

Meta-review: This work proposes and investigates a purity law for the routing problem, which is an interesting and important observation that "the proportion of different edges in the optimal solution follows a negative exponential law based on their purity orders across various instances," where the purity order is defined as a measure of vertex density around edges. During the rebuttal, a formal analysis is provided to further support this observation for Euclidean routing problems with random distribution. Based on the purity law, this work further proposes the Purity Policy Optimization (PUPO) training paradigm to improve the generalization ability for neural solvers. Experimental results show that PUPO can be integrated with different neural routing solvers to improve their generalization performance.

The reviewers find this paper well-written with clear motivation, the introduced purity law intuitive, elegant, and impressive, the proposed PUPO method novel, effective, and can be easily integrated into different neural routing solvers, and the experimental studies thorough with strong results. Some concerns have been raised on the REINFORCE training method, theoretical analysis, extension to non-Euclidean problems, extension to the "heavy-decoder/encoder" paradigm, experimental settings, and results. After the rebuttal, most of these concerns have been properly addressed. Finally, two reviewers vote to clearly accept this work, one reviewer leans toward weak acceptance, and one reviewer recommends a weak rejection. In the final justification, the most negative reviewer believes this paper is "substantially improved with theoretical results that prove its primary claim", the provable property is "conceptually clear and elegant", and the comparisons are "now thorough". 

I read the paper myself and fully agree with the reviewers that the introduced purity law is novel and impressive, and the proposed PUPO training method is effective with strong generalization performance. I appreciate the formal theoretical analysis provided in the rebuttal to support the observation of purity law, and believe this analysis has substantially improved the quality and impact of this work. Similar to Reviewer Kzrh, I also look forward to seeing the extended results on non-Euclidean problems and the family of BQ-NCO/LEHD methods on much larger scale instances. Therefore, I recommend a clear acceptance of this work.    

Please make sure all the discussion and revisions are carefully incorporated into the final paper, and make all the code and detailed training logs open source as promised.
Decision: Accept (poster)