Traveling Salesman Problem and Membership in Pedigree Polytope - A Numerical Illustration

DOI10.1007/978-3-540-87477-5_16zbMath1160.90629MaRDI QIDQ3627687

Tiru S. Arthanari, Laleh Haerian Ardekani

Publication date: 13 May 2009

Published in: Communications in Computer and Information Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-87477-5_16

zbMATH Keywords

combinatorial optimization; traveling salesman problem; membership problem; multistage insertion formulation; pedigree polytope

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C27: Combinatorial optimization

Uses Software

• TSPLIB
• Concorde

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An analytical comparison of different formulations of the travelling salesman problem
• Geometric algorithms and combinatorial optimization
• The traveling salesman. Computational solutions for RSP applications
• An alternate formulation of the symmetric traveling salesman problem and its properties
• On pedigree polytopes and Hamiltonian cycles
• Integer Programming Formulation of Traveling Salesman Problems
• A New Formulation for the Travelling Salesman Problem
• On the Membership Problem of the Pedigree Polytope
• The adjacency relation on the traveling salesman polytope is NP-Complete
• Technical Note—An n-Constraint Formulation of the (Time-Dependent) Traveling Salesman Problem
• A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem
• On the equivalence of the multistage-insertion and cycle-shrink formulations of the symmetric traveling salesman problem