Let G = (V, E, T, c) be an undirected graph, with
the set of vertices V and its subset T called terminals, and with the edges E associated with non-negative costs c.
|| The Steiner Tree Problem in Graphs (STP) consists of
finding a connected subgraph T = (V' ,E' ) of G that connects all terminals and minimizes the
sum of the costs of the edges needed to establish the network.
In network design applications the edges of the input graph typically correspond to the local street map, with the edges vertices
representing street intersections and the location of potential customers. The cost c associated with an edge is the
cost of establishing the connection, i.e., of laying the pipe or cable on the corresponding street segment.
| NEW BENCHMARK INSTANCES
We propose two new sets of benchmark instances for the STP that are derived from real-world examples of telecommunication networks:
- GEO Instances: This set contains 23 instances originating from an Austrian city, with different deployment areas and different density concerning the number of terminals.
The graphs contain between 42 481 and 235 686 nodes, 52 552 and 366 093 edges, and between 88 and 6313 terminals.
The simple preprocessing step (see below) was skipped for the GEO instances, it deemed unnecessary, hence no comparison data is available for this step.
- I Instances:
This set contains 85 instances representing deployment areas from various Austrian cities, but they also include rural areas with
smaller population density and very sparse infrastructure. The coordinates and
construction data of the set I cannot be disclosed to the public.
The instances we publish are modified in a way that does not allow inference
of the original data. This is the reason why only simple preprocessed data (see below) is available for the I-instances. The underlying graphs
contain between 7886 and 178 810 nodes, 9265 and 239 552 edges, and between 38 and 4991 terminals.
| DOWNLOAD FILES
|| GEO instances are available in their original form (including node-coordinates), or after advanced preprocessing as proposed by Ribeiro et al., and implemented in Bossa.
I Instances are available after simple preprocessing (node one- and two-degree test), or after advanced preprocessing.
All instances are provided in the SteinLib format.
|| M. Leitner, I. Ljubic, M. Luipersbeck, M. Prossegger, M. Resch: New Real-world Instances for the Steiner Tree Problem in Graphs, Technical Report, ISOR, Uni Wien, 2014
| Instance GEO-107
|| Instance GEO-203
|| Instance GEO-309
- T. Koch and A. Martin: Solving Steiner tree problems in graphs to optimality, Networks 32(3), pp. 207-232, 1998
- M. Prossegger: Generation of a Weighted Network Graph based-on Hybrid Spatial Data,
Proceedings of The Fifth International Conference on Advanced Geographic Information Systems, Applications, and Services,
GEOProcessing, Nice, France, pp. 120--124, 2013
- C.C. Ribeiro, E. Uchoa, R.F.F. Werneck: A hybrid GRASP with perturbations for the Steiner problem in graphs,
INFORMS Journal on Computing 14(3), pp. 228-246,2002