Data for TSP Constant

Euclidean Instances, Integer Coordinates in [0,10**7] Square

table.euc - Summary of Euclidean data. Each line gives n = # of cities followed by the mean and standard deviation for the TSP optimal, the subtour relaxation bound, and the percentage gap between the optimal value and the bound. These results are each use a sample of 10,000 random instances.
table.euc.1m - Summary of Euclidean data for a sample of 1,000,000 random instances.

etsp.1000 - list of optimal Eulidean TSP values. Each line gives n and the mean scaled tour length (over 10,000 instances). Values for n = 10, 20, ... , 1000
Fitting with gnuplot to f(x) = beta + a/sqrt(x) + b/x (with n >= 100), gives beta = 0.712029, a = 0.58816, b = 0.568922

esub.1000 - list of optimal Eulidean subtour values. Each line gives n and the mean scaled subtour value (over 10,000 instances). Values for n = 10, 20, ... , 1000
egap.1000 - list of relative gaps between the Euclidean subtour bound and the TSP values. Each line gives n and the mean gap (over 10,000 instances). Values for n = 10, 20, ... , 1000
Fitting with gnuplot to f(x) = beta + a/sqrt(x) + b/x (with n >= 300), gives beta = 0.598202, a = 5.86522, b = -43.0213

esub.100000 - list of optimal Eulidean subtour values. Each line gives n and the mean scaled subtour value (over 10,000 instances). Values for n = 10, 20, ... , 1000, 2000, 3000, ... , 10000, 20000, 30000, ... , 100000 Fitting with gnuplot to f(x) = beta + a/sqrt(x) + b/x (with n >= 100), gives beta = 0.707938, a = 0.537951, b = 0.893107

beta_100_1000.gif - plot of the Eulidean TSP values.

Optimal TSP Values

beta.100_1000.gz - raw data for the 10,000 samples for n = 100, 110, 120 , ... , 1000. Each line has an identifier (from 0 up to 9,999) followed by 91 values, one for each n.

X.tgz - Raw data for TSP Values.

Xsub.tgz - Raw data for Subtour Values.

Heuristic TSP Values (upper and lower bounds on optimal value)

bounds.100k - 100 samples for n = 100,000. Each line has an identifier (from 0 up to 99) followed by 2 values, the tour length and the lower-bound.

tours.1mil - 25 samples for n = 1,000,000. Each line has an identifier (from 0 up to 24) followed by 1 value, the tour length.

tours.10mil - 10 samples for n = 10,000,000. Each line has an identifier (from 0 up to 9) followed by 1 value, the tour length.



Toroidal Instances, Integer Coordinates in [0,10**7] Square
The edges of the square are identified.

table.tor - Summary of toroidal data. Values for 10, 20, ..., 100, 200, ... , 1000 are over 1,000,000 random instances.

ttsp.1000.1m - list of optimal Toroidal TSP values. Each line gives n and the mean scaled tour length (over 1,000,000 instances). Values for n = 10, 20, ... , 100, 200, ... , 1000
Fitting with gnuplot to f(x) = beta + a/sqrt(x) + b/x (with n >= 100), gives beta = 0.712389, a = 0.000584166, b = 0.0421982

tsub.10000.1m - list of optimal Toroidal subtour values. Each line gives n and the mean scaled subtour value (over 1,000,000 instances). Values for n = 10, 20, ... , 100, 200, ... , 1000, 2000, ..., 10000
tgap.1000.1m - list of relative gaps between the Toroidal subtour bound and the TSP values. Each line gives n and the mean gap (over 1,000,000 instances). Values for n = 10, 20, ... , 100, 200, ... , 1000

tor_100_1000.gif - plot of the Toroidal TSP values.

Optimal TSP Values (Raw data files are no longer on web.)
TOROPT.tgz - Optimal TSP Values
tho.2000.gz - Optimal TSP Values for n = 2000
1,000,000 samples for each of n = 100, 200, ... , 1000.
100,000 samples for n = 2000.

Subtour Values (Raw data files are no longer on web.)
TORSUB.tgz - Subtour TSP Values
1,000,000 samples for each of n = 100, 200, ... , 1000.
1,000,000 samples for each of n = 1000, 2000, ... , 10000.
1000 samples for n = 100,000.
100 samples for n = 1,000,000.