Springer, Nonlinear Dynamics, 4(97), p. 2003-2022, 2019
DOI: 10.1007/s11071-019-05092-5
Full text: Download
In this work, we construct heuristic approaches for the traveling salesman problem (TSP) based on embedding the discrete optimization problem into continuous spaces. We explore multiple embedding techniques -- namely, the construction of dynamical flows on the manifold of orthogonal matrices and associated Procrustes approximations of the TSP cost function. In particular, we find that the Procrustes approximation provides a competitive biasing approach for the Lin--Kernighan heuristic. 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 for the $k$-opt moves. This computation is traditionally based on generating $1$-trees for a modified distance matrix obtained by a subgradient optimization method. Our novel approach, instead, relies on the solution of a two-sided orthogonal Procrustes problem, a natural relaxation of the combinatorial optimization problem to the manifold of orthogonal matrices and the subsequent use of this solution to bias the $k$-opt moves in the Lin--Kernighan heuristic. Although the initial cost of computing these edges using the Procrustes solution is higher than the 1-tree approach, 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.