Sylvia Boyd

Vertices of the Subtour Elimination Polytope


 

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 Kkyroku 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 sylvia@site.uottawa.ca to let me know how they were useful to you.

 

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