This page contains pointers to the benchmark instances used in the challenge. If you have instances you would like to contribute, please contact the organizers. We want this set to grow significantly as the challenge progresses! Contributions to any interesting variant of the classical Steiner tree problem are welcome.

Instances for all problems are given in the STP format and natural variants. The format should be clear enough from the files themselves, but detailed specifications will be posted soon.

Note that some (clearly marked) instances have been recently updated (mostly to fix formatting issues). Please make sure you test the latest version.

To help compare codes run on different machines, the challenge organizers have prepared a single-file C/C++ program for calibration purposes. We ask all participants in the competition to perform the following steps:

1. Create a temporary folder/directory (we will refer to it as temp below, but actual name does not matter).
2. Download this zip file, which contains a small set of test instances used by our benchmark. Unzip the file and copy its contents to temp.
3. Download the benchmark code, compile it with your favorite compiler using full optimization, and save the executable to temp.
4. Run the executable (without parameters, inside temp). It will read some files, perform a series of computations (minimum spanning trees), and finally output a score. Higher scores indicate faster machines. A machine that is twice as fast as another will produce a score that is twice as high.
5. In your paper submission, please report the score of the machine you used for testing.

This should make it easy to compare results from different articles. This method is far from perfect, but should be more accurate than simply comparing clock frequencies.

If you find any issues with the code, let the organizers know as soon as possible.

The capacitated ring tree problem (CRTP) combines the capacitated Steiner tree problem and the vehicle routing problem with homogeneous demands. A ring tree is a tree with an optional additional edge that closes a unique cycle. Such a cycle is called a ring and the nodes on it are called ring nodes. The CRTP asks for a network of minimal overall edge cost that connects given customers to a depot by ring trees. Ring trees are required to intersect in the depot, which must be either a ring node in a ring tree or a node of degree one if the ring tree does not contain a ring. Customers are predefined as of type 1 (which can be either ring nodes or nodes in tree substructures) or type 2 (which must be ring nodes). Additionally, optional Steiner nodes can be used as intermediate network nodes if advantageous. Capacity constraints bound both the number of the ring trees as well as the number of customers allowed in each ring tree. The objective is to minimize the total cost of the edges used.

• TSPR: Problems generated from TSPLIB instances by Alessandro Hill and Stefan Voss, with randomly assigned customer types. More details can be found at Hill and Voss (2014).

In the classical SPG problem, one is given a graph with nonnegative weights on edges and with a subset of the vertices marked as terminals. The objective is to find a minimum-weight connecting all terminals.

• SteinLib: A collection of instances for the Steiner tree problem in graphs.

• Vienna: Instances generated from real-world telecommunication networks by Ivana Ljubic's group at the University of Vienna. The file contains two subfamilies (GEO and I), each with two different levels of preprocessing. Detailed descriptions of the instances can be found on a technical report by Leitner et al. (2014) and on a dedicated webpage. (Last updated on August 24, 2014.)

• Copenhagen14: Graphs based on the IND, RC and RT instances for the Obstacle-avoiding rectilinear Steiner tree problem. For each instance, the ObSteiner software package of Huang and Young (2013) was used to generate a set of full Steiner trees (FSTs), which were then merged into a single graph. This is an optimality-preserving transformation. These graph instances were made available for the challenge by Daniel Juhl.

• PUCN: Unweighted versions of the code covering instances from the PUC series. Instances made available for the challenge by Ivana Ljubic.

• GAPS: Synthetic instances reflecting generalizations of Steiner tree LP gap examples from various sources, including Byrka et al. (2013) and Polzin (2003). Instances contributed to the challenge by Stephan Beyer.

• EFST: These instances, made available for the challenge by Daniel Juhl, David M. Warme, Pawel Winter, and Martin Zachariasen, are obtained by full Steiner tree generation for the classical Euclidean Steiner tree problem in the plane (as explained in their challenge presentation). By solving the graph problem, the underlying Euclidean Steiner tree problem is solved to optimality (modulo rounding errors in the transformation).

  Each instance has one version with fractional numbers suitable for 64-bit floating point types, and another where the weights are suitable for 64-bit unsigned integer types. In the latter case the original distances have been scaled with a suitable factor of 10^k and rounded to the nearest integer such that the sum of edge weights is less than 2^64; these instance sets have suffix "INT". The authors recommend using the floating point instances if at all possible, since scaling and rounding to integers in general results in a worse approximation of the original Euclidean distances.

  There are four sets of instances:

  • TSPEFST | TSPEFSTINT: Instances from TSPLIB with 198 to 18,512 terminals.
  • R25KEFST | R25KEFSTINT: 15 randomly generated instances with 25,000 terminals.
  • R50KEFST | R50KEFSTINT: 15 randomly generated instances with 50,000 terminals.
  • R100KEFST | R100KEFSTINT: 15 randomly generated instances with 100,000 terminals.

  The best known bounds for these instances as of March 24, 2015 are available as a text file. For instances in which optimality is not proven, a lower bound is also provided. (INT instances last updated on May 10, 2015.)

Additional resources:

• Updated report by Polzin and Vahdati Daneshmand. This report contains up-to-date results obtained by the state-of-the-art algorithm described in the PhD theses of Tobias Polzin and Siavash Vahdati Daneshmand. The authors reran their algorithm using current computational resources (machine and LP solver), and tested both SteinLib and challenge instances. The algorithm itself is essentially unchanged.

• Best bounds as of September 12, 2014 for SteinLib instances. Collectively, the papers submitted to challenge improved the best known bounds of dozens of instances. For such instances, the file indicates the paper(s) that found the new upper bound: GKRS (Gamrath et al.), FLLLMRSS (Sinnl et al.), UW (Uchoa and Werneck), or PV (the above report by Polzin and Vahdati Daneshmand).

• Best bounds as of August 1, 2014 for SteinLib instances. We stress that these are the best published bounds; several groups have already improved some of them while preparing for the challenge. To ensure consistency, however, we asked that submissions to the workshop compare against the published bounds above when reporting relative errors. The bounds above come mostly from the SteinLib, with some updates from Biazzo et al. (2012), Ribeiro et al. (2001), and Uchoa and Werneck (2012).

The input of the degree-constrained Steiner tree (DCST) problem is a graph with weights on edges, and the goal is to find a minimum Steiner tree such that each node satisfies a given degree constraint (or prove that such a Steiner tree does not exist).

• TreeFam: Instances from a computational biology application, corresponding to protein families taken from the phylogeny database TreeFam. Each node represents a protein sequence and edge weights correspond to alignment scores. The graphs are complete. There are instances corresponding to two types of minimum Steiner trees: (1) every node has degree at most three; and (2) each terminal has degree one, and every nonterminal has degree either zero or three. All instances were made available for the challenge by Susanne Pape.

The input of the HCDST problem is a directed graph G=(V,A) with weights on arcs, a root vertex r, a subset T of V of terminals, and integer H. The object is to find a minimum-weight arborescence rooted at A which (1) contains all vertices in T as leaves; and (2) uses no more than H arcs in total.

• RELAY: Instances from 3D placement of unmanned aerial vehicles used for multi-target surveillance, as tested by Burdakov et al. (2014) (to be presented at the workshop). They have a relatively small number of terminal nodes and a very large number of nodes and arcs. Given their size, the instances are maintained externally and use a different compression tool. Instances contributed to the challenge by Oleg Burdakov and Jonas Kvarnström.

The input to the GSMT problem is a set of points (terminals) on the plane (or higher dimensions). We consider two variants. In the rectilinear (RSMT) case, the goal is to find the minimum-length rectilinear tree (with axis-aligned segments) connecting all terminals. In the Euclidean (ESMT) case, the tree can use arbitrary segments. The instances below can be used for either variant.

• DEG: Each file in this series contains a thousand randomly generated instances with the same number of terminals, introduced by Chu and Wong (2008). Each file consists of concatenated STP instances. (Last updated on October 14, 2013.)

• IBM: The IBM suite was created by Chu and Wong (2008) from the ISPD98 benchmark suite, which in turn are translated from internal IBM designs. Each file (in concatenated STP format) contains thousands of instances, but many have only 2 or 3 terminals. (Last updated on October 14, 2013.)

• ESTEIN: This series includes instances tested by Beasley (1992). Each file is in concatenated STP format. The first file contains 46 instances from Soukup and Chow (1973). The remaining inputs, with 10 to 10000 points chosen at random in the unit square, were generated by Beasley himself. These instances are also available (in different format) from the OR-Library. (Last updated on October 14, 2013.)

• ESTEIN-3D: Three-dimensional instances obtained by adding a random z-coordinate to each point in the (two-dimensional) ESTEIN instances. Instances made available for the challenge by Daniel Juhl.

• PROTEIN-3D: Three-dimentional instances generated from the coordinates of atoms in five proteins (1X0O, 2JZC, 3WCZ, 4OAA, and 2OED) based on PDB files. Five different configurations of 2OED are used, based on PDB files provided by Wouter Boomsma from the Bioinformatics Centre at the University of Copenhagen; the corresponding instances start with 'W'. Two instances have been generated per PDB file: 1) where all atoms are included (identified by '_all') and 2) where some atoms (almost all carbon, all nitrogen and some oxygen and sulfur). Instances made available for the challenge by Daisy Jørgensen and Pawel Winter.

• CANCER: Instances derived from a problem in cancer genomics to model the progression of genetic changes in a solid tumor Chowdhury et al. (2013). A more detailed description can be found in the zip file. Instances made available for the challenge by Alejandro A. Schäffer.

• bonn-3d: Three-dimensional rectilinear Steiner tree problems from Hougardy et al. (2015). Instances made available after the challenge by Jannik Silvanus.

The following instances were made available for the challenge by Marcia Fampa, Jon Lee, and Wendel Melo:

• IOWA2005: Randomly-generated instances with 3 to 5 dimensions and 10 terminals from Fampa and Anstreicher (2008).

• SMITH: Instances from Smith (1992) representing simplices and octahedra in high dimensions (up to 8).

• SOLIDS: Three-dimensional instances whose terminals are the vertices of the five platonic solids.

• CARIOCA: Random instances with 3, 4, and 5 dimensions and 11 to 20 terminals.

The following instances were contributed to the challenge by Daniel Juhl, and tested in The GeoSteiner Software Package for Computing Steiner Trees in the Plane: An Updated Computational Study, by D. Juhl, D. M. Warme, P. Winter and M. Zachariasen (to be presented at the challenge):

• ESTEIN-large: a subset of with the 31 largest instances from the ESTEIN series above. (Last updated on November 10, 2014.)

• RandPoints: Instances with size 1000, 2000, ..., 10000 (with 15 instances for each size). The points are randomly and uniformly distributed within a 10,000,000 times 10,000,000 integral square, then scaled into the unit square. These instances were generated by the rand_points program included in the GeoSteiner package. (Last updated on November 10, 2014.)

• TSPLIB: Set of 46 instances from the TSPLIB, a library of instances for the traveling salesman problem mainly drawn from the real-world. This set include all geometric instances of size 500 or greater, as well as all instances used by Warme et al. (2000). (Last updated on November 10, 2014.)

In the MWCS problem, the input is a graph with (possibly negative) node weights. The goal is to find a subtree that maximizes the sum of its node weights.

• ACTMOD: Instances from integrative biological network analysis, in which the task is to find active modules (sets of connected genes likely involved in a common cellular mechanism). Note that the instances are not necessarily connected. For a detailed description of the problem see Dittrich et al. (2008). These instances were made available for the challenge by Gunnar W. Klau and Mohammed El-Kebir.

• JMPALMK: Euclidean instances created by Álvares-Miranda et al. (2013) based on random geometric instances described by Johnson et al. (1999). Instances made available for the challenge by Gunnar W. Klau. (Last updated on November 10, 2014.)

• GAM: Instances from network enrichment analysis used to identify active modules, as described in Loboda et al. (2016). Instances made available after the challenge by Alexey A. Sergushichev.

The GMWCS problem is an extension of the MWCS including (possibly negative) edge weights.

• GMWCS-GAM: Instances from network enrichment analysis used to identify active modules, as described in Loboda et al. (2016). Instances made available after the challenge by Alexey A. Sergushichev.

In the MVDST problem, one is given a weighted undirected graph, M disjoint sets of terminals (each with its own root), and a hop limit H. The goal is to find M vertex-disjoint Steiner trees, one for each set of terminals, such that (1) every terminal is within at most H hops from its root and (2) the sum of the weights of all edges used is minimized.

• Polito: Instances tested in On the performance of a cavity method based algorithm for the Prize-Collecting Steiner Tree Problem on graphs, by Biazzo et al., which will be presented at the challenge. A link to the actual paper will be added once the final version is available. These instances include regular (fixed-degree) graphs, Erdos-Renyi random graphs, and fully connected (complete) graphs. See zip file for details. Instances made available for the challenge by Anna Muntoni.

The NWSPG is a generalization of the Steiner Problem in Graphs in which both vertices and edges have weights. The objective is to connect all terminals while minimizing the total weight (including vertices and edges) of the corresponding tree.

• HIV: Instances from a Computational Biology application, contributed by Sharon Hüffner and Falk Hüffner. The weights of both nodes and edges are negative log values of probabilities. For a node, this is the probability of its existence; for an edge, it is the probability of the corresponding transition. Terminals are nodes that exist with high probability (0.95 or more). The node-weighted minimum Steiner tree is the most parsimonious explanation for the empirical data. (Last updated on November 4, 2013.)

In the OARSMT problem, the input is a set of terminals on the plane and a set of obstacles, and the goal is to find the minimum-length rectilinear tree (with axis-aligned segments) connecting all terminals without going through the interior of any obstacle. Obstacles are axis-aligned rectangles and described by the coordinates of two opposite corners (as x1 y1 x2 y2). While the solution tree is not allowed to enter an obstacle, it is allowed to use segments along their borders. Some instances may contain overlapping obstacles.

• RC: Randomly generated instances introduced by Feng et al. (2006). Made available for the challenge by Chris Chu. (Last updated on October 14, 2013.)

• IND: Industrial test cases from Synopsys, first used by Lin et al. (2008). Made available for the challenge by Chris Chu. (Last updated on October 14, 2013.)

• RT: Randomly generated instances introduced by Lin et al. (2008), with ratios of obstacles to terminals set to 5, 10, and 50. Made available for the challenge by Chris Chu. (Last updated on October 14, 2013.)

• RL: Large randomly generated test cases from Long et al. (2008). Made available for the challenge by Chris Chu. (Last updated on October 14, 2013.)

In the reach-aware variant of the OARSMT problem, solutions may intersect the interior of the blocked area (obstacles), but the length of a connected component of the Steiner tree and its intersection with the interior of the blocked area must not exceed a given reach length.

• BONN: Reach-aware industrial instances arising from a cooperation between the Research Institute for Discrete Mathematics (University of Bonn) and IBM on algorithms for chip design. Instances made available for the challenge by Stephan Held and Sophie Spirkl. (Updated on October 31, 2013.)

In the PCSPG problem, the input is a graph with a subset of its vertices marked as terminals. Each edge has a nonnegative cost, and each terminal a nonnegative penalty. The goal is to find a tree of minimum weight, given by the sum of its edge costs plus the penalties associated with the terminals that are not spanned by the tree.

The following instances have been made available for the challenge by Mauricio Resende:

• JMP: Instances introduced by Johnson et al. (1999). Instances of type P are unstructured with constant expected degree and prize to weight ratio. Type K corresponds to random geometric instances whose structure is somewhat similar to street maps.
• CRR: Random instances based on the C and D families from the SteinLib (and OR-Library), introduced by Canuto et al. (2001).

• PUCNU: Instances based on the PUC series for the classical Steiner Problem in Graphs. All edges have weight 1, and terminal penalties are either 1 or 2. Instances made available for the challenge by Ivana Ljubic.

The following instances, tested by Biazzo et al. (2013), have been made available for the challenge by Indaco Biazzo:

• i640: Random graphs with incidence weights based on SPG instances by C. Duin.
• H: Hypercubes based on SPG instances originally proposed by Rossetti et al. (2001). These PCSPG instances were introduced by Ljubic et al. (2006).
• RANDOM: random graphs.

The instances below were also made available by Indaco Biazzo:

• H2: Hypercubes based on SPG instances originally proposed by Rossetti et al. (2001). They have the same parameters of class H above, but use different random seeds. These are not the instances that appear in Biazzo et al. (2013).

The following instances were made available by Gunnar W. Klau and Mohammed El-Kebir:

• ACTMODPC: Instances from integrative biological network analysis, in which the task is to find active modules (sets of connected genes likely involved in a common cellular mechanism). The instances are not necessarily connected. These PCSPG instances were created by Daniel Juhl by transforming instances for the Maximum-Weight Connected Subgraph Problem (also available) following the reduction described in Dittrich et al. (2008).

The following class of instances was made available for the challenge by Ludwig Schmidt:

• Hand: Images of hand-written text derived from an application of the PCSPG problem in signal processing (sparse approximation). These instances were introduced in A Fast, Adaptive Variant of the Goemans-Williamson Scheme for the Prize-Collecting Steiner Tree Problem (by Chinmay Hegde, Piotr Indyk, and Ludwig Schmidt), which will be presented at the challenge. A link to the actual paper will be added once the final version is available.

The rooted prize-collecting Steiner tree problem (RPCST) is a variant of the standard prize-collecting Steiner tree problem in which one particular vertex (the root)) must be part of the network.

• Cologne: Instances are based on real-world examples used in the design of fiber optic networks for some German cities. The instances have been generated according to GIS databases, with connections and vertex positions based on the actual infrastructure. For data protection, the choice of customers and their prizes have been slightly changed. These instances, first tested by Ljubic et al. (2006) (see also here), were made available for the challenge by Ivana Ljubic and can also be found (in different format) on her website.

The Steiner Tree Problem with Revenues, Budget, and Hop Constraints (STPRBH) takes as input an undirected graph. Each edge has an associated nonnegative cost, and each vertex has a nonnegative nonnegative revenue; vertices with positive revenue are called profitable. The input also defines a root vertex r, a budget B, and a hop limit H. The goal is to find a revenue-maximizing tree that is rooted at r, whose edge costs are at most B, and such that the number of tree edges between any tree vertex and r is at most H.

• RANDOM: Random instances based on the B and C classes of the OR-Library for the plain Steiner Problem in Graphs. This set includes instances originally proposed by Alysson M. Costa as well new instances. A PDF included in the zip file has additional details. These instances were made available for the challenge by Zhang-Hua Fu and Jin-Kao Hao.

The Two-Stage Stochastic Steiner Tree Problem problem is a variant of the Steiner Problem in Graphs in which uncertainty the set of terminals and the edge costs are subject to uncertainty. There are two stages. In the first stage (now), we are given a graph, initial edge costs, and probabilistic information about a finite number of possible scenarios (outcomes) for the second stage (the future). Each scenario specifies a terminal set, (higher) edge costs, and a probability for the scenario to be realized. One may buy some edges at a lower price during the first stage and, in the second stage, when one of the given scenarios is realized, one must purchase additional edges in order to connect the (now known) terminals. The goal is to minimize the expected cost of all edges purchased. All instances were created from deterministic instances through the introduction of 5 to 1000 scenarios.

• K100s: Instances based on K-type instances from Johnson et al. (1999) for the Prize-Collecting Steiner Problem in Graphs.
• P100s: Instances based on P-type instances from Johnson et al. (1999) for the Prize-Collecting Steiner Problem in Graphs.
• WRP3s: Instances based on the WRP3 instances from the Steiner Problem in Graphs.
• LINs: Instances based on the LIN instances from the Steiner Problem in Graphs.

Additional details about the problem itself (and the instances) are available at a dedicated webpage at TU Dortmund.

All instances were made available for the challenge by Bernd Zey.