An improved algorithm for computing Steiner minimal trees in Euclidean d-space

M. Fampa (fampadcc.ufrj.br)
K.M. Anstreicher (kurt-anstreicheruiowa.edu)

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 terminal nodes are added. Computational results demonstrate substantial gains compared to Smith's original algorithm.

Keywords: Euclidean Steiner problem, Steiner tree, branch and bound, strong branching

Category 1: Global Optimization (Other )

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Citation: Dept. of Management Sciences, University of Iowa, Iowa City IA, 52242, March 2006.

Download: [Postscript][PDF]

Entry Submitted: 04/17/2006
Entry Accepted: 04/18/2006
Entry Last Modified: 04/17/2006

Modify/Update this entry