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. It can typically compute minimum Steiner trees even for large-scale graphs with several hundred thousand edges within minutes.

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.
06/July/2022 The PhD thesis in which SCIP-Jack was developed wins the EURO Doctoral Dissertation Award.
07/September/2022 The PhD thesis in which SCIP-Jack was developed wins the GOR Dissertation Award.
12/September/2022 The PhD thesis in which SCIP-Jack was developed is a finalist of the INFORMS George B. Dantzig Dissertation Award.

Download

The current version of SCIP-Jack is 2.0. Due to a licence change of SCIP, SCIP-Jack will not be available anymore as part of the SCIP Optimization Suite. It can still be obtained on request. Please contact Daniel Rehfeldt.

Installation

See the INSTALL file in the SCIP-Jack directory.

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

License

SCIP-Jack is distributed under the ZIB Academic License. You are allowed to retrieve 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-constrained 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.