On the facial structure of symmetric and graphical traveling salesman polyhedra

DOI10.1016/j.disopt.2013.12.003zbMath1308.52011arXiv0712.1269OpenAlexW2081534497MaRDI QIDQ2339807

Dirk Oliver Theis

Publication date: 9 April 2015

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0712.1269

zbMATH Keywords

rotationprojectiongraphical traveling salesman polyhedronsymmetric traveling salesman polyhedron

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items

The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract)

Uses Software

• Concorde
• PORTA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On a class of metrics related to graph layout problems
• Survivable networks, linear programming relaxations and the parsimonious property
• A note on the relationship between the graphical traveling salesman polyhedron, the Symmetric Traveling Salesman Polytope, and the metric cone
• On the graphical relaxation of 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
• A complete description of the traveling salesman polytope on 8 nodes
• Faces with large diameter on the symmetric traveling salesman polytope
• The monotonic diameter of traveling salesman polytopes
• Shelling polyhedral 3-balls and 4-polytopes
• Interchange graphs and the Hamiltonian cycle polytope
• Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems
• The graphical relaxation: A new framework for the symmetric traveling salesman polytope
• Combinatorial optimization and small polytopes
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Worst-case comparison of valid inequalities for the TSP
• Faces of diameter two on the Hamiltonian cycle polytope
• All 0-1 polytopes are traveling salesman polytopes
• On the symmetric travelling salesman problem I: Inequalities
• On the symmetric travelling salesman problem II: Lifting theorems and facets
• Not Every GTSP Facet Induces an STSP Facet
• The traveling salesman problem on a graph and some related integer polyhedra
• Small Travelling Salesman Polytopes
• A Bound of 4 for the Diameter of the Symmetric Traveling Salesman Polytope
• Convex Polytopes
• DECOMPOSITION AND PARALLELIZATION TECHNIQUES FOR ENUMERATING THE FACETS OF COMBINATORIAL POLYTOPES
• Solution of a Large-Scale Traveling-Salesman Problem
• The Symmetric Traveling Salesman Polytope: New Facets from the Graphical Relaxation
• The Symmetric Traveling Salesman Polytope Revisited
• Separation Algorithms for Classes of STSP Inequalities Arising from a New STSP Relaxation