ug[SCIP-Jack,*]: A parallel solver for Steiner
tree and related problems
Daniel Rehfeldt · Thorsten Koch · Yuji Shinano
TU Berlin
Zuse Institute Berlin

UG Workshop 2021

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

1 / 28

The Steiner tree problem in graphs
Given:
G = (V , E ): undirectedgraph
T ⊆ V : subset of verticesc ∈ RE>0 : non-negative edge
costs

D. Rehfeldt, T. Koch, Y. Shinano

1

2

1
1

A parallel solver for Steiner tree problems

2

2

2
1

UG Workshop 2021

2 / 28

The Steiner tree problem in graphs
Given:
G = (V , E ): undirectedgraph
T ⊆ V : subset of verticesc ∈ RE>0 : non-negative edge
costs

1

2

1
1

2

2

2
1

A tree S ⊆ G is called Steiner tree in (G, T , c) if T ⊆ V (S)D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

2 / 28

The Steiner tree problem in graphs
Given:
G = (V , E ): undirectedgraph
T ⊆ V : subset of verticesc ∈ RE>0 : non-negative edge
costs

1

2

1
1

2

2

2
1

A tree S ⊆ G is called Steiner tree in (G, T , c) if T ⊆ V (S)Steiner tree problem in graphs (SPG)
Find a Steiner tree S in (G, T , c) with minimum edge costs

X

c(e)

e∈E (S)

Decision variant of SPG is one of Karp’s 21 NP-complete problems
D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

2 / 28SPG is among the most studied problems in combinatorial
optimization
SPG and close relatives are used in many real-world applications

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

3 / 28SPG is among the most studied problems in combinatorial
optimization
SPG and close relatives are used in many real-world applications

In the following, we describe SCIP-Jack, an exact solver for SPG and
15 related problems, and its parallel extension ug[SCIP-Jack,*].

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

3 / 28

Why not using a general MIP solver?
Consider exemplary (rather small-scale)
network design instance with:|V | = 12 715|E | = 20 632|T | = 475
CPLEX 12.10: No optimal solution
after one week
Instance from network
telecommunication design for Austrian
cities, see New Real-world Instances
for the Steiner Tree Problem in
Graphs (Leitner et al., 2014)

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

4 / 28

Why not using a general MIP solver?
Consider exemplary (rather small-scale)
network design instance with:|V | = 12 715|E | = 20 632|T | = 475
CPLEX 12.10: No optimal solution
after one week
SCIP-Jack: Solves to optimality in
0.2 seconds

D. Rehfeldt, T. Koch, Y. Shinano

Instance from network
telecommunication design for Austrian
cities, see New Real-world Instances
for the Steiner Tree Problem in
Graphs (Leitner et al., 2014)

A parallel solver for Steiner tree problems

UG Workshop 2021

4 / 28

Why not using a general MIP solver?
Consider exemplary (rather small-scale)
network design instance with:|V | = 12 715|E | = 20 632|T | = 475
CPLEX 12.10: No optimal solution
after one week
SCIP-Jack: Solves to optimality in
0.2 seconds
SCIP-Jack is routinely employed for
instances with millions of edges inindustry
D. Rehfeldt, T. Koch, Y. Shinano

Instance from network
telecommunication design for Austrian
cities, see New Real-world Instances
for the Steiner Tree Problem in
Graphs (Leitner et al., 2014)

A parallel solver for Steiner tree problems

UG Workshop 2021

4 / 28

Solving by integer programmingFirst, transform SPG instance to equivalent (bi-)directed Steiner tree
problem.

r

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

5 / 28

Solving by integer programmingFirst, transform SPG instance to equivalent (bi-)directed Steiner tree
problem.

r

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

5 / 28

Formulation
Second, use cutting plane algorithm based on well-known
flow-balance directed-cut formulation:

Formulation (Wong, 1984; Duin, 1993)
min c T yy (δ + (W )) > 1−

for all W ⊂ V , r ∈ W , (V \ W ) ∩ T 6= ∅+y (δ (v )) 6 y (δ (v ))y (a) ∈ {0, 1}

D. Rehfeldt, T. Koch, Y. Shinano

for all v ∈ V \ T
for all a ∈ A

A parallel solver for Steiner tree problems

UG Workshop 2021

6 / 28

Formulation
Second, use cutting plane algorithm based on well-known
flow-balance directed-cut formulation:

Formulation (Wong, 1984; Duin, 1993)
min c T yy (δ + (W )) > 1−

for all W ⊂ V , r ∈ W , (V \ W ) ∩ T 6= ∅+y (δ (v )) 6 y (δ (v ))y (a) ∈ {0, 1}

for all v ∈ V \ T
for all a ∈ A

Theorem (Rehfeldt, Franz, Koch, 2020)
If |T | < 4, then flow-balance directed-cut formulation has tight LP
relaxation.
D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

6 / 28

The framework: SCIP (Solving Constraint Integer
Programs)

Functionality
full-scale mixed-integer optimizer for general MIPs and MINLPs
generic framework for implementing problem-specificbranch-cut-and-price

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

7 / 28SCIP-Jack: A Steiner tree solver
SCIP-Jack works by combining generic and problem specificalgorithms:

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

8 / 28SCIP-Jack: A Steiner tree solver
SCIP-Jack works by combining generic and problem specificalgorithms:
examples for genericIIfast separator routine based on new max-flow implementation
dual-ascent heuristic

examples for problem specificefficient transformations to directed Steiner tree problem(needed for applying generic separator)
I preprocessing routines
I domain propagation
I dynamic-programming algorithms
I primal heuristics
I

Current development version of SCIP-Jack consists of > 110 000 lines
of code.
D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

8 / 28

Computational results: PACE Challenge 2018
The goal of the Parameterized Algorithms and Computational
Experiments (PACE) Challenge is to investigate the applicability ofalgorithmic ideas studied and developed in the subfields ofparameterized, or fixed-parameter tractable algorithms.
PACE 2018:
dedicated to Steiner tree problems in graphs, for which several
fixed-parameter tractable (FPT) algorithms are known
Tracks A,B,C, each including 100 instances, time limit 30 min.
took place in May 2018, 40 participating teams from 16
countries

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

9 / 28

PACE 2018
SCIP-Jack1 with SoPlex as LP solver competed in all three tracks(although did not include any FPT algorithms). Result:
Track A (exact, few terminals): 3rd place2
Track B (exact, low treewidth): 1st place
Track C (heuristic, different FPT structures): 2nd place3

1

Team members: T. Koch, D. Rehfeldt
Winning team: Yoichi Iwata, Takuto Shigemura (NII, Japan)
3
Winning team: Emmanuel Romero Ruiz, Emmanuel Antonio Cuevas, Irwin
Enrique Villalobos López, Carlos Segura González (CIMAT, Mexico)2

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

10 / 28

PACE 2018
Current SCIP-Jack significantly outperforms PACE version:
SCIP-Jack-NEW
Track
A
B

SCIP-Jack-PACEBest other# instancessolvedavg. time [s]solvedavg. time [s]solved

100
100

99
99

38
25

94
92

111
132

95
77

Table: Updated computational results for PACE 2018 instances.

(also much stronger on heuristic Track C)

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

11 / 28

Computational results (2)Fastest SPG solver established by Polzin and Vahdati
Daneshmand 20 years ago (non-public)
Drastically outperforms best other SPG solvers, even thewinning solvers from DIMACS Challenge 2014 and PACE
Challenge 2018 (did not participate in either challenge)...we made a large effort in last two years to outperform Polzin
and Vahdati Daneshmand

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

12 / 28

Consider 14 benchmark test-sets from the literature (almost all non-trivial setsfrom DIMACS Challenge and SteinLib library). Time limit of 24 hours, results of(non-public) solver by Polzin, Vahdati are scaled for fair comparison.
# solved mean time (sh. geo. mean)
Test-set

#

VLSI
116
TSPFST 76
WRP4
62
2R
27
vienna-a 85
vienna-s 85
WRP3
63
GEO-a
23
GEO-org 23
ES10000 1
Cophag14 21
SP
8
LIN
37
PUC
50

P.&V. S.-J. P.&V. [s] S.-J. [s] speedup
116 116
0.5
0.8
76 76
1.5
1.1
62 62
3.2
2.4
27 27
5.0
3.0
85? 857.2
5.2
85? 85
7.8
6.2
63 63
22.8
13.5
23? 23
158.7
55.3
23? 23
145.6
58.5
1
1
138.0
83.0
20? 21
27.7
13.8
6
8
159.4
25.8
35 36
31.3
14.7
17? 18 14964.9 11901.1

0.63
1.36
1.33
1.67
1.38
1.26
1.69
2.87
2.49
1.66
2.01
6.18
2.13
1.26

maximum time
P.&V. [s] S.-J. [s] speedup
53.9
83.3
0.65
1161.4 263.1
4.41
106.1
90.8
1.17
43.9
21.1
2.08
441.3
59.0
7.48
623.5
60.7
10.27
6073.2 4886.4
1.24
6476.5 880.9
7.35
4385.0 842.1
5.21
138.0
83.0
1.66
>86400 3845.3 >22.47>86400 1688.3 >51.18>86400 >86400
1.00>86400 >86400
1.00

Shift s = 10 used for shifted geometric mean.
Times marked by a ? were obtained by P.&V. with (specialized) non-default settings.
D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

13 / 28

Consider aggregated results. Group [x , 86400]: all instances solved byat least one solver in at least x and at most 86400 seconds.
shifted geometric mean timeGroup

# P.&V. [s] S.-J. [s][0, 86400]
644[1, 86400]
342[10, 86400]
180[100, 86400]
66[1000, 86400] 30

12.2
7.9
34.5
19.6
122.5
52.0
1403.2 286.6
8035.8 1096.9

speedup
1.54
1.76
2.36
4.90
7.33

arithmetic mean time
P.&V. [s] S.-J. [s] speedup
1235.5 264.9
2326.4 498.7
4417.1 944.6
11999.0 2546.3
25923.1 5435.6

4.66
4.66
4.68
4.71
4.77

Table: Computational comparison of our solver (S.-J.) and solver by
Polzin, Vahdati (P.&V.), with instance groups ordered by hardness.

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

14 / 28

Steiner tree relatives

SCIP-Jack significantly outperforms specialized solvers for several
important Steiner tree relatives, e.g. forMaximum-weight connected subgraph problem
Prize-collecting Steiner tree problem
Geometric Steiner tree problems (for concatenation, see next
slide)

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

15 / 28

SCIP-Jack also useful for solving Euclidean Steiner tree problem:
Can be used instead of commonly used hypergraphic concatenation.
Comparison on largest instances from the literature withstate-of-the-art geometric Steiner tree solver GeoSteiner 5.1 (Juhl etal., 2018):
1) 15 instances with 50 000 terminals in the plane:
GeoSteiner solves 8 within one week
SCIP-Jack solves all 15 in three minutes

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

16 / 28

SCIP-Jack also useful for solving Euclidean Steiner tree problem:
Can be used instead of commonly used hypergraphic concatenation.
Comparison on largest instances from the literature withstate-of-the-art geometric Steiner tree solver GeoSteiner 5.1 (Juhl etal., 2018):
1) 15 instances with 50 000 terminals in the plane:
GeoSteiner solves 8 within one week
SCIP-Jack solves all 15 in three minutes2) 15 instances with 100 000 terminals in the plane:
GeoSteiner solves 3 within one week
SCIP-Jack solves all 15 in 11 minutes→ 19 instances solved for the first time to optimality.
D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

16 / 28

Going parallel

Two approaches within SCIP-Jack:
parallelizing reduction techniques and heuristics (shared-memory
only)parallelizing branch-and-bound search (shared- anddistributed-memory)

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

17 / 28

Going parallel

Two approaches within SCIP-Jack:
parallelizing reduction techniques and heuristics (shared-memory
only)parallelizing branch-and-bound search (shared- anddistributed-memory) → using UG

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

17 / 28

ug[SCIP-*,*]-libraries
Customized SCIP solvers (such as SCIP-Jack) include a set of
SCIP plugins, to be integrated in the solution process

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

18 / 28

ug[SCIP-*,*]-libraries
Customized SCIP solvers (such as SCIP-Jack) include a set of
SCIP plugins, to be integrated in the solution processug[SCIP-*,*]-libraries are general purpose libraries that allow one
to parallelize the branch-and-bound search of such customized
SCIP solvers

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

18 / 28

ug[SCIP-*,*]-libraries
Customized SCIP solvers (such as SCIP-Jack) include a set of
SCIP plugins, to be integrated in the solution processug[SCIP-*,*]-libraries are general purpose libraries that allow one
to parallelize the branch-and-bound search of such customized
SCIP solvers
Usually, fewer than 200 lines of glue code are required for thisparallelization...but some debugging maybe be necessary, especially whenusing SCIP in a non-standard way

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

18 / 28

Parallelization of SCIP-Jack by UG
UG framework to parallelize B&B search both in shared,ug[SCIP-Jack, C++11 threads], and distributed, ug[SCIP-Jack,
MPI], environments.
Parallelization can be realized with a few lines of code.

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

19 / 28

Parallelization of SCIP-Jack by UG
UG framework to parallelize B&B search both in shared,ug[SCIP-Jack, C++11 threads], and distributed, ug[SCIP-Jack,
MPI], environments.
Parallelization can be realized with a few lines of code.
... but to improve performance both UG and SCIP-Jack had to
be extended.
Difficulties:
Long running time in root node.
Special branching.
I Distributing problem specific preprocessing effects.
I
I

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

19 / 28

Branching on vertices
SCIP-Jack branches on vertices of the graph.
Including vertex v corresponds to the constraint:X

xa = 1a∈δ − (v )Excluding vertex v corresponds to constraint:X

xa = 0a∈δ − (v )∪δ + (v )→ added new features to UG to allow branching on constraints

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

20 / 28

Building new subproblems

To retain previous branching decisions, SCIP-Jack/UG allows totransfer the branching history together with a subproblem.
SCIP-Jack then changes the underlying graph (adds terminals
and deletes vertices).
Improves finding heuristically locally valid solutions and helps
with cut generation. Local cuts are also transferred by UG.

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

21 / 28

Aggressive presolving of subproblems

Strong point of UG: presolving of subproblems during
branch-and-bound.
Problem:
For Steiner tree problems MIP presolving quite unsuccessful.
Specialized Steiner tree presolving is performed before SCIP
initiated (for performance reasons)→ needed to adapt SCIP-Jack to perform Steiner tree presolving also
after transfer of new branch-and-bound node to a UG solver

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

22 / 28

SCIP presolving vs. SCIP-Jack presolving

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

23 / 28

Parallel results

Using up to 43 thousand cores on supercomputers, weSolved five notoriously hard SPG instances for the first time to
optimality
Solved two prize-collecting Steiner tree instances from 11th
DIMACS Challenge (results not published)

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

24 / 28

Solving benchmark instance hc9p to optimality
Time
Idle
(sec.)(%)
604,796
72
< 0.3
(317)

Run Computer Cores
1.1 ISM

Trans.
738

1.2 ISM

2,304 604,794 < 1.5

979,695

1.3 HLRN III

24,57686,336 < 1.7 8,811,512

1.4 HLRN III

12,28843,199 < 1.5 1,709,027

1.5 HLRN III

12,288 118,259

1.5 9,158,920

Primal boundDual bound(Upper bound) (Lower bound)
30,242.0000
29,879.3721
30,242.0000
30,058.9366
30,242.0000
30,058.7930
30,242.0000
30,102.7556
30,242.0000
30,102.6645
30,242.0000
30,116.3592
30,242.0000
30,115.3331
30,242.0000
30,120.4801
30,242.0000
30,120.4801
30,242.0000
30,242.0000

Gap
Nodes
(%)
1.21
0
0.61
110,012,6240.61
00.46 3,758,532,6000.46
00.42 2,402,406,311
0.42
0
0.40
664,909,985
0.40
00.00 1,677,724,126

Table: Statistics for solving hc9p on supercomputers.
Resources:
ISM: HPE SGI 8600, 384 compute nodes, each node consisting of two Intel Xeon Gold 6154
3.0GHz CPUs (18 cores×2) sharing 384GB of memory, and an Infiniband (Enhanced
Hypercube) interconnect.
HLRN III: Cray XC40 with 1872 compute nodes, each node consisting of two 12-core Intel Xeon
IvyBridge/Haswell CPUs sharing 64 GiB of RAM, with Aries interconnect.
D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

25 / 28

Future work

Possible future work:
combine internal parallelization of SCIP-Jack with UG (bydynamic thread allocation)
solve further classic unsolved Steiner tree benchmark instancesby using ug[SCIP-Jack, MPI]

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

26 / 28

New SCIP-Jack (and ug[SCIP-Jack, *]) will be made freely available
for academic use as part of SCIP Optimization Suite 8(www.scipopt.org).

D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

27 / 28

References
Rehfeldt, Shinano, Koch
SCIP-Jack: An Exact High Performance Solver for Steiner Tree Problems in
Graphs and Related Problems, HPSC 2018
Shinano, Rehfeldt, Koch., Building Optimal Steiner Trees on
Supercomputers by Using up to 43,000 Cores, CPAIOR 2019
Rehfeldt, Koch, Combining NP-Hard Reduction Techniques and Strong
Heuristic in an Exact Algorithm for the Maximum-Weight Connected
Subgraph Problem, SIAM Journal on Optimization, 2019
Rehfeldt, Koch, Implications, Conflicts, and Reductions for Steiner Trees,
IPCO 2021
Rehfeldt, Koch, On the exact solution of prize-collecting Steiner tree
problems, INFORMS Journal on Computing, 2021

Thank you!
D. Rehfeldt, T. Koch, Y. Shinano

A parallel solver for Steiner tree problems

UG Workshop 2021

28 / 28