�ݺ�ߣ

A Divide-and-Bridge Heuristic for
Steiner Minimal Trees on the
Euclidean Plane

Badri Toppur, Ph.D.
Associate Professor of Operational Research
Great Lakes Institute of Management
Chennai, India

INTRODUCTION TO THE STEINER
PROBLEM
• The Steiner problem in cost management has its
origins from Fermat’s problem in the Renaissance
period.

• Connect three villages in the area, using another site if
necessary so that the total interconnecting length is
minimum.

• Torricelli, Napolean and Steiner among others have
worked on solutions that use only compass and ruler.
21st Symposium on Mathematical
Programming, TU Berlin

COMPASS AND RULER
CONSTRUCTIONS
• The location of the Steiner site can be found through
elementary geometric operations for three fixed
terminals.
• The sites are found within the convex hull of the fixed
terminals.
• Triangles erected on the sides of the triangle formed by
the fixed terminals.
• The circumscribing circles around the erected triangles
intersect precisely at the location of the Steiner site.
• There are some alternative Euclidean constructions.
• These methods can be extended to handle more sites.


SOLVING THE STEINER PROBLEM
USING A COMPUTER
• The scale of Fermat’s problem to be tackled has
become large because of the extreme globalization and
nationalization of the supply chain.
• The large-scale problem is called the Steiner problem
and can be described using algebraic notation that
makes for a computer solution.
• Connect sites v1, v2, …vn in the Euclidean plane, using
other sites s1,….sn-2 if necessary so that the total
interconnecting length of the resulting tree is
minimum.

ENUMERATION METHODS
• Melzak, Gilbert and Pollak provided the earliest
enumeration approaches to this NP hard problem.
• Winter, Zachariasen and others have implemented
good methods for the 2d problem.
• Warren Smith’s Branch and Bound is the best
enumeration method for any dimension, though with
an exponential time limitation.
• Sets with up to 15 sites can be solve exactly in
reasonable time.
• A number of heuristics have been implemented to
obtain good solutions for more than 15 sites, in
reasonable time.

COMPUTATIONAL GEOMETRY
HEURISTIC
• James MacGregor Smith in 1978, in collaboration with
his guide Judith Liebman, published numerous
polynomial time methods using Computational
Geometry principles to solve the Steiner problem in 2d.
His application was in architectural design.

• He was my advisor at Umass, Amherst when I worked
in 1996 on a heuristic for the same problem but in 3d.
We worked on atomic coordinate datasets of
compounds such as Silk, Actin and Collagen.

GRAPH ALGORITHM HEURISTIC

• My heuristic was based on Depth First Search, a graph
algorithm technique I had learnt earlier at Clemson
University, during my M.S.

• I used DFS of the Minimum Spanning Tree using the
optimization method for a fixed topology that is a part
of the exponential algorithm design of Warren D.
Smith.


DIVIDE AND BRIDGE HEURISTIC
• This heuristic is inspired by three popular Computer
Science principles.
 Lexicographic Sort
 Divide and Conquer
 Local Search for Best Topology

• The first two principles were used successfully by
Preparata and Hong in their convex hull algorithm
• In addition to these two methods, Local Search is
required in this heuristic


WHAT IS LEXICOGRAPHIC SORT?
Site X coordinate Y coordinate Site X coordinate Y coordinate

V1 3.0 6.0 V6 1.0 2.0
V2 1.1 3.0 V3 1.1 2.5
V3 1.1 2.5 V2 1.1 3.0
V4 2.0 4.0 V4 2.0 4.0
V5 2.0 5.0 V5 2.0 5.0
V6 1.0 2.0 V1 3.0 6.0
BEFORE SORT AFTER SORT


THE RECURSIVE DIVISION OF A SET
Set Size Partition Set Size Partition
6 (3, 3) 16 (4, 4, 4, 4)
7 (4, 3) 17 (5, 4, 4, 4)
8 (4, 4) 18 (5, 4, 5, 4)
9 (5, 4) 19 (5, 5, 5, 4)
10 (5, 5) 20 (5, 5, 5, 5)
11 (3, 3, 5) 21 (3, 3, 5, 5, 5)
12 (3, 3, 3, 3) 22 (3, 3, 5, 3, 3, 5)
13 (4, 3, 3, 3) 23 (3, 3, 3, 3, 3, 3, 5)
14 (4, 3, 4, 3) 24 (3, 3, 3, 3, 3, 3, 3, 3)
15 (4, 4, 4, 3) 25 (4, 3, 3, 3, 3, 3, 3, 3)


BRIDGE BETWEEN TWO TREES


BRIDGE SOLUTION SUBOPTIMAL

BRIDGE ACROSS STEINER
THE DIVIDE SITE

SET 1 SET 2 TOPOLOGY 1
IS NOT OPTIMAL

THE FIFTEEN ELEMENTARY PARTITIONS
Scenario Set Size Partition Scenarios Set Size Partition

1 2 (1, 1) 9 7 (2, 5)
2 3 (1, 2) 10 7 (3, 3)
3 4 (1, 3) 11 8 (3, 4)
4 5 (1, 4) 12 8 (3, 5)
5 6 (1, 5) 13 8 (4, 4)
6 4 (2, 2) 14 9 (4, 5)
7 5 (2, 3) 15 10 (5, 5)
8 6 (2, 4)

Local search for the best topology is essential for these
fifteen scenarios. The big topology is a union of these.

SCENARIO 1 SCENARIO 2

STEINER
SITE
SET 1 SET 2

PRIMARY BRIDGE
ACROSS THE DIVIDE

Scenario #1 (1, 1) 21st Symposium on Mathematical Scenario #2 (1, 2)

SCENARIO 3a

SET 1

SET 2

STEINER
PRIMARY BRIDGE SITE
ACROSS THE DIVIDE
Scenario #3a (1, 3) Topology a


SCENARIO 3b

SET 1

SET 2

STEINER
SITE

PRIMARY BRIDGE
ACROSS THE DIVIDE
Topology b
Scenario #3b (1, 3) 21st Symposium on Mathematical

SCENARIO 3c

SET 1

SET 2

STEINER
SITE

PRIMARY BRIDGE
ACROSS THE DIVIDE

Topology c
Scenario #3c (1, 3) 21st Symposium on Mathematical

SCENARIO 4a

SET 1

STEINER
SET 2
PRIMARY BRIDGE SITE
ACROSS THE DIVIDE

Topology a
Scenario #4a (1, 4) 21st Symposium on Mathematical

SCENARIO 4b

SET 1

STEINER
SET 2
PRIMARY BRIDGE SITE
ACROSS THE DIVIDE

Topology b
Scenario #4b (1, 4) 21st Symposium on Mathematical

SCENARIO 5a

SET 1

PRIMARY BRIDGE
ACROSS THE DIVIDE SET 2
STEINER
SITE
Scenario #5a (1, 5)
21st Symposium on Mathematical Topology a

SCENARIO 5b

SET 1

PRIMARY BRIDGE
ACROSS THE DIVIDE SET 2
STEINER
SITE
Scenario #5b (1, 5)
Topology b

SCENARIO 6a Topology A may
not be optimal

PRIMARY BRIDGE STEINER
ACROSS THE DIVIDE SITE

SET 1 SET 2
Topology A

Scenario #6 (2, 2) 21st Symposium on Mathematical

Topology B can be obtained from Topology A by
adding a secondary bridge.
TOPOLOGY B
IS OPTIMAL

REMOVE THIS EDGE TO
BREAK THE CYCLE

ADD A SECONDARY BRIDGE

Scenario #6 (2, 2) 21st Symposium on Mathematical

THE CHOICE OF PRIMARY BRIDGE
AND SECONDARY BRIDGE
• Since there are at most five fixed sites in each set, with
three Steiner sites the first bridge across the divide is
selected in at most 8×8 ways. Iterate and find the best
one.

• The secondary bridge that creates the cycle and could
lead to the other topology is selected in at most 7x7
ways. Trace out the cycle and exclude the longest edge.
Iterate and find the best one.


PSEUDOCODE OF THE HEURISTIC
Step 1. If the cardinality of set T0 > 6, sub-divide the given set T0 into two smaller sets
T1 and T2, otherwise calculate SMT using exact algorithm.
If the cardinality of set T1 > 6 divide it into two sets to obtain T3 and T4.
If the cardinality of set T2 > 6 divide it into two sets to obtain T5 and T6.
Continue dividing until all the sites are in subsets ( Va, Vb, Vc,…., Vp ) having three,
four or five vertices.

Step 2.a Calculate the MST for each subset in the list ( Va, Vb, Vc,…., Vp) using Prim's algorithm.
Step 2.b Calculate the SMT for each subset in the list ( Va, Vb, Vc,…., Vp) using Smith's
exponential algorithm.

Step 3.a Identify the closest pair of sets Vi and Vj in the list (Va, Vb, Vc, ….Vp).
Step 3.b Bridge the sets Vi and Vj to obtain Vq using the bridge terminals si and sj.
Step 3.c Add Vq to the end of the list. Delete the sets Vi and Vj from the list.

Step 4.a The two bridge terminals si and sj become Steiner vertices of the bridged tree Vq.
Step 4.b Modify the topology of the bridged tree Vq to include the two new Steiner vertices.
Step 4.c Optimize the coordinates of the bridged tree Vq using the O(N) algorithm.


PSEUDOCODE OF THE HEURISTIC
CONTINUED
Step 5.a Changes in the adjacencies of the bridged tree
5.a.(i) Insert a bridge from one of the n1 nodes in Vi to one of the n2 nodes in Vj
5. a.(ii) Insert a secondary bridge, not coincident with the primary bridge above, but
one that forms a cycle with it and the other edges of the tree Vq. The cycle
formed is broken by excluding the most expensive edge.
5.a.(iii) Optimize Steiner site coordinates with one or more split operations. Some of
the Steiner sites will be coincident.
Step 5.b Including a site in a neigbhouring set.

Step 6. Repeat Step 3, Step 4 and Step 5, until there is one tree.


PERFORMANCE ON SAUSAGES
• Fejes Toth: A sausage is an arrangement of
simplices that is spatially most compact.

• In 2d it is a series of abutting triangles, and in 3d
it is a series of abutting tetrahedrons that spiral
around an asymptotic axis.
• The heuristic requires no local search for sausage
shaped data and gives optimal solutions for
every problem size.

PERFORMANCE ON RANDOM DATA
WITHOUT SECONDARY BRIDGE
• The heuristic without local search, gave the optimal solution on one
in five occasions for five datasets containing 2d coordinates.

• For five datasets of 3d coordinate data it did not have even that
20% accuracy.

• Therefore local search is a must after the divide-and-bridge gives a
feasible solution. Things left to do:

i) Try other bridges, besides minimum length bridge.
ii) Use a secondary bridge after picking a primary bridge.
Break any cycle formed.
iii) Move a site from one set to a neighbouring set.


Heuristic matches
Optimal solution
SMALL SETS OF SITES IN 2D
Six Optimal DAB MST Seven Optimal DAB MST
Sites SMT Heuristic Sites SMT Heuristic
SMT SMT
A 2.612875 2.712754 2.679682 A 2.515521 2.746555 2.725121

B 2.187850 2.187850 2.353033 B 2.837967 2.880656 2.880656

C 2.527078 2.527078 2.596151 C 3.733940 4.084624 3.745920

D 3.062734 3.138599 3.138598 D 3.094959 3.200600 3.163372

E 2.529469 2.529469 2.603461
E 3.555844 3.555844 4.570067


Heuristic matches
Optimal solution SMALL SETS OF SITES IN 2D
Eight Optimal DAB MST Nine Optimal DAB MST
Sites SMT Heuristic Sites SMT Heuristic
SMT SMT
A 3.148039 3.392032 3.196633 A 3.888391 3.911463 4.006239

B 3.572636 3.845596 3.778452 B 4.149458 4.161037 4.269023

C 3.269300 4.342299 3.380685 C 3.596876 3.596876 3.647144

D 4.115045 4.115045 4.231006 D 3.836754 4.010826 3.963898

E 3.781634 4.615251 3.864216 E 3.177895 3.243970 3.268170


THANKS AND REFERENCES
• James MacGregor Smith for guidance in my initial exposure to heuristics for
the problem. MacGregor~Smith, J. R. Weiss, and Minoo Patel. 1995. An O(N2)
Heuristic for Steiner Minimal Trees in E3. Networks, Vol. 25, pp. 273-289.

• Warren D. Smith for the exact exponential time algorithm written in C.
Smith, Warren D., 1992, How to find Steiner Minimal Trees in Euclidean d-
Space., Algorithmica 7, pp. 137-177.

• Preparata, F. P. and S. J. Hong, 1977, Convex Hulls of Finite Sets of Points in
Two and Three Dimensions. Communications of the ACM Volume 20, Number
2.

• John Beasley for emphasizing benchmark problems. Beasley, J. E. and F.
Goffinet, 1994. A Delaunay Triangulation-Based Heuristic for the Euclidean
Steiner Problem Networks, Volume 24, pp. 215-224.


ANYTHING THAT HAS NOT BEEN SUFFERED AND SOLVED
TO THE END WILL RETURN.
HERMANN HESSE


�ݺ�ߣ

Ismp 2012

More Related Content

Ismp 2012