Abstract
We empirically study phase transitions of the asymmetric Traveling Salesman. Using random instances of up to 1,500 cities, we show that many properties of the problem, including the backbone and optimal tour cost, experience sharp transitions as the precision of intercity distances increases across a critical value. We also show that the average computational cost of the well-known branch-and-bound subtour elimination algorithm for the problem also exhibits a threshold behavior, transitioning from easy to difficult as the distance precision increases. These results provide strong positive evidences to a decade-long open question regarding the existence of phase transitions of the Traveling Salesman.
Introduction
In combinatorial optimization, "phase transitions" are critical points where a system's global properties change dramatically due to a small change in a control parameter. While these transitions are well-documented in decision problems like Boolean Satisfiability, their existence in optimization problems like the Traveling Salesman Problem (TSP) remained an open question for decades. This research investigates the Asymmetric TSP (ATSP), where the distance from city A to B is not necessarily equal to the distance from B to A, a problem central to logistics and scheduling.
Methodology
The study utilizes synthetic datasets of uniformly random ATSP instances with sizes ranging from 100 to 1,500 cities. Distances are integers chosen uniformly from the range $[0, R-1]$, where $R$ is determined by the distance precision (the number of digits used). This precision serves as the primary control parameter.
Instances were solved using a Depth-First Branch-and-Bound (DFBnB) algorithm with subtour elimination, employing the Assignment Problem (AP) as a lower-bound cost function. To ensure results are intrinsic to the problem rather than specific to size, the researchers applied finite-size scaling, a technique from statistical physics that collapses data from different scales onto a single universal curve.
Empirical Results
The core insight is that the "hardness" of an ATSP instance is heavily dictated by distance precision. At low precision, numerous "ties" in distance values make the problem significantly easier to solve. As precision increases, the fraction of distinct distances in the cost matrix undergoes a sharp transition.
Tour Cost and Backbone Solidification
The average optimal tour cost exhibits an abrupt increase as the effective number of digits crosses a critical threshold. This behavior is a hallmark of a phase transition.
This transition in cost is closely linked to the "backbone" of the problem—the set of edges present in every optimal solution. As precision increases, the backbone fraction follows a nearly identical transition pattern, indicating that the problem becomes more constrained and structurally rigid, which in turn drives computational difficulty.
Computational Complexity and Asymptotic Limits
The computational effort, measured by calls to the AP function, grows dramatically once the distance precision exceeds the critical threshold. Furthermore, the study quantifies the gap between the AP relaxation and the true ATSP optimal. For very large problems ($n \to \infty$), the AP cost approaches ~1.6439 while the ATSP cost approaches ~1.6444. At low precision, the AP solution is frequently identical to the ATSP solution, but this probability drops to zero as precision increases.
Conclusion
This empirical evidence confirms the existence of phase transitions in the ATSP, driven by distance precision. These results suggest that generating truly challenging benchmark instances requires scaling distance precision alongside problem size. Future research may explore whether similar precision-based transitions exist in other optimization domains, such as Job Shop Scheduling or the Quadratic Assignment Problem.
Summary updated