In this Article, we introduce an ensemble of the Traveling Salesperson problem (TSP)
that can be tuned with a parameter \(\sigma\) from the trivial case of cities
equidistant on a circle to the random Euclidean TSP in a plane.
For this ensemble we determine some phase transitions from an “easy” phase to
a “not-that-easy” phase using linear programming. For each of these transitions
we present structural properties of the optimal solution, which change at these
points characteristically. Since the optimal solution is independent of the
solution method, those phase transitions are not only relevant for the specific
linear program respectively the solver implementation used to solve them, but
a fundamental property of this TSP ensemble.
We used the classical linear program of Dantzig:
\begin{align}
\label{eq:objective}
&\text{minimize} & \sum_i \sum_{j<i} c_{ij} x_{ij}\\
\label{eq:int}
&\text{subject to} & x_{ij} &\in \{0,1\}\\ %\mathbb{Z}\\
\label{eq:inout}
& & \sum_{j} x_{ij} &= 2& & \forall i \in V \\
\label{eq:sec}
& & \sum_{i \in S, j \notin S} x_{ij} &\ge 2& & \forall S \varsubsetneq V, S \ne \varnothing
\end{align}
Here \(c_{ij}\) is the distance matrix between all pairs of cities
of \(V\) and \(x_{ij}\) is the adjacency matrix, i.e., \(x_{ij} = 1\),
if \(i\) and \(j\) are consecutive in the tour and \(x_{ij} = 0\) otherwise.
Therefore, the first line minimizes the length of the tour.
To avoid that we conclude that \(x_{ij} = 0\), i.e., staying at home,
is identified as the optimal tour, we introduce the third line to
force each city to have two connections, enough to enter and leave.
But our salesman is clever and can trick us by choosing
\(x_{ij} = 0.5\). Since we can not interpret this, we introduce line 2
to force all \(x_{ij}\) to integers.
Still valid are two unconnected tours, which we forbid with
the fourth line, the subtour elimination constraints.
Well, the careful reader might already see that we defined
one constraint for each subset of the cities, which are exponentially
many in the number of cities. But we can solve this by starting
without this class of constraints and only adding the ones which
are actually violated by a solution. The violated ones can luckily
be found easily by calculating the minimum cut of the proposed solution. The corresponding
constraint can be added and the procedure is repeated until no
subtour elimination constraint is violated anymore.
So does that mean that we found an efficient algorithm to solve
the traveling salesperson problem? No, unfortunately we can not
claim the Millenium Prize yet. There is no known
algorithm which can efficiently solve this problem under the
integer constraint.
But if we drop this constraint, we can use efficient algorithms
of linear programming to solve the
relaxation. The resulting length will always
be a lower bound on the actual solution and if we, by chance, find
an integer solution, we can be sure that it is actually the
optimal solution.
As the order parameter of the transitions from easy to hard we use the probability that a simplex
solver yields an integer, and therefore optimal, solution. Without the Subtour Elimination Constraints,
the transition occurs at the point at which the optimal solution deviates
from the order of the cities on the initial circle. With the Subtour
Elimination Constraints the transition coincides with the point at which
the optimal tour changes from a zig-zag course to larger meandering arcs.
This is measured by the tortuosity
\begin{align*}
\tau = \frac{n-1}{L} \sum_{i=1}^{n} \left( \frac{L_i}{S_i}-1 \right).
\end{align*}
which is maximal at this point. For the tortuosity the tour is divided in \(N\)
parts of same-sign-curvature. For each part the ratio of the direct end-to-end
distance \(S_i\) to the length along the arc \(L_i\) is summed.
So, we detected continuous phase transitions in the hardness
of the problem with linear programming and correlated them
with structural changes.