A Lightweight Algorithm for
Steiner Tree Problem Based on
Distance Network Heuristic
Miroslav Kadlec
1
Contents
●
Steiner Minimum Tree
●
Motivation
●
Algorithms
●
Distance Network Heuristic, Takahashi, Zelikovsky
●
DNH optimizations
●
Experiments
●
ČEZ networks
●
SteinLib
2
Steiner (minimum) tree in graphs
●
Inputs
●
graph G=(N, E)
●
set of terminals S N⊆
●
weights assigned to edges
●
Steiner Tree = any tree, that spans S
●
Steiner Minimum Tree (SMT) = the ST of minimum total weight
●
Minimum Spanning Tree?
3
Steiner (not minimum) tree in a graph
4
Motivation
●
Design communication lines between major elements of
the power grid (substations)
●
Fiber optics added to selected power lines
●
Deploment cost vary
●
Some communication lines already deployed
●
Overall cost should be minimized
5
Power grid as a graph
●
Graph G = (N, E)
●
Nodes:
●
stations
●
topo. points (deg. > 2)
●
sem. points (deg. > 1)
●
Edges:
●
power lines
●
existing comm. lines
●
Weights based on:
●
line length
●
placement
●
current state
6
Steiner trees for communication lines planning
●
Existing optics
– cost/weight to 0
– we can utilize it to shorten runtime
●
Use-case = iterative use
●
incremental growth of the communication
network
●
solutions for various scenarios
●
variable circumstances
●
=> need for fast algorithm
7
Algorithms & heuristics
●
Steiner Minimum Tree - NP-hard problem
●
Preprocessing – reduce number of nodes and edges
●
Solving:
●
Distance Network Heuristic
●
Takahaski algorithm
●
Zelikovsky algorithm
8
Distance Network Heuristic
●
Based on Distance Network (DN)
●
Paths between all pairs of terminals
●
Fast execution, basic quality
●
Process
1) Compute DN
2) Compute MST using paths
3) Mark all used nodes as terminals
4) Recompute DN and MST with paths again
9
Takahaski algorithm
●
Based on Dijkstra algorithm
●
Fastest execution, lowest quality
●
Process
1) Select a random terminal as a partial solution
2) While not all terminals are connected
a) Find closest disconnected terminal
b) Add to the solution
10
Zelikovsky algorithm
●
Based on searching beneficial stars (incremental improvement)
●
Star = 1 nonterminal connected to 3 terminals
●
Win function – quantifies benefit of using each star
●
Slower execution, higher quality
●
Process
1) Start with a basic DNH
2) Construct Zelikovsky Tree
3) For each nonterminal
a) For each triplet of terminals
i) Evaluate Win of such star
4) Add center nonterminal of the best Win star to terminals and go to 2)
5) Recompute DNH with all added nonterminals
11
12
Tuned DNH - assumptions
●
We expected DNH to be a good trade-off between
runtime and solution quality
●
DNH is simple approach and can be optimized to run
faster without quality loss
●
Centrality might be incorporated in DNH to increase
quality
13
Tuned DNH (1/4) - DN & MST alg.
●
Distance network computation
●
Floyd-Warshall
●
Dijkstra algorithm
●
DNH needs distances between pairs of terminals only
– for |S| << |N| outperforms Floyd-Warshall even in basic implementation
●
Can run in parallel
●
We can limit the searching depth (hopefully without quality loss)
●
Minimum Spanning Tree
●
Prim’s algorithm - faster than Kruskal’s
14
Tuned DNH (2/4) - Limited search depth
●
Longer paths (# edges) are usually more expensive
→ low probability for the final solution
●
Risk1: Outlying terminals
●
terminals not distributed evenly
●
outliers may not be connected
●
Solution1: limit given by
number of terminals met
15
Tuned DNH – limited search depth
●
Risk2: Isolated clusters
●
larger than „terminals-met“ limit
●
the terminals only „find“ other
of the same cluster
●
Solution2: Force the Dijkstra
algorithm to “meet” existing optics
before ending
16
Tuned DNH (3/4) - shrinked optics subgraph
●
Risk: Existing optics edges are searched first
●
Solution: Shrinked optics
●
1) Store the path to closest node with existing optics
●
2) Update the distance network
●
Eliminates the disconnections within the steiner tree while
reducing the runtime of the algorithm
17
Tuned DNH (4/4) - Centrality
●
Higher centrality = higher
probability for a path to be
shared
●
number of shortest paths
using given node
●
Price discounts for paths with high centrality
18
Comparison
●
Datasets:
●
Subgraphs of ČEZ power distribution network
●
Existing optics, relatively sparse
●
SteinLib
●
Open-source dataset of graphs for SMT
19
Algorithms comparison – solution quality
20
Algorithms comparison – solution quality
21
Algorithms comparison – execution time
22