Phase Transitions and Backbones of the Asymmetric Traveling Salesman Problem

Weixiong Zhang

TL;DR

This paper investigates "phase transitions" in the Asymmetric Traveling Salesman Problem (ATSP), demonstrating that key problem properties like optimal tour cost and the "backbone" (essential edges for optimal solutions) change dramatically with the precision of intercity distances. These findings confirm a long-standing question about TSP phase transitions and offer practical guidance for generating challenging ATSP instances.

What Problem Does This Paper Address?

The Traveling Salesman Problem (TSP), and its asymmetric variant (ATSP), are classic NP-hard problems with numerous real-world applications. While phase transitions have been extensively studied in decision problems like Boolean Satisfiability (SAT), their existence and nature in optimization problems, particularly the TSP, remained an open question. Specifically, the authors aimed to resolve the debate on whether the TSP exhibits clear phase transitions and to understand how problem properties, such as the "backbone" (the set of variables that must take a specific value in all optimal solutions), change with problem parameters. Understanding these transitions is crucial for developing effective algorithms and for generating hard problem instances for benchmarking.

Methods

The authors employed an empirical approach, generating a large number of random ATSP instances with varying numbers of cities (up to 1,500) and, crucially, varying "precision" of intercity distances. This precision was controlled by the number of digits used to represent distances, which in turn influences the fraction of distinct distances in the distance matrix. They analyzed several key properties:

  • ATSP Tour Cost: The cost of the optimal tour.
  • Backbone Size: The proportion of arcs that are part of all optimal tours.
  • Assignment Problem (AP) Cost: The cost of the relaxed assignment problem, which serves as a lower bound for the ATSP.
  • Probability of AP Cost = ATSP Cost: How often the lower bound matches the actual optimal tour cost.
  • Existence of Hamiltonian Circuits with Zero-Cost Edges: A decision problem related to low-precision distance matrices.
  • Computational Complexity of a Branch-and-Bound Algorithm: The performance of a standard subtour elimination algorithm.

They utilized "finite-size scaling" techniques to analyze how these properties change across different problem sizes and to identify critical points where transitions occur.

Datasets

The paper does not introduce new datasets. Instead, it generates synthetic datasets of uniformly random Asymmetric Traveling Salesman Problem instances. These instances vary in the number of cities (from 100 to 1,500) and, critically, in the precision of intercity distances. The distance values were drawn from a uniform distribution over integers, with the range of these integers determined by the number of digits used.

Key Insights and Ideas

  • ATSP Exhibits Clear Phase Transitions: Contrary to some prior beliefs, the ATSP, like many decision problems, exhibits sharp phase transitions in its properties. This confirms a long-standing question in the field.
  • Distance Precision is the Key Control Parameter: The "effective number of digits" used to represent intercity distances acts as a critical control parameter that drives these phase transitions. As precision increases, the problem's characteristics shift dramatically.
  • Backbone as a Measure of Constraint: The size of the backbone (essential arcs for optimal solutions) is directly related to the problem's constrainedness. As distances become more distinct (higher precision), the backbone grows, indicating a more tightly constrained problem.
  • Thrashing Behavior in Algorithms: The computational cost of a standard branch-and-bound subtour elimination algorithm for ATSP also exhibits a "thrashing behavior," mirroring phase transitions. The algorithm goes from easy to difficult as distance precision increases.
  • Practical Implications for Instance Generation: The findings provide crucial guidance on how to generate challenging ATSP instances. Instead of simply increasing problem size, one needs to carefully control distance precision to create instances that lie near the phase transition, which are typically the hardest.

Key Results

  • ATSP Tour Cost and Backbone Transitions: Both the average optimal ATSP tour cost and the average fraction of backbone variables show abrupt, dramatic transitions as the effective number of digits increases. These transitions become sharper for larger problem sizes.
  • Critical Points Identified: The authors identified critical values for the control parameter (effective number of digits) for various properties, such as $\beta_c = 1$ for tour cost and backbone, and $\beta_c = 1.17 \pm 0.005$ for the probability that the Assignment Problem cost equals the ATSP cost.
  • Assignment Problem Accuracy: The accuracy of the Assignment Problem as a lower bound for the ATSP improves as distance precision increases, with a phase transition occurring around $\beta_c = 0.97$.
  • Algorithm Complexity: The average computational complexity (measured by AP calls) of the branch-and-bound subtour elimination algorithm increases exponentially with the number of digits, exhibiting a thrashing behavior that can be captured by finite-size scaling.
  • Asymptotic AP Cost: The experimental AP cost approaches the theoretical asymptotic value of $\pi^2/6 \approx 1.64493$ (Aldous, 2001; Mézard & Parsi, 1987), with the ATSP cost being very close.

Limitations and Future Work

  • Mathematical Determination of Critical Points: The authors note that the exact mathematical determination of the critical points for these phase transitions remains an open problem, likely requiring methods from statistical physics.
  • Generalizability to Other Distance Distributions: While the findings are based on uniformly distributed distances, the authors suggest that phase transitions would likely persist for other distance distributions, though the critical points might differ.
  • Structured TSP Instances: The paper focuses on random instances. Future work could explore phase transitions in structured TSP instances, such as those with triangle inequalities or derived from specific applications.
  • Algorithm-Specific vs. Problem-Specific: While the paper highlights phase transitions in the ATSP itself, it also discusses algorithm-specific behavior (thrashing). Further research could disentangle these more definitively.

Summary updated

Abstract

In recent years, there has been much interest in phase transitions of combinatorial problems. Phase transitions have been successfully used to analyze combinatorial optimization problems, characterize their typical-case features and locate the hardest problem instances. In this paper, we study phase transitions of the asymmetric Traveling Salesman Problem (ATSP), an NP-hard combinatorial optimization problem that has many real-world applications. Using random instances of up to 1,500 cities in which intercity distances are uniformly distributed, we empirically show that many properties of the problem, including the optimal tour cost and backbone size, experience sharp transitions as the precision of intercity distances increases across a critical value. Our experimental results on the costs of the ATSP tours and assignment problem agree with the theoretical result that the asymptotic cost of assignment problem is pi ^2 /6 the number of cities goes to infinity. In addition, we show that the average computational cost of the well-known branch-and-bound subtour elimination algorithm for the problem also exhibits a thrashing behavior, transitioning from easy to difficult as the distance precision increases. These results answer positively an open question regarding the existence of phase transitions in the ATSP, and provide guidance on how difficult ATSP problem instances should be generated.
BibTeX
@article{zhang2004phase,
  author = {Weixiong Zhang},
  title = {{Phase Transitions and Backbones of the Asymmetric Traveling Salesman Problem}},
  journal = {J. Artif. Intell. Res.},
  year = {2004},
  doi = {10.1613/jair.1389},
}
Figure