The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study. (English) Zbl 1411.90225

Juhl, Daniel; Warme, David M.; Winter, Pawel; Zachariasen, Martin

Math. Program. Comput. 10, No. 4, 487-532 (2018).

Summary: The GeoSteiner software package has for about 20 years been the fastest (publicly available) program for computing exact solutions to Steiner tree problems in the plane. The computational study by Warme, Winter and Zachariasen, published in 2000, documented the performance of the GeoSteiner approach – allowing the exact solution of Steiner tree problems with more than a thousand terminals. Since then, a number of algorithmic enhancements have improved the performance of the software package significantly. We describe these (previously unpublished) enhancements, and present a new computational study wherein we run the current code on the largest problem instances from the 2000-study, and on a number of larger problem instances. The computational study is performed using the commercial GeoSteiner 4.0 code base, and the performance is compared to the publicly available GeoSteiner 3.1 code base as well as the code base from the 2000-study. The software studied in the paper is being released as GeoSteiner 5.0 under an open source license.

MSC:

90C10	Integer programming
90C27	Combinatorial optimization
05C05	Trees
05C65	Hypergraphs
51N20	Euclidean analytic geometry
68W35	Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.)

Keywords:

euclidean Steiner tree problem; rectilinear Steiner tree problem; fixed orientation Steiner tree problem; exact algorithm; computational study

Software:

CPLEX; DIMACS; GeoSteiner; LEDA; OR-Library

References:

[1]	Althaus, E.: Berechnung optimaler Steinerbäume in der Ebene. Master’s thesis, Max-Planck-Institut für Informatik in Saarbrücken, Universität des Saarlandes (1998)
[2]	Applegate, David; Bixby, Robert; Chvátal, Vašek; Cook, William, TSP Cuts Which Do Not Conform to the Template Paradigm, 261-303, (2001), Berlin, Heidelberg · Zbl 1052.90060
[3]	Beasley, JE, OR-library: distributing test problems by electronic mail, J. Oper. Res. Soc., 41, 1069-1072, (1990)
[4]	Brazil, M.; Thomas, DA; Weng, JF; Zachariasen, M., Canonical forms and algorithms for Steiner trees in uniform orientation metrics, Algorithmica, 44, 281-300, (2006) · Zbl 1095.68074
[5]	Brazil, M.; Zachariasen, M., Steiner trees for fixed orientation metrics, J. Glob. Optim., 43, 141-169, (2009) · Zbl 1169.90467
[6]	Brazil, M.; Zachariasen, M., The uniform orientation Steiner tree problem is NP-hard, Int. J. Comput. Geom., 24, 87-105, (2014) · Zbl 1319.68227
[7]	Brazil, M., Zachariasen, M.: Optimal Interconnection Trees in the Plane: Theory, Algorithms and Applications. Springer, Berlin (2015) · Zbl 1319.05044
[8]	Fößmeier, U.; Kaufmann, M.; Burkard, R. (ed.); Woeginger, G. (ed.), Solving rectilinear Steiner tree problems exactly in theory and practice, No. 1284, 171-185, (1997), Berlin
[9]	Garey, MR; Graham, RL; Johnson, DS, The complexity of computing Steiner minimal trees, SIAM J. Appl. Math., 32, 835-859, (1977) · Zbl 0399.05023
[10]	Garey, MR; Johnson, DS, The rectilinear Steiner tree problem is NP-complete, SIAM J. Appl. Math., 32, 826-834, (1977) · Zbl 0396.05009
[11]	Gilbert, EN; Pollak, HO, Steiner minimal trees, SIAM J. Appl. Math., 16, 1-29, (1968) · Zbl 0159.22001
[12]	Hanan, M., On Steiner’s problem with rectilinear distance, SIAM J. Appl. Math., 14, 255-265, (1966) · Zbl 0151.33205
[13]	Huang, T.; Young, EFY, Obsteiner: an exact algorithm for the construction of rectilinear Steiner minimum trees in the presence of complex rectilinear obstacles, IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 32, 882-893, (2013)
[14]	Hwang, FK; Richards, DS, Steiner tree problems, Networks, 22, 55-89, (1992) · Zbl 0749.90082
[15]	Hwang, F.K., Richards, D.S., Winter, P.: The Steiner Tree Problem. Annals of Discrete Mathematics, vol. 53. Elsevier, Amsterdam (1992)
[16]	Kahng, A.B., Mandoiu, I.I., Zelikovsky, A.Z.: Highly scalable algorithms for rectilinear and octilinear Steiner trees. In: Proceedings of the Asia and South Pacific Design Automation Conference, New York, pp. 827-833 (2003)
[17]	Mehlhorn, K., Näher, S.: LEDA: a library of efficient data types and algorithms. In: Proceedings of the Seventeenth International Colloquim on Automata, Languages and Programming, pp. 1-5 (1990)
[18]	Mehlhorn, K., Näher, S.: LEDA—A Platform for Combinatorial and Geometric Computing. Max-Planck-Institut für Informatik, Saarbrücken http://www.mpi-sb.mpg.de/LEDA/leda.html (1996)
[19]	Mehlhorn, K., Näher, S.: LEDA—A Platform for Combinatorial and Geometric Computing. Max-Planck-Institut für Informatik, Saarbrücken (1996). http://www.mpi-sb.mpg.de/LEDA/leda.html
[20]	Polzin, T.; Daneshmand, SV, On Steiner trees and minimum spanning trees in hypergraphs, Oper. Res. Lett., 31, 12-20, (2003) · Zbl 1013.90131
[21]	Salowe, JS; Warme, DM, Thirty-five-point rectilinear Steiner minimal trees in a day, Networks, 25, 69-87, (1995) · Zbl 0820.90120
[22]	Smith, JM; Lee, DT; Liebman, JS, An \(O(n \log n)\) heuristic for Steiner minimal tree problems on the Euclidean metric, Networks, 11, 23-29, (1981) · Zbl 0459.68032
[23]	Thomborson, CD; Alpern, B.; Carter, L.; Dean, N. (ed.); Shannon, GE (ed.), Rectilinear Steiner tree minimization on a workstation, No. 15, 119-136, (1994), Providence · Zbl 0814.68054
[24]	Warme, D. M.: Spanning Trees in Hypergraphs with Applications to Steiner Trees. PhD thesis, University of Virginia, (1998) · Zbl 0903.90175
[25]	Warme, DM; Winter, P.; Zachariasen, M.; Du, D-Z (ed.); Smith, JM (ed.); Rubinstein, JH (ed.), Exact algorithms for plane Steiner tree problems: a computational study, 81-116, (2000), Boston · Zbl 0968.90067
[26]	Widmayer, P.; Wu, YF; Wong, CK, On some distance problems in fixed orientations, SIAM J. Comput., 16, 728-746, (1987) · Zbl 0625.68049
[27]	Winter, P., An algorithm for the Steiner problem in the Euclidean plane, Networks, 15, 323-345, (1985) · Zbl 0586.90087
[28]	Winter, P.; Zachariasen, M., Euclidean Steiner minimum trees: an improved exact algorithm, Networks, 30, 149-166, (1997) · Zbl 0893.90170
[29]	Zachariasen, M., Rectilinear full Steiner tree generation, Networks, 33, 125-143, (1999) · Zbl 0918.90136
[30]	Zachariasen, M.; Rohe, A., Rectilinear group Steiner trees and applications in VLSI design, Math. Program., 94, 407-433, (2003) · Zbl 1030.90132
[31]	Zachariasen, M.; Winter, P., Concatenation-based greedy heuristics for the Euclidean Steiner tree problem, Algorithmica, 25, 418-437, (1999) · Zbl 0944.68146
[32]	Zachariasen, Martin; Winter, Pawel, Obstacle-Avoiding Euclidean Steiner Trees in the Plane: An Exact Algorithm, 286-299, (1999), Berlin, Heidelberg