TY - JOUR

T1 - The GeoSteiner software package for computing Steiner trees in the plane

T2 - an updated computational study

AU - Juhl, Daniel

AU - Warme, David M.

AU - Winter, Pawel

AU - Zachariasen, Martin

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

KW - Computational study

KW - Euclidean Steiner tree problem

KW - Exact algorithm

KW - Fixed orientation Steiner tree problem

KW - Rectilinear Steiner tree problem

U2 - 10.1007/s12532-018-0135-8

DO - 10.1007/s12532-018-0135-8

M3 - Journal article

AN - SCOPUS:85054649553

VL - 10

SP - 487

EP - 532

JO - Mathematical Programming Computation

JF - Mathematical Programming Computation

SN - 1867-2949

IS - 4

ER -