# GeoSteiner

### Software for Computing Steiner Trees

The **GeoSteiner** package solves the following *NP*-hard problems:
- Euclidean Steiner Tree Problem in the Plane
- Rectilinear Steiner Tree Problem in the Plane
- Uniformly Oriented Steiner Tree Problem in the Plane
- Minimum Spanning Tree Problem in Hypergraphs

The code is written in ANSI C and requires no supplementary software or
libraries. The code makes heavy use of linear programming (LP);
the public domain LP-solver
lp_solve
is included (in a significantly modified form).
However, the package also supports CPLEX,
a proprietary product of the ILOG division of
IBM
Inc., which is one of the fastest and most robust LP-solver available.
Would you like to see a *large* Steiner tree?
Here is the optimal solution for
the 10000 point Euclidean instance in the
OR-Library
.

### Authors

- David Warme,
Group W, Inc., Virginia, USA
- Pawel Winter,
University of Copenhagen, Denmark
- Martin Zachariasen,
University of the Faroe Islands, Faroe Islands

### Download

GeoSteiner 5.3
Unpack the downloaded (gzip'ed tar) file by using the command

gtar xzvf geosteiner-5.3.tar.gz

or by using the sequence of commands
gunzip geosteiner-5.3.tar.gz
tar xvf geosteiner-5.3.tar

Please read the
LICENSE,
README and
INSTALL files carefully
(in the given order).
Manual for latest version:
geosteiner-5.3-manual.pdf

Previous versions:
GeoSteiner 5.2
GeoSteiner 5.1
GeoSteiner 5.0.1
GeoSteiner 5.0
(GeoSteiner 4.0 was a commercial product.)
GeoSteiner 3.1
GeoSteiner 3.0

Steiner tree problem instances:
Problem Instances.

### Relevant Publications

Warme, D.M.
*Spanning Trees in Hypergraphs with Applications to Steiner Trees*

Ph.D. Thesis, Computer Science Dept., The University of Virginia, 1998.

Winter, P. and Zachariasen, M.
*Euclidean Steiner Minimum Trees: An Improved Exact Algorithm*

*Networks 30, 149-166, 1997*.

Zachariasen, M.
*Rectilinear Full Steiner Tree Generation*

*Networks* 33, 125-143, 1999.

Warme, D. M., Winter, P. and Zachariasen, M.
*Exact Algorithms for Plane Steiner Tree Problems: A Computational Study*

In D.Z. Du, J.M. Smith and J.H. Rubinstein (Eds.)
*Advances in Steiner Trees*, pages 81-116,

Kluwer Academic Publishers, 2000.

Juhl, D., Warme, D. M., Winter, P. and Zachariasen, M.

*The GeoSteiner Software Package for Computing Steiner Trees in the
Plane: An Updated Computational Study*

*Mathematical Programming Computation*, 10, 487-532, 2018.

Brazil, M. and Zachariasen, M.
*Optimal Interconnection Trees in the Plane:
Theory, Algorithms and Applications*

Springer, 2015.

http://www.geosteiner.com/
webmaster@geosteiner.com,
June 10, 2023