On the graphical relaxation of the symmetric traveling salesman polytope

DOI10.1007/S10107-006-0060-XzbMATH Open1111.52014OpenAlexW2018781529MaRDI QIDQ877195FDOQ877195

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

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

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)

Cites Work

• Combinatorial optimization and small polytopes
• Title not available (Why is that?)
• A cutting plane procedure for the travelling salesman problem on road networks
• The traveling salesman problem on a graph and some related integer polyhedra
• On the symmetric travelling salesman problem I: Inequalities
• On the solution of traveling salesman problems
• Linear optimization and extensions. Problems and solutions
• Worst-case comparison of valid inequalities for the TSP
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• A complete description of the traveling salesman polytope on 8 nodes
• Survivable networks, linear programming relaxations and the parsimonious property
• DECOMPOSITION AND PARALLELIZATION TECHNIQUES FOR ENUMERATING THE FACETS OF COMBINATORIAL POLYTOPES
• The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities
• The traveling salesman problem in graphs with some excluded minors
• Small Travelling Salesman Polytopes
• Separation Algorithms for Classes of STSP Inequalities Arising from a New STSP Relaxation
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (11)

• 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
• Not Every GTSP Facet Induces an STSP Facet
• Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem
• Exploiting planarity in separation routines for the symmetric traveling salesman problem
• The Symmetric Traveling Salesman Polytope: New Facets from the Graphical Relaxation

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)