Abstract
Given p points in \({\mathbb {R}}^n\), called terminal points, the Euclidean Steiner Tree Problem (ESTP) consists of finding the shortest tree connecting them, using or not extra points, called Steiner points. This is a well-known NP-hard combinatorial optimization problem. Instances with thousands of points have been solved for \(n=2\). However, methods specialized for the ESTP in \({\mathbb {R}}^2\) cannot be applied to problems in higher dimensions. Enumeration schemes have been proposed in the literature. Unfortunately, the number of Steiner trees having p terminal points grows extremely fast with p, so the enumeration of all trees is only possible for very small values of p. For \(n\ge 3\), even small instances with tens of points cannot be solved with exact algorithms in a reasonable time. In this work, we present two heuristics for the ESTP. These heuristics differ from most existent ones in the literature in the fact that they do not rely on the minimum spanning tree of the terminal points. Instead, they start with a single extra point connected to all terminal points and new extra points are introduced iteratively according to angle properties for two consecutive edges. The heuristics return the optimal solution in most of the small test instances. For large instances, where the optimum is not known, the heuristics return relatively good solutions, according to their Steiner ratio.
Similar content being viewed by others
References
Arbel A (1993) Exploring interior-point linear programming: algorithms and software. MIT Press, Foundations of computing
Beasley JE (1992) A heuristic for Euclidean and rectilinear Steiner problems. Eur J Oper Res 58:284–292
Brazil M, Thomas D, Nielsen B, Winter P, Wulff-Nilsen C, Zachariasen M (2009) A novel approach to phylogenetic trees: d-dimensional geometric Steiner trees. Networks 53(2):104–111. https://doi.org/10.1002/net.20279
Brazil M, Graham R, Thomas DA, Zachariasen M (2014) On the history of the Euclidean Steiner Tree Problem. Arch Hist Exact Sci 68:327–354. https://doi.org/10.1007/s00407-013-0127-z
Chandrasekaran R, Tamir A (1990) Algebraic optimization Fermat-Weber location problem. Math Program 46:219–224. https://doi.org/10.1007/BF01585739
Chapeau-Blondeau F, Janez F, Ferrier JL (1997) A dynamic adaptive relaxation scheme applied to the Euclidean Steiner minimal tree problem. SIAM J Optim 7(4):1037–1053. https://doi.org/10.1137/S1052623494275069
Costa V, Fampa MHC, Maculan N (2016) Um modelo matemático para o problema euclidiano de Steiner em \({R}^n\). A Investigação Operacional em Portugal: Novos Desafios. Editora IST PRESS, Lisboa, pp 145–158
do Forte V, Montenegro FMT, Brito JAM, Maculan N, (2016) Iterated local search algorithms for the Euclidean Steiner tree problem in \(n\) dimensions. Int Trans Oper Res (ITOR) 23(6):1185–1199. https://doi.org/10.1111/itor.12168
Dreyer DR, Overton ML (1998) Two heuristics for the Euclidean Steiner tree problem. J Global Optim 13:95–106. https://doi.org/10.1023/A:1008285504599
Du DZ (1991) On Steiner ratio conjectures. Ann Oper Res 33:437–449. https://doi.org/10.1007/BF02071981
Du DZ, Hwang FK (1990) The Steiner ratio conjecture of Gilbert and Pollak is true. Proc Natl Acad Sci 87(23):9464–9466. https://doi.org/10.1073/pnas.87.23.9464
Du DZ, Hwang FK (1992) A proof of the Gilbert-Pollak conjecture on the Steiner ratio. Algorithmica 7:121–135. https://doi.org/10.1007/BF01758755
Fampa MHC, Anstreicher K (2008) An improved algorithm for computing Steiner minimal trees in Euclidean d-space. Discret Optim 5(2):530–540. https://doi.org/10.1016/j.disopt.2007.08.006
Fampa MHC, Maculan N (2001) A new relaxation in conic form for the Euclidean Steiner problem in \({R}^n\). RAIRO Oper Res 35(4):383–394. https://doi.org/10.1051/ro:2001120
Fampa MHC, Maculan N (2004) Using a conic formulation for finding Steiner minimal trees. Numer Algorithms 35(4):315–330. https://doi.org/10.1023/B:NUMA.0000021765.17831.bc
Fampa M, Lee J, Melo W (2016) A specialized branch-and-bound algorithm for the Euclidean Steiner tree problem in n-space. Comput Optim Appl 65(1):47–71. https://doi.org/10.1007/s10589-016-9835-z
Fampa MHC, Lee J, Maculan N (2016) An overview of exact algorithms for the Euclidean Steiner tree problem in n-space. Int Trans Oper Res (ITOR) 23(5):861–874. https://doi.org/10.1111/itor.12207
FICO Xpress Optimization (2021) https://www.fico.com/en/products/fico-xpress-optimization. Accessed 21 Dec 2021
Garey M, Johnson D (1979) Computers and intratability: a guide to the theory of NP-completeness. W. H. Freeman and Company, San Francisco
Garey MR, Graham RL, Johnson DS (1977) The complexity of computing Steiner minimal trees. SIAM J Appl Math 32(4):835–859. https://doi.org/10.1137/0132072
Gilbert EN, Pollak HO (1968) Steiner minimal trees. SIAM J Appl Math 16(1):1–29. http://www.jstor.org/stable/2099400
Gurobi Optimization (2021) https://www.gurobi.com/products/gurobi-optimizer/. Accessed 21 Dec 2021
IBM CPLEX Optimizer (2021) https://www.ibm.com/br-pt/analytics/cplex-optimizer. Accessed 21 Dec 2021
Ivanov AO, Tuzhilin AA (2012) The Steiner ratio Gilbert-Pollak Conjecture is still open. Algorithmica 62:630–632. https://doi.org/10.1007/s00453-011-9508-3
Maculan N, Michelon P, Xavier A (2000) The Euclidean Steiner tree problem in \({R}^n:\) a mathematical programming formulation. Ann Oper Res 96:209–220. https://doi.org/10.1023/A:1018903619285
Maculan N, Negreiros-Gomes MJ, Pinto R (2021) A new computational approach for the Fermat-Weber problem and extensions. Tech. Rep. ES-772/21, Systems Engineering and Computer Science, Federal University of Rio de Janeiro. https://www.cos.ufrj.br/index.php/pt-BR/publicacoes-pesquisa/details/15/2986
Melzak ZA (1961) On the problem of Steiner. Can Math Bull 4(2):143–148. https://doi.org/10.4153/CMB-1961-016-2
Montenegro FMT (2001) Heurísticas para o problema de Steiner Euclideano em R\(^n\). PhD thesis, Systems and Computer Science, COPPE, Federal University of Rio de Janeiro
Montenegro F, Torreão JRA, Maculan N (2003) Microcanonical optimization for the Euclidean Steiner problem in \({R}^n\) with application to phylogenetic inference. Phys Rev E 68(5):056702. https://doi.org/10.1103/PhysRevE.68.056702
Montenegro F, Maculan N, Plateau G, Boucher P (2001) Essays and surveys in metaheuristics, Kluwer Academic Publishers, chap New Heuristics for the Euclidean Steiner Problem in \({{\mathbb{R}}^n}\), pp 509–524
Ouzia H, Maculan N (2021) Mixed integer nonlinear optimization models for the Euclidean Steiner tree problem in \(\mathbb{R}^d\). J Glob Optim. https://doi.org/10.1007/s10898-021-01001-6
Pinto RV, Ouzia H, Maculan M (2020) New mixed integer non linear programming (MINLP) models for the Euclidean Steiner tree problem in \({R}^n\). Tech. Rep. ES-769/20, Systems Engineering and Computer Science. Federal University of Rio de Janeiro. https://www.cos.ufrj.br/index.php/pt-BR/publicacoes-pesquisa/details/15/2966
Rimola LF (2017) Sobre o problema Euclidiano de Steiner no R\(^n\). PhD thesis, Systems and Computer Science, COPPE, Federal University of Rio de Janeiro
Smith WD (1992) How to find Steiner minimal trees in Euclidean d-space. Algorithmica 7:137–177. https://doi.org/10.1007/BF01758756
Smith WD, MacGregor Smith J (1995) On the Steiner ratio in 3-space. J Comb Theory Ser A 69(2):301–332. https://doi.org/10.1016/0097-3165(95)90055-1
Smith JM, Jang Y, Kim MK (2007) Steiner minimal trees, twist angles, and the protein folding problem. Proteins 66(4):889–902. https://doi.org/10.1002/prot.21257
Soukup J, Chow WF (1973) Set of test problems for the minimum length connection networks. ACM/SIGMAP Newslett 15:48–51
Stanton C, Smith JM (2004) Steiner trees and 3-D macromolecular conformation. INFORMS J Comput 16(4):470–485. https://doi.org/10.1287/ijoc.1040.0101
Warme DM, Winter P, Zachariasen M (2000) Exact algorithms for plane Steiner tree problems: a computational study. Springer, Boston, pp 81–116. https://doi.org/10.1007/978-1-4757-3171-2_6
Winter P, Zachariasen M (1996) Large Euclidean Steiner minimal trees in an hour
Xue G, Ye Y (1997) An efficient algorithm for minimizing a sum of Euclidean norms with applications. SIAM J Optim 4(7):1017–1036. https://doi.org/10.1137/S1052623495288362
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Pinto, R.V., Maculan, N. A new heuristic for the Euclidean Steiner Tree Problem in \({\mathbb {R}}^n\). TOP 31, 391–413 (2023). https://doi.org/10.1007/s11750-022-00642-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-022-00642-4