SCIP-Jack

ZIB

About

SCIP-Jack is a solver for the classic Steiner tree problem in graphs, and fourteen related problems, such as the prize-collecting Steiner tree problem, or the maximum-weight connected subgraph problem. SCIP-Jack is currently the fastest solver for almost all of these fifteen problem classes, including the Steiner tree problem in graphs, the prize-collecting Steiner tree problem, and the maximum-weight connected subgraph problem.

Description
Classic Steiner tree instance with terminals drawn as red squares.
Description
Minimum weight Steiner tree (optimal solution).


Description
Computational results on the 200 benchmark instances of Tracks A and B of the PACE Challenge 2018. Comparison of leading commerical MIP-solver (Commercial), best other solver from PACE Challenge (SPDP), and SCIP-Jack with SoPlex 5.0 (SCIP-Jack/spx) and Gurobi 9.5 (SCIP-Jack/grb) as LP-solver. Average time given as arithmetic mean (as in PACE Challenge 2018) with time-outs counted as 3600 seconds each.

Time limit: 3600 seconds.

Hardware: Intel Xeon CPUs E3-1245 @ 3.40~GHz, 32 GB RAM.

News

10/May/2018 SCIP-Jack achieves top rankings in all three tracks of the PACE Challenge 2018, dedicated to fixed-parameter tractable Steiner tree instances: 2nd place in Track A (exact, bounded number of terminals), 1st place in Track B (exact, bounded tree-width), 3rd place in Track C (heuristic).
02/December/2021 SCIP-Jack 2.0 released (as part of SCIP Optimization Suite 8.0). Major improvements across most problem classes, especially for Steiner tree problem in graphs and prize-collecting Steiner tree problem.

Download

The current version of SCIP-Jack is 2.0. As part of SCIP its source can be found in the directory 'applications/STP'. You can download the source code via the SCIP website.

Further information on the code can be found in this short documentation.

Installation

(See also the INSTALL file in the SCIP-Jack directory.)

Building SCIP-Jack with make:

  1. Build SCIP: see the INSTALL file in the SCIP directory or the webpage.
  2. Build SCIP-Jack: change into the applications/STP directory and execute make on the command line
    • if SCIP was built with make [options], then run make [options] with the same options in the applications/STP directory

Building SCIP-Jack with CMake:

  1. Build SCIP: see the INSTALL file in the SCIP directory or the webpage.
  2. Build SCIP-Jack: We assume that the build directory of SCIP was named 'build'. Execute

    cmake --build build --target scipstp on the command line.

The default installation uses SoPlex as LP-solver for SCIP-Jack, but it is recommended to use a commerical LP-solver such as CPLEX, Gurobi, or Xpress whenever possible. Note that SCIP-Jack 2.0 was delevoped while using CPLEX (version 12.10) as LP-solver, so the best results can probably be achieved with CPLEX (12.10) as LP-solver.

Execution

SCIP-Jack can read the .stp and .gr file formats.

  1. To run a SCIP-Jack binary compiled by make, go to the directory /applications/STP and execute

    bin/stp -f filename.stp on the command line

  2. To get the Steiner tree computed by SCIP-Jack, create a file called (for example) 'write.set' in folder /applications/STP/settings with content 'stp/logfile = "use_probname"', and execute

    bin/stp -f filename.stp -s settings/write.set on the command line.

    3. The Steiner tree will be written to the file 'filename.stplog'. Alternatively, you can set the logfile parameter via the interactive shell.

To run a SCIP-Jack binary compiled by CMake, replace 'stp' by 'scipstp' in the above description, and use the folder /build/bin/Release instead of /applications/STP/bin.

How To Cite

Please include one of the following references if you use SCIP-Jack for your work (depending on which problem class you consider):

Steiner tree problem in graphs:
D. Rehfeldt,T. Koch: Implictions, conflicts, and reductions for Steiner trees.
Integer Programming and Combinatorial Optimization: 22th International Conference, IPCO 2021, Mohit Singh and David P. Williamson (Eds.), ISBN: 978-3-030-73879-2,
Lecture Notes in Computer Science Vol. 12707
BibTeX

Prize-collecting Steiner tree problem:
D. Rehfeldt,T. Koch: On the Exact Solution of Prize-Collecting Steiner Tree Problems.
INFORMS Journal on Computing, 2021, published online first, DOI: https://doi.org/10.1287/ijoc.2021.1087
BibTeX

Maximum-weight connected subgraph problem:
D. Rehfeldt,T. Koch: Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem.
SIAM Journal on Optimization, 2019, 29(1), pages 369–398, DOI: https://doi.org/10.1137/17M1145963
BibTeX

Other problem classes:
D. Rehfeldt, Y. Shinano, T. Koch: SCIP-Jack: An exact high performance solver for Steiner tree problems in graphs and related problems.
Modeling, Simulation and Optimization of Complex Processes, HPSC 2018, Hans Georg Bock, Willi Jäger, Ekaterina Kostina, Hoang Xuan Phu (Eds.), ISBN: 978-3-030-55240-4
BibTeX

Parallelization extensions of SCIP-Jack:
D. Rehfeldt, Y. Shinano, T. Koch: Building Optimal Steiner Trees on Supercomputers by Using up to 43,000 Cores.
Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2019, Louis-Martin Rousseau, Kostas Stergiou (Eds.), ISBN: 978-3-030-19212-9
Lecture Notes in Computer Science Vol. 11494
BibTeX

Developers

Daniel Rehfeldt (main developer)

Gerald Gamrath

Thorsten Koch

Stephan Maher

Yuji Shinano (parallelization extensions)

License

SCIP-Jack is part of SCIP and distributed under the ZIB Academic License. You are allowed to retrieve SCIP and SCIP-Jack as a member of a non-commercial and academic institution. For commercial use or support please contact I²DAMO GmbH.

Contact

For further questions, or in case of bugs/problems with SCIP-Jack, please contact Daniel Rehfeldt.

Problem Classes

The following problem classes can be handled by SCIP-Jack:

Steiner tree problems in graphs,

Steiner arborescence problems (directed Steiner tree problem),

rectilinear Steiner minimum tree problems (see note below),

node-weighted Steiner tree problems,

prize-collecting Steiner tree problems,

rooted prize-collecting Steiner tree problems,

maximum-weight connected subgraph problems,

rooted maximum-weight connected subgraph problems,

maximum-weight connected subgraph problems with budget constraints,

partial-terminal node-weighted Steiner tree problems,

degree-constrained Steiner tree problems,

group Steiner tree problems,

full Steiner tree problems,

partial-terminal Steiner tree problems,

hop-honstrained directed Steiner tree problems.

For Euclidean Steiner tree problems and rectilinear Steiner tree problems, it is recommended to use the full Steiner tree generation provided by GeoSteiner and solve the resulting Steiner tree problem in graphs with SCIP-Jack. Many large benchmark instances that cannot be solved by the default GeoSteiner solver in one week can be solved by SCIP-Jack within minutes in this way. Including Euclidean Steiner tree instances with 100 thousand points in the plane.

Problem Libraries

A collection of well-known Steiner tree test-sets can be found in the SteinLib. See also 11th DIMACS Challenge for additional benchmark instances.

Imprint and privacy statement

© 2022 by Zuse Institute Berlin (ZIB). For the imprint and privacy statement we refer to the Imprint of ZIB.