Optimization Online


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

M. Fampa (fampa***at***dcc.ufrj.br)
K.M. Anstreicher (kurt-anstreicher***at***uiowa.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society