DESCRIPTION:  11th DIMACS Implementation Challenge was dedicated to the study of Steiner tree problems. The code available at this website provides implementations of algorithms for finding exact and heuristic solutions for the following problem types:
 The Steiner tree problem in graphs (STP),
 The prizecollecting Steiner tree problem (PCSTP),
 The rooted prizecollecting Steiner tree problem (RPCSTP),
 The maximumweight connected subgraph problem (MWCS), and
 The degreeconstrained 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, 2016), and can be turned on/off by appropriate parameter settings (see usermanual for more details).

REFERENCE: 
Please refer to the following publication when using our solver:
M. Fischetti, M. Leitner, I. Ljubic, 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, to appear, 2016, DOI: 10.1007/s1253201601110

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 nonnegative 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 degreeconstrained 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 nonnegative nodeprofits p, and with the set of edges E associated with nonnegative costs c.
The PrizeCollecting Steiner Tree Problem (PCSTP) consists of
finding a connected subgraph T = (V' ,E' ) of G that maximizes the
sum of collected nodeprofits minus the costs of the edges needed to establish the network.
Given, in addition, a root node r, the Rooted PrizeCollecting 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 nodeweights w, and with the set of edges E.
The MaximumWeight Connected Subgraph Problem (MWCS) consists of
finding a connected subgraph T = (V' ,E' ) of G that maximizes the
sum of collected nodeweights.


STAYNERD SOLVER:

The provided executable is a 64bit 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. Ljubic, 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, to appear, 2016, DOI: 10.1007/s1253201601110
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 staynerdcode has been developed with academic CPLEX and OGDF license for noncommercial purposes only.

CONTACT: 
ivana.ljubic @essec.edu
