changelog

生成直角Steiner树的程序包

	of references all over the place!)

	* The reductions in sec_comp.c were not being done as completely
	as possible.  Whenever uncongested vertices are removed from a
	component, we now force the CC and BCC tests to be run again.
	This caused a noticeable improvement in performance, presumeably
	due to (a) smaller problems to separate, and (b) improved
	constraint strengthening.

	* Completely replaced the merge_chains() routine (in sec_comp.c)
	with a much more sophisticated algorithm.  The old version was
	very slow, and quite closely tied to the old "tmasks" array which
	is now obsolete.  The old algorithm did not translate too well to
	the framework required by the new "rverts" array.  The new
	algorithm runs in a number of distinct O(n) passes -- each pass
	successively "homes in" more closely on those vertices and edges
	that can be in a chain.  Finally it uses a disjoint-set union-find
	to identify which chain each edge belongs to.

	* Modified delete_vertex_from_component() to permit a negative
	vertex number (sec_comp.c).  In this case, the component is just
	re-simplified after whatever changes the caller may have made to
	it.

	* In check_component_subtour() (in sec_comp.c), added experimental
	code for cleaning up constraints.  This code is an alternate
	method (currently disabled) for computing the congested components
	of the subtour that does not start over with the subgraph of the
	original problem induced by the subtour vertices.  This method is
	currently disabled because it probably misses some potential
	reductions that are caught if you start all over.  Also added some
	debugging code (currently disabled) to plot the LP solution,
	the "unstrengthened" constraint found by the flow separator and
	the strengthened subtour violations -- but only if the reductions
	split the violation into at least 3 distinct subtours.  Now using
	new add_component_subtour() routine to encapsulate component ==>
	real translation, duplicate and violation testing.

	* Made check_unique_subtour() non-static (sec_heur.c).  Changed
	calling convention of enumerate_all_subtours() and
	find_small_subtours() to take a "struct bbinfo *" instead of a
	"struct bbnode *".

	* Created completely new versions of enumerate_all_subtours() and
	find_small_subtours() (in sec_heur.c).  The new versions are used
	by default (#ifndef OLD_ENUMERATION), and use the new
	recurse_enum() routine which is faster because it does not
	recompute the constraint's LHS and RHS at each recursion level,
	but updates these quantities inductively while recursing.  Added
	the "struct bbinfo *" to the old recursive enumeration routine
	(enumerate_subtours(), probably now obsolete).  In
	find_small_subtours(), removed specially intense processing of
	the root node and the first 4 "Xi = 0" branches -- we now use the
	same intensity of enumeration at every node.

	* Modified find_integer_cycles() and cwalk() (in sec_heur.c) to
	eliminate near-infinite loops caused by attempting to find all
	cycles in highly cyclic structure.  We now count EVERY cycle
	discovered, whether previously seen or not -- and we no longer
	reset the cycle counter at the beginning of each connected
	component.  Whenever the cycle count exceeds the limit, we bail --
	even skipping the unprocessed connected components.

	* Fixed a bug in sll.c wherein the heuristic gave an infinite
	length in the case where all input points were colinear.

	* Modified sll.c to use efuncs.h, translate mean of point set to
	the origin, use BSD information (if available), and to use dist_t
	instead of double.  Added pre-declarations of all static
	functions.

	* Added new file sortints.c containing a new routine sort_ints()
	that efficiently sorts an array of integers.  It does a single
	bubble-sort scan.  If sufficiently little remains to be sorted, we
	continue with bubble sort, otherwise we switch to heapsort.
	Replaced all local copies with calls to this more intelligent
	version.

	* Patched triangle.c so that malloc() really invokes our own new()
	routine.  This lets us handle malloc(0) properly, instead of
	barfing with an "out of memory" error.

	* Removed the obsolete compute_fstmst_index() routine, and added
	the new "ubinfo" structure and the startup_heuristic_upper_bound()
	and shutdown_heuristic_upper_bound() routines (in ub.c and ub.h).
	These provide better encapsulation of the upper bound heuristic,
	and make it easier to add more global state to it.

	* Major improvements to the upper bound heuristic (in ub.c):
	(1) It now repeats the computation using (up to) TWO different FST
	rankings (FST/MST ratio, and len(e)/(|e|-1) ratio) -- the ranking
	is used to break ties when two edges have the same LP weight.
	(2) For each ranking, it performs greedy tree construction and
	then repeats the greedy tree construction using a new edge
	sequence wherein all MST edges are placed last.
	(3) Each greedy tree construction starts with a single Kruskal run
	to construct an initial tree.  After that, one of a set of
	diversification procedures are applied: randomized rounding,
	greedy local search, round robin, very greedy, and less greedy
	(currently, the greedy local search seems to be the best).  Each
	diversification procedure performs a sequence of K ~ log2(nedges)
	additional Kruskal runs, each run chooses an edge to force into
	the solution (by placing it first in the sorted list).  The
	currently used greedy local search chooses the first edge in the
	list that was NOT used by the previous Kruskal run.  Whenever an
	improvement is used, the list of edges to force is replaced with
	the current solution plus all 2-edges (thereby causing the search
	to focus on using these edges).  If the current heuristic solution
	is very close to the best known solution, then the search is
	intensified by increasing the iteration limit K and restarting the
	scan of edges at the beginning.  Only one such restart per run of
	the greedy local search procedure is permitted.  The other
	diversification procedures are currently disabled.  Read the code
	for details on these.

	* Modified all main() routines to do "exit (0)" instead of "return
	(0)", since the latter does not work correctly on certain broken
	operating systems.

	* Added new lib_points program to extract point sets from either
	OR-library or TSPLIB formatted files.

	* Added new tracef() routine and tracef_control structure to
	utils.c.  tracef() is now used exclusively instead of printf()
	throughout the entire call tree reached by branch_and_cut(),
	including the print_mask() routine (also in utils.c).  Added new
	gst_strdup() routine, which does a strlen(), new() and strcpy().
	This routine is our own portable and dependable version of
	strdup().  Added the new store_double() routine that let's us
	force double precision when the compiler/processor are giving us
	too much precision.  Also added the configuration-dependent
	routines for saving and restoring the floating point precision and
	forcing it to double.  (utils.c)

	* Fixed delete_row_set() (in lp_solve_2.3/lpkit.c) to modify the
	basis more carefully when deleting rows.

	* Modified isvalid() (in lp_solve_2.3/solve.c) to not complain
	about empty columns that are fixed.

	* Fixed minoriteration() (in lp_solve_2.3/solve.c) to not overflow
	the eta allocation by 1, when exactly full on last item.

	* Fixed disabled debugging code dualloop() (in
	lp_solve_2.3/solve.c) to use lp->sum instead of defunc global
	"Sum".

	* Fixed dualloop() (in lp_solve_2.3/solve.c) to set Extrad = 0
	when switching to the primal.

	* Fixed try_branch() (in lp_solve_2.3/solve.c) to also return the
	special "infeasible value" on cutoffs as well as infeasibility.

	* Added new PT procedure to prelude.ps for use by new
	plot_subtour() routine.

	* Updated the INSTALL, LICENSE and README files for version 3.1.

Mon Jan 11 07:46:39 1999  David Warme  <[e-mail]>

	* Geosteiner version 3.0.  This is the combined efforts of David
	Warme, Pawel Winter and Martin Zachariasen.  It is also the first
	release of this code to the general research community.

	* Obsoleted the following programs: prep, old_bs and rstprune.
	prep was the Salowe-Warme rectilinear FST generator, old_bs was
	the old backtrack-search FST concatenator, and rstprune was a
	stand-alone rectilinear FST pruning program.  The following files
	died as a result: art.c coarse.c compat.c decomp.c fine.c
	gensets.c old_bs.c prep.c prune.c rstprune.c search.c.

	* Introduced Warme's latest implementation of Zachariasen's
	rectilinear FST generator.  This includes the following new files:
	rfst.c rfst.h emptyr.c emptyr.h.  This new front-end is a
	stand-alone command called "rfst".

	* Got rid of most of the metric-specific stuff in steiner.h by
	moving it into rfst.h.  All declarations specific to the
	Salowe-Warme RFST generator are now gone.  Eliminated the
	full_set.style field.

	* Completely eliminated all compile-time limits on problem size!
	For example, the "struct pset" now contains an array of only one
	point, so all instances of this structure are dynamically
	allocated to be the correct size.  The constants MAX_TERMINALS,
	MAX_STEINERS, MAX_POINTS, and N_TERM_BMAP are now all dead!  The
	pnum_t type is now int instead of int16s for greater range.  Made
	the full_set.tree_num field be an int instead of inst16u for
	greater range.

	* While incorporating the new RFST generator, the disjoint-set
	union-find code was split off as the new files dsuf.c and dsuf.h.
	In addition, the rectilinear MST code was renamed from mst.c to
	rmst.c, to make room for the arrival of Euclidean MST code.

	* Completely replaced the bottleneck Steiner distance (BSD) code
	in bsd.c.  Introduced the new file bsd.h to define its interface.
	The new interface is much more general and can work with any
	metric, since you give it an MST in edge-list form.  The new
	interface also permits multiple internal representations for
	storing the BSD matrix, which gets quite huge on large problems
	since it grows O(n^2) with the number of terminals.  Currently we
	only implement one representation -- a lower-triangular matrix of
	MST edge numbers, requiring N^2 - N bytes of storage.  In the
	future we may implement other schemes, including a row cache
	scheme and the dynamic trees method.

	* Completely renamed and redefined the routines to compute MST's
	using the bottleneck Steiner distance (in bmst.c).  They now use
	"bmst" in the name instead of "bottleneck_mst" and they use the
	new BSD data structures for generality.

	* Added the new dumpfst utility (file dumpfst.c).  This makes it
	much easier to compare the outputs of different FST generators.

	* Obsoleted the -a, -r and -s options of the fsplot command.
	These controlled Print_Articulation_Components, Print_Relief_Map,
	and Print_Split_Full_Sets, respectively.  Also obsoleted the file
	relief.c that implemented the "relief map" plots.  "relief.c" has
	not been useful for a long time, and its reliance on the
	particular RFST encoding in the Salowe-Warme algorithm made it too
	difficult to maintain.  The other options are just plain
	obsolete.  Now using "FST" instead of "Full Set" in the titles of
	the plots generated.

	* Modified kr.c to handle dynamically sized struct pset's, and
	eliminate the compile-time problem size limits.

	* Modified redg.c to read an FST data file rather than a point
	set.  This is now possible because of our requirement that the FST
	graph for rectilinear FST's always represent a top-most and
	left-most Hwang topology.  We can therefore just use the FST graph
	to draw each FST onto the grid.  This gets rid of the -i and -o
	command line switches for this program.

	* Renamed the output.c file to be genps.c, which is more
	descriptive of its function -- generating Postscript output.  The
	definition of its interfaces were split off from steiner.h into
	the new file genps.h.

	* Integrated Martin Zachariasen's latest implementation of the
	Winter-Zachariasen Euclidean FST generator.  Martin re-implemented
	this in plain C (from C++ with LEDA) using my implementation of
	his RFST generator as a template.  Martin also implemented a
	simple version of the rectangle idea of Ernst Althaus, which
	improves the performance manyfold on large uniformly distributed
	instances.  The new files introduced are efst.c efst.h emst.c
	sll.c triangle.c triangle.h.  Our hats off to Jonathan Shewchuk
	for making his 	'triangle' code available for use in applications
	like ours!

	* Obsoleted the old submodular SEC separator, sec.c and sec.h.
	The new flow formulation renders the old submodular code to the
	junkheap of historical interest.

	* Obsoleted the clique generator, clique.c and clique.h.  Oddly
	enough, clique constraints only seemed to slow things down!