Continuous relaxations for the traveling salesman problem

DOI10.1007/S11071-019-05092-5zbMATH Open1430.37126arXiv1702.05224OpenAlexW3105081266WikidataQ127498502 ScholiaQ127498502MaRDI QIDQ2296989FDOQ2296989

Authors: Tuhin Sahai, Adrian Ziessler, Stefan Klus, Michael Dellnitz 

Publication date: 18 February 2020

Published in: Nonlinear Dynamics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1702.05224

Recommendations

• Large-step Markov chains for the TSP incorporating local search heuristics
• Learning heuristics for the TSP by policy gradient
• On the neighborhood structure of the traveling salesman problem generated by local search moves
• General \(k\)-opt submoves for the Lin-Kernighan TSP heuristic
• A linearithmic heuristic for the travelling salesman problem

zbMATH Keywords

stable manifoldstraveling salesman problemdynamical systems for optimizationprocrustes solution

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Dynamical systems in optimization and economics (37N40)

Cites Work

• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• TSPLIB—A Traveling Salesman Problem Library
• ScaLAPACK Users' Guide
• Title not available (Why is that?)
• A feasible method for optimization with orthogonality constraints
• Title not available (Why is that?)
• Introduction to algorithms.
• The Geometry of Algorithms with Orthogonality Constraints
• Compression, inversion, and approximate PCA of dense kernel matrices at near-linear computational complexity
• Procrustes Problems
• Title not available (Why is that?)
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Title not available (Why is that?)
• Assignment Problems and the Location of Economic Activities
• Title not available (Why is that?)
• The Traveling-Salesman Problem and Minimum Spanning Trees
• On the solution of traveling salesman problems
• Computing the Polar Decomposition—with Applications
• The traveling-salesman problem and minimum spanning trees: Part II
• Worst-case analysis of a new heuristic for the travelling salesman problem
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Dynamical systems that sort lists, diagonalize matrices, and solve linear programming problems
• Hearing the clusters of a graph: A distributed algorithm
• A subdivision algorithm for the computation of unstable manifolds and global attractors
• SONET/SDH ring assignment with capacity constraints
• Regularity of embeddings of infinite-dimensional fractal sets into finite-dimensional spaces
• Optimal control of plotting and drilling machines: A case study
• General \(k\)-opt submoves for the Lin-Kernighan TSP heuristic
• Reducibility among combinatorial problems
• On Lagrangian relaxation of quadratic matrix constraints
• Title not available (Why is that?)
• A New Lower Bound Via Projection for the Quadratic Assignment Problem
• Solving the equality generalized traveling salesman problem using the Lin-Kernighan-Helsgaun algorithm
• A dynamical systems approach to weighted graph matching
• Least squares matching problems
• A variational perspective on accelerated methods in optimization
• Title not available (Why is that?)
• Matrix representation and gradient flows for NP-hard problems
• Accelerated branch exchange heuristics for symmetric traveling salesman problems
• The numerical computation of unstable manifolds for infinite dimensional dynamical systems by embedding techniques
• A Set-Oriented Numerical Approach for Dynamical Systems with Parameter Uncertainty
• A spectral assignment approach for the graph isomorphism problem

Cited In (4)

• Dynamical Systems Theory and Algorithms for NP-hard Problems
• Relaxed tours and path ejections for the traveling salesman problem
• Title not available (Why is that?)
• Adaptive CP-based Lagrangian relaxation for TSP solving

Uses Software

• ScaLAPACK
• TSPLIB
• GAIO
• LKH

This page was built for publication: Continuous relaxations for the traveling salesman problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2296989)