The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities

DOI10.1007/BF01586945zbMath0748.90072OpenAlexW2021199373WikidataQ58002948 ScholiaQ58002948MaRDI QIDQ1181903

Giovanni Rinaldi, Denis Naddef

Publication date: 27 June 1992

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

Full work available at URL: https://doi.org/10.1007/bf01586945

zbMATH Keywords

Hamilton cycleTraveling Salesman Problemfacet- inducing inequalitiesgraphical relaxation

Mathematics Subject Classification ID

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

Related Items

A polyhedral approach to the rural postman problem, New techniques for cost sharing in combinatorial optimization games, Routing problems: A bibliography, Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies, On the graphical relaxation of the symmetric traveling salesman polytope, Upgrading edges in the graphical TSP, New results on the windy postman problem, On the general routing polytope, The anti-join composition and polyhedra, Traveling salesman path problems, Polyhedral study of the capacitated vehicle routing problem, A note on the relationship between the graphical traveling salesman polyhedron, the Symmetric Traveling Salesman Polytope, and the metric cone, Zigzag inequalities: a new class of facet-inducing inequalities for arc routing problems, Recent results on Arc Routing Problems: An annotated bibliography, The graphical relaxation: A new framework for the symmetric traveling salesman polytope, Hamiltonian path and symmetric travelling salesman polytopes, The general routing polyhedron: A unifying framework, New inequalities for the general routing problem, The general routing problem polyhedron: Facets from the RPP and GTSP polyhedra, On the facets and diameter of thek-cycle polytope, On the facial structure of symmetric and graphical traveling salesman polyhedra, Survey of facial results for the traveling salesman polytope

Cites Work

• Unnamed Item
• Unnamed Item
• A new class of cutting planes for the symmetric travelling salesman problem
• The graphical relaxation: A new framework for the symmetric traveling salesman polytope
• Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
• On the symmetric travelling salesman problem I: Inequalities
• 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: Solution of a 120-city problem
• On the symmetric travelling salesman problem: A computational study
• Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
• The Binested Inequalities for the Symmetric Traveling Salesman Polytope
• Properties of vertex packing and independence system polyhedra
• On the facial structure of set packing polyhedra
• The Symmetric Traveling Salesman Polytope: New Facets from the Graphical Relaxation
• Edmonds polytopes and weakly hamiltonian graphs