J E Beasley

OR-Library is a collection of test data sets for a variety of OR problems.

A full list of the test data sets available in OR-Library can be found here.

Euclidean Steiner problem

There are currently 15 data files.

These data files are the test problems solved in J.E.Beasley
"A heuristic for Euclidean and rectilinear Steiner problems",
European Journal of Operational Research 58 (1992) 284-292.

These data files include the 46 test problems from J.Soukup
and W.F.Chow "Set of test problems for the minimum length 
connection networks" ACM/SIGMAP Newsletter 15 (1973) 48-51.

The following table gives the relationship between test problems
and the appropriate file.

Number of points (n)    File
10                      estein10
20                      estein20
30                      estein30
40                      estein40
50                      estein50
60                      estein60
70                      estein70
80                      estein80
90                      estein90
100                     estein100
250                     estein250
500                     estein500
1000                    estein1000
10000                   estein10000

The Soukup and Chow test problems are in data file estein1.

The format of these data files is:
number of test problems (m)
for each test problem i (i=1,...,m) in turn: 
number of points (n)
for each point j (j=1,...,n): x-coordinate, y-coordinate

Optimal solution information for files estein1, estein10, ...,estein100
can be found in the files estein1opt, estein10opt, ...,estein100opt.
These files were contributed by Martin Zachariasen of the University 
of Copenhagen (email martinz@diku.dk) and were found using the algorithm
described in "Large Euclidean Steiner minimal trees in an hour" by
P. Winter and M. Zachariasen, available here

The format of these files is:
number of test problems (m)
for each test problem i (i=1,...,m) in turn:
   optimal steiner solution value
   minimal spanning tree solution value
   number of Steiner points (S)
   for each Steiner point s (s=1,...,S): x-coordinate, y-coordinate

The largest file is estein1000 of size 350Kb (approximately).
The entire set of files is of size 1100Kb (approximately).

Click here to access these files