ug[SCIP-Jack, MPI]: A Massively Parallel Steiner
Tree Solver

Daniel Rehfeldt · Yuji Shinano · Thorsten Koch
Zuse Institute Berlin
Technische Universität Berlin

UG19, Berlin, January 2019

The Steiner Tree Problem in Graphs
Given:. G = (V , E ): undirected graph. T ⊆ V : subset of vertices. c ∈ RE>0 : positive edge costs

Thorsten Koch · Daniel Rehfeldt

2 / 46

The Steiner Tree Problem in Graphs
Given:. G = (V , E ): undirected graph. T ⊆ V : subset of vertices. c ∈ RE>0 : positive edge costs
A tree S ⊆ G is called Steiner tree in (G, T , c) if T ⊆ V (S)Thorsten Koch · Daniel Rehfeldt

2 / 46

The Steiner Tree Problem in Graphs
Given:. G = (V , E ): undirected graph. T ⊆ V : subset of vertices. c ∈ RE>0 : positive edge costs
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)

SPG is one of the fundamental combinatorial optimization problems;decision variant is one of Karp’s 21 N P-complete problems.
Thorsten Koch · Daniel Rehfeldt

2 / 46

Why not using a general MIP solver?
Consider (small-scale) network
design instance with:|V | = 12 715|E | = 41 264|T | = 475. CPLEX 12.7.1: No optimal
solution within 72 hours. SCIP-Jack: Solves to optimality
in 7.5 seconds
For larger problems CPLEX runs outof memory almost immediately(largest real-world instance
SCIP-Jack solved so far has 64
million edges, 11 million vertices)
Thorsten Koch · Daniel Rehfeldt

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

3 / 46

Applications
Some real-world applications of Steiner trees:. design of fiber optic networks. prediction of tumor evolution. deployment of drones. computer vision. wire routing. computational biology. ...

Rooted prize-collecting Steiner tree
problem

E.g. An algorithmic framework for the exact solution of the prize-collecting
Steiner tree problem (Ljubic et al., 2006)

Thorsten Koch · Daniel Rehfeldt

4 / 46

Applications
Some real-world applications of Steiner trees:. design of fiber optic networks. prediction of tumor evolution. deployment of drones. computer vision. wire routing. computational biology. ...

Rectilinear Steiner minimum tree
problem

E.g. Phylogenetic analysis of multiprobe fluorescence in situ hybridization
data from tumor cell populations (Chowdhury et al., 2013)

Thorsten Koch · Daniel Rehfeldt

4 / 46

Applications
Some real-world applications of Steiner trees:. design of fiber optic networks. prediction of tumor evolution. deployment of drones. computer vision. wire routing. computational biology. ...

Hop-constrained directed Steiner tree
problem

E.g. Local Search for Hop-constrained Directed Steiner Tree Problem with
Application to UAV-based Multi-target Surveillance (Burdakov, 2014)

Thorsten Koch · Daniel Rehfeldt

4 / 46

Applications
Some real-world applications of Steiner trees:. design of fiber optic networks. prediction of tumor evolution. deployment of drones. computer vision. wire routing. computational biology. ...

Maximum-weight connected subgraphproblem

E.g. Efficient activity detection with max-subgraph search(Chen, Grauman, 2012)

Thorsten Koch · Daniel Rehfeldt

4 / 46

Applications
Some real-world applications of Steiner trees:. design of fiber optic networks. prediction of tumor evolution. deployment of drones. computer vision. write routing. computational biology. ...
Group Steiner tree problem

E.g. Rectilinear group Steiner trees and applications in VLSI design(Zachariasen, Rohe, 2003)
Thorsten Koch · Daniel Rehfeldt

4 / 46

Applications
Some real-world applications of Steiner trees:. design of fiber optic networks. prediction of tumor evolution. deployment of drones. computer vision. wire routing. computational biology. ...

Maximum-weight connected subgraphproblem

E.g. Solving Generalized Maximum-Weight Connected Subgraph Problems
for Network Enrichment Analysis (Loboda et al., 2016)

Thorsten Koch · Daniel Rehfeldt

4 / 46

Applications
Some real-world applications of Steiner trees:. design of fiber optic networks. prediction of tumor evolution. deployment of drones. computer vision. wire routing. computational biology. ...

Maximum-weight connected subgraphproblem

Real-world applications usually require variations of SPG

Thorsten Koch · Daniel Rehfeldt

4 / 46

How it started...Jack

What we wanted: Solver for Steiner tree and many related problems

Thorsten Koch · Daniel Rehfeldt

5 / 46

How it started...Jack

What we wanted: Solver for Steiner tree and many related problems
What we had: an old solver for SPG, Jack-III

Thorsten Koch · Daniel Rehfeldt

5 / 46

How it started...Jack
What we wanted: Solver for Steiner tree and many related problems
What we had: an old solver for SPG, Jack-III; based on. transformation into a Steiner arborescence problem and ...

r

Thorsten Koch · Daniel Rehfeldt

5 / 46

How it started...Jack
What we wanted: Solver for Steiner tree and many related problems
What we had: an old solver for SPG, Jack-III; based on. transformation into a Steiner arborescence problem and ...

r

Thorsten Koch · Daniel Rehfeldt

5 / 46

Formulation... cutting plane algorithm based on flow balance directed-cut
formulation:

Formulation
min c T yy (δ + (W )) > 1−

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

Thorsten Koch · Daniel Rehfeldt

for all v ∈ V \ T
for all a ∈ δ + (v ), v ∈ V \ T
for all a ∈ A

6 / 46

Framework

Thorsten Koch · Daniel Rehfeldt

7 / 46

Some Facts about SCIP
. general setup
plugin based systemdefault plugins handle MIPs and nonconvex MINLPs
I support for branch-and-price and custom relaxations
I
I. documentation and guidelinesI

more than 500 000 lines of C code, 20% documentationI

36 000 assertions, 5 000 debug messages

HowTos: plugins types, debugging, automatic testing
11 examples and 5 applications illustrating the use of SCIP
I active mailing list scip@zib.de (300 members)II. interface and usability
user-friendly interactive shellinterfaces to AMPL, GAMS, ZIMPL, MATLAB, Python and JavaI C++ wrapper classes
I LP solvers: CLP, CPLEX, Gurobi, MOSEK, QSopt, SoPlex, Xpress
I over 1 600 parameters and 15 emphasis settings
I
I

Thorsten Koch · Daniel Rehfeldt

8 / 46

(Some) Universities and Institutes using SCIP

about 8000 downloads per year
Thorsten Koch · Daniel Rehfeldt

9 / 46SCIP plus Jack
SCIP

Jack

SCIP-Jack
Development of SCIP-Jack has been joint work with:
Gerald Gamrath · Thorsten Koch · Stephen J. Maher · Yuji Shinano
Thorsten Koch · Daniel Rehfeldt

10 / 46

A Steiner class solver
SCIP-Jack can solve SPG and 12 related problems:Abbreviation

Problem Name

SPG

Steiner tree problem in graphs

SAP

Steiner arborescence problem

RSMT

Rectilinear Steiner minimum tree problem

OARSMT

Obstacle-avoiding rectilinear Steiner minimum tree problem

NWSTP

Node-weighted Steiner tree problem

NWPTSTP

Node-weighted partial terminal Steiner tree problem

PCSTP

Prize-collecting Steiner tree problem

RPCSTP

Rooted prize-collecting Steiner tree problem

MWCSP

Maximum-weight connected subgraph problem

RMWCSP

Rooted maximum-weight connected subgraph problem

DCSTP

Degree-constrained Steiner tree problem

GSTP

Group Steiner tree problem

HCDSTP

Hop-constrained directed Steiner tree problem

Thorsten Koch · Daniel Rehfeldt

11 / 46SCIP-Jack
SCIP-Jack works by combining generic and problem specificalgorithms:

Thorsten Koch · Daniel Rehfeldt

12 / 46SCIP-Jack
SCIP-Jack works by combining generic and problem specificalgorithms:. genericextremely fast separator routine based on new max-flow
implementation
I all general methods provided by SCIP
e.g., generic cutting planesI. problem specificefficient transformations to Steiner arborescence problem(needed for applying generic separator)
I preprocessing and propagation routines
I primal and dual heuristics
I

Thorsten Koch · Daniel Rehfeldt

12 / 46SCIP-Jack
RMST

OA
RMST

SPG

GSTP

NWST

RPCST

Trans
formation

PCST

HCDST

DT

RMWCS

DCST

CNS

MWCS
DA

stp

nativeSCIP

GreedyPC

VQ

nativeSCIP

Cutpool

Reader

HBND
native
SCIP

BT
BND

CBND

Pro
pagator

LP
Interface

NTDk

RSPH
DC

recombinationNV

Dual
Heuristic

Local
MWCS

WriterSL

ACNS

SCIP-Jack

PrimalHeuristic

Pre
processing
SD

prune

NPVk

Node
selector···
AVS

ascendprune
Greedy
MWCS

RSPH
RSPH
SAP

UNT

BranchPricerRelaxator

Parallel

PNT

SDC

NNP
RPT

PVD

native
SCIP

UNPV

CT

Separator

BR

distributedstp
sharednativeSCIP

Thorsten Koch · Daniel Rehfeldt

stpdualascentbased

13 / 46Performance of SCIP-Jack for SPG

SCIP-Jack is. usually between two and three orders of magnitude faster thanJack-III (both using CPLEX 12.7.1 as LP-solver). fastest publicly available solver for SPG. also fastest solver for several related problems...

Thorsten Koch · Daniel Rehfeldt

14 / 46

PACE 2018 https://pacechallenge.wordpress.com/pace-2018
The Parameterized Algorithms and Computational Experiments Challenge
fixed-parameter tractable instances; more than 100 participantsSetting: 3 tracks, 100 instances in each track, time limit 30 min.
▷ Track A: exact, few terminals; results on public instances:▶ Winner:
94/100 Iwata, Shigemura (NII, Japan)▶ SCIP-Jack/SoPlex:
93/100 3rd place▶ SCIP-Jack/CPLEX: 100/100▷

Track B: exact, low treewidth; results on public instances:
SCIP-Jack/SoPlex: 98/100 1st place▶ SCIP-Jack/CPLEX:
99/100▶ best other:
84/100▶

▷Track C: heuristic, mean ratio to best known upper bound:▶ Winner:
99.92 Ruiz, Cuevas, López, González (CIMAT, Mexico)▶ SCIP-Jack/SoPlex:
99.81 2nd place▶ SCIP-Jack/CPLEX:
100

A mostly
through optimization
Thorsten
Koch discrete· Danieltour
Rehfeldt

Thorsten Koch

15 / 4685

Relatives

Prize-collecting Steiner tree problem

Thorsten Koch · Daniel Rehfeldt

16 / 46

Prize-Collecting Steiner Trees
Given:. undirected graph G = (V , E ). vertex costs p ∈ RV>0
. edge costs c ∈ RE>0

Prize-Collecting Steiner Tree Problem (PCSTP)
Find a tree S ⊆ G such thatPP
. e∈E (S) c(e) + v ∈V \V (S) p(v ) is minimized

Tp := {v ∈ V | p(v ) > 0} are called potential terminals.

Thorsten Koch · Daniel Rehfeldt

17 / 46

Transformation: PCSPG to SAP
r0
M

p=7

M
7

0

p=2.5

0
1.1

0.6
1.5

2.5

0
0
1.1

0.6
1.5

Transformation to SAP ...
. allows to use powerful cut-separation routine of SCIP-Jack. allows to employ strong heuristics based on a dual-ascent algorithm
for SAP

Thorsten Koch · Daniel Rehfeldt

18 / 46

Transformation: PCSPG to SAP
r0
M

p=7

M
7

0

p=2.5

0
1.1

0.6
1.5

2.5

0
0
1.1

0.6
1.5

Transformation to SAP ...
. allows to use powerful cut-separation routine of SCIP-Jack. allows to employ strong heuristics based on a dual-ascent algorithm
for SAPworks, but not enough to be competitive...
Thorsten Koch · Daniel Rehfeldt

18 / 46

Reduction techniques
Some recent work ...

Definition
Let vi , vj ∈ V . Call walk W = (vi1 , ei1 , vi2 , ei2 , ..., eir , vir ) with vi1 = vi
and vir = vj prize-constrained (vi , vj )-walk if no v ∈ Tp ∪ {vi , vj }contained more than once in W .

Definition
Define prize-collecting cost of W as
cpc (W ) :=Xe∈E (W )Thorsten Koch · Daniel Rehfeldtc(e) −

X

p(v ).

v ∈V (W )\{vi ,vj }19 / 46

Reduction techniques (2)Definition
Define prize-constrained length of W :lpc (W ) := max{cpc (W (vik , vil )) | 1 6 k 6 l 6 r , vik , vil ∈ Tp ∪{vi , vj }}.
Let Wpc (vi , vj ) prize-constrained (vi , vj )-walks define prize-constrained
distance between vi and vj :dpc (vi , vj ) := min{lpc (W 0 ) | W 0 ∈ Wpc (vi , vj )}.

Thorsten Koch · Daniel Rehfeldt

20 / 46

Reduction techniques (3)Proposition
Let {vi , vj } ∈ E . Ifc({vi , vj }) > dpc (vi , vj )is satisfied, then {vi , vj } cannot be contained in any optimal solution.
Prize-constrained concept allows for very powerful reduction tests;
dominates previous concept from Uchoa 2006 (Oper. Res. Let.) andgeneralizes tests known for SPG.
Downside: NP-hard. But: Nice (easy to implement) approximation by
an extension of Dijkstra’s algorithm.

Thorsten Koch · Daniel Rehfeldt

21 / 46

Prize-constrained walks (2)Another use of prize-constrained walks:

Definition
Let W be prize-constrained (vi , vj ) walk. Define left-rooted
prize-constrained length of W as:−(W ) := max{cpc (W (vi , vik )) | vik ∈ V (W ) ∩ (Tp ∪ {vj })}.
lpc

Definition
Define left-rooted prize-constrained (vi , vj )-distance as:−−
dpc(vi , vj ) := min{lpc(W 0 ) | W 0 ∈ Wpc (vi , vj )}.

Thorsten Koch · Daniel Rehfeldt

22 / 46

Left-rooted prize-constrained walks

Proposition
Let vi , vj ∈ V . If−p(vi ) > dpc(vi , vj ),then every optimal solution that contains vj also contains vi .

Thorsten Koch · Daniel Rehfeldt

23 / 46

Using left-rooted prize-constrained walks
r0
M

p=7

M
7

0

p=2.5

0
1.1

0.6
1.5

2.5

0
0
1.1

0.6
1.5

. Use prize-constrained walks to identify terminals ti that need to bepart of all optimal solutions. ...allows for better transformation to SAP:

Thorsten Koch · Daniel Rehfeldt

24 / 46

INPUT: RPCSTP (V , E , Tf , c, p) and tp , tq ∈ Tf Tf := {t1 , t2 , ..., tz } fixed terminals
OUTPUT: SAP
1. Set V 0 := V , A0 := {(v , w ) ∈ V 0 × V 0 | {v , w } ∈ E }, c 0 := c, r 0 := tq .
2. For each i ∈ {1, ..., z}:
2.1 add node ti0 to V 0 ,2.2 add arc (ti , ti0 ) of weight 0 to A0 ,2.3 add arc (tp , ti0 ) of weight p(ti ) to A0 .
3. Define set of terminals T 0 := {t10 , ..., tz0 } ∪ Tf .
4. Return (V 0 , A0 , T 0 , c 0 , r 0 ).

r0
p=7

2.5

0

p=2.5
1.1

0.6
1.1

0.6

1.5

1.5
We have recently proved: Choice of tp , tq does not change LP value! But: Can have strong
impact in practival solving, natural candidate for UG racing ramp up parameter!

Thorsten Koch · Daniel Rehfeldt

25 / 46

Prize-constrained walks in branch-and-cut. preprocessing. probing. propagation. cutting planes. primal heuristics. dual heuristics. B&B
We can exploit that when using UG!

Thorsten Koch · Daniel Rehfeldt

26 / 46Performance of SCIP-Jack on PCSTP

Thorsten Koch · Daniel Rehfeldt

27 / 46Performance of SCIP-Jack on PCSTP

Many PCSTP solvers introduced in the literature lately, the two best:. Fischetti et. al. 2017 (Math. Prog. C). Leitner et. al. 2018 (INFORMS J. Comput.) ... stronger by far

Thorsten Koch · Daniel Rehfeldt

28 / 46

mean time [s]max. time [s]# solved

Test set

#

L18

SJ

L18

SJ

L18

SJ

JMP
Cologne1
Cologne2
CRR
ACTMODE
HANDBIHANDBD
I640
PUCNU
H

34
14
15
80
8
40
14
14
100
18
14

0.0
0.0
0.1
0.1
0.9
1.8
36.5
34.1
8.7
278.9
488.7

0.0
0.0
0.1
0.1
0.3
0.2
14.9
13.3
6.1
80.2
477.4

0.0
0.1
0.2
5.7
3.5
>3600
>3600
>3600
>3600
>3600
>3600

0.0
0.0
0.1
1.1
1.5
34.5
>3600
>3600
>3600
>3600
>3600

34
14
15
80
8
37
12
13
90
7
4

34
14
15
80
8
40
13
13
91
11
5

SJ - SCIP-Jack
L18 - Leitner et. al. 2018
Thorsten Koch · Daniel Rehfeldt

29 / 46Performance of SCIP-Jack on PCSTP (2). SCIP-Jack often more than two or three orders of magnitude fasterthan next best solver (from Fischetti et. al. 2017, Math. Prog. C).
E.g. max. time on Cologne2:
I
I

Fischetti et. al.: > 200 seconds
SCIP-Jack:< 0.1 seconds. Recent PCSTP improvements of SCIP-Jack allowed us to solve twoand improve best known solutions for more than one third of
unsolved DIMACS 2014 instances.

Thorsten Koch · Daniel Rehfeldt

30 / 46

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 beextended.
. Difficulties:
Long running time in root node.
Special branching.
I Distributing problem specific preprocessing effects.
I
I

Thorsten Koch · Daniel Rehfeldt

31 / 46

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. ...but (in particular for PCSTP) we need to adapt underlying graph!

Thorsten Koch · Daniel Rehfeldt

32 / 46

Building new subproblems. SCIP-Jack/UG transfers branching history together with
subproblem. SCIP-Jack changes underlying graph (e.g. deletesvertices).
. Improves finding locally valid solutions and helps cut generation.
Local cuts also transferred by UG.
. Using branching history for separation and heuristics, we got
speed-up of about 30% with 32 threads.

Thorsten Koch · Daniel Rehfeldt

33 / 46Aggressive presolving of subproblems

Strong point of UG: presolving of subproblems during
branch-and-bound.
Problem:. For Steiner tree problems MIP presolving remarkably unsuccessful.
. Complex Steiner reduction techniques not easy to reflect in IP.
Thus Steiner tree solvers only perform reductions to delete vertices
and edges during B&B.
We make use of following observation:

Thorsten Koch · Daniel Rehfeldt

34 / 46Aggressive presolving of subproblems(2)Each SCIP-Jack Steiner tree reduction transforms SPG (V , E , T , c)
to SPG (V 0 , E 0 , T 0 , c 0 ) and provides function p : E 0 → P (E ) suchthat for each (optimal) solution S 0 ⊆ E 0 to transformed problem, set
Se∈S 0 p(e) is (optimal) solution to original problem.

Observation
Let (V , E , T , c), (V 0 , E 0 , T 0 , c 0 ), and p as above. DefineS
E 00 := e∈E 0 p(e),V 00 := {v ∈ V | ∃(v , w ) ∈ E 00 , w ∈ V },T 00 := {t ∈ T | ∃(t, w ) ∈ E 00 , w ∈ V },c 00 := c|E 00 .
Each (optimal) solution to (V 00 , E 00 , T 00 , c 00 ) is (optimal) solution to(V , E , T , c).

Thorsten Koch · Daniel Rehfeldt

35 / 46Aggressive presolving of subproblems(3)Observation allows us to perform aggressive presolving whenever new
subproblems are initialized. About 25% speed-up with 32 threads andimproved scaling behaviour.

Thorsten Koch · Daniel Rehfeldt

36 / 46

Customized racing ramp-up

Racing ramp-up with customized racing paramaters (new feature ofUG) is also used.

Thorsten Koch · Daniel Rehfeldt

37 / 46

Shared memory results for PCSTP
Threads i640-115 i640-141 cc10-2nu cc7nu
1
8
16
32
64

201
102
80
78
79

809
314
210
110
101

812 4,333
311 1,922
200 1,023
167
843
165
723

root time
max # solvers
first max active time

15
13
55

28
48
152

107
34
211

55
64
301

All times in seconds

Thorsten Koch · Daniel Rehfeldt

38 / 46

Results for SPG
We performed experiments on PUC, the most difficult Steiner tree
test set: 29 of 50 instances have remained unsolved.

SCIP-Jack (sequential) is currently the strongest solver on PUC:
. # instances solved in one hour:II

13 by SCIP-Jack:
12 by best other (Polzin, Vahdati Daneshmand, 2014)1. # instances solved in 12 hours:
II2

18 by SCIP-Jack:
13 by best other (Polzin, Vahdati Daneshmand, 2014)

Run time is scaled, as solver is not publicly available

Thorsten Koch · Daniel Rehfeldt

39 / 46

Distributed memory results

Two years ago on the PUC test set ug[SCIP-Jack, MPI]:. improved primal bounds for 14 instances. solved three instances to optimality for first time
In recent computational experiments we were able to. improve two best known primal bounds. solve one previously unsolved instanceThorsten Koch · Daniel Rehfeldt

40 / 46

Solving hc9p

Supercomputers used:. ISM: HPE SGI 8600 with 384 compute nodes, each node has twoIntel Xeon Gold 6154 3.0GHz CPUs(18 cores×2) sharing 384GB ofmemory, and Infiniband (Enhanced Hypercube) interconnect. HLRN III: Cray XC40 with 1872 compute nodes, each node withtwo 12-core Intel Xeon Ivy- Bridge/Haswell CPUs sharing 64 GiB
of RAM, and with Aries interconnect
Thorsten Koch · Daniel Rehfeldt

41 / 46

How open nodes and active solvers evolved (hc9p)

Thorsten Koch · Daniel Rehfeldt

42 / 46

Solving hc11p

Supercomputers used:. ISM: HPE SGI 8600 with 384 compute nodes, each node has twoIntel Xeon Gold 6154 3.0GHz CPUs(18 cores×2) sharing 384GB ofmemory, and Infiniband (Enhanced Hypercube) interconnect. HLRN III: Cray XC40 with 1872 compute nodes, each node withtwo 12-core Intel Xeon Ivy- Bridge/Haswell CPUs sharing 64 GiB
of RAM, and with Aries interconnect

Thorsten Koch · Daniel Rehfeldt

43 / 46

How open nodes and active solvers evolved (hc11p)

Thorsten Koch · Daniel Rehfeldt

44 / 46

(Parallel) Outlook
We plan to. (considerably) improve sequential performance of both SPG andrelated problems. add internal shared memory parallelizations to SCIP-JackAnd:. solve more open PUC instances with ug[SCIP-Jack, MPI]
. solve open instances of related problems with ug[SCIP-Jack, MPI]

Thorsten Koch · Daniel Rehfeldt

45 / 46

(Parallel) Outlook
We plan to. (considerably) improve sequential performance of both SPG andrelated problems. add internal shared memory parallelizations to SCIP-JackAnd:. solve more open PUC instances with ug[SCIP-Jack, MPI]
. solve open instances of related problems with ug[SCIP-Jack, MPI]

Thank you!
Thorsten Koch · Daniel Rehfeldt

45 / 46

Some references. Gamrath, Koch, Maher, Rehfeldt, Shinano: SCIP-Jack – A solver for STP andvariants with parallelization extentions, Math. Prog. Comp. (2017). Rehfeldt, Koch: Transformations for the Prize-Collecting Steiner Tree Problem
and the Maximum-Weight Connected Subgraph Problem to SAP, J. of Comp.
Math. (2018). Rehfeldt, Koch: Reduction-based exact solution of prize-collecting Steiner tree
problems ZR 18-55 (2018). Shinano, Rehfeldt, Koch: Building Optimal Steiner Trees on Supercomputers
by using up to 43,000 Cores ZR 18-58 (2018). Rehfeldt, Koch, Maher, Reduction Techniques for the Prize-Collecting Steiner
Tree Problem and the Maximum-Weight Connected Subgraph Problem,
Networks (2019, in press). Rehfeldt, Koch: Combining NP-Hard Reduction Techniques and Strong
Heuristic in an Exact Algorithm for the Maximum-Weight Connected Subgraph
Problem SIAM J. Opt. (2019, in press)

SCIP Opt. Suite: http://scip.zib.de
Thorsten Koch · Daniel Rehfeldt

46 / 46