An overview of exact algorithms for the Euclidean Steiner tree problem in n‐space. (13th September 2015)

• Record Type: Journal Article
• Authors: Fampa, Marcia; Lee, Jon; Maculan, Nelson
• Other Names: Lavor Carlile guestEditor.; Firer Marcelo guestEditor.; Martínez José Mario guestEditor.; Liberti Leo guestEditor.
• Is Part Of: International transactions in operational research. Volume 23:Number 5(2016:Sep.)
• Page Start: 861
• Page End: 874
• Publication Date: 2015-09-13
• Subjects: Euclidean Steiner tree problem -- n‐dimensional Euclidean space -- exact algorithm -- mixed‐integer nonlinear programming -- global optimization; Operations research -- Periodicals; 003
• DOI: 10.1111/itor.12207
• Languages: English
• ISSNs: 0969-6016

Abstract

Abstract: 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.