Title: Continuous Relaxations for the Traveling Salesman Problem,
Abstract: In this work, we aim to explore connections between dynamical systems
techniques and combinatorial optimization problems. In particular, we construct
heuristic approaches for the traveling salesman problem (TSP) based on
embedding the relaxed discrete optimization problem into appropriate manifolds.
We explore multiple embedding techniques -- namely, the construction of new
dynamical systems on the manifold of orthogonal matrices and associated
Procrustes approximations of the TSP cost function. Using these dynamical
systems, we analyze the local neighborhood around the optimal TSP solutions
(which are equilibria) using computations to approximate the associated
\emph{stable manifolds}. We find that these flows frequently converge to
undesirable equilibria. However, the solutions of the dynamical systems and the
associated Procrustes approximation provide an interesting biasing approach for
the popular Lin--Kernighan heuristic which yields fast convergence. The
Lin--Kernighan heuristic is typically based on the computation of edges that
have a `high probability' of being in the shortest tour, thereby effectively
pruning the search space. Our new approach, instead, relies on a natural
relaxation of the combinatorial optimization problem to the manifold of
orthogonal matrices and the subsequent use of this solution to bias the
Lin--Kernighan heuristic. Although the initial cost of computing these edges
using the Procrustes solution is higher than existing methods, we find that the
Procrustes solution, when coupled with a homotopy computation, contains
valuable information regarding the optimal edges. We explore the Procrustes
based approach on several TSP instances and find that our approach often
requires fewer $k$-opt moves than existing approaches. Broadly, we hope that
this work initiates more work in the intersection of dynamical systems theory
and combinatorial optimization.