Solving the Asymmetric Traveling Salesman Problem via Trace-Guided Cost Augmentation
Authors: Zhen Zhang
Javen Qinfeng Shi
Wee Sun Lee
Venue: NeurIPS 2025 poster ()
Keywords: TSP
Combinatorial Optimization
Primary area: optimization

Abstract: The Asymmetric Traveling Salesman Problem (ATSP) ranks among the most fundamental and notoriously difficult problems in combinatorial optimization. We propose a novel continuous relaxation framework for the Asymmetric Traveling Salesman Problem (ATSP) by leveraging differentiable constraints that encourage acyclic structures and valid permutations. Our approach integrates a differentiable trace-based Directed Acyclic Graph (DAG) constraint with a doubly stochastic matrix relaxation of the assignment problem, enabling gradient-based optimization over soft permutations. We develop a projected exponentiated gradient method with adaptive step size to minimize tour cost while satisfying the relaxed constraints. To recover high-quality discrete tours, we introduce a greedy post-processing procedure that iteratively corrects subtours using cost-aware cycle merging. Our method achieves state-of-the-art performance on standard asymmetric TSP benchmarks and demonstrates competitive scalability and accuracy, particularly on large or asymmetric instances where heuristic solvers such as LKH-3 struggle.

Solving Asymmetric Traveling Salesman Problem via Trace-Guided Cost Augmentation
Zhen Zhang
Javen Qingfeng Shi
'Responsible AI Research Centre Australian Institute for Machine Learning The University of Adelaide & &CSRIO zhen@zzhang org
'Responsible Al Research Centre
Australian Institute for Machine Learning
2hh University of Adelaide javen shi wwwesshheeeaeeeee @aiiidielaid..... edu au
Wee Sun Lee School of Computing National University of Singapore leews@comp. nus edu. 5g
Abstract
The Asymmetric Traveling Salesman Problem (ATSP) is one of the most funda- mental and notoriously challenging problems in combinatorial optimization. We propose a novel continuous relaxation framework for ATSP that leverages differ- entiable constraints encourage acyclic structures and valid permutations. Our approach integrates diffcrentiable trace-based Directed Acyclic Graph (DAG) constraint with a doubly stochastic matrix relaxation of the assignment problem, enabling gradient- gradient-based optimization over soft permutations. We further develop a projected exponentiated-grann -raddient method with adaptive step size to minimize tour cost while satisfying the relaxed constraints. To recover high-quality discrete tours, we introduce greedy post-processing procedure that iteratively eliminates subtours through cost-aware cycle merging. Empirically, state-of oatte-of-th-art
method achieves the-art art performance on standard asymmetric TSP benchmarks and demon- strates strong scalability and accuracy, particularly large highly asymmetric instances where heuristic solvers such as LKH-3 often struggle.
Introduction
The Asymmetric Traveling Salesman Problem (ATSP) of the most fundamental and notoriously challenging problems in combinatorial optimization. Many important combinatorial optimization (CO) problems are theoretically reducible ATSP, Recent work by Pan al. [22] has shown that such reductions are not only of theoretical interest but can also be practically feasible for certain small-scale CO tasks, suggesting that advances in ATSP solvers could yield broad benefits across the
CO landscape.
Although the symmetric TSP is special case of ATSP, solvers designed specifically for the asym- metric case often perform poorly on symmetric instances. Conversely, any ATSP instance can be transformed into symmetric TSP by doubling the number of nodes [9] enabling symmetric solvers to be applied to asymmetric problems. Consequently, much of the CO community has focused on the
symmetric TSP [ g 20 26), leading the development of increasingly effective handcrafted and learning-based heuristics. Recently, methods such as those proposed by Drakulic et al. 4 5) Pan al. (22) have employed reinforcement learning directly search for optimal ATSP tours. These approaches provide faster inference compared to state-of- are heuristics such as LKH-3
[ but typ-
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

ically yield lower-quality solutions- even though LKH-3 was originally developed for the symmetric TSP.
Assignment-problem (AP) relaxations have long been used to provide strong lower bounds within branch-and-bounde and branch-and-cut TSP solvers 17 [9], and they remain effective for large-scale asymmetric instances, Several constructive heuristics, including the Karp-Steele Patching (KSP) algorithm [12 [33 and its variants, attempt to lift assignment solutions into valid tours. However, based on existing open-source implementations, these heuristics often underperform relative to LKH-3, Interestingly, AP relaxations tend be tighter for asymmetric TSPs than for symmetric ones, motivating the development of stronger heuristics grounded in AP formulations.
A general TSP can be formulated ensuring that the solution forms exactly one cycle [ We observe that this constraint is equivalent to requiring all proper subgraphs of the assignment to be Directed Acyelic Graphs (DAGs). Inspired by
linear assignment problem with additional constraint
recent progress differentiable DAG learning [2 28 29). we propose a novel continuous relaxation of the TSP that incorporates DAG constraints into the assignment formulation. We show that the global minimum of this relaxed problem exactly recovers the true TSP solution.
Although the proposed relaxation is non-convex, we find empirically that local minima obtained via approximate projected gradient descent often yield high-quality solutions. In many cases, our method recovers valid tours with shorter lengths than those produced by LKH-3. For instances where the relaxed optimization does not directly yield a valid tour, we introduce a simple greedy post-processing heuristic to eliminate subtours and construct feasible solutions. Finally, we apply 2-opt local refinement to further improve tour quality. Together, these components constitute a new heuristic for solving general (asymmetric, non-metrie) TSP instances that consistently outperforms LKH-3, particularly on large-scale problems. When applied to small-scale symmetric TSPs, our method remains cumpeeiitvv-aachivviin slightly lower solution quality than LKH-3 but offering significantly faster runtime performance.
In summary, main contributions are:
Novel TSP formulation: novel exact continuous formulation that suppresses subtours via trace-based acyclicity loss.
Soft assignment optimization: A doubly stochastic matrix relaxation of ATSP solved via projected exponentiated gradient descent.
Efficient greedy decoding: A post-processing algorithm that reconstructs valid tours from fractional assignments with minimal additional cost.
Strong empirical performance: Extensive experiments show method outperforms
LKH-3 on ATSP benchmarks and scales well to large problem sizes.
Related Works
Learning- based TSP Solvers Recently, learning-based approaches have been increasingly applied to combinatorial optimization (CO) problems, including the Traveling Salesman Problem (TSP). While many existing works focus the Euclidean TSP, where inputs given as point coordinates
[6] [22 have extended these methods to handle general asymmetric TSPs. Kwon et al. [16] treat distance matrices directly as transformer input tokens, which is computationally inefficient and unsuitable for large graphs. Subsequent efficiently, enabling
14
15|
18
20
23 24 31], more recent studies 4 [5]
methods 4 22 address this limitation by encoding distance matrices
scalability to graphs with thousands of nodes. These approaches 4 5 16 22
generate tours in an
auto-regressive manner, formulating the tour-construction process as a Markov Decision Process (MDP). Reinforcement learning is then applied to optimize over the MDP, thereby avoiding reliance on expensive ground-truie optimal solutions.
In contrast to these auto-regressive frameworks, Min et al. (0 proposed a surrogate loss based on seeggmeent-probleen relaxations of the TSP. However, their approach is limited to the Euclidean setting and only enforces the absence of length-2 loops in the solution, necessitating a post-processing step construct valid tours.
seariing-hased solvers generally outperform classical heuristics such as LKH-3 terms of computa- tional efficiency, although they may produce slightly less accurate tours. In reinforcement learning

---

settings, nigh-qualing solutions from fast heuristics (even if suboptimal) can serve valuable offline data for off oolliolcy algorithms, potentially accelerating training and improving solution quality.
Beyond methods that directly generate tours from node coordinates or distance matrices, another branch-and-boume or local search policies. These approaches replace handcrafted heuristics in traditional solvers with learned decision mechanisms, leading more adaptive and data-driven optimization behavior.
line of research [27 30) focuses learning improved search strategies-
Assignment Problem Relaxations for TSP Relaxations of the Traveling Salesman Problem (TSP) based on the classical linear Assignment Problem (AP) have been extensively studied due to their computational efficiency and strong theoretical foundations 2 17. These relaxations typically involve solving a linear program in which the tour constraints are relaxed, allowing the solution to contain multiple disconnected subtours. To recover valid TSP tour, additional strategies such as iterative subtour elimination or branch-and- bouddd frameworks are employed [9]. Although AP relaxations do not always yield feasible tours directly, they provide tight lower bounds [6] and serve as key components in exact solvers and heuristic algorithms. Several courtconstruction heuristics have also been developed based AP relaxations often perform worse than modern LKH-3 solvers. For a more comprehensive discussion, we refer readers to Cirasella al. 2 Glover al. 77. and Önean al. [2
[ 13:: however, existing open-source implementations
Exact Continuous Relaxation of TSP
Let D I be the non-negative distance (or cost) matrix, where its entry di denotes the distance or cost of traveling from node i to node j. The general TSP seeks tour (i.e., a permutation of the nodes forming single cycle that visits each node exactly once) that minimizes the total travel cost. This can be formulated as:
min
D,X) = ΣV
dig
XE(0,I)axx
i= 1=
subject to
Zij 1 for all {I.....n.) (each node exits exactly once),
j=1
n Fij for all (I (each node is entered exactly once),
X forms single Hamiltonian cycle (no subtours).
Here, X is permutation matrix corresponding to single cycle over the nodes. The final constraint prohibits subtours-i.e.. disjoint cycles that do not span all nodes-ensuring that the solution corresponds to a valid TSP tour.
Differentiable DAG Constraints Recently, family of differentiable constraints for enforcing acyclicity in graphs was proposed the literature [25] 28 29). For any positive adjacency matrix X,
acyclicity can be enforced by the following constraint:
((X)
Σ
tr tr(x')= =
In this constraint, each term tr(X)) is strictly positive when X contains cycles of length i, since all entries of X are positive. Therefore, setting the total sum to zero guarantees that there are no cycles of any length, ensuring that X represents Directed Acyelic Graph (DAG).
Based on these differentiable DAG constraints, we propose a novel continuous relaxation of the TSP by enforcing that any proper subgraph of the assignment matrix X forms a DAG. This leads the following formulation:
min D
D, X
dy
subject
tr tx')) 0,
(3)
3

---

where D XX E [0, 1 X1 = 1, 1-x=11)11 is the set of doubly stochastic matrices of size n.
=1
One appealing property of this relaxation is its tightness, as stated below:
Proposition (Exactness of the Continuous Relaxation). The global minimum of the relaxed problem (3 coincides with the optimal solution of the original TSP.
Proof. To prove the result, it suffices to show that any fractional matrix X DD' cannot satisfy the constraint E tr(X)) ) 0. In other words, all feasible solutions must be permutation matrices representing Hamiltonian cycles.
The proof follows from the Birkhoff-voo Neumann theorem [0), which states that any doubly stochastic matrix E D can be expressed as a convex combination permutation matrices:
X O.P 0,20, 0: -1,
where P; are permutation matrices.
Assume for contradiction that fractional X D satisfies the constraint in Then its Birkhoff-von Neumann decomposition contains at least two distinct permutation matrices P. If any P. corresponds to a subtour (i.e., not single Hamiltonian cycle), then tr(P() > for some j < n, and hence tr tr(X)) ) > 0 for some j < n due to linearity and positivity. This violates the constraint R--1 tr X = 0, making X infeasible.
Even if all P; represent valid Hamiltonian cycles, convex combination of two or more distinet tours will produce fractional entries in X. These fractional values imply the presence of edges from multiple tours, which results the presence of subtours and nonzero traces X for some j n. Thus, X would again be infeasible.
Therefore, the only feasible solutions are permutation matrices representing single Hamiltonian cycles. Among them, the one minimizing (D, X) is exactly the TSP solution.
4 Trace Guided Tour Search
To efficiently optimize the relaxation in Equation (3. we introduce an auxiliary variable Y E Rax with elementwise constraints Y < O, and define the assignment matrix as X = exp(Y), where exponential applied elementwise. This reparameterization ensures that X strictly positive and facilitates optimization over the interior of the doubly stochastic polytope D Compared to optimizing directly over X, working the log-domain (i.e., optimizing Y) avoids boundary issues, improves numerical stability, and enables smooth gradients that more amenable to gradient-based learning methods. The relaxed optimization problem is then formulated as:
121
min D, (Dexp((Y)) = Σ Σ de exp(yi)) subject to tr Σ (exp( 0, EE
(5)
where D is the cost matrix, and the trace constraint eliminates self-loops and short cycles. By introducing a I Lagrange multiplier X, the constrained problem can be rewritten as the following unconstrained objective:
min EYD
J(Y) = (D,exp(Y)) + Atr Σ (exp(Y)').
(6)
The gradient of this objective with respect Y given by:
n-2 Σ
Vyf(Y) = D exp +
(1+
c cxp(Y),
(7)
==0
where @ denotes elementwise multiplication. This formulation enables efficient and scalable opti- mization while preserving the structural constraints required by the TSP.

---

Algorithm Approximate Projected Gradient Descent for Exponentiated TSP Relaxation
1: Input: Cost matrix D R=**, initial slep size a > O, scaling factor > O, max iterations T
2: Initialize Y --D
3: Compute initial assignment Tprev f- LinearAssignmenn(-
4: for t= I to 7 do
5:
Compute gradient:
n Σ (i exp(Y))
Vyf(Y) D exp((Y) + A
c eYp((Y)
6:
Update Y new t Y VY Project: X Sinkhorn (Y new)), )), Y new log X
7:
elementwise projection onto D
8:
Compute new assignment Tnew f- LinearAssignmentt new)
9:
if Nnww # ppev then a + -a/2
10:
11:
else
12:
a + 2a
13:
end if
14:
Y
< Y new Tprev f- Tnew
15:
if Tnew has only one loop then
16:
break end if
18:
end for
Output: Y. permutation Tnew
Approximate Projected Gradient Descent for Exponentiated TSP Relaxation: To optimize the exponentiated relaxation of the TSP problem, we propose an approximate projected gradient descent algorithm over the log-domain variable Y. The algorithm initializes Y as the negative of the cost matrix, Y < DD and iteratively updates using the gradient of the relaxed objective. At each step, the gradient is computed and used to update Y with a step size a. To maintain feasibility within the doubly stochastic set, apply Sinkhorn 3 normalization the exponentiated matrix exp(Y) and then project back to the tog-domain via (.). ensuring that cxp(Y) E D The step size a is dynamically adjusted based whether the solution to the linear assignment problem (using -Y as the cost) changes after the update: if does, the step size is reduced; otherwise, it is increased to accelerate convergence. This adaptive strategy helps balance exploration and stability. The process terminates either after fixed number of iterations or once a valid TSP tour (a single loop) is found in the assignment. The algorithm returns the optimized Y and the corresponding assignment matrix exp(Y).
Approximate
Gradient Computation: In our gradient expression, the term
Ei-3 e)) involves computing weighted sum of matrix powers, which can be computationally expensive. Although efficient approximations such as the truncated Neumann series proposed in Zhang multiplications, the cost remains significant for large instances due to the O(n²) complexity of matrix multiplication. To address this, we adopt lightweight approximation by substituting exp(Y) with the hard assignment matrix corresponding to the current solution Tpev- Since permutation matrices are sparse and binary, their powers are simply eyclic shifts, and the sum can be computed in Onn²) time. This approximation significantly accelerates training while preserving useful structural signals from the current assignment during optimization.
(28) can reduce the number of operations to O n) matrix
Greedy Tour Decoding from Invalid Assignments: Although the proposed optimization approach typically converges rapidly for asymmetric TSP instances, there exist hard cases where convergence valid permutation (i.e., single-loop tour) does not oceur. address such situations, we apply greedy decoding strategy to extract a valid TSP tour from the relaxed assignment matrix. Specifically, we begin by selecting a random starting node and iteratively follow the highest-assigned edge (i.e., the node with the largest assignment probability) to determine the next node in the tour. If the selected
5

---

Method
ATSP20
ATSP50
Avg. GAP
Median GAP
Runtime (s)
Avg. GAP
Median GAP
Runtime (s)
LKH-3 (10, 10000)
0.00%
0.00%
1.68
0.00%
0.00%
5.18
LKH-3 (1, 500)
0.02%
0.00%
0.02
1.00%
0.40%
0.060
LKH-3 (1, 10000)
0.0005%
0.00%
0,18
0.28%
0.00%
0.54
Ma(POENet
27.36%
27.80%
0.0067
688.67
675.04%
0,016
GOAL
36.50%
33.59%
0.002
108. 20%.29%
109.38%
0.0095
Ours
1.9%
0.08%
0.005
2.6%
0.8%
0.012
Table I: Comparison of methods on small-scale pure random ATSP (TSP20 and TSP50). GAP measured relative to LKH-3 (10, 10000). The results are average from 128 instances. The performance of learning based approaches is far worse than their reported results they trained on ATSP with triangle incquality and they failed to generalize to random ATSP.
Method
ATSP20
ATSP50
Avg. GAP
Median GAP
Runtime (S)
Avg. GAP
Median GAP
Runtime (s)
LKH-3 (10, 10000)
0.00%
0.00%
2.54
0.00%
0.00%
4.51
LKH-3 (1,
0.00%
0.00%
0.03
0.06%
0.00%
0.05
LKH-3 (1, 10000)
0.00%
0.00%
0,27
0.004%
0.00%
0.48
Ma(POENet
7.4%
5.3%
0.0063
1.4%
1.1%
0,016
GOAL
9.26%
10.15%
0.002
5.87%
5.83%
0.0095
Ours
0.97%
0.00%
0.006
0.6%
0.00%
0.009
Table 2: Comparison of methods small-scale random ATSP with triangle inequality problems (TSP20 and TSP50). GAP measured relative to L.HH3 (10, 10000). The results are average from 128 instances.
edge would result in the formation of premature loop revisiting node, instead choose the closest unvisited node according to the original cost matrix. This process continues until all nodes have been visited exactly once, ensuring the construction of a valid Hamiltonian cycle. This decoding heuristic is simple, efficient, and empirically effective in recovering feasible tours from imperfect or fractional assignments.
Time Complexity. The dominant computational cost in each iteration of the proposed algorithm lies in solving the linear assignment problem for approximating eYp(Y), which has worst-case time complexity of O(n²) when using the Hungarian algorithm. However, practice, the Hungarian algorithm is typically much faster due to early termination and efficient implementations. Addition- ally, viewing assignment step through the lens of primal-dual linear programming reveals an opportunity to reuse the dual variables warm starts for subsequent iterations, potentially accel- crating convergence. Alternatively, the assignment problem can also be solved using the Auction algorithm, which offers better parallelism and is more amenable to GPU implementation. This opens up promising directions for future work, where the entire optimization process could be ported to GPUs to achieve significant speed-ups and scalability for large-scale TSP instances.
Local Search Refinement. To further improve the quality of the obtained tour, our implementation applies simple 2-opt heuristic as a post-processing step. We observe that for asymmetric TSP instances, the 2-opt heuristic often brings negligible improvements due the directional nature of the cost structure. In contrast, for symmetric TSPs, the 2-opt refinement can lead to noticeable performance gains by eliminating crossing edges and reducing the overall tour length. While 2-opt lightweight and easy to implement, it may be suboptimal for larger or more complex instances. As future direction, one could consider replacing the 2-opt heuristic with more powerful local search methods such as the Lin fin-Keemighhn-HHeggau solution could serve as high-quality initialization for LKH, potentially reducing the number of local search iterations required and improving overall efficiency.
(LKH) algorithm [8] In such setup, our learned

---

Experimental Results
Hardware All experiments were conducted on a workstation equipped with an AMD Ryzen 3900X CPU, 128GB DDR4 memory, and an NVIDIA RTX 3090 GPU. The LKH-3 heuristic was implemented in C++ and executed in a single-threaded mode on the CPU. Our proposed method was implemented using Python and SciPy, and it was also executed utilizing the GPU. In contrast, all learning- based approaches (e.g., GOAL and MatPOENet) were executed on the GPU to leverage hardware acceleration during inference.
single CPU process without
Dataset We evaluate our method on randomly generated Asymmetric TSP (ATSP) instances of sizes 20, 50, 100, 200, 500, and 1000. Following prior works [16], the cost matrices for these instances are generated by sampling each entry independently from uniform distribution over the interval [0, 1]. Kwon et al. [16] add an post- post-processing procedure to ensure the triangle inequality in enforced in the generated ATSP, while we also consider the cases where the triangle inequality is not satisfied. For solvers that require integer- valued cost matrices, we scale the costs by 10 and round them the nearest integer preserve precision. Additionally, we evaluate symmetric TSP instances of sizes 20 and 50. In line with previous settings, we first sample n random points in 2D space from uniform distribution over (0, 1]², and use the Euclidean distances between these points to construct the symmetric cost matrices.
approach
Competitors We compare our method against several strong baselines, including both classical heuristics and recent learning-based approaches. Specifically, we consider LKH-3, state-of-th art heuristic algorithm for solving TSP, GOAL a reinforcement learning-based approach using graph neural networks, and MatPOENet [22], transformer- optimization problems. For GOAL and MatPOENet, we use their publicly released pretrained weights to ensure fair comparison. For LKH-3, we evaluate three configurations: (i) one with 500 search trials, (ii) one run with 10,000 search trials, and (iii) ten runs with 10,000 search trials each. These configurations allow to assess both the performance and robustness of LKH-3 under varying computational budgets. Exact solvers such as Gurobi and Concorde 1 are not compared as they are often too slow for large scale problems.
model for solving combinatorial
Method
ATSPI00
ATSP200
Avg. GAP
Median GAP
Runtime (s)
Avg. GAP
Median GAP
Runtime (s)
LKH-3 (10, 10000)
0.00%
0.00%
11.40
0.00%
0.00%
18.67
LKH-3 500)
5.38%
5.06%
0.13
12.59%
12.72%
0.27
LKH-3 (1, 10000)
1.06%
0.91%
1.19
2.02%
1.90%
2.03
MatPOENet
295.18%
295.62%
0.047
747.56%
750.27% %
0.165
GOAL
181.92%
177. 77%.47%
0.058
265.03%
261.43%
0.16
Ours
3.39%
1.77%
0.043
0.32%
-1.01 %
0.13
Table 3: Comparison of methods on medium-scale pure random ATSP problems (TSP100 and TSP200). GAP is measured relative to LKH-3 (10, 10000). The results are average from 128 instances. The performance of learning based approaches is far worse than their reported results as they are trained on ATSP with triangle inequality and they failed to generalize to random ATSP.
5.1 Asymmetric Problems
Small Scale Problems The comparison of running time and solution quality for small-scale problems is presented in Table and Table Our method, while yielding slightly worse average performance than LKH-3, demonstrates sigmificantly faster running times. For the learning-bast based approaches, which are trained on ATSP witht triangle inequality instances, their performance degrades substantially on purely random ATSP problems-underpenn underperforming all other competitors. This indicates that current neural combinatorial solvers may struggle to generalize across different problem distributions. Additionally, MatPOENet performs considerably worse on our test set than reported in its original paper, suggesting a potential distribution shift between the test scenarios.
Surprisingly, GOAL achieves the best performance on asymmetric TSP20 with triangle inequality, outperforming the state-of-the-un LKH-3 heuristic by a substantial margin. Given that GOAL was
7

---

Method
ATSPI00
ATSP200
Avg. GAP
Median GAP
Runtime (S)
Avg. GAP
Median GAP
Runtime (s)
LKH-3 (10, 10000)
0.00%
0.00%
7.31
0.00%
0.00%
11.69
LKH-3 (1, 500)
0.25%
0.11%
0.11
0.64%
0.06%
0.23
LKH-3 (1, 10000)
0.09%
0.00%
0.787
0.18%
0.01 %
1.34
MatPOENet
14.91%
13.84%
0.047
35.58%
35.72%
0.165
GOAL
3.83%
4.04%
0.058
0.77%
0.74%
0.44
Ours
0.52%
0.04%
0.027
0.16%
0.00%
0.10
Table 4: Comparison of methods on medium-scale random ATSP with triangle inequality problems (TSP100 and TSP200). GAP measured relative LKH-3 (10, 10000). The results are average from 128 instances. There may potentially be distribution shift between the training set of MatPOENet and our test set.
Method
ATSP500
ATSP1000
Avg. GAP
Median GAP
Runtime (8)
Avg. GAP
Median GAP
Runtime (8)
LKH-3 (10, 10000)
0.00%
0.00%
29.99
0.00%
0.00%
46.64
LKH-3 (1, 500)
24.47%
24.86%
1.08
51.23%
51.48%
3.81
LKH-3 (1, 10000)
2.50%
2.45%
3.85
3,25%
2.94%
7.91
MatPOENct
6400.51%
6400.50%
1.51
15017.16%
15016. 60%
10.24
GOAL
369.69%
369.40%
6.84
305.84%
304.62%
58.53
Ours
-10.77 %
-11.59%
0.87
-21.40%
-21.86%
5.22
Table 5: Comparison of methods on large-scale pure random ATSP problems (TSP500 and TSP1000).
GAP is measured relative to LKKH- (10, 10000). The results are average from 128 instances. Our approaches outperforms the state-of-the-arts LKH-3 heuristics in terms of solution quality. The performance of learning based approaches is far worse than their reported results as they are trained on ATSP with triangle inequality and they failed to generalize to random ATSP.
trained on 100-node triangle asymmetric instances, this result suggests that training neural solvers on large, structured, and challenging problems may enhance their generalization to smaller problem instances.
Medium and Large Scale Problems The comparison of running time and solution quality for medium- and large-scale problems is presented in Table Table Table and Table Consistent with the small-scale setting, learning- purely random asymmetric TSPs. In these settings, our algorithm outperforms LKH-3(1,500) for graphs with more than 100 nodes, and even surpasses nodes. As the graph size increases, our method increasingly outperforms all LKH-3 heuristics, with performance gap becoming more pronounced for larger instances. On 1000-node problems, our algorithm achieves over 20 % improvement compared to LKH-3(10, 1000000) and over 70% compared to LKH-3(1,500), Meanwhile, our runtime on large graphs is comparable to that of LKH-3(1,500) and remains faster than the learning- based approaches. On asymmetric TSPs with triangle inequality, similar trends are observed. Our method continues to outperform LKH-3 on large graphs, although the performance margin is smaller compared to the purely random setting.
approaches perform significantly worse than others on
10000) for graphs with more than 200
In terms of running time, it notable that, despite our implementation its execution speed is often faster than that of LKH-3. On very large graphs, our method can outper- approaches, even when those methods are accelerated by GPUs. Furthermore, most operations in our algorithm are amenable to parallel execution and could potentially benefit significantly from GPU acceleration.
being carefully optimized,
form learning-base
5.2 Symmetric Problems
Although our algorithm not specifically designed for symmetric TSPs and does not exploit any symmetry properties, we evaluated its performance small-scale symmetric instances. The results are presented Table 7 asymmetric TSPs.
The performance trends closely resemble those observed on triangle

---

Method
ATSP500
ATSP1000
Avg. GAP
Median GAP
Runtime (s)
Avg. GAP
Median GAP
Runtime (s)
LKH-3 (10, 10000)
0.00%
0.00%
20.88
0.00%
0.00%
36.72
LKH-3 (1, 500)
1.08%
1.00%
1.02
51.23%
51.48%
3.93
LKH-3 (1, 10000)
0.25%
0.24%
2.93
3.25%
2.94%
7.05
MatPOENet
12.48%
112.19%
1.50
156.48%
156.24%
10.21
GOAL
1.07%
1.01 %
6.85
1.266
1.22%
58.48
Ours
-0.06
-0.11% %
0.74
-0.35 %
-0.36
5.10
Table 6: Comparison of methods on large-scale random ATSP with triangle inequality problems (TSP500 and TSP1000). GAP is measured relative to LKH-3 (10, 10000). The results are average from 128 instances. Our approaches outperforms the state-of-the-arss LKH-3 heuristics in terms of solution quality.
Method
TSP20
TSP50
Avg. GAP
Median GAP
Runtime
Avg. GAP
Median GAP
Runtime (s)
LKH-3 (10, 10000)
0.00%
0.00%
3.21
0.00%
0.00%
4.51
LKH-3 50,)
0.00%
0.00%
0.03
0.06%
0.00%
0.05
LKH-3 (1, 10000)
0.00%
0.00%
0.33
0.004%
0.00%
0.48
MatPOENet
1.50%
1.25%
0.0064
0.63%
0.58% %
0.015
GOAL
14.06%
15.14%
0.002
14.34%
15.18%
0,0095
Ours
0.04%
0.00%
0.013
0.86%
0.66%
0.094
Table 7: Comparison of methods on small-scale random symmetric TSP problems (TSP20 and
TSP50). GAP is measured relative to LKH-3 (10, 10000). The results are average from 128 instances.
6 Conclusions and Future Works
In this work, we introduced novel continuous relaxation framework for the Asymmetric Traveling Salesman Problem (ATSP) that combines differentiable acyclicity constraints with doubly stochastic matrix relaxations. Our key innovation lies in the formulation of ATSP as a constrained optimization problem where trace-based DAG constraints naturally eliminate subtours while maintaining differen- tiability for gradient-baat based optimization. The proposed projected exponentiated gradient method with adaptive step sizes demonstrates efficient convergence properties, and our greedy post-processing procedure effectively recovers valid tours from fractional assignments.
Through extensive experiments standard benchmarks, we have shown that method achieves state-of-the-art performance on asymmetric TSP instances, particularly excelling on large-scale problems where traditional heuristics like LKH-3 struggle. The results reveal several important insights: (1) our continuous relaxation provides a tight formulation that frequently converges to valid tours without post-processing. (2) the approach scales favorably with problem size, maintaining both computational efficiency and solution quality, and (3) the method remains competitive even on symmetric TSP instances despite not being specifically designed for them.
The success our framework suggests several promising directions for future research. First, differentiable nature of our formulation makes it potentially amenable to integration with learning- based approaches, where the solver could be trained to predict good initializations or adaptive penalty parameters. Second, the trace-based constraints may generalize to other combinatorial optimization problems that require acyclic substructures. Finally, investigating more sophisticated optimization techniques within our framework could lead to further improvements in both solution quality and computational efficiency.
This work bridges important gap between continuous relaxations and discrete combinatorial optimization, offering a new perspective on solving challenging problems like ATSP through dif- ferentiable programming. The demonstrated effectiveness of our approach on large-scale instances suggests that similar techniques could prove valuable for other NP-hard optimization problems where traditional methods face scalability limitations.

---

Acknowledgments and Disclosure of Funding
This research is supported by Responsible AI Research Center (RAIR) and the Ministry of Education, Singapore, under its Academic Research Fund Tier (A-80018 10000814-000 8814-00-00..
10

---

References
[1] David L Applegate, Robert E Bixby, Vašek Chvátal, William Cook, Daniel G Espinoza, Marcos Goycoolea. and Keld Helsgaun. Certification of an optimal isp tour through 85,90 500000 cities. Operations Research Letters. 37(1):11-15, 2009.
[2] Jill Cirasella, David S Johnson, Lyle A McGeoch, and Weixiong Zhang. The asymmetric traveling salesman problem: Algorithms, instance generators, and tests. In Workshop on algorithm engineering and experimentation, pages 32 22-59. Springer, 2001.
[3] Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26, 2013.
[4] Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Mare Andreoli. Bq-nco: Bisimulation quotienting for efficient neural combinatorial optimization. Advances in Neural Information Processing Systems, 36:77416 774229, 2023.
[5] Darko Drakulic. Sofia Michel, and Jean-Mare Andreoli. Goal: A generalist combinatorial optimization agent learner. In The Thirteenth International Conference on Learning Representations, 2024.
[6] Alan Frieze and Gregory B Sorkin. The probabilistic relationship between the assignment and asymmetric traveling salesman problems. SIAM Journal on Computing, 36(5):1435-1453 2007.
[7) Fred Glover, Gregory Gutin, Anders Yeo, and Alexey Zverovich. Construction heuristics for the asymmetric tsp. European Journal of Operational Research, 129(3):555 568, 2001.
[8] Keld Helsgaun. An extension of the lin keemighan-hclsgaunn tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 12:966-980, 2017.
[91 Karla L Hoffman, Manfred Padberg, Giovanni Rinaldi, et al. Traveling salesman problem. Encyclopedia of operations research and management science, 111573-15788 2013.
[10] GLENN Hurlbert. A short proof of the birkhoff- von neumann theorem. preprint (unpublishhed), 2008.
[11] Chaitanya K Joshi, Thomas Laurent. and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.0 01227, 2019.
[12] Richard M Karp. A patching algorithm for the nonsymmetric traveling-salesman salesman problem. SIAM Journal 1979.
Computingg 8(4):561-
[13] Richard M Karp and J Michael Steele. Probabilistic analysis of heuristics. The traveling salesman problem, pages 181-205, 1985.
[14] Wouter Kool, Herke van Hoof. and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations. 2019.
[15] 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 22198, 2020.
[16] Yeong-Dat Dae Kwon, Jinho Choo, Iljoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. Advances in Neural Information Processing Systems, 34:5138-5141 2021.
[17] Gilbert Laporte. The traveling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(2):231-247 1992.
[18] Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. T2t: From distribution learning in training to gradient scarch in testing for combinatorial optimization. Advances in Neural Information Processing Systems, 36:50020- 1..50020-50000. 2023.
[19] Donald L Miller and Joseph F Pekny. Exact solution of large asymmetric traveling salesman problems. Science, 251 (4495),, 1991.
[20] Yimeng Min, Yiwei Bai, and Carla P Gomes. Unsupervised learning for solving the travelling salesman problem. Advances in Neural Information Processing Systems, 36:4726444777 472788, 2023.
[21] Temel Öncan, Kuban Alunel, and Gilbert Laporte. A comparative analysis of several asymmetric traveling salesman problem formulations. Computers & Operations Research, 36(3):637-655 654, 2009.
[22] Wenzheng Pan, Hao Xiong, Jiale Ma, Wentao Zhao, Yang Li. and Junchi Yan. UniCO: On unified combinatorial optimization via problem reduction matrix- general tsp. In The Thirteenth International Conference on Learning Representations, 2025.
[23] Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. Dimes: A differentiable meta solver for combinatorial optimization problems. Advances in Neural Information Processing Systems, 35:25531 -25546, 2022.
[24] Zhiqing Sun and Yiming Yang. Difusco: Graph- based diffusion solvers for combinatorial optimization. Advances in neural information processing systems,
2023.
11

---

[25] Dennis Wei, Tian Gao, and Yue Yu. Dags with No Fears: A closer look at continuous optimization for learning bayesian networks. Advances in Neural Information Processing Systems, 33:3895-3906, 2020.
[26] Yifan Xia, Xianliang Yang, Zichuan Liu, Zhihao Liu, Lei Song. and Jiang Bian. Position: Rethinking post-hoc search search-based neural approaches for solving large-scale traveling salesman problems. arXiv preprint 2406 03503, 2024.
[27] 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-timc. In Proceedings of the
AAAI Conference on Artificial Intelligence, volume 38, pages 20284-20292. 2024.
(28) Zhen Zhang, Ignavier Ng, Dong Gong, Yuhang Liu, Ehsan Abbasnejad, Mingming Gong, Kun Zhang, and Javen Qinfeng Shi. Truncated matrix power iteration for differentiable dag learning. Advances in Neural Information Processing Systems, 35:1 15:18390-18400 2022.
[29] Zhen 7hang, Ignavier Ng. Dong Gong, Yuhang Liu, Mingming Gong, Biwei Huang, Kun Zhang, Anton van den Hengel, and Javen Qinfeng Shi. Analytic dag constraints for differentiahle dag learning. arXiv preprint arXiv:2503. 19218, 2025.
[30] Jiongzii Zheng, Kun He, Jianrong Zhou, Yan Jin, Chu-Min Combining reinforcement learning with han-kernighan-helssaaen algorithm for the traveling salesman problem. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 12445 12452, 2021.
[31] Zhi Zheng. Changliang Zhou, Tong Xialiang, Mingxuan Yuan, and Zhenkun Wang. Ude: A unified neural divide-and conquer framework for large-scale combinatorial optimization problems. arXiv preprint arXiv:2407.00:1 12, 2024.
12

---

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: Justification: The main contributions of our work emphasized throughout the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or 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.
It is fine to include aspirational goals as motivation long is clear that these goals are 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 clearly stated that our approaches are for asymmetric TSPs and may not have good performance symmetric cases.
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-speciiiatiinn 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 on 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?
13

---

Answer: [Yes]
Justification:
We proved that our continuous relaxation is exact.
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 in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should 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 not)?
Question:
Answer: [Yes]
Justification: The pseudo code of the algorithm is given, and an implementation based on that would work.
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 a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be 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 reproducibility may be tricky in some cases, in which case authors are welcome 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 possible for other researchers to have some path reproducing verifying the results. 5. Open access to data and code
14

---

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?
Question:
Answer: [No]
Justification:
The code will be made publication after publication.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /ttee//ggudddeeeedSuuuummbbbba ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The construction of the dataset is clear stated the experimental section.
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 to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification:
We not only provide average results, but also provide median results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
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.)
15

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state 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 of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
It is clearly stated in the experiments section.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well 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 make 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 httpp:///horrpss.ccphpppp//cccea
Answer: [Yes]
Justification:
We follow the code ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS 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 or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: This paper presents work whose goal is advance the field Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Guidelines:
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 societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied 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 to point out that an 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 to 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 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 system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not have such problem.
Guidelines:
The answer NA means that the paper poses no 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 to 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 we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: 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?
Answer: [Yes]
Justification: All third-party -arty assets used in this paper-such such as code, datasets, and mod- els are properly credited, with licenses and terms of use explicitly acknowledged.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.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.
If assets are released, the license, copyright information, and terms of use in the Datasets.papersstt
package should be provided. For popular datasets, paperswi thcode. cww/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The dataset generation process is clearly stated.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/cood/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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. Crowdsoureing 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 screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We do not have any human experiments.
Guidelines:
The answer NA means that the paper does not 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 the main paper.
According the NeurIPS 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We do not have any human experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending 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 expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: This research does not involve LLMs any important, original, non- standard components.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
19

---

Appendix: Solving Asymmetric Traveling Salesman Problem via Trace-Guided Cost Augmentation
A Linear Assignment Problem
The linear assignment problem aims to determine permutation matrix that minimizes the total assignment cost given by matrix D R=x", whose entries are denoted by dej. Let X Rax= be the assignment matrix, where 2ij 1 indicates that row i is assigned to column j, and zero otherwise. The problem can be formulated the following linear program:
minimize
Σ
==
subject to
Tij =1 for all i = 1,..., n,
(8)
j=1
Tij = for all j = 1, ,,,
Fij 2 0 for all i,j.
The dual problem introduces variables u, and v/ corresponding to the row and column constraints, respectively, and is given by:
maximize
Σ
Vj
(9)
subject
+ 0j S dig
for all i,
Strong duality holds for this problem, guarantecing that the optimal values of the primal and dual problems are equal when feasible solution exists.
The Hungarian Algorithm is, in fact, primal-dual method for solving the Linear Assignment Problem (LAP). This insight allows us to exploit the structure Algorithm[]] where multiple LAPs solved iteratively. Specifically, use them as the initialization for subsequent runs of the Hungarian Algorithm. This warm-start strategy significantly accelerates convergence, the optimal dual variables often remain close across successive LAP instances.
retain the previously optimal dual variables and v and
B Further Refining Performance by Branch-and-Bound
We further refined our implementation by incorporating two key strategies: (1) reusing the dual variables and as described in the previous section, and (2) introducing simple branch-and-boum heuristic, In our branch-and- aarochh-nn-bbuudd strategy, we first solve the Linear Assignment Problem (LAP) to obtain lower bound for the ATSP instance. We then identify the edge with the highest cost in the LAP solution and branch on For each branch, we apply Algorithm to compute a potentially global upper bound, while the LAP provides a local lower bound. Our heuristic allows up to five branch-and- bound iterations.
With these enhancements, the results on large-scale ATSP instances satisfying the triangle inequality are presented Table g As shown, reusing the dual variables accelerates our algorithm by up to factor of five compared to the original implementation. Additionally, the branch-and-bound strategy offers further performance improvements. Similar gains are observed on purely random ATSP instances, shown in Table
20

---

Method
TSPS00
TSP1000
Avg. GAP
Median GAP
Runtime (s)
Avg. GAP
Median GAP
Runtime (8)
LKH-3 (10, 10000)
0.00%
0.00%
20.88
0.00%
0.00%
36.72
LKH-3 (1, 500)
1.08%
1.00%
1.02
51.23%
51.48%
3.93
LKH-3 (1, 10000)
0.25%
0.24%
2.93
3.25%
2.94%
7.05
MatPOENet
112.48%
112.19%
1.50
156.48%
156.24%
10.21
GOAL
1.07%
1.01 %
6.85
1.26%
1.22%
58.48
Ours
-0.06 %
-0.11%
0.74
-0.35%
-0.36%
5.10
Ours-reuse u, v)
-0.04%
-0.09%
0.19
-0.55%
-0.36%
0.97
Ours-reuse u, v BnB -0.11%
-0.12%
0.70
-0.38% %
-0.38 %
2.91
Table 8: Comparison of methods on large-scale random ATSP with triangle inequality problems (TSP500 and TSP1000). GAP is measured relative to LKH-3 (10, 10000). The results are average from 128 instances. Our approaches outperforms the state-of-the-arts LKH-3 heuristics terms of solution quality.
Method
ATSP500
ATSP1000
Avg. GAP
Median GAP
Runtime (8)
Avg. GAP
Median GAP
Runtime (8)
LKH-3 (10, 10000)
0.00%
0.00%
29.99
0.00%
0.00%
LKH-3 (1, 500)
24.47%
24.86%
1.08
51.23%
51.48%
3.81
LKH-3 (1, 10000)
2.50%
2.45%
3.85
3.25%
2.94%
7.91
MatPOENet
6400.51 5
6400.50%
1.51
15017.1695
15016.7055
10.24
GOAL
369 69%
369.40%
6.84
305.84%
304.62%
58.53
Ours
10.77 %
-11.5%%
0.87
-21.40%
-21.86%
5.22
Ours-reuse u, v) Ours-reuse u. v BnB -1.88%
-00.9%%
-11.67%
0.33
-21.49%
-21.98%
1.54
-12.02%
0.84
22.31 %
-22.39%
3.63
Table 9: Comparison of methods on large-scale pure random ATSP problems (TSP500 and TSP1000).
GAP is measured relative to LKH-3 (10, 10000). The results average from 128 instances. Our approaches outperforms the state-of-the-art LKH-3 hcuristics in terms of solution quality. The performance of learning based approaches is far worse than their reported results they trained on ATSP with triangle inequality and they failed to generalize to random ATSP.
C Experimental Results TSPLIB instances
We evaluated our algorithm on large-scale ATSP benchmark instances from TSPLIB, particularly those derived from stacker crane problems. Our method consistently outperforms LKH-3 (1-100) in terms of solution quality while also requiring less computational time. These results demonstrate the practical effectiveness of our approach real-world structured benchmarks, further validating its scalability and competitiveness beyond synthetic instances.
D
Comparison with ILP Solver
conducted a preliminary comparison between our method and an exact ILP solver on both symmetric and asymmetric TSP instances. Specifically, we tested the solver on 100-node symmetric problems and 500-node asymmetric problems and found that the IIP solver was able to return optimal solutions within reasonable time budget.
Due to time constraints, evaluated both methods on 10 randomly sampled instances for each case. The results are summarized below. While the ILP solver guarantees optimality, our method achieves competitive solution quality with significantly faster runtimes, particularly for larger asymmetric instances-highllee its scalability and practical utility for large-scale problems.
D.1 Performance comparison on 100-node symmetric TSP problems
D.2 Performance comparison 500-node asymmetric TSP problems
21

---

Table 10: Comparison of algorithms on asymmetric TSP benchmark instances.
Instance
Algorithm
Best Known Result
Running Time (s)
Result
LKH(I-100)
1.46
1388
LKH((-10000)
3.38
1346
rbg323
LKH(10-10000)
1326
20.32
1346
Ours
0.42
1360
Ours (no 2-opt)
0.20
1365
LKH((-100))
1.67
1294
LKH((110000)
4.03
1175
rbg358
LKH(10-10000)
1163
25.16
1175
Ours
0.09
1180
Ours (no 2-opt)
0.04
1180
LKH(1-100)
6.27
2536
LKH((-10000)
26.99
2498
rbg403
LKH(10-10000)
2465
9.06
2498
Ours
1.53
2473
Ours (no 2-opt)
1.28
2473
LKH(1-100)
5,44
2813
LKH 1-1((110)))))
7.87
2762
rbg443
LKH
2720
30.06
2756
Ours
0.52
2760
Ours (no 2-opt)
0.27
2760
Table 11: Performance comparison 100-node symmetric TSP problems.
Algorithm
Running Time (s)
Ratio to Optimal (Mean)
Ratio to Optimal (Median)
LKH(1-100)
0.07
0.61%
0.17%
LKH(1-
1.24
0.12%
0.00%
(K0000010000)
12.14
0.00%
0.00%
Gurobi
2.06
0.00%
0.00%
Ours (no local search)
0.03
15.2%
14.4%
Ours (local search)
0.05
1.47%
1.35%
Table 12: Performance comparison on 500-node asymmetric TSP problems.
Algorithm
Running Time (S)
Ratio to Optimal (Mean)
Ratio to Optimal (Median)
LKH(I-100)
0.87
2.22%
0.17%
LKH(1-10000)
2.82
0.45%
0.00%
LKH(10-10000)
20.23
0.18%
0.00%
Gurobi
6.36
0.00%
0.00%
Ours (no local search)
0.17
0.005%
0,001 %
Ours (local search)
0.30
0.005%
0.001%
22


Reviews:
[{"review_id": "PPUigYSHZy", "reviewer": "Reviewer_4nDe", "summary": "This paper proposes a new continuous relaxation framework for the ATSP using trace-based acyclicity constraints and doubly stochastic matrix optimization. The method integrates differentiable DAG constraints to eliminate subtours, employs projected exponentiated gradient descent for optimization, and uses a greedy post-processing step to recover valid tours. Experiments demonstrate state-of-the-art performance on large-scale ATSP instances, outperforming LKH-3 and learning-based baselines.", "questions": "I don't have specific questions.", "limitations": "n/a", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I have to say that I am usually working on the approximation algorithms for the network design problem (etc., approximating ATSP). By reading the abstract, I thought this work was related to my field. But, it turns out that it goes beyond my experience after reading the whole paper. I am not the right person to judge the contribution and novelty of the paper. \n\nFrom my perspective, the paper has the following strengths:\n\n1. The idea of using trace-based constraints looks interesting to me. This approach is to enforce acyclicity in ATSP relaxations, and Proposition 1 establishes that the global minimum of the relaxed problem recovers the exact TSP solution; this is also an interesting idea to me.\n\n2. From my view, the gradient approximation (using hard assignments) efficiently addresses the high cost of matrix power computations. However, I don't know whether it's computationally practical (e.g., easy to implement) or not.\n\n3. This paper gives competitive results on symmetric TSPs (as shown in Table 7), suggesting potential generality beyond ATSP.\n\nThe main weakness that I can see is that:\n\nThe non-convex optimization (Equation 6) lacks a theoretical analysis of convergence rates or approximation bounds. The adaptive step size heuristic is pragmatic but ad hoc. This probably can become a big problem in other datasets.", "was_revised": true, "final_justification": "The authors addressed my concern during the rebuttal, and thus, I will keep my score. But this paper goes beyond my experience, so please take my review with caution.", "rebuttal": "Thank you for your insightful comments. We would like to offer the following clarifications regarding the approximation properties of Eq. (6).\n\n### Approximation Properties of Eq. (6)\n\nThe constraint term in Eq. (6), $\\operatorname{tr}\\left(\\sum_{i=1}^{n-1} \\mathrm{exp}(\\mathbf{Y})^i\\right)$, is zero **if and only if** $\\mathrm{exp}(\\mathbf{Y})$ corresponds to a valid Hamiltonian tour. Therefore, when the Lagrange multiplier $\\lambda$ is sufficiently large, the relaxation in Eq. (6) becomes exact—i.e., the global minimizer of the relaxed problem coincides with the solution of the original TSP.\n\nHowever, Eq. (6) defines a non-convex optimization problem. As with other non-convex objectives, gradient-based methods can generally only guarantee convergence to a local minimum. If the exact gradient is used and the step size is selected in the interval $[1, 2]$, the convergence rate of the projected exponentiated gradient or  Frank-Wolfe method for solving Eq. (6) is $\\mathcal{O}(1/\\sqrt{t})$ [1].\n\nWhen using **approximate gradients**—as we do in our implementation for efficiency—the convergence rate becomes more difficult to characterize formally. This remains an open theoretical question, and we acknowledge it as a direction for future work.\n\nThat said, we observe empirically that the use of approximate gradients **yields better performance** in practice compared to exact gradients. This is likely due to reduced noise in gradient estimation and improved numerical stability during training.\n\nWe thank the reviewer again for raising this important point.\n\n**References:**\n\n[1] Lacoste-Julien, Simon. *Convergence rate of Frank-Wolfe for non-convex objectives*. arXiv preprint arXiv:1607.00345 (2016).  \n[2] Conn, Andrew R., et al. *Global convergence of a class of trust region algorithms for optimization using inexact projections on convex constraints*. SIAM Journal on Optimization 3.1 (1993): 164–221."}, {"review_id": "iXhnzCwYm9", "reviewer": "Reviewer_iiun", "summary": "The authors present a local search algorithm for finding solutions to the TSP. The algorithm is based upon incorporating a differentiable formulation of the constraints into the objective and subsequently applying gradient descent to find solutions. Additionally, the resulting TSP formulation is relaxed to allow for continuous solutions. Improvements and details regarding runtime and numerical stability are discussed, as well as an approach to recover feasible solutions from invalid assignments. Evaluation is performed on randomly generated TSP instances, and the presented approach is compared to SotA local search heuristics and learning-based approaches.", "questions": "1. How is the multiplier $\\lambda$ chosen? Which impact does the choice have on the performance of the algorithm?\n2. How dependent is the output on the chosen initialization $Y = -D$? Would the algorithm benefit from re-running using different initializations?\n3. How does the presented algorithm perform on benchmark instances from i.e. TSPLIB?\n4. How does the approximate gradient computation affect the output of the algorithm? Is the purpose of the approximation purely to improve runtime or does it also improve the final output of the algorithm?\n5. On line 160 it is stated that stepwidth $\\alpha$ is increased to accelerate convergence. \nUsually in gradient descent, one increases the stepwidth to achieve greater exploration, while decreasing it leads to convergence to a local minimum. Why does increasing the stepwidth accelerate convergence for this algorithm?\nFurthermore, it is stated that the adaptive strategy helps to balance exploration and stability. It is not entirely clear what is meant by stability here. Does stability here mean the ability of the algorithm to converge to a local solution?\n6. Proposition 1 states that any fractional matrix cannot satisfy the constraint. Does this not imply that the feasible solutions to the relaxed problem defined in Eq. (3) and of the original problem definition in Eq. (1) are the same, and therefore (3) is not a relaxation of (1), but (3) is an equivalent way of stating (1)?\n7. Additionally, on the small instances (TSP20 and TSP50) a comparison to the optimal solution found by an ILP solver would be interesting. This could also be useful in validating the experimental results as e.g. in Table 2 multiple algorithms consistently find the same solution (indicated by the avg. and median gap both being 0.0%), which can be a sign that they all have found the optimal solution.\nHowever, there exists an algorithm that consistently finds better solutions (GOAL in this case). Comparing to the optimal solution found by an ILP solver could be used to verify that no error has been made when taking these measurements.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- The key concepts of the paper are laid out clearly and in an easy-to-follow manner.\n- The algorithm shows convincing performance on the evaluated random instances with respect to solution quality and needed runtime in comparison to state-of-the-art methods, especially on large instances.\n\n**Weaknesses**\n- The evaluation is restricted to purely randomly generated TSP instances.\n- The paper has several grammar and spelling mistakes, e.g.:\n    - line 71 \"auto-aggressive way\"\n    - line 72 \"learning approach are applied\"\n    - line 82 \"Besides on those approaches\"\n    - line 83 \"choose learn better\"", "was_revised": true, "final_justification": "I think this is an interesting work and I will maintain my score.", "rebuttal": "Thank you for your insightful comments. We appreciate the opportunity to clarify several aspects of our work. Below, we address the concerns raised by the reviewers and provide additional explanations and evidence where appropriate.\n\n---\n\n### How is the multiplier $\\lambda$ chosen? What impact does the choice have on the performance of the algorithm?\n\nTheoretically, $\\lambda$ should be sufficiently large to enforce the acyclicity constraint. However, in practice, since candidate solutions are derived by solving linear assignment problems, the trace term $\\operatorname{tr}\\left(\\sum_{i=1}^{n-1} \\exp(\\mathbf{Y})^i\\right)$ becomes significantly large whenever a loop exists in the solution. As a result, even a moderate value of $\\lambda$ is effective at penalizing cycles.\n\nIn our experiments, we fixed $\\lambda = 1$ as it provides a good balance between constraint enforcement and optimization stability. We also tested larger values, such as $\\lambda = 10$, and observed no significant difference in performance. This suggests that our algorithm is relatively insensitive to the exact value of $\\lambda$, as long as it is reasonably large.\n\n---\n\n### How dependent is the output on the chosen initialization? Would the algorithm benefit from re-running using different initializations?\n\nWe experimented with both random and fixed initialization strategies and found that the choice of initialization has minimal impact on the final solution quality. This is likely due to the stability and robustness of our optimization procedure, which consistently converges to high-quality solutions regardless of the starting point. For simplicity and reproducibility, we therefore adopt a fixed initialization rule in all our experiments.\n\n---\n\n### How does the approximate gradient computation affect the output of the algorithm? Is the purpose of the approximation purely to improve runtime or does it also improve the final output of the algorithm?\n\nWe have experimentally evaluated the impact of using approximate versus exact gradients. In particular, when applying exact gradient computation on a 20-node symmetric TSP, we observed a performance gap of approximately **1.5%** relative to LKH-3—significantly larger than the gap achieved when using the approximate gradient.\n\nThis suggests that the purpose of the approximation is **not purely for runtime efficiency**, but that it also has a **positive effect on the final solution quality**. One possible explanation is that the use of inexact gradients introduces a form of implicit regularization or stochasticity that encourages better exploration of the solution space. In contrast, exact gradients may lead to faster convergence but can get trapped in poorer local minima.\n\nTherefore, while the approximation does speed up computation, it also empirically improves the robustness and effectiveness of the algorithm.\n\n---\n\n### On step size adaptation and stability in the optimization process\n\nThank you for the thoughtful question. We clarify that in our method, the **adaptive step size strategy** is designed to balance **exploration** and **convergence speed** during optimization.\n\nIn our setting, decreasing the step size typically causes the algorithm to converge more quickly to a **nearby local minimum**. While this can improve numerical stability, it may lead to **suboptimal solutions** due to premature convergence.\n\nConversely, increasing the step size enables the optimizer to **explore a broader region** of the solution space, potentially escaping poor local minima and discovering better solutions. However, this also introduces a risk of oscillation or divergence, which is why careful control is required.\n\nOur adaptive rule increases the step size when the current assignment remains unchanged (suggesting that a larger step may help move away from a plateau), and decreases it when a change is detected (to avoid overshooting). This dynamic adjustment aims to maintain a **balance between exploration and stability**.\n\nHere, by *stability*, we refer to the algorithm’s ability to maintain **progress toward a feasible and high-quality solution** without oscillation or divergence—not necessarily convergence to a global or even local minimum in the classical sense.\n\nWe hope this clarifies the intention behind our step size strategy.\n\n---\n\n### How does the presented algorithm perform on benchmark instances from, e.g., TSPLIB?\n\nWe evaluated our algorithm on large-scale ATSP benchmark instances from TSPLIB, particularly those derived from stacker crane problems. Our method consistently outperforms LKH-3 (1–100) in terms of solution quality while also requiring less computational time. These results demonstrate the practical effectiveness of our approach on real-world structured benchmarks, further validating its scalability and competitiveness beyond synthetic instances.\n\n| Instance | Best Known Result | Algorithm        | Running Time (s) | Results |\n|----|-----|--|---|---|\n| rbg323   | 1326              | LKH(1–100)       | 1.46             | 1388    |\n|          |   | LKH(1–10000)     | 3.38             | 1346    |\n|          |   | LKH(10–10000)    | 20.32            | 1346    |\n|          |   | Ours             | 0.42             | 1360    |\n|          |   | Ours (no 2-opt)  | 0.20             | 1365    |\n| rbg358   | 1163              | LKH(1–100)       | 1.67             | 1294    |\n|          |   | LKH(1–10000)     | 4.03             | 1175    |\n|          |   | LKH(10–10000)    | 25.16            | 1175    |\n|          |   | Ours             | 0.09             | 1180    |\n|          |   | Ours (no 2-opt)  | 0.04             | 1180    |\n| rbg403   | 2465              | LKH(1–100)       | 6.27             | 2536    |\n|          |    | LKH(1–10000)     | 26.99            | 2498    |\n|          |   | LKH(10–10000)    | 9.06             | 2498    |\n|          |   | Ours             | 1.53             | 2473    |\n|          |   | Ours (no 2-opt)  | 1.28             | 2473    |\n| rbg443   | 2720    | LKH(1–100)       | 5.44             | 2813    |\n|          |    | LKH(1–10000)     | 7.87             | 2762    |\n|          |    | LKH(10–10000)    | 30.06            | 2756    |\n|          |    | Ours             | 0.52             | 2760    |\n|          |   | Ours (no 2-opt)  | 0.27             | 2760    |\n\n---\n\n### Proposition 1 states that any fractional matrix cannot satisfy the constraint. Does this not imply that the feasible solutions to the relaxed problem defined in Eq. (3) and of the original problem definition in Eq. (1) are the same, and therefore (3) is not a relaxation of (1), but an equivalent formulation?\n\nYes, Proposition 1 implies that the continuous formulation in Eq. (3) is an exact representation of the original TSP defined in Eq. (1), in the sense that both share the same set of feasible solutions—namely, permutation matrices corresponding to valid tours.\n\nHowever, we still refer to Eq. (3) as a *relaxation* in the context of optimization because it replaces the discrete permutation constraint with continuous doubly stochastic and trace-based constraints. While the feasible set remains unchanged, this formulation enables the use of gradient-based optimization techniques over continuous variables. It is worth noting that, despite being continuous, Eq. (3) remains non-convex and NP-hard in general.\n\nTherefore, Eq. (3) should be viewed as a continuous but exact reformulation of the TSP, offering new algorithmic opportunities while preserving the problem's combinatorial structure.\n\n---\n\n### Comparison with ILP Solver\n\nWe conducted a preliminary comparison between our method and an exact ILP solver on both symmetric and asymmetric TSP instances. Specifically, we tested the solver on 100-node symmetric problems and 500-node asymmetric problems and found that the ILP solver was able to return optimal solutions within a reasonable time budget.\n\nDue to time constraints, we evaluated both methods on 10 randomly sampled instances for each case. The results are summarized below. While the ILP solver guarantees optimality, our method achieves competitive solution quality with significantly faster runtimes, particularly for larger asymmetric instances—highlighting its scalability and practical utility for large-scale problems.\n\n#### Performance comparison on 100-node symmetric TSP problems\n\n| Algorithm              | Running Time (s) | Ratio to Optimal (Mean) | Ratio to Optimal (Median) |\n|----|----|---|---|\n| LKH(1–100) | 0.07| 0.61%| 0.17%|\n| LKH(1–10000)| 1.24| 0.12%| 0.00%|\n| LKH(10–10000) | 12.14| 0.00%| 0.00%|\n| Gurobi| 2.06| 0.00%| 0.00%|\n| Ours (no local search) | 0.03| 15.2%| 14.4%|\n| Ours (local search)| 0.05| 1.47%| 1.35%|\n\n#### Performance comparison on 500-node asymmetric TSP problems\n\n| Algorithm| Running Time (s) | Ratio to Optimal (Mean) | Ratio to Optimal (Median) |\n|---|---|---|---|\n| LKH(1–100) | 0.87| 2.22%                    | 0.17%                      |\n| LKH(1–10000)| 2.82| 0.45%                    | 0.00%                      |\n| LKH(10–10000)| 20.23| 0.18%                    | 0.00%                      |\n| Gurobi| 6.36| 0.00%                    | 0.00%                      |\n| Ours (no local search) | 0.17| 0.005%                   | 0.001%                     |\n| Ours (local search) | 0.30| 0.005%                   | 0.001%                     |\n\n---\n\n### Results of GOAL\n\nWe carefully examined the implementation of GOAL and found that it is trained to solve the **Open Loop TSP**, where the tour does not require returning to the starting node. Additionally, the official evaluation code for GOAL **omits the cost of returning to the origin**, which leads to an underestimation of the total tour length.\n\nAs a result, the reported performance of GOAL is **not directly comparable** to other methods in our evaluation, which all solve the **Closed Loop TSP** (i.e., Hamiltonian cycles). We note this discrepancy to ensure a fair and transparent interpretation of the benchmark results."}, {"review_id": "E8qgKYRNK2", "reviewer": "Reviewer_F8bh", "summary": "This paper presents an innovative continuous relaxation framework for the Asymmetric Traveling Salesman Problem (ATSP). The core idea is to combine a differentiable, trace-based Directed Acyclic Graph (DAG) constraint with a doubly stochastic matrix relaxation to formulate the problem. This approach effectively suppresses subtours, enabling the use of gradient-based optimization to find solutions. The proposed method demonstrates superior performance and scalability compared to state-of-the-art methods like LKH-3, especially on large-scale ATSP benchmarks.", "questions": "Please refer to weakness.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n* The paper proposes a novel, differentiable, and exact continuous formulation for ATSP.\n* On large-scale ATSP instances (with more than 200 nodes), the method's solution quality and runtime are superior to the highly-optimized LKH-3 heuristic.\n* The algorithm shows convincing performance with solid evaluation.\n\n**Weaknesses:**\n* The experiments report average and median results  but do not provide error bars or confidence intervals.\n* A valuable direction for future work would be to explore the algorithm's performance in worst-case scenarios.", "was_revised": true, "final_justification": "Although I am not familiar with this research topic, I find this to be an interesting work.", "rebuttal": "We would like to respectfully clarify that the review appears to be based on a misunderstanding of our submission.\n\nOur paper does **not** address the problem of learning Directed Acyclic Graphs (DAGs) from observational data, nor does it consider Structural Hamming Distance (SHD) as a performance metric. Instead, our work focuses on solving the **Asymmetric Traveling Salesman Problem (ATSP)** by proposing a **trace-based acyclicity constraint** within a continuous optimization framework. The trace penalty is used to suppress **cyclic subtours in assignment matrices**, not to enforce acyclicity in the context of causal discovery or DAG learning.\n\nThe mention of concepts such as **LiNGAM**, **statistical identifiability**, or **post-processing in DAG structure learning** (e.g., thresholding of adjacency matrices) is therefore unrelated to our setting and not applicable to our contributions.\n\nWe kindly ask the reviewer to reconsider the evaluation in light of the actual scope of our paper, which is a continuous formulation for combinatorial optimization, **not causal inference** or **graphical model learning**."}, {"review_id": "Y1FvGfNAV3", "reviewer": "Reviewer_UGcr", "summary": "This paper propose to continuously relax the ATSP of discrete variables, and uses differentiable directed acyclic graph techniques and assignment problem relaxation to achieve gradient-based optimization. Since the relaxation is non-convex, this paper develops an adaptive step-size projected gradient descent to find high-quality solutions; for cases where the relaxation optimization does not yield a valid path, a simple greedy post-processing heuristic method is introduced to eliminate sub-cycles and construct feasible solutions.", "questions": "- What are the results on ATSPLIB [1] and real-world ATSP datasets [2]?\n\n- Table 7 is about a small-scale symmetric TSP problem. How does it perform on a larger-scale symmetric TSP problem?\n\n- Why is the proposed algorithm not as good as GOAL on ATSP20 (Table 2)?\n\n- Why does the proposed algorithm perform worse than LKH3 on a small scale but better on a large scale (Table 1)?\n\n- The method in this paper does not involve learning. Why mention learning-based methods separately in related work?\n\n- Does the initial solution have a big impact on the solution quality?\n\n- The headers of Tables 1 to 6 should be ATSP instead of TSP. Please do not omit it. This will confuse people at first glance, especially since Table 7 is about TSP.\n- Also see weaknesses.\n\n[1] http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/atsp/\n\n[2] Neural Combinatorial Optimization for Real-World Routing, arxiv 2025.", "limitations": "yes.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- The proposed method is reasonable and sound.\n- Extensive experiments show that the proposed method generally outperforms LKH-3 on the ATSP benchmark and has good generalization ability for problem sizes.\n\n**Weaknesses**\n- It is unclear how many chances there are to find a valid solution directly and find a valid solution via continuous iteration, respectively.\n- No ablation experiments are included to analyze the effectiveness of the proposed method components.\n- The authors did not report the results without 2-opt.\n- The article mentions that Gurobi and Concorde are not included as baselines because they run very slowly on large scales. What about small-scale problems?", "was_revised": true, "final_justification": "I thank the authors for their detailed response, which has addressed most of my concerns. Additionally, I would appreciate it if the author could add a discussion section on how to combine the proposed method with learning-based methods in the field of neural combinatorial optimization. Overall, it is an interesting work, and I would like to increase the score to 4. Nevertheless, since I am not particularly familiar with the field of this paper, I’ll defer to the AC and other reviewers.", "rebuttal": "Thank you for your insightful comments. We appreciate the opportunity to clarify several aspects of our work. Below, we address the concerns raised by the reviewers and provide additional explanations and evidence where appropriate.\n\n---\n\n## Results on real-world datasets\n\nWe evaluated our algorithm on large-scale ATSP benchmark instances from TSPLIB, particularly those derived from stacker crane problems. Our method consistently outperforms LKH-3 (1–100) in terms of solution quality while also requiring less computational time. These results demonstrate the practical effectiveness of our approach on real-world structured benchmarks, further validating its scalability and competitiveness beyond synthetic instances.\n\n| Instance | Best Known Result | Algorithm        | Running Time (s) | Results |\n|----------|-------------------|------------------|------------------|---------|\n| rbg323   | 1326              | LKH(1–100)       | 1.46             | 1388    |\n|          |                   | LKH(1–10000)     | 3.38             | 1346    |\n|          |                   | LKH(10–10000)    | 20.32            | 1346    |\n|          |                   | Ours             | 0.42             | 1360    |\n|          |                   | Ours (no 2-opt)  | 0.20             | 1365    |\n| rbg358   | 1163              | LKH(1–100)       | 1.67             | 1294    |\n|          |                   | LKH(1–10000)     | 4.03             | 1175    |\n|          |                   | LKH(10–10000)    | 25.16            | 1175    |\n|          |                   | Ours             | 0.09             | 1180    |\n|          |                   | Ours (no 2-opt)  | 0.04             | 1180    |\n| rbg403   | 2465              | LKH(1–100)       | 6.27             | 2536    |\n|          |                   | LKH(1–10000)     | 26.99            | 2498    |\n|          |                   | LKH(10–10000)    | 9.06             | 2498    |\n|          |                   | Ours             | 1.53             | 2473    |\n|          |                   | Ours (no 2-opt)  | 1.28             | 2473    |\n| rbg443   | 2720              | LKH(1–100)       | 5.44             | 2813    |\n|          |                   | LKH(1–10000)     | 7.87             | 2762    |\n|          |                   | LKH(10–10000)    | 30.06            | 2756    |\n|          |                   | Ours             | 0.52             | 2760    |\n|          |                   | Ours (no 2-opt)  | 0.27             | 2760    |\n\n---\n\n### Q: Why does the proposed algorithm perform worse than LKH-3 on small-scale problems, but better on large-scale problems (Table 1)?\n\nThe performance difference arises primarily from the nature of the search strategies employed by our method and LKH-3. LKH-3 is a randomized heuristic algorithm whose performance depends on the number of search trials specified by its hyperparameters. On small-scale problems, the search space is relatively small, so even a modest number of trials allows LKH-3 to explore a substantial portion of the space, leading to high-quality solutions.\n\nIn contrast, our method can be viewed as a guided search strategy. Rather than exhaustively exploring the space, it prioritizes search efficiency by following a trace-guided optimization pathway. This allows our approach to scale more gracefully with problem size, but also means that on small instances, it may not explore the solution space as thoroughly as LKH-3 under high-budget settings.\n\nAs the problem size increases, the search space grows exponentially. For large-scale problems, the coverage of LKH-3's randomized search becomes sparse without significantly increasing the number of trials—leading to diminishing returns. In such cases, our method's guided search provides a more effective exploration strategy, enabling it to find higher-quality solutions more consistently and efficiently. This explains why our approach begins to outperform LKH-3 on larger ATSP instances.\n\n---\n\n### Q: The method in this paper does not involve learning. Why mention learning-based methods separately in the related work?\n\nWhile our method is not learning-based, we include learning-based approaches in the related work because they represent a significant and actively growing direction in solving TSP and other combinatorial optimization problems. Many such methods build on heuristic frameworks, with some leveraging learning to optimize components like hyperparameters or search strategies—e.g., tuning parameters for LKH-3 or learning local improvement rules.\n\nMoreover, reinforcement learning-based solvers often do not require access to ground-truth optimal tours, but their performance is heavily influenced by the quality of the heuristic signals they rely on during training. In this context, stronger heuristics—such as our proposed algorithm—can serve as better guidance or high-quality rollouts, potentially improving the training and generalization of learning-based methods. Therefore, our method could be complementary to learning-based approaches and facilitate their further advancement.\n\n---\n\n### Q: Does the initial solution have a big impact on the solution quality?\n\nWe experimented with both random and fixed initialization strategies and found that the choice of initialization has minimal impact on the final solution quality. This is likely due to the stability and robustness of our optimization procedure, which consistently converges to high-quality solutions regardless of the starting point. For simplicity and reproducibility, we therefore adopt a fixed initialization rule in all our experiments.\n\n---\n\n### Ablation studies\n\nWe have conducted ablation studies to evaluate the contribution of individual components of our method, particularly the 2-opt local refinement step. Additionally, we compared our approach against the exact solver Gurobi on a set of problem instances. Due to time constraints, these experiments were conducted on 10 randomly selected instances. Despite the limited scale, the results provide useful insights into the effectiveness of our design choices and confirm that our algorithm performs competitively even without the local refinement.\n\nFrom the results and our earlier findings on TSPLIB ATSP problems, we observe that the 2-opt local search strategy **significantly improves performance on symmetric TSP problems**, but has **limited impact on asymmetric TSP problems**.\n\n#### Performance comparison on 100-node symmetric TSP problems\n\n| Algorithm              | Running Time (s) | Ratio to Optimal (Mean) | Ratio to Optimal (Median) |\n|------------------------|------------------|--------------------------|----------------------------|\n| LKH(1–100)             | 0.07             | 0.61%                    | 0.17%                      |\n| LKH(1–10000)           | 1.24             | 0.12%                    | 0.00%                      |\n| LKH(10–10000)          | 12.14            | 0.00%                    | 0.00%                      |\n| Gurobi                 | 2.06             | 0.00%                    | 0.00%                      |\n| Ours (no local search) | 0.03             | 15.2%                    | 14.4%                      |\n| Ours (local search)    | 0.05             | 1.47%                    | 1.35%                      |\n\n#### Performance comparison on 500-node asymmetric TSP problems\n\n| Algorithm              | Running Time (s) | Ratio to Optimal (Mean) | Ratio to Optimal (Median) |\n|------------------------|------------------|--------------------------|----------------------------|\n| LKH(1–100)             | 0.87             | 2.22%                    | 0.17%                      |\n| LKH(1–10000)           | 2.82             | 0.45%                    | 0.00%                      |\n| LKH(10–10000)          | 20.23            | 0.18%                    | 0.00%                      |\n| Gurobi                 | 6.36             | 0.00%                    | 0.00%                      |\n| Ours (no local search) | 0.17             | 0.005%                   | 0.001%                     |\n| Ours (local search)    | 0.30             | 0.005%                   | 0.001%                     |\n\n---\n\n### Results of GOAL\n\nWe carefully examined the implementation of GOAL and found that it is trained to solve the **Open Loop TSP**, where the tour does not require returning to the starting node. Additionally, the official evaluation code for GOAL **omits the cost of returning to the origin**, which leads to an underestimation of the total tour length.\n\nAs a result, the reported performance of GOAL is **not directly comparable** to other methods in our evaluation, which all solve the **Closed Loop TSP** (i.e., Hamiltonian cycles). We note this discrepancy to ensure a fair and transparent interpretation of the benchmark results.\n\n\n--- \n\n### Table captions\n\nWe will update the captions in revised version."}]

Author rebuttal:

Meta-review: This paper introduces a novel continuous relaxation framework for the ATSP, using differentiable trace-based constraints combined with doubly stochastic formulations and gradient-based optimization. A greedy post-processing step ensures valid tours.

The main strengths are the original formulation and the empirical performance: the method consistently outperforms LKH-3 and  other  baselines, particularly on large-scale ATSP and TSPLIB benchmarks. 

While theoretical convergence guarantees are limited, and some reviewers noted lower confidence due to field mismatch, the work is technically sound, clearly presented, and demonstrates substantial practical impact. The rebuttal provided convincing clarifications and additional results.
Decision: Accept (poster)