On the graphical relaxation of the symmetric traveling salesman polytope
From MaRDI portal
Publication:877195
DOI10.1007/s10107-006-0060-xzbMath1111.52014MaRDI QIDQ877195
Dirk Oliver Theis, Gerhard Reinelt, 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
Facets; Polyhedral combinatorics; Graphical Traveling Salesman Problem; Polyhedral computation; Symmetric Traveling Salesman Problem
52B12: Special polytopes (linear programming, centrally symmetric, etc.)
52B55: Computational aspects related to convexity
90C27: Combinatorial optimization
Uses Software
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
