Hamiltonian path and symmetric travelling salesman polytopes

DOI10.1007/BF01581260zbMATH Open0781.90088MaRDI QIDQ1803617FDOQ1803617

Authors: Maurice Queyranne, Yaoguang Wang 

Publication date: 29 June 1993

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

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

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)

Cites Work

• A cutting plane procedure for the travelling salesman problem on road networks
• 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
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• 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
• Title not available (Why is that?)
• The equipartition polytope. I: Formulations, dimension and basic facets
• The graphical relaxation: A new framework for the symmetric traveling salesman polytope
• A complete description of the traveling salesman polytope on 8 nodes
• A lifting procedure for asymmetric traveling salesman polytope and a large new class of facets
• On the symmetric travelling salesman problem: A computational study
• 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
• Small Travelling Salesman Polytopes
• Title not available (Why is that?)
• The Binested Inequalities for the Symmetric Traveling Salesman Polytope
• The Crown Inequalities for the Symmetric Traveling Salesman Polytope

Cited In (10)

• A branch-and-cut algorithm for the median-path problem
• SC-Hamiltonian graphs and digraphs: new necessary conditions and their impacts
• Traveling salesman polytopes and cut polytopes. Affine reducibility
• On the graphical relaxation of the symmetric traveling salesman polytope
• 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
• The Hamiltonian Cycle and Travelling Salesman Problems in cP Systems
• Survey of facial results for the traveling salesman polytope

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)