Last modified: 25 September 2001
The Traveling Salesman Problem (TSP) is very simple to state: given N points (or ``cities''), find the length of the shortest closed path (``tour'') passing through all points. The problem is, however, extremely difficult to solve.
To theoretical physicists such as myself, the TSP has been of particular interest in its stochastic form, where the configuration of the N cities is random. This allows the problem to be considered as a member of a large class of disordered systems, and allows the analytical formalism developed for other disordered systems to be used in obtaining TSP results. When we discuss the stochastic TSP, we must specify how the N cities are randomly distributed in an instance. One simple choice is to distribute the points randomly and independently, with a uniform distribution, in a d-dimensional Euclidean space. (Consider a unit hypercube, for simplicity.) The question then arises of how the average optimum tour length, L(N,d), depends on N and d. Using new algorithmic methods that we have developed, we have obtained the large N expression for the tour length with finite size corrections, L(N,d) = ß(d) N 1-1/d [1+A(d)/N+O(1/N²)], where ß(d) and A(d) are functions of the dimensionality d only. We have found extremely precise numerical values for ß(2) and ß(3) -- to a precision, in fact, 20 times greater than was possible using previously available methods. For d = 2 and d = 3, our expression then gives the average optimum tour length to within 0.1% for N > 50.
It would be nice to have a general method for finding at least the leading-order function ß(d). We do this using the random link approximation, where all lengths between cities are taken to be completely independent of one another. This assumption is clearly not perfect in standard Euclidean space: correlations between distances, such as the triangle inequality, do exist. The great advantage of the approximation, however, it that it allows us to solve the problem, thanks to an analytical approach developed by theoreticians working in spin glasses and other disordered systems. We use this approach to obtain an approximate ß(d) expression. For d = 2 and d = 3, the random link approximation turns out to be a very good one (within 2% of our numerical values). In the large d limit, we argue that in fact the approximation becomes exact -- specifying, furthermore, that its relative error decreases as O(1/d²). This results in a conjecture on the true expression for ß(d) at large d, in terms of a 1/d series where leading and subleading coefficients are given.
Statistical physics may thus be used to obtain quantitative results for the TSP. At the same time, though, work done on the TSP can in turn lead to advances in physics and other fields. In physics, much remains to be learned about where the TSP is situated within the context of disordered systems. A better understanding of the random link formalism as applied to the TSP, for instance, could tell us a lot about the nature of these systems. Certain hypotheses pertaining to the physical properties of the TSP have been adopted in the analytical approach -- most notably the hypothesis of no replica symmetry breaking. While there is good reason to believe that this property holds for the TSP, a better understanding is required. One of my present goals is to use our TSP work to test the hypothesis. By implementing certain modifications to our algorithms, we will in fact be able to perform direct numerical checks on the analytical theory itself. Confirmation of the hypothesis of no replica symmetry breaking in the TSP could open the way to a much deeper understanding of the general behavior of disordered systems, particularly that of problems such as the spin glass where this property is generally held to be false.
I am also interested in examining other physical properties arising from, but not directly related to, the TSP. All of our work so far has been on the zero-temperature (T = 0) case -- that is, we have concerned ourselves uniquely with tours that are optimal. There is still a lot to be learned about what happens at T > 0, when the optimality constraint is relaxed. For a better understanding of the random link approximation, it would be useful to see how accurately it predicts finite-temperature thermodynamic quantities, such as the density of states. Knowing whether or not such quantities obey self-averaging could, furthermore, enlighten us considerably on the question of replica symmetry breaking. Along these lines, questions of T > 0 phase transitions in the TSP also remain largely unexplored. I would like to study more closely the system's critical behavior, as this too will provide indications of how to translate our TSP work to a large class of disordered systems.
Outside of physics, the TSP has much to contribute as well. Our random link approximation is of relevance in numerous combinatorial optimization problems, such as the assignment and matching problems. I would be interested in pursuing these analogies further, in order to obtain state-of-the-art methods applicable to a broad range of questions in operations research. Another area ripe for further exploration is geometry. In the course of our TSP work, we have discovered a surprising universality: if one looks at the mean distance between kth-nearest neighbors, for N points randomly and uniformly distributed in a unit hypercube, this distance may be written in terms of a 1/N series that is itself independent of k. In other words, the same finite size dependence applies to all kth-nearest neighbor distances, regardless of k. This property is in fact what led us to find the finite size dependence for the TSP tour length. But at the same time, it is an important geometric discovery in itself, and leads to many open questions of a more mathematical nature. What is the dependence of the universality on the nature of the physical space used? How is the property affected by different topologies? Is it valid in non-Euclidean spaces, and how is it related to the curvature of the space?
This paper deals with the random link TSP, where the lengths between cities are taken to be i.i.d. random variables. We first review the cavity method, an analytical method that has been used to provide predictions for the large N optimal tour length, assuming replica symmetry. We then perform a numerical study to test these predictions. The broad agreement found suggests that for the TSP, unlike for other disordered systems such as spin glasses, the replica symmetry assumption is correct.
Consider N sites randomly and uniformly distributed on a smooth manifold without boundaries, and look at the expected distance from a point on the manifold to the kth-nearest site. When the manifold has no curvature, we show that the 1/N scaling law for this quantity is universal in k. When the manifold has intrinsic curvature, we show that the leading 1/N term depends only on the Euler characteristic and is thus a topological invariant.
This paper presents a number of new results on the stochastic TSP. Using advanced heuristic methods, we give the most precise asymptotic (large N) values to date for the Euclidean optimum tour length. We then make use of the random link approximation to derive analytical predictions of the tour length, showing that at high dimension d the approximation is valid up to O(1/d²).
This thesis, available in both English and French, discusses the stochastic TSP as well as scaling properties of nearest-neighbor distances for randomly distributed points. We perform a numerical study of optimal TSP tour lengths in Euclidean space, and we examine the analytical theory behind the random link approximation where distances between cities are taken to be independent random variables. The thesis contains versions (some of them preliminary) of the three papers listed above.
Using related scaling properties, we extract the asymptotic expression for the length of the shortest closed tour going through N points randomly distributed in Euclidean space. We then consider a mean field approach. This gives a good approximation of the large N tour length at low dimension, as well as its dimensional scaling law at high dimension.
Last modified: 25 September 2001