The Subtour
Elimination Problem (SEP) is the LP relaxation of the Symmetric Travelling
Salesman Problem. Let Sn represent the polytope
associated with the SEP on n nodes.
Below are the files that contain a
complete list of all the vertices of Sn ,6 £ n ≤ 12, which have
non-isomorphic weighted support graphs.
Note that for n £ 5, all the vertices of Sn represent TSP tours. The description of how these files were
generated for 6 £ n ≤ 10 can be found in
Benoit, G., Boyd, S. (2008), Finding the exact integrality gap for small
traveling salesman problems (journal version), Mathematics of Operations
Research, Volume 33, Number 4, 921-931.
and for n=11, 12 can be found in
Boyd, S.,
Elliott-Magwood, P. (2010), Structure
of the Extreme Points of the Subtour Elimination
Problem of the STSP, In: S. Iwata, editor, Combinatorial Optimization and Discrete Algorithms, RIMS Kôkyûroku Bessatsu B23, Kyoto University, Kyoto, Japan, 33-47.
Let the nodes of the complete graph Kn be labelled 1, 2, 3, ..., n. In these
files, each line of text represents a vertex x of Sn,
where the values of xe for all edges e of
the complete graph Kn are
listed in the edge order 1-2, 1-3, 1-4, ..., 1-n, 2-3, 2-4, 2-5, ..., 2-n, 3-4,
.... etc.. Note
that the files do not include the tour for
6 £ n ≤ 10, but do include it for
n=11, 12.
If you desire to use these lists for
your research you are welcome to do so, but it would be appreciated if you
could reference this work, and contact me at
· Vertices for n=6 nodes: vertices_6.txt
· Vertices for n=7 nodes: vertices_7.txt
· Vertices for n=8 nodes: vertices_8.txt
· Vertices for n=9 nodes: vertices_9.txt
· Vertices for n=10 nodes: vertices_10.txt
Drawings of the weighted support graphs for n = 10: 10nodeverticespics.ps
· Vertices for n=11 nodes: vertices_11.txt
· Vertices for n=12 nodes: vertices_12.txt