On the graphical relaxation of the symmetric traveling salesman polytope

DOI10.1007/s10107-006-0060-xzbMath1111.52014OpenAlexW2018781529MaRDI QIDQ877195

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

FacetsPolyhedral combinatoricsGraphical Traveling Salesman ProblemPolyhedral computationSymmetric Traveling Salesman Problem

Mathematics Subject Classification ID

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

Related Items

Upgrading edges in the graphical TSP, The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract), A note on the relationship between the graphical traveling salesman polyhedron, the Symmetric Traveling Salesman Polytope, and the metric cone, On the facial structure of symmetric and graphical traveling salesman polyhedra

Uses Software

• SMAPO

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Survivable networks, linear programming relaxations and the parsimonious property
• A cutting plane procedure for the travelling salesman problem on road networks
• On the solution of traveling salesman problems
• The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities
• The traveling salesman problem in graphs with some excluded minors
• A complete description of the traveling salesman polytope on 8 nodes
• Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems
• The graphical relaxation: A new framework for the symmetric traveling salesman polytope
• Hamiltonian path and symmetric travelling salesman polytopes
• Combinatorial optimization and small polytopes
• Worst-case comparison of valid inequalities for the TSP
• On the symmetric travelling salesman problem I: Inequalities
• The traveling salesman problem on a graph and some related integer polyhedra
• Small Travelling Salesman Polytopes
• DECOMPOSITION AND PARALLELIZATION TECHNIQUES FOR ENUMERATING THE FACETS OF COMBINATORIAL POLYTOPES
• Separation Algorithms for Classes of STSP Inequalities Arising from a New STSP Relaxation
• Linear optimization and extensions. Problems and solutions