A new second-order conic optimization model for the Euclidean Steiner tree problem in \(\mathbb{R}^d\). (English) Zbl 07745349
Summary: In this work, a new second-order conic optimization model for the Euclidean Steiner tree problem in \(d\)-space, where the dimension \(d\) is at least three, will be presented. Also, two strategies for eliminating isomorphic trees will be developed. Computational results highlighting the efficiency of this model compared to existing models for the Euclidean Steiner tree problem will be discussed. Finally, enforcing the proposed model with any of the isomorphic tree elimination strategies permits us to compute for the first time, to the best of our knowledge, the minimum Steiner tree for the cube in \(\mathbb{R}^3 \).
{© 2023 The Authors. International Transactions in Operational Research published by John Wiley & Sons Ltd on behalf of International Federation of Operational Research Societies}
{© 2023 The Authors. International Transactions in Operational Research published by John Wiley & Sons Ltd on behalf of International Federation of Operational Research Societies}
MSC:
| 90-XX | Operations research, mathematical programming |
Keywords:
second-order conic optimization; integer programming; Euclidean Steiner tree problem; Steiner tree; nonlinear optimization models; mixed integer nonlinear optimizationReferences:
| [1] | AMPL, 2023. https://ampl.com/products/solvers/all‐solvers‐for‐ampl/, version 20200501. |
| [2] | BARON, 2023. https://minlp.com/baron‐solver, version 21.1.13. |
| [3] | Beyer, T., Hedetniemi, S.M., 1980. Constant time generation of rooted trees. SIAM Journal on Computing9, 4, 706-712. · Zbl 0453.05020 |
| [4] | Brazil, M., Graham, R.L., Thomas, D.A., Zachariasen, M., 2014. On the history of the Euclidean Steiner tree problem. Archive for History of Exact Sciences68, 327-354. · Zbl 1295.05002 |
| [5] | Brazil, M., Thomas, D.A., Nielsen, B.K., Winter, P., Wulff‐Nilsen, C., Zachariasen, M., 2009. A novel approach to phylogenetic trees: d‐dimensional geometric Steiner trees. Networks53, 2, 104-111. · Zbl 1168.92035 |
| [6] | Cavalli‐Sforza, L.L., Edwards, A.W.F., 1967. Phylogenetic analysis: models and estimation procedures. Evolution21, 3, 550-570. |
| [7] | D’Ambrosio, C., Fampa, M., Lee, J., Vigerske, S., 2015. On a nonconvex MINLP formulation of the Euclidean Steiner tree problem in n‐space. In Bampis, E. (ed.) (ed), Experimental Algorithms, Springer International Publishing, Cham, pp. 122-133. |
| [8] | D’Ambrosio, C., Fampa, M., Lee, J., Vigerske, S., 2020. On a nonconvex MINLP formulation of the Euclidean Steiner tree problem in n‐space: missing proofs. Optimization Letters14, 409-415. · Zbl 1442.90135 |
| [9] | Do Forte, V.L., Montenegro, F.M.T., De Moura Brito, J.A., Maculan, N., 2015. Iterated local search algorithms for the Euclidean Steiner tree problem in n dimensions. International Transactions in Operational Research23, 6, 1185-1199. · Zbl 1348.90601 |
| [10] | Fampa, M., 2019. Insight into the computation of Steiner minimal trees in Euclidean space of general dimension. Discrete Applied Mathematics308, 4, 4-19. · Zbl 1483.90134 |
| [11] | Fampa, M., Anstreicher, K.M., 2008. An improved algorithm for computing Steiner minimal trees in Euclidean d‐space. Discrete Optimization5, 2, 530-540. · Zbl 1152.90663 |
| [12] | Fampa, M., Lee, J., Maculan, N., 2016a. An overview of exact algorithms for the Euclidean Steiner tree problem in n‐space. International Transactions in Operational Research23, 4, 861-874. · Zbl 1348.90593 |
| [13] | Fampa, M., Lee, J., Melo, W., 2016b. A specialized branch‐and‐bound algorithm for the Euclidean Steiner tree problem in n‐pace. Computational Optimization and Applications65, 47-71. · Zbl 1353.90165 |
| [14] | Fampa, M., Maculan, N., 2001. A new relaxation in conic form for the Euclidean Steiner problem in \(\mathbb{R}^n\). RAIRO‐Operations Research35, 4, 283-394. · Zbl 1020.90042 |
| [15] | Fampa, M., Maculan, N., 2004. Using a conic formulation for finding Steiner minimal trees. Numerical Algorithms35, 4, 315-330. · Zbl 1047.90055 |
| [16] | FICO‐XPRESS, 2023. https://www.fico.com/en/products/fico‐xpress‐solver, Version 8.13.1(39.01.02). |
| [17] | Fonseca, R., Brazil, M., Winter, P., Zachariasen, M., 2014. Faster exact algorithms for computing Steiner trees in higher dimensional Euclidean spaces. In Proceedings of the 11th DIMACS Implementation Challenge Workshop, Providence, RI. December 4-5, 2014. |
| [18] | Garey, M., Graham, R., Johnson, D.S., 1977. The complexity of computing Steiner minimal trees. SIAM Journal of Applied Mathematics32, 4, 835-859. · Zbl 0399.05023 |
| [19] | Garey, M., Johnson, D., 1979. Computers and Intractability: A Guide to the Theory of NP‐Completeness. W.H. Freeman and Company, San Francisco, CA. · Zbl 0411.68039 |
| [20] | Gilbert, E.N., Pollak, H.O., 1968. Steiner minimal trees. SIAM Journal on Applied Mathematics16, 1, 1-29. · Zbl 0159.22001 |
| [21] | Laarhoven, J.W.V., Anstreicher, K.M., 2013. Geometric conditions for Euclidean Steiner trees in \(\mathbb{R}^d\). Computational Geometry46, 520-531. · Zbl 1277.65014 |
| [22] | Lorenzen, S.S., Winter, P., 2016. Steiner tree heuristic in the Euclidean d‐space using bottleneck distances. In Goldberg, A.V. (ed.), Kulikov, A.S. (ed.) (eds), Experimental Algorithms SEA 2016, Lecture Notes in Computer Science, Vol. 9685. Springer, Cham, pp. 217-230. |
| [23] | Maculan, N., Michelon, P., Xavier, A.E., 2000. The Euclidean Steiner tree problem in \(\mathbb{R}^n:\) a mathematical programming formulation. Annals of Operations Research96, 209-220. · Zbl 0966.90064 |
| [24] | Montenegro, F., Maculan, N., Plateau, G., Boucher, P., 2002. New heuristics for the Euclidean Steiner problem in \(\mathbb{R}^n\). In Ribeiro, C.C. (ed.), Hansen, P. (ed.) (eds), Essays and Surveys in Metaheuristics, Springer US, Boston, MA, pp. 509-524. · Zbl 1006.90072 |
| [25] | Montenegro, F., Torreão, J.R.A., Maculan, N., 2003. Microcanonical optimization for the Euclidean Steiner problem in \(\mathbb{R}^n\) with application to phylogenetic inference. Physical Review E68, 056702. |
| [26] | Ouzia, H., Maculan, N., 2021. Mixed integer nonlinear optimization models for the Euclidean Steiner tree problem in R^d. Journal of Global Optimization83, 119-136. · Zbl 1491.90175 |
| [27] | Pinto, R.V., Maculan, N., 2022. A new heuristic for the Euclidean Steiner tree problem in \(\mathbb{R}^n\). TOP. https://doi.org/10.1007/s11750‐022‐00642‐4. · Zbl 1527.90242 · doi:10.1007/s11750‐022‐00642‐4 |
| [28] | Ribeiro, C., Hansen, P., 2002. Essays and Surveys in Meta‐heuristics. Springer, New York, NY. |
| [29] | Rubinstein, J.H., Thomas, D.A., Wormald, N.C., 1997. Steiner trees for terminals constrained to curves. SIAM Journal on Discrete Mathematics10, 1-17. · Zbl 0869.05023 |
| [30] | Smith, J.M., Jang, Y., Kim, M.K., 2007. Steiner minimal trees, twist angles, and the protein folding problem. Proteins: Structures, Functions, and Bioinformatics66, 4, 889-902. |
| [31] | Smith, W.D., 1992. How to find Steiner minimal trees in Euclidean d‐space. Algorithmica7, 2‐3, 137-177. · Zbl 0751.05028 |
| [32] | Stanton, C., Smith, J.M., 2004. Steiner trees and 3‐d macromolecular conformation. Informs Journal on Computing16, 470-485. · Zbl 1239.92038 |
| [33] | Warme, D.M., Winter, P., Zachariasen, M., 1999. Exact solutions to large‐scale plane Steiner tree problems. In Proceedings of the tenth annual ACM‐SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, pp. 979-980. · Zbl 0929.68094 |
| [34] | Warme, D.M., Winter, P., Zachariasen, M., 2000. Exact algorithms for plane Steiner tree problems: A computational study. In Advance in Steiner Trees, Kluwer Academic Publishers, Netherlands, pp. 81-116. · Zbl 0968.90067 |
| [35] | Whittle, D., Brazil, M., Grossman, P.A., Rubinstein, J.H., Thomas, D.A., 2020. Solving the prize‐collecting Euclidean Steiner tree problem. International Transactions in Operational Research29, 3, 1479-1501. · Zbl 07771166 |
| [36] | Wright, R.A., Richmond, B., Odlyzko, A., McKay, B., 1986. Constant time generation of free trees. SIAM Journal on Computing15, 2, 540-548. · Zbl 0616.68063 |
| [37] | Zachariasen, M., 1998. Large Euclidean Steiner minimum trees in an Hour. Ph.D. thesis, University of Copenhagen. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
