An overview of exact algorithms for the Euclidean Steiner tree problem in n-space

作者：Fampa Marcia^*; Lee Jon; Maculan Nelson

来源：International Transactions in Operational Research, 2016, 23(5): 861-874.

DOI：10.1111/itor.12207

• Euclidean Steiner tree problem
• n-dimensional Euclidean space
• exact algorithm
• mixed-integer nonlinear programming
• global optimization

The Euclidean Steiner tree problem (ESTP) in R-n is to find a shortest network interconnecting p given points in n-dimensional Euclidean space. The problem was first described in the plane and an algorithm with very good practical efficiency has been proposed to solve this particular case. The generalization for higher dimensions was proposed in the 19th century, however the numerical solution of the problem remains very challenging when n >= 3. We give an overview of the exact algorithms presented in the literature for the ESTP when n >= 3 and discuss their common and distinguished features, their advantages and drawbacks, and some possible directions for improvement toward the numerical solution of large instances of the problem.

• 出版日期2016-9