文件列表:

lp_solve_2.3\read.c (17331, 1998-12-11)
lp_solve_2.3\read.h (301, 1998-02-03)
config.log (2257, 2003-10-23)
bb.h (14249, 2001-03-01)
bbsubs.h (1095, 2001-03-01)
bsd.h (1305, 2001-03-01)
btsearch.h (729, 2001-03-01)
config.h (2380, 2003-10-23)
constrnt.h (5084, 2001-03-01)
cra.h (602, 2001-03-01)
cutset.h (1811, 2001-03-01)
lp_solve_2.3\debug.h (199, 1998-02-03)
dsuf.h (1143, 2001-03-01)
efst.h (5005, 2001-03-01)
efuncs.h (11821, 2001-03-01)
egmp.h (1107, 2001-03-01)
emptyr.h (1009, 2001-02-12)
flow.h (2389, 2001-03-01)
genps.h (1655, 2001-03-01)
lp_solve_2.3\hash.h (552, 1998-09-22)
lp_solve_2.3\lpglob.h (1034, 1998-02-03)
lp_solve_2.3\lpkit.h (17788, 1999-01-13)
p1io.h (1949, 2001-03-01)
lp_solve_2.3\patchlevel.h (25, 1998-02-03)
rfst.h (7790, 2001-03-01)
sec_comp.h (3289, 2001-03-01)
sec_heur.h (1995, 2001-03-01)
sec2.h (902, 2001-03-01)
steiner.h (8550, 2001-03-01)
triangle.h (21607, 1998-12-12)
ub.h (1380, 2001-03-01)
bb.c (72762, 2001-03-14)
bbmain.c (11854, 2001-03-01)
bbsubs.c (15273, 2001-03-02)
bmst.c (4186, 2001-03-01)
bsd.c (7336, 2001-03-01)
btsearch.c (16060, 2001-03-01)
... ...

======================================================================== 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: David.Warme@Emergent-IT.com Phone: 703-***5-8441 Fax: 703-***1-7172 Pawel Winter Department of Computer Science (DIKU), University of Copenhagen Universitetsparken 1, DK-2100 Copenhagen East, Denmark E-mail: pawel@diku.dk Phone: +45 35 32 14 00 Fax: +45 35 32 14 01 Martin Zachariasen Department of Computer Science (DIKU), University of Copenhagen Universitetsparken 1, DK-2100 Copenhagen East, Denmark E-mail: martinz@diku.dk Phone: +45 35 32 14 00 Fax: +45 35 32 14 01 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 1***5. 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 19***, 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, 19***. 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 ***-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. @RC Experimental output from -R switch. @UO @UN This pair of messages is emitted every time the upper 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. prunefst - Reduce the set of FSTs generated by "rfst" or "efst" while still retaining at least one optimal solution among the remaining set of FSTs. This program can reduce the time to solve the FST concatenation problem considerably, but is only worthwhile for large instances. The following options are permitted: -d txt Description of problem instance. -f E Epsilon multiplication factor for floating point comparisons. Default is 32. -t Print detailed timings to stderr. dumpfst - Dumps information about the FSTs generated by "rfst" and "efst" in a readable form. There are two forms of this command, each producing different types of output. The first form of the command is obtained whenever the -d or -h switches are used. These switches provide summary information ONLY -- FST statistics, and/or a histogram of FST sizes: dumpfst [-d | -h [-a]] rsmt70.ps (cat prelude.ps; rand_points 70 | efst | bb) >esmt70.ps The complete set of FSTs can also be plotted as follows: (cat prelude.ps; rand_points 70 | rfst | plotfst -fgo) >rfsts.ps (cat prelude.ps; rand_points 70 | efst | plotfst -fgo) >efsts.ps A reduced Hanan grid in the OR-Library format (for the rectilinear problem) can be generated as follows: rand_points 70 | rfst | fst2graph By pruning the set of FSTs an even more reduced grid graph can be generated: rand_points 70 | rfst | prunefst | fst2graph An Euclidean Steiner minimal tree for the "berlin52.tsp" instance from TSPLIB can be constructed and displayed as follows (assuming that the file "berlin52.tsp" is present in your GeoSteiner directory): (cat prelude.ps; cat berlin52.tsp | lib_points | efst | bb) | \ ghostview - Overview of the Source Code =========================== The GeoSteiner source code resides entirely in the top-level directory. There is a single subdirectory "lp_solve_2.3" that contains the source code for a *CUSTOMIZED* version of this public-domain LP solver written by Michel Berkelaar and Jeroen Dirks. For a description of the changes we have made to this package, see the file: lp_solve_2.3/README.custom The original unmodified distribution of lp_solve_2.3 can be obtained from: ftp://ftp.es.ele.tue.nl/pub/lp_solve Detailed description of each file in the GeoSteiner distribution: bb.c (Branch-and-cut) All of the gory details of the branch-and-cut algorithm. The various separation procedures are called from this file, but are defined in other files. bb.h (Branch-and-cut) Data structures and function prototypes pertaining to the branch-and-bound / branch-and-cut algorithm. bbmain.c (Main program) The main routine for the "bb" program. bbsubs.c (Branch-and-cut) Low-level subroutines of the branch-and-cut. bbsubs.h (Branch-and-cut) Declarations of low-level branch-and-cut routines. bmst.c (FST generator, miscellaneous utility) Routines to compute the MST of a subset of the terminals using the bottleneck Steiner distance as the metric. bsd.c (FST generator, miscellaneous utility) Routines to compute the bottleneck Steiner distance between two terminals. bsd.h (FST generator, miscellaneous utility) Data structures and function prototypes pertaining to the bottleneck Steiner distance routines. btsearch.c (FST pruning) Routines to perform backtrack search for a solution. Faster than branch-and-cut for small instances. btsearch.h (FST pruning) Declarations for the special backtrack search used by the FST pruning code. config.h (General utility) Created by running the ./configure script. Defines various constants and switches that control the configuration of GeoSteiner 3.1. This file is automatically generated from the template file `config.h.in'. constrnt.c (Branch-and-cut) Routines that maintain the constraint pool and the constraints currently in the LP tableaux. Most of the details of interfacing to a particular LP solver reside in this file. constrnt.h (Branch-and-cut) Data structures and function prototy ... ...

近期下载者：

相关文件：

评论：[我要评论] [举报此文件]

收藏者：