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