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