readme

生成直角Steiner树的程序包

========================================================================
                            GeoSteiner 3.1

	Copyright (c) 1999, 2001 by David M. Warme, Pawel Winter,
				    & Martin Zachariasen.

========================================================================

This directory contains GeoSteiner version 3.1, which solves the
following NP-hard problems:

	- Euclidean Steiner minimal tree
	- Rectilinear Steiner minimal tree
	- Minimum spanning tree in hypergraphs

Geosteiner is the joint work of:

	- David Warme		Emergent Information Technologies, Inc.
	- Pawel Winter		University of Copenhagen
	- Martin Zachariasen	University of Copenhagen

The latest news regarding the GeoSteiner package can be found at:

	http://www.diku.dk/geosteiner/

Bug reports, suggested improvements and constructive comments are
greatly appreciated.


Author's information
====================

David Warme
Emergent Information Technologies, Inc.
2600 Park Tower Drive, Suite 900
Vienna, Virginia  22180  USA
E-mail:	[e-mail]
Phone:	[phone]
Fax:	[phone]

Pawel Winter
Department of Computer Science (DIKU), University of Copenhagen
Universitetsparken 1, DK-2100 Copenhagen East, Denmark
E-mail:	[e-mail]
Phone:	[phone]
Fax:	[phone]

Martin Zachariasen
Department of Computer Science (DIKU), University of Copenhagen
Universitetsparken 1, DK-2100 Copenhagen East, Denmark
E-mail:	[e-mail]
Phone:	[phone]
Fax:	[phone]


Historic Note
=============

To the best knowledge of the authors, this code represents the
computational state of the art as of February 2001.  It solves problems
more than an order of magnitude larger than any other software of which
we are aware.

The "GeoSteiner" name was coined (and is therefore "owned") by Pawel
Winter, whose seminal program GEOSTEINER started it all back in 1985.
In 1996 Winter and Zachariasen published an improved algorithm called
"GeoSteiner96".

On the other hand, Warme's first Steiner tree code was the Salowe-Warme
algorithm in 1993, which used backtrack search to concatenate
rectilinear FSTs.  In 1998, Warme's PhD dissertation described a new
branch-and-cut code for finding minimum spanning trees in arbitrary
hypergraphs -- which was applied to the FST concatenation problem for
both rectilinear and Euclidean FSTs.

The first distribution of the combined code therefore represented the
"third version" of each group's code, and it was thus named
GeoSteiner version 3.0.  This and subsequent versions continue
that naming convention.


References
==========

D. M. Warme.  Spanning Trees in Hypergraphs with Applications to Steiner
Trees.  Ph.D. Thesis, Computer Science Dept., The University of
Virginia, 1998.

P. Winter and M. Zachariasen.  Euclidean Steiner Minimum Trees: An
Improved Exact Algorithm.  Networks, 30:149--166, 1997.

M. Zachariasen.  Rectilinear Full Steiner Tree Generation.  Networks 33,
125-143, 1999.


Building and Installing GeoSteiner
==================================

GeoSteiner comes with a "GNU style" configure script.  For those of
you who are especially impatient, type the following:

	$ ./configure
	$ make

For complete instructions on building and installing Geosteiner, see
the INSTALL file.


Program Descriptions
====================

GeoSteiner consists of the following programs:

	rand_points
	lib_points
	efst
	rfst
	bb
	dumpfst
	plotfst
	prunefst
	fst2graph
	kr

and a single data file:

	prelude.ps


rand_points
	- Generates random point sets.  The coordinates of the points
	  are integers chosen (more or less) uniformly from the range
	  0 <= x,y < 10000.  The following options are permitted:

		-e	Display the initial seed used on stderr.

		-f	Display the final seed state (to stderr, unless
			-o is specified, in which case to stdout).

		-o	Display the initial seed to stdout.

		-n	Use the "new" random number generator that uses
			a 64-bit shift register with XOR feedback.
			Without this option a generator is used that
			functions identically to the original PDP-11
			Unix  rand(3) routine (with all of its ugly
			warts intact).

		-s N	Set the initial seed to be N.

		-r	Randomize.  Use an initial seed chosen from the
			current date and time.

lib_points
	- Reads a point set in either TSPLIB or OR-Library format from
	  stdin and converts the input to clean point coordinates as
	  required by "efst" or "rfst".  The program automatically
	  determines the input file type.  The program has one
	  optional parameter (which has value 1 by default) that
	  specifies which instance number should be extracted from an
	  OR-Library file.

efst	- Reads a point set from stdin, and generates a set of Euclidean
	  FSTs that contains at least one Euclidean Steiner minimal tree.
	  The output on stdout is ASCII encoded, but not particularly
	  meaningful except as input to the "bb", "dumpfst",
	  "plotfst", "prunefst" and "fst2graph" programs.
	  The following options are permitted:

		-d txt	Description of problem instance.
		-e K	Sets the initial number of equilateral points
			per terminal to K.  The default is 100.  The
			equilateral points are automatically reallocated
			as needed, but some very large point sets may run
			out of memory unless the initial allocation is
			sufficient.
		-f E	Epsilon multiplication factor for floating
			point comparisons.  Default is 32.
		-g	Use greedy heuristic instead of Smith-Lee-Liebman
			(more time consuming but generates fewer eq-points).
		-k K	Generate only FSTs having at most K terminals.
			This can save considerable time but can also
			eliminate FSTs that must be in the optimal
			Steiner tree (i.e., solutions can become
			suboptimal).
		-m M    Use multiple precision.  Larger M use it more.
			Default is M=0 which disables multiple precision.
			The use of this option requires that the GNU
			Multi-Precision arithmetic library (GMP) has
			been linked with the program (see the INSTALL
			file for more details).
		-t	Print detailed timings to stderr.
		-v N	Generate the output in version N of the FST
			data format.  Supported versions are 0, 2 and 3.
			Version 3 is the default.

rfst	- Reads a point set from stdin, and generates a set of rectilinear
	  FSTs that contains at least one rectilinear Steiner minimal tree.
	  The output on stdout is ASCII encoded, but not particularly
	  meaningful except as input to the "bb", "dumpfst",
	  "plotfst", "prunefst" and "fst2graph" programs.
	  The following options are permitted:

		-d txt	Description of problem instance.
		-k K	Generate only FSTs having at most K terminals.
			This can save time but can also	eliminate FSTs
			that must be in the optimal Steiner tree
			(i.e., solutions can become suboptimal).
		-t	Print detailed timings to stderr.
		-v N	Generate the output in version N of the FST
			data format.  Supported versions are 0, 2 and 3.
			Version 3 is the default.

bb	- The FST concatenation algorithm using branch-and-cut to solve
	  an IP formulation of the problem.  The FST data is read from
	  stdin and a plot of the solution is produced on stdout in an
	  "incomplete" postscript form.  A printable postscript file can
	  be obtained by PREPENDING the file "prelude.ps" to the program
	  output.  Various trace messages appear in the output as
	  postscript comments.  (The name "bb" is for branch-and-bound
	  -- note that the name "bc" is already taken on Unix.)  The
	  following options are permitted:

		-2	Omit all 2-terminal SEC's from the initial
			constraint pool.
		-b	Disable "strong branching", which chooses
			branching variables very carefully.
		-B N	Set branch variable selection policy.
		         N=0: naive max of mins,
			 N=1: smarter lexicographic max of mins (default),
			 N=2: product of improvements.
		-l T	Sets a CPU time limit of T.
		-r	Plot the optimal LP relaxation solution for the
			root node, but only if it is fractional.
		-R	When optimal root LP relaxation is obtained,
			determine for each LP iteration the number of
			final constraints whose first violation occurred
			during that iteration.
		-T N	Search N times more thoroughly for strong
			branching variables.
		-u B	Specify B to be the initial upper bound assumed
			by the branch-and-bound.
		-z N	Sets the target number of pool non-zeros to N.

	  When configured to use CPLEX, the following additional
	  option is permitted:

		-a M N	Force CPLEX allocation to be at least M rows
			and N non-zeros.

	  When configured to use lp_solve, the following additional
	  options are permitted:

		-p	Turn on the use of perturbations.  This is the
			method that lp_solve_2.3 uses to deal with
			degenerate problems.

		-s	Turn on the use of problem scaling.  Once again
			a rather crude attempt to address problems that
			are badly behaved numerically.

	  The following "grep-able" items appear in the output within
	  postscript comments, and may be potentially useful:

		@0	The instance description from the FST data
			file.
		@1	Summary statistics:
				- Number of terminals
				- Number of FSTs/hyperedges
				- Number of branch-and-bound nodes
				- Number of LP's solved
				- Phase 1 CPU time (FST generation)
				- Phase 2 CPU time (branch-and-cut)
				- Total CPU time
		@2	LP/IP statistics:
				- Length of optimal Steiner tree
				- Length of LP relaxation at root node
				- Percent of LP/IP "gap"
				- # of LP's solve for root node
				- CPU time for root node
				- Percent reduction of SMT over MST
		@3	Initial constraint pool statistics:
				- Number of rows in pool
				- Number of non-zeros in pool
				- Number of rows in LP tableaux
				- Number of non-zeros in LP tableaux
		@4	Constraint pool statistics for root node:
				- Number of rows in pool
				- Number of non-zeros in pool
				- Number of rows in LP tableaux
				- Number of non-zeros in LP tableaux
		@5	Final constraint pool statistics:
				- Number of rows in pool
				- Number of non-zeros in pool
				- Number of rows in LP tableaux
				- Number of non-zeros in LP tableaux
		@6	Statistics on FSTs occurring in the SMT:
				- Number of FSTs in SMT
				- Average FST size in SMT
				- Maximum FST size in SMT
				- Number of FSTs of size 2 in SMT
				- Number of FSTs of size 3 in SMT
				- Number of FSTs of size 4 in SMT
				- Number of FSTs of size 5 in SMT
				- Number of FSTs of size 6 in SMT
				- Number of FSTs of size 7 in SMT
				- Number of FSTs of size 8 in SMT
				- Number of FSTs of size 9 in SMT
				- Number of FSTs of size 10 in SMT
				- Number of FSTs of size > 10 in SMT
		@C	Coordinates of a Steiner point in the optimal
			solution.  The Steiner points form a
			"certificate" of the optimal solution since the
			optimal solution can be reconstructed by
			computing a minimum spanning tree of the
			original terminals and these Steiner points.
		@D	Deletion of slack rows from LP tableaux.
		@LO
		@LN	This pair of messages is emitted every time the
			lower bound gets tighter.  They contain the CPU
			time and the old/new bound, as well as the
			old/new gap percentages.  These can be plotted
			(i.e., using gnuplot) to graphically show the
			convergence rate of the algorithm.
		@NC	Creation of a new branch-and-bound node:
				- Node number
				- Parent node number
				- Branch variable
				- Branch direction
				- Objective value (the real LP objective
				  is at least this value)
		@PAP	Adding "pending" pool constraints to the LP
			tableaux.
		@PL	State of LP tableaux constraints.
		@PMEM	Constraint pool memory status.  Printed before
			and after each garbage collection, and after
			adding new/initial constraints to the pool.
		@r	Experimental output from -R switch.