An alternate formulation of the symmetric traveling salesman problem and its properties

DOI10.1016/S0166-218X(99)00154-7zbMath0947.90097OpenAlexW2003186772MaRDI QIDQ1962065

Yanyan Li

Publication date: 30 January 2000

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00154-7

zbMATH Keywords

traveling salesman problemproblem formulationssubtour elimination polytope

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (7)

A simulated annealing algorithm for the restricted stochastic traveling salesman problem with exponentially distributed arc lengths ⋮ Study of the pedigree polytope and a sufficiency condition for nonadjacency in the tour polytope ⋮ The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract) ⋮ On pedigree polytopes and Hamiltonian cycles ⋮ On the equivalence of the multistage-insertion and cycle-shrink formulations of the symmetric traveling salesman problem ⋮ Traveling Salesman Problem and Membership in Pedigree Polytope - A Numerical Illustration ⋮ On Pedigree Polytopes and Hamiltonian Cycles

Cites Work

• An analytical comparison of different formulations of the travelling salesman problem
• A classification of formulations for the (time-dependent) traveling salesman problem
• Dynamic Programming Treatment of the Travelling Salesman Problem
• A Dynamic Programming Approach to Sequencing Problems
• Solution of a Large-Scale Traveling-Salesman Problem
• Unnamed Item
• Unnamed Item

This page was built for publication: An alternate formulation of the symmetric traveling salesman problem and its properties