StayNerd: Solver for Steiner Trees and Related Problems

([‘ʃtʌɪnə])
by Matteo Fischetti, Markus Leitner, Ivana Ljubić, Martin Luipersbeck, Michele Monaci, Max Resch, Domenico Salvagnin, Markus Sinnl University of Padua and University of Vienna

DESCRIPTION

11th DIMACS Implementation Challenge was dedicated to the study of Steiner tree problems. The code available at this web-site provides implementations of algorithms for finding exact and heuristic solutions for the following problem types:

The Steiner tree problem in graphs (STP)
The prize-collecting Steiner tree problem (PCSTP)
The rooted prize-collecting Steiner tree problem (RPCSTP)
The maximum-weight connected subgraph problem (MWCS), and
The degree-constrained Steiner tree problem (DCST)

According to the results of the 11th DIMACS Challenge, our exact solver (aka MOZARTBALLS) and heuristic solver (aka STAYNERD) are the winners in most of the categories for the selected group of problems. Both, exact and heuristic algorithms are available in the provided package (corresponding to the version published in the Mathematical Programming Computation, 2017), and can be turned on/off by appropriate parameter settings (see user-manual for more details).

REFERENCE

Please refer to the following publication when using our solver:
M. Fischetti, M. Leitner, I. Ljubić, M. Luipersbeck, M. Monaci, M. Resch, D, Salvagnin, M. Sinnl
Thinning out Steiner trees: a node based model for uniform edge costs
Mathematical Programming Computation 9(2): 203-229, 2017, DOI: 10.1007/s12532-016-0111-0

PROBLEM DEFINITION

STP/DCST

Let G = (V, E, T, c) be an undirected graph, with the set of nodes 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.
Given, in addition, a maximum node degree function d associated to each node, the degree-constrained Steiner tree problem (DCST) consists of finding a Steiner tree of minimum cost that does not violate maximum node degrees given by d.

PCSTP/RPCSTP

Let G = (V, E, c, p) be an undirected graph, with the set of nodes V associated with non-negative node-profits p, and with the set of edges E associated with non-negative costs c. The Prize-Collecting Steiner Tree Problem (PCSTP) consists of finding a connected subgraph T = (V' ,E' ) of G that maximizes the sum of collected node-profits minus the costs of the edges needed to establish the network.
Given, in addition, a root node r, the Rooted Prize-Collecting Steiner Tree Problem (RPCSTP) consists of finding a rooted PCSTP of maximum weight that contains the root node.

MWCS:

Let G = (V, E, w) be an undirected graph, with the set of nodes V associated with node-weights w, and with the set of edges E. The Maximum-Weight Connected Subgraph Problem (MWCS) consists of finding a connected subgraph T = (V' ,E' ) of G that maximizes the sum of collected node-weights.

STAYNERD SOLVER

The provided executable is a 64-bit Linux binary (compiled with GCC 4.9.2, requiring GLIBC version 2.3 or later). For running the solver, the user is required to provide dynamic CPLEX libraries.
By default, a CPLEX installation will only include static libaries, so the corresponding dynamic libary files must be generated manually from the set of static library files. For this purpose the following software is required:

GCC version 4.9.2 or greater
IBM ILOG CPLEX Optimization Studio (version 12.6)

Steps necessary to build the dynamic libraries and verify that the solver works correctly:

Set the environment variable CPLEX_DIR to the base directory of the CPLEX installation on your system (e.g., /opt/ibm/ILOG/CPLEX_Studio126).
Run the script make_cplex_dynamic.sh provided with the binary to create the dynamic CPLEX library files libconcert.so, libcplex.so and libilocplex.so.
Make sure that the dynamic libraries are placed in the same directory as the solver binary staynerd and the license file staynerd.license.
A simple way to run the solver is as follows (see user manual for more options):
staynerd [inputfile] [timelimit] [threads] [outputfile]

DOWNLOAD THE PACKAGE HERE
SEND US EMAIL REQUEST FOR OBTAINING A VALID LICENSE KEY

User Manual and Input Format

User manual can be downloaded HERE.
Input format recognized by our solver is the STP format defined at the 11th Dimacs Challenge.

Licensing

This code is free software to be used for academic purpose only. If you use it in your research, give the credits to our publication:
M. Fischetti, M. Leitner, I. Ljubić, M. Luipersbeck, M. Monaci, M. Resch, D, Salvagnin, M. Sinnl
Thinning out Steiner trees: a node based model for uniform edge costs,
Mathematical Programming Computation 9(2): 203-229, 2017, DOI: 10.1007/s12532-016-0111-0

Part of the staynerd code makes use of the following software (for which you might need a valid license in order to be able to run the code):

CPLEX 12.6 or later
OGDF library, (we thank to the OGDF team for granting us a special permission to statically link the OGDF library)
OGDF is GPL software, see also: M. Chimani, C. Gutwenger, M. Jünger, G. W. Klau, K. Klein, P. Mutzel. The Open Graph Drawing Framework (OGDF). Chapter 17 in: R. Tamassia (ed.), Handbook of Graph Drawing and Visualization, CRC Press, 2014.
dtree: dynamic trees a la carte

The staynerd-code has been developed with academic CPLEX and OGDF license for non-commercial purposes only.

Ivana LJUBIC