SMAPO

Symmetric and Graphical Traveling Salesman polyhedra

The Symmetric Traveling Salesman Problem (STSP) asks for a minimum length Hamilton cycle in a complete graph. The Symmetric Traveling Salesman Polytope on n nodes, STSP(n), is the convex hull of all incidence vectors edge sets of Hamilton cycles.
 The Graphical Traveling Salesman Problem (GTSP) is defined analogously to the STSP, except that it allows to visit nodes and/or traverse edges more than once. The Graphical Traveling Salesman Polyhedron on n nodes, GTSP(n), is equal to the convex hull of all incidence vectors of edge multi-sets of spanning closed walks.

The facets of STSP and GTSP partition into classes: all members of a class are equal modulo permutation of nodes. The inequalities files list only one representative per class. The facet defining inequalities are given in tight triangular form, except for the non-negativity inequalities xe ≥ 0.

STSP(5)

Status: complete description
Only non-negativity and subtour facets.

GTSP(5)

Status: complete description (Fonlupt, J. and D. Naddef, 1992, The Traveling Salesman Problem in graphs with some excluded minors. Math. Program. 53 (2), 147--172)
Only non-negativity, degree, and subtour facets.

STSP(6)

Status: complete description
# Classes 4   Access data.
# Total 100

GTSP(6)

Status: complete description (Oswald, M., G. Reinelt and D.O. Theis, 2005, Not every GTSP facet induces an STSP facet, in: M. Jünger and V. Kaibel (eds.) Integer Programming and Combinatorial Optimization 2005, Springer)
# Classes 4 + 1 degree   Access data.
# Total 100 + 6 degree

STSP(7)

Status: complete description (Boyd, S.C. and W.H. Cunningham, 1991, Small Travelling Salesman Polytopes. Math. Oper. Res., 16, 259--271)
# Classes 6   Access data.
# Total 3,437

GTSP(7)

Status: complete description (Oswald, M., G. Reinelt and D.O. Theis, 2005, Not every GTSP facet induces an STSP facet, in: M. Jünger and V. Kaibel (eds.) Integer Programming and Combinatorial Optimization 2005, Springer)
# Classes 6 + 1 degree   Access data.
# Total 3,437 + 7 degree

STSP(8)

Status: complete description (Christof, T., M. Jünger and G. Reinelt, 1991, A Complete Description of the Traveling Salesman Polytope on 8 Nodes. Oper. Res. Lett., 10, 497--500)
# Classes 24   Access data.
# Total 194,187

GTSP(8)

Status: complete description (Oswald, M., G. Reinelt and D.O. Theis, 2005, Not every GTSP facet induces an STSP facet, in: M. Jünger and V. Kaibel (eds.) Integer Programming and Combinatorial Optimization 2005, Springer)
# Classes 24 + 1 degree   Access data.
# Total 194,187 + 8 degree

STSP(9)

Status: complete description (Christof, T. and G. Reinelt, 1996, Combinatorial optimization and small polytopes. Top 4 (1), 1--53)
# Classes 192   Access data.
# Total 42,104,442

GTSP(9)

Status: complete description (Oswald, M., G. Reinelt and D.O. Theis, The geometry of the Graphical Relaxation of the Symmetric Traveling Salesman Polytope, abstract
# Classes 192 + 1 + 1 degree   Access data.
# Total 42,104,442 + 362880 + 9 degree

STSP(10)

Status: conjectured complete description (Christof, T. and G. Reinelt, 2001, Decomposition and Parallelization Techniques for Enumerating the Facets of Combinatorial Polytopes. Int. J. Comput. Geom. Appl. 11, 423--437)
# Classes 15,379   Acces data: text, gz
# Total 51,043,900,866

GTSP(10)

Status: conjectured complete description (Oswald, M., G. Reinelt and D.O. Theis, D. Büttner: Improving the Performance of Outer Description Calculations of GTSP Polyhedra using High Performance Computing Methods)
# Classes 15379 + 243 + 1 degree   Access data of 243 non NR classes.

References

Jünger, M., G. Reinelt and G. Rinaldi
1995
The Traveling Salesman Problem
M. Ball, T. Magnanti, C.L. Monma and G.L. Nemhauser, eds. Handbooks in Operations Research and Management Sciences: Networks North-Holland

Grötschel, M. and M.W. Padberg
1985
Polyhedral theory
E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, eds. The Traveling Salesman Problem
Chichester:Wiley & Sons

Naddef D. and G. Rinaldi
1993
The Graphical Relaxation: A New Framework for the Symmetric Travelling Salesman Polytope
Math. Program., 58, 53--87

A library of STSP problem instances is provided by TSPLIB.

Comments or suggestions? Mail to: comopt at informatik dot uni-heidelberg dot de

Last modified: Januar + September 2011