Solving the Asymmetric Traveling Salesman Problem via Trace-Guided Cost Augmentation

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.

---

Results on real-world datasets

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 on real-world structured benchmarks, further validating its scalability and competitiveness beyond synthetic instances.

---

Q: Why does the proposed algorithm perform worse than LKH-3 on small-scale problems, but better on large-scale problems (Table 1)?

The 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.

In 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.

As 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.

---

Q: The method in this paper does not involve learning. Why mention learning-based methods separately in the related work?

While 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.

Moreover, 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.

---

Q: Does the initial solution have a big impact on the solution quality?

We 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.

---

Ablation studies

We 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.

From 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.

Performance comparison on 100-node symmetric TSP problems

Performance comparison on 500-node asymmetric TSP problems

---

Results of GOAL

We 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.

As 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.

---

Table captions

We will update the captions in revised version.

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.

---

How is the multiplier $\lambda$ chosen? What impact does the choice have on the performance of the algorithm?

Theoretically, $\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.

In 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.

---

How dependent is the output on the chosen initialization? Would the algorithm benefit from re-running using different initializations?

We 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.

---

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?

We 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.

This 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.

Therefore, while the approximation does speed up computation, it also empirically improves the robustness and effectiveness of the algorithm.

---

On step size adaptation and stability in the optimization process

Thank 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.

In 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.

Conversely, 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.

Our 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.

Here, 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.

We hope this clarifies the intention behind our step size strategy.

---

How does the presented algorithm perform on benchmark instances from, e.g., TSPLIB?

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 on real-world structured benchmarks, further validating its scalability and competitiveness beyond synthetic instances.

---

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?

Yes, 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.

However, 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.

Therefore, 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.

---

Comparison with ILP Solver

We 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.

Due 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.

Performance comparison on 100-node symmetric TSP problems

Performance comparison on 500-node asymmetric TSP problems

---

Results of GOAL

We 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.

As 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.

We would like to respectfully clarify that the review appears to be based on a misunderstanding of our submission.

Our 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.

The 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.

We 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.

Thank you for your insightful comments. We would like to offer the following clarifications regarding the approximation properties of Eq. (6).

Approximation Properties of Eq. (6)

The 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.

However, 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].

When 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.

That 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.

We thank the reviewer again for raising this important point.

References:

[1] Lacoste-Julien, Simon. Convergence rate of Frank-Wolfe for non-convex objectives. arXiv preprint arXiv:1607.00345 (2016).
[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.