On the graphical relaxation of the symmetric traveling salesman polytope

DOI10.1007/S10107-006-0060-XMaRDI QIDQ877195zbMATH OpenOpenAlexFDO

Authors Gerhard Reinelt, Dirk Oliver Theis, Marcus Oswald

Publication date 19 April 2007

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

Full work available at URL https://doi.org/10.1007/s10107-006-0060-x

zbMATH Keywords

FacetsGraphical Traveling Salesman ProblemPolyhedral combinatoricsPolyhedral computationSymmetric Traveling Salesman Problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Computational aspects related to convexity (52B55)

Recommendations

• The graphical relaxation: A new framework for the symmetric traveling salesman polytope
• Not Every GTSP Facet Induces an STSP Facet
• The Symmetric Traveling Salesman Polytope: New Facets from the Graphical Relaxation
• The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities
• A note on the relationship between the graphical traveling salesman polyhedron, the Symmetric Traveling Salesman Polytope, and the metric cone

Cites work

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3495892 (Why is no real title available?)
• scientific article; zbMATH DE number 2084783 (Why is no real title available?)
• scientific article; zbMATH DE number 795217 (Why is no real title available?)
• scientific article; zbMATH DE number 5021774 (Why is no real title available?)
• A complete description of the traveling salesman polytope on 8 nodes
• A cutting plane procedure for the travelling salesman problem on road networks
• Combinatorial optimization and small polytopes
• DECOMPOSITION AND PARALLELIZATION TECHNIQUES FOR ENUMERATING THE FACETS OF COMBINATORIAL POLYTOPES
• Hamiltonian path and symmetric travelling salesman polytopes
• Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems
• Linear optimization and extensions. Problems and solutions
• On the solution of traveling salesman problems
• On the symmetric travelling salesman problem I: Inequalities
• Separation Algorithms for Classes of STSP Inequalities Arising from a New STSP Relaxation
• Small Travelling Salesman Polytopes
• Survivable networks, linear programming relaxations and the parsimonious property
• 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 in graphs with some excluded minors
• The traveling salesman problem on a graph and some related integer polyhedra
• Worst-case comparison of valid inequalities for the TSP

Cited in

(11)

• The Symmetric Traveling Salesman Polytope: New Facets from the Graphical Relaxation
• The graphical relaxation: A new framework for the symmetric traveling salesman polytope
• A note on the relationship between the graphical traveling salesman polyhedron, the Symmetric Traveling Salesman Polytope, and the metric cone
• Traveling salesman polytopes and cut polytopes. Affine reducibility
• Upgrading edges in the graphical TSP
• On the facial structure of symmetric and graphical traveling salesman polyhedra
• The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract)
• Lower bounds for the symmetric travelling salesman problem from Lagrangean relaxations
• Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem
• Not Every GTSP Facet Induces an STSP Facet
• Exploiting planarity in separation routines for the symmetric traveling salesman problem

Describes a project that uses

Uses Software

• SMAPO

This page was built for publication: On the graphical relaxation of the symmetric traveling salesman polytope

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