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.

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. |

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.

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

Building SCIP-Jack with **make**:

- Build SCIP: see the INSTALL file in the SCIP directory or the webpage.
- 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**:

- Build SCIP: see the INSTALL file in the SCIP directory or the webpage.
- Build SCIP-Jack: We assume that the build directory of SCIP was named 'build'. Execute
`cmake --build build --target scipstp`on the command line.

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

- 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 - 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.
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.

**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

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.

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

*
*

* 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.

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