Journal article
An improved algorithm for computing Steiner minimal trees in Euclidean d -space
Discrete optimization, Vol.5(2), pp.530-540
05/01/2008
DOI: 10.1016/j.disopt.2007.08.006
Abstract
We describe improvements to Smith’s branch-and-bound (B&B) algorithm for the Euclidean Steiner problem in
R
d
. Nodes in the B&B tree correspond to full Steiner topologies associated with a subset of the terminal nodes, and branching is accomplished by “merging” a new terminal node with each edge in the current Steiner tree. For a given topology we use a conic formulation for the problem of locating the Steiner points to obtain a rigorous lower bound on the minimal tree length. We also show how to obtain lower bounds on the child problems at a given node without actually computing the minimal Steiner trees associated with the child topologies. These lower bounds reduce the number of children created and also permit the implementation of a “strong branching” strategy that varies the order in which the terminal nodes are added. Computational results demonstrate substantial gains compared to Smith’s original algorithm.
Details
- Title: Subtitle
- An improved algorithm for computing Steiner minimal trees in Euclidean d -space
- Creators
- Marcia Fampa - Universidade Federal do Rio de JaneiroKurt M. Anstreicher - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Discrete optimization, Vol.5(2), pp.530-540
- Publisher
- Elsevier B.V
- DOI
- 10.1016/j.disopt.2007.08.006
- ISSN
- 1572-5286
- eISSN
- 1873-636X
- Language
- English
- Date published
- 05/01/2008
- Academic Unit
- Industrial and Systems Engineering; Computer Science; Business Analytics
- Record Identifier
- 9984380441602771
Metrics
3 Record Views