Mathematical Programming
https://doi.org/10.1007/s10107-021-01757-5
FULL LENGTH PAPER
Series B
Implications, conflicts, and reductions for Steiner trees
Daniel Rehfeldt1·Thorsten Koch1,2
Received: 26 May 2021 / Accepted: 3 December 2021
© The Author(s) 2021
Abstract
The Steiner tree problem in graphs (SPG) is one of the most studied problems in
combinatorial optimization. In the past 10 years, there have been significant advances
concerning approximation and complexity of the SPG. However, the state of the art
in (practical) exact solution of the SPG has remained largely unchallenged for almost
20 years. While the DIMACS Challenge 2014 and the PACE Challenge 2018 brought
renewed interest into Steiner tree problems, even the best new SPG solvers cannot
match the state of the art on the vast majority of benchmark instances. The following
article seeks to advance exact SPG solution once again. The article is based on a
combination of three concepts: Implications, conflicts, and reductions. As a result,
variousnewSPGtechniquesareconceived.Notably, severaloftheresultingtechniques
are (provably) stronger than well-known methods from the literature that are used in
exact SPG algorithms. Finally, by integrating the new methods into a branch-and-cut
framework, we obtain an exact SPG solver that is not only competitive with, but even
outperforms the current state of the art on an extensive collection of benchmark sets.
Furthermore, we can solve several instances for the first time to optimality.
Keywords Steiner tree problem ·Optimal solution ·Reduction techniques
Mathematics Subject Classification 90C27 ·90C10 ·90C35
1 Introduction
Given an undirected connected graph G=(V,E), edge costs c:E→Q>0and a set
T⊆Vof terminals,theSteiner tree problem in graphs (SPG) is to find a tree S⊆G
BDaniel Rehfeldt
rehfeldt@zib.de
Thorsten Koch
koch@zib.de
1Applied Algorithmic Intelligence Methods Departement, Zuse Institute Berlin, Takustr. 7, 14195
Berlin, Germany
2Chair of Software and Algorithms for Discrete Optimization, TU Berlin, Str. des 17. Juni 135, 10623
Berlin, Germany
123
D.Rehfeldt,T.Koch
with T⊆V(S)such that c(E(S)) is minimized. The SPG is a classic NP-hard
problem [23], and one of the most studied problems in combinatorial optimization.
Part of its theoretical appeal might be attributed to the fact that the SPG generalizes
two other classic combinatorial optimization problems: Shortest paths, and minimum
spanning trees. On the practical side, many applications can be modeled as SPG or
closely related problems, see e.g. [6,27].
The SPG has seen numerous theoretical advances in the last 10 years, bringing
forth significant improvements in complexity and approximability. See e.g. [5,15]for
approximation, and [24,29,47] for complexity results. However, when it comes to
(practical) exact algorithms, the picture is significantly more bleak. After flourishing
in the 1990s and early 2000s, algorithmic advances came to a staggering halt with the
(joint) PhD theses of Polzin and Vahdati Daneshmand almost 20 years ago [31,46].
They introduced a wealth of new results and algorithms for SPG, and combined them
in an exact solver that drastically outperformed all previous results from the literature.
Their work is also published in a series of articles [32–36]. However, their solver is
not publicly available.
The 11th DIMACS Challenge in 2014, dedicated to Steiner tree problems, brought
renewed interest to the field of exact algorithms. In the wake of the challenge, several
new exact SPG solvers were introduced in the literature [13,14,17,30]. Overall, the
11th DIMACS Challenge brought notable progress on the solution of notoriously hard
SPG instances that had been designed to defy known solution techniques, see [26,41].
Several of these instances could be solved for the first time to optimality. However, on
the vast majority of instances from the literature, Polzin and Vahdati Daneshmand [31,
46] (whose solver did not compete at the DIMACS Challenge) stayed out of reach: For
many benchmarkinstances, their solver is even two orders of magnitude or more faster,
and it can furthermore solve substantially more instances to optimality—including
those introduced at the DIMACS Challenge [37]. In 2018, the 3rd PACE Challenge
[4] took place, dedicated to fixed-parameter tractable algorithms for SPG. Thus, the
PACE Challenge considered mostly instances with a small number of terminals, or
with small tree-width. Solvers that successfully participated in the PACE Challenge
are for example described in [18,21]. Still, even for these special problem types, the
solver by [31,46] remained largely unchallenged, see e.g. [21].
The following article aims to once again advance the state of the art in exact SPG
solution.
1.1 Contribution
This article is based on a combination of three concepts: Implications, conflicts, and
reductions. As a result, various new SPG techniques are conceived. The main contri-
butions are as follows.
– By using a new implication concept, a distance function is conceived that provably
dominates the well-known bottleneck Steiner distance. As a result, several reduc-
tion techniques that are stronger than results from the literature can be designed.
– We show how to derive conflict information between edges from the above meth-
ods. Further, we introduce a new reduction operation whose main purpose is to
123
Implications, conflicts, and reductions for Steiner trees
introduce additional conflicts. Such conflicts can for example be used to generate
cuts for the integer programming (IP) formulation.
– We introduce a more general version of the powerful so-called extended reduction
techniques. We furthermore enhance this framework by using both the previously
introduced new distance concept, and the conflict information.
– Finally, we integrate the components into a branch-and-cut algorithm. Besides pre-
processing, domain propagation, and cuts, also primal heuristics can be improved
(by using the new implication concept). The practical implementation is realized
as an extension of the branch-and-cut solver SCIP- Jack [14].
The resulting exact SPG solver outperforms the current state-of-the-art solver from
[31,46] on many well-established benchmark sets from the literature. Furthermore, it
can solve several instances for the first time to optimality.
1.2 Preliminaries and notation
We write G=(V,E)for an undirected graph, with vertices Vand edges E.Weset
n:= |V|and m:= |E|. We denote the vertices and edges of any subgraph S⊆G
by V(S)and E(S), respectively. For a walk Wwe likewise denote the set of vertices
and the set of edges it contains by V(W)and E(W). For any U⊆Vwe define the
cut δ(U):= {{u,v}∈E|u∈U,v ∈V\U}. We write δG(U)to emphasize that the
cut is defined with respect to graph G.Forv∈Vwe write δ(v) := δ({v}). For any
v∈Vwe define its neighborhood as N(v) := {w∈W|{v,w}∈δ(v)}. Note that
v/∈N(v).
Given edge costs c:E→ Q≥0, the triplet (V,E,c)is referred to as network.
By d(v, w) we denote the cost of a shortest path (with respect to c) between vertices
v,w ∈V. For any (distance) function ˜
d:V
2→ Q≥0, and any U⊆Vwe define the
˜
d-distance network on Uas the network
DG(U,˜
d):= (U,U
2,˜c), (1)
with ˜c({v,w}):= ˜
d(v, w) for all v,w ∈U.If ˜
dis the standard distance (i.e. ˜
d=d),
we write DG(U)instead of DG(U,d). Note that we write usually ˜
d(v, w) instead of
˜
d({v,w}). For an SPG instance on a graph G=(V,E)with terminal set T⊆Vand
edge costs cwe write (G,T,c)or (V,E,T,c).
2 From implications to reductions
Reduction techniques have been a key ingredient in exact SPG solvers, see e.g. [9,25,
33,45]. Among these techniques, the bottleneck Steiner distance introduced in [11]is
arguably the most important one, being the backbone of several powerful reduction
methods. This section introduces a (provably) stronger distance concept, and discusses
several applications for improved reduction methods.
123
D.Rehfeldt,T.Koch
2.1 The bottleneck Steiner distance
Let Pbe a simple path with at least one edge. The bottleneck length [11]ofPis
bl(P):= max
e∈E(P)c(e).
Let v,w ∈V.LetP(v, w) be the set of all simple paths between vand w.The
bottleneck distance [11] between vand wis defined as
b(v, w) := inf{bl(P)|P∈P(v, w)},
with the common convention that inf ∅=∞. It holds that b(v, w) =∞if and only
if vand ware unconnected1. Note that b(v, w) is equal to the bottleneck length of the
path between vand won any minimum spanning tree (MST) of (G,c), as observed
in [8].
Now consider the distance network D:= DG(T∪{v, w}).LetbDbe the bottleneck
distance in D. Define the bottleneck Steiner distance or special distance [11] between
vand was
s(v, w) := bD(v, w).
The arguably best known bottleneck Steiner distance reduction method is based on
the following criterion, which allows for edge deletion [11].
Theorem 1 Let e ={v,w}∈E. If s(v, w) < c(e), then no minimum Steiner tree
contains e.
Note the analogy between bottleneck distance applied to the MST problem, and
bottleneck Steiner distance applied to the SPG: Any edge e={v, w}that satisfies
b(v, w) < c(e)cannot be part of an MST. Otherwise, ecould be replaced by an edge
of cost at most b(v, w) to obtain a spanning tree of smaller cost. Any edge e={v, w}
that satisfies s(v, w) < c(e)cannot be part of a minimum Steiner tree. Otherwise, e
could be replaced by a path in Gcorresponding to an edge in D=DG(T∪{v,w})
with cost at most bD(v, w). In this case, one would obtain a Steiner tree of smaller cost.
We also point out that bottleneck Steiner distances can be computed in polynomial
time, but in practice (heuristic) approximations are used. See [33] for a state-of-the-art
algorithm.
2.2 A stronger bottleneck concept
In the following, we describe a generalization of the bottleneck Steiner distance.
Initially, for an edge e={v,w}define the restricted bottleneck distance b(e)[33]as
the bottleneck distance between vand won (V,E\{e},c).
1While we always assume the graph underlying an SPG instance to be connected, we will use auxiliary
graphs that can be unconnected in the following.
123
Implications, conflicts, and reductions for Steiner trees
Thebasis of the newbottleneckSteinerconceptisformed by a node-weight function
that we introduce in the following. For any v∈V\Tand F⊆δ(v) define
p+(v, F):= max 0,sup{b(e)−c(e)|e∈F,e∩T=∅}
.(2)
We call p+(v, F)the F-implied profit of v. The following observation motivates the
subsequent usage of the implied profit. Assume that p+(v, {e})>0 for an edge
e∈δ(v). If a Steiner tree Scontains v, but not e, then there is a Steiner tree Swith
e∈E(S)such that c(E(S)) +p+(v, {e})≤c(E(S)).
Let v,w ∈V. Consider a finite walk W=(v1,e1,v
2,e2,...,er−1,v
r)with v1=
vand vr=w. We say that Wis a (v, w)-walk. For any k,l∈Nwith 1 ≤k≤l≤r
define the subwalk W(k,l):= (vk,ek,v
k+1,ek+1,...,el−1,v
l).Wwill be called
Steiner walk if V(W)∩T⊆{v,w}and v, w are contained exactly once in W(the
latter condition could be omitted, but has been added for ease of presentation). The
set of all Steiner walks from vto wwill be denoted by WT(v, w). With a slight abuse
of notation we define δW(u):= δ(u)∩E(W)for any walk Wand any u∈V. First,
for a Steiner walk W∈WT(v, w) define
P+
W:= {u∈V(W)|p+(u,δ(u)\δW(u))>0}∪{v,w}.
Define the implied Steiner cost of Was
c+
p(W):=
e∈E(W)
c(e)−
u∈P+
W\{v,w}
p+(u,δ(u)\δW(u)).
Define the implied Steiner length of Was
l+
p(W):= max{c+
p(W(vk,v
)) |1≤k≤≤r,v
k,v
∈P+
W}.(3)
To understand the usage of the implied Steiner length, consider the SPG instance
segment shown in Fig. 1. Assume that edge {v1,v
4}is part of Steiner tree S.Removing
this edge from Sresults in two trees Sand S with v1∈V(S),v4∈V(S). Consider
the Steiner walk W:= (v1,{v1,v
2},v
2,{v2,v
3},v
3,{v2,v
3},v
2,{v2,v
4},v
4).Note
that p+(v3,δ(v
3)\δW(v3))=3, and thus l+
p(W)=4. We claim that Sand S can
be reconnected to a Steiner tree ˜
Sthat is of smaller weight than Sby using only edges
from W. First, assume v3is contained in either Sor S. In this case, we can use the
edges {v1,v
2},{v2,v
3}(if v3∈V(S)) or the edges {v2,v
3},{v2,v
4}(if v3∈V(S))
to reconnect Sand S. Second, assume that v3is neither contained in Snor in S.
In this case, also the edge {v3,t1}cannot be contained in Sor S: Because Sis a
Steiner tree, we have t1∈V(S). Indeed, also {t1,v
4}∈E(S)holds. Reconnect S
and S by adding all edges of Wthat are neither in Snor in S. This procedure results
in a Steiner tree ˜
S. Next, add edge {v3,t1}and remove edge {t1,v
4}from ˜
S.This
exchange reduces the weight of ˜
Sby p+(v3,δ(v
3)\δW(v3)). Thus, the final Steiner
tree ˜
Ssatisfies c(E(˜
S)) ≤c(E(S)) −1.
123
Loading more pages...