Ivana LJUBIC

Ivana LJUBIC

Professor of Operations Research at the ESSEC Business School

Real-World Instances for the Steiner Tree Problem in Graphs

by Markus Leitner, Ivana Ljubić , Martin Luipersbeck, Markus Prossegger, Max Resch
University of Vienna

Input

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.

Definition

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.

Downloads

GEO instances are available in their original form (including node-coordinates), or after advanced preprocessing as proposed by Ribeiro et al.[4], 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.

Documentation

M. Leitner, I. Ljubić, 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

Bibliography:

  1. Bossa
  2. T. Koch and A. Martin: Solving Steiner tree problems in graphs to optimality, Networks 32(3), pp. 207-232, 1998
  3. 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
  4. 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
  5. SteinLib