Hamiltonian path and symmetric travelling salesman polytopes

DOI10.1007/BF01581260MaRDI QIDQ1803617zbMATH OpenFDO

Authors Maurice Queyranne, Yaoguang Wang

Publication date 29 June 1993

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

zbMATH Keywords

facet liftingclique-liftingHamiltonian path polytopeprojective approachsymmetric traveling salesman polytopes

Mathematics Subject Classification ID

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

Recommendations

• The Symmetric Traveling Salesman Polytope: New Facets from the Graphical Relaxation
• scientific article; zbMATH DE number 3943559
• On the facial structure of symmetric and graphical traveling salesman polyhedra
• scientific article; zbMATH DE number 1031384
• Symmetric Inequalities and Their Composition for Asymmetric Travelling Salesman Polytopes

Cites work

• scientific article; zbMATH DE number 4027206 (Why is no real title available?)
• scientific article; zbMATH DE number 3495892 (Why is no real title available?)
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• A complete description of the traveling salesman polytope on 8 nodes
• A cutting plane procedure for the travelling salesman problem on road networks
• A lifting procedure for asymmetric traveling salesman polytope and a large new class of facets
• A new class of cutting planes for the symmetric travelling salesman problem
• 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
• On the symmetric travelling salesman problem: A computational study
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• Small Travelling Salesman Polytopes
• The Binested Inequalities for the Symmetric Traveling Salesman Polytope
• The Crown Inequalities for the Symmetric Traveling Salesman Polytope
• The equipartition polytope. I: Formulations, dimension and basic facets
• The graphical relaxation: A new framework for the symmetric traveling salesman polytope
• The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities
• The traveling salesman problem on a graph and some related integer polyhedra

Cited in

(10)

• A branch-and-cut algorithm for the median-path problem
• SC-Hamiltonian graphs and digraphs: new necessary conditions and their impacts
• On the graphical relaxation of the symmetric traveling salesman polytope
• Traveling salesman polytopes and cut polytopes. Affine reducibility
• Three value TSP and linkages with the three value linear spanning 2-forests
• A branch-and-cut algorithm for the target visitation problem
• Multi-depot multiple TSP: a polyhedral study and computational results
• Combinatorial optimization and small polytopes
• Survey of facial results for the traveling salesman polytope
• The Hamiltonian Cycle and Travelling Salesman Problems in cP Systems

This page was built for publication: Hamiltonian path and symmetric travelling salesman polytopes

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