TY - JOUR
T1 - Continuous relaxations for the traveling salesman problem
AU - Sahai, Tuhin
AU - Ziessler, Adrian
AU - Klus, Stefan
AU - Dellnitz, Michael
N1 - Funding Information:
The authors thank Prof. Keld Helsgaun for discussions related to the Lin–Kernighan heuristic and his software and also Dr. Mirko Hessel-von Molo and Steffen Ridderbusch for discussions related to the approach. This material is based upon work supported by the Defense Advanced Research Projects Agency (DARPA) and Space and Naval Warfare Systems Center Pacific (SSC Pacific) under Contract No. N6600118C4031.
Publisher Copyright:
© 2019, Springer Nature B.V.
PY - 2019/9
Y1 - 2019/9
N2 - 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 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 on average requires fewer k-opt moves than existing approaches. Broadly, this work connects dynamical systems theory with combinatorial optimization to provide algorithmic and computational complexity insights.
AB - 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 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 on average requires fewer k-opt moves than existing approaches. Broadly, this work connects dynamical systems theory with combinatorial optimization to provide algorithmic and computational complexity insights.
KW - Dynamical systems for optimization
KW - Procrustes solution
KW - Stable manifolds
KW - Traveling salesman problem heuristic
UR - http://www.scopus.com/inward/record.url?scp=85068956824&partnerID=8YFLogxK
U2 - 10.1007/s11071-019-05092-5
DO - 10.1007/s11071-019-05092-5
M3 - Article
AN - SCOPUS:85068956824
SN - 0924-090X
VL - 97
SP - 2003
EP - 2022
JO - Nonlinear Dynamics
JF - Nonlinear Dynamics
IS - 4
ER -