Hamiltonian path and symmetric travelling salesman polytopes

DOI10.1007/BF01581260zbMath0781.90088MaRDI QIDQ1803617

Yaoguang Wang, Maurice Queyranne

Publication date: 29 June 1993

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

projective approachfacet liftingclique-liftingHamiltonian path polytopesymmetric traveling salesman polytopes

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Related Items

Multi-depot multiple TSP: a polyhedral study and computational results, On the graphical relaxation of the symmetric traveling salesman polytope, A branch-and-cut algorithm for the median-path problem, SC-Hamiltonian graphs and digraphs: new necessary conditions and their impacts, A branch-and-cut algorithm for the target visitation problem, Combinatorial optimization and small polytopes, Three value TSP and linkages with the three value linear spanning 2-forests, Survey of facial results for the traveling salesman polytope

Cites Work

• A cutting plane procedure for the travelling salesman problem on road networks
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• A new class of cutting planes for the symmetric travelling salesman problem
• The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities
• A complete description of the traveling salesman polytope on 8 nodes
• The graphical relaxation: A new framework for the symmetric traveling salesman polytope
• A lifting procedure for asymmetric traveling salesman polytope and a large new class of facets
• The equipartition polytope. I: Formulations, dimension and basic facets
• Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
• On the symmetric travelling salesman problem I: Inequalities
• On the symmetric travelling salesman problem II: Lifting theorems and facets
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• The traveling salesman problem on a graph and some related integer polyhedra
• On the symmetric travelling salesman problem: A computational study
• Small Travelling Salesman Polytopes
• The Crown Inequalities for the Symmetric Traveling Salesman Polytope
• The Binested Inequalities for the Symmetric Traveling Salesman Polytope
• Unnamed Item
• Unnamed Item