changelog

生成直角Steiner树的程序包

Mon Feb 26 09:28:07 2001  David Warme  <[e-mail]>

	* Geosteiner version 3.1.  Significant new features, including
	efficient pruning of FSTs, enhanced numeric stability of the EFST
	generator, and improvements to the branch-and-cut.

	* Critical bug fix in lp_solve_2.3/solve.c: fixed try_branch
	routine, which was still using the obsolete "Rows" global variable
	instead of "lp -> rows" to copy the solution back out to the
	caller.  This could result in premature cutoff and suboptimal
	solutions.

	* Critical bug fix in check_for_better_IFS (in bb.c): verify that
	the solution vector x satisfies all of the 0-1 variable bounds.
	This has always been the case when using CPLEX because the CPLEX
	version of try_branch always completely solves each LP.  The
	lp_solve version of try_branch, however, stops after 50 or so
	pivots leaving us with an x vector that may not even satisfy the
	bound constraints.  check_for_better_IFS was erroneously
	recognizing some of these "infeasible basic solutions" as INTEGER
	FEASIBLE SOLUTIONS.  When it later recomputed the objective
	function, the bounds obtained were incorrect -- even totally
	preposterous.  This could result in suboptimal solutions.

	* Split several new files off from bb.c:  bbmain.c contains the
	"main()" routine for the "bb" program, and all of the command line
	processing stuff.  (This permits the branch-and-cut to be called
	as a subroutine from prunefst.c, which has its own main routine.)
	New files bbsubs.c and bbsubs.h now contain the subroutines for
	handline bbnodes and bbtrees, creating and destroying bbinfo, and
	for starting up and shutting down the LP solver, etc.

	* Fixed numerous memory leaks in bb.c, especially the various
	bbinfo and bbtree data structures.

	* Replaced all calls to "printf" within the branch-and-cut with
	calls to a new "tracef" routine.  The output produced by "tracef"
	can be controlled by options specified in a new "tracef_control"
	structure.  Currently, the only such option is to disable all
	output from tracef.  This is an easy way to muzzle the
	branch-and-cut when you want to call it as a subroutine (e.g.,
	like prunefst.c now does).  The tracef_control structure is
	currently global, a misfeature that should be corrected sometime.

	* Encapsulated all startup and shutdown of the LP solver (i.e.,
	CPLEX in a pair of new routines startup_lp_solver and
	shutdown_lp_solver (in bbsubs.c).

	* Encapsulated the creation of the bbinfo (including constraint
	pool, LP formulation, branch-and-bound tree, and initial root
	node) in a new "create_bbinfo" routine.  This routine returns a
	bbinfo * such that the root node is inactive (in the heap waiting
	to be selected for processing).  The branch_and_cut routine now
	simply takes a single "bbinfo *" argument, which makes it easier
	to call as a subroutine (e.g., from prunefst.c or other
	applications).  We anticipate that in future versions, the caller
	might instruct (via settable parameters) branch_and_cut to return
	early -- before an optimal solution is proven -- and that the
	computation can be continued by calling it again with the same
	argument.  For example, the user might want to suspend the
	computation when a specified gap is achieved, when the optimal
	subtour relaxation is obtained, or when a certain number of
	sufficiently good upper bounds are obtained, etc.  Partitioning
	the problem setup code from the optimization code is a step in
	this direction.

	* Changes to "struct bbnode" (in bb.h): Widened the "var", "dir",
	"depth" and "br1cnt" fields from 16 to 32 bits.  Replaced the
	"xhist" and "xh_index" fields (and their associated
	NUM_X_HISTORIES_PER_NODE equate) with a new "bheur" field that
	holds data used to heuristically prioritize branch variables.
	Added the new "x", and "cpiter" fields so that each node can
	remember its most recent LP solution (and also the version of the
	constraint pool that produced this LP solution).  If a node is
	suspended and later resumed without any new constraints being
	added to the pool, then we can skip re-solving the LP and go
	straight on to the separation algorithms using the saved LP
	solution.

	* Added the new "zlb" field to "struct bbnode".  This array
	records 2 values for each variable Xj:  the highest Xj=0 bound
	seen and the highest Xj=1 bound seen.  For example, if a variable
	Xj is non-basic at its upper bound of 1, then ZLB[j,0] = Z + d[j]
	is a lower bound on the objective if Xj=0 is forced.  (Z is the
	current objective value and d[j] is variable Xj's reduced cost.)
	The "zlb" array accumulates the maximum lower bounds ever seen.
	This improves the effectiveness of reduced cost variable fixing.
	For example, if a certain LP instance results in a very high
	reduced cost, then the lower bound that results is remembered even
	if the bound is not currently high enough to cause the variable to
	be fixed.  The variable may be fixed later on when the upper bound
	improves below the "zlb" value -- even if the current Z+dj value
	is not high enough to justify fixing.  These bounds are also
	useful in choosing branch variables.

	* Moved the next-node policy equates (NN_DEPTH_FIRST and
	NN_BEST_NODE) from bb.c into bb.h.  Obsoleted the "z" and "x"
	fields of the bbinfo.  All code now uses the per-node values
	"bbip -> nodep -> z" and "bbip -> nodep -> x" instead.

	* The bbinfo structure now contains a new "ubip" field instead of
	the old "fstmst_index" field.  This provides better encapsulation
	of the information needed by the upper bound heuristic.

	* Added the "obj_scale" field to the CPLEX version of "struct
	lpmem" (in bb.h) to support scaling of objective coefficients.
	This is to work around unscaled infeasibility errors from CPLEX
	when objective coefficients have large magnitudes.

	* Modified the _MYCPX macros to properly address changes in the
	CPLEX API beginning with CPLEX version 5.0.  Starting with 5.0,
	the following routines changed names:  CPXloadbase ==>
	CPXcopybase, CPXoptimize ==> CPXprimopt, INFBOUND ==>
	CPX_INFBOUND.

	* Added "-a N M" switch to "bb" program (CPLEX version only).
	This forces the CPLEX LP to have at least N rows and M non-zeros
	whenever it is allocated and/or reallocated.  The default rules
	for allocating and reallocating the CPLEX problem sometimes cause
	lots of reallocations.  This wastes some time, increases memory
	fragmentation, and perhaps also wastes some memory.  This can be
	avoided by using this switch to set the initial allocation to be
	large enough.

	* Added the "-B N" switch to "bb" program.  This lets the user
	specify one of several (currently three) branch variable selection
	policies.

	* Removed the "-t X" switch that specified a lower bound threshold
	at which to begin trial branch computations.  This was an
	experimental routine whose purpose was to discover properties of
	branch variables that were highly correllated with good
	performance as branch variables.  The discovery was that variables
	that spend long periods of time "stuck" at the same fractional
	value are good branch variable candidates with high probability.
	The probability seems to increase if their fractional value is
	simple, such as 1/2, 1/3, 2/3, 1/4, 3/4, etc.  The new branch
	variable selection code now makes use of these discoveries, so
	this switch (and the experimental test_branching_variables()
	routine) were removed.

	* Added the "-T N" switch to "bb".  This says to be N times more
	thorough in looking for good branch variable candidates during
	strong branching.  If the default would be to check candidate
	variables (in order by most promising to least promising) and stop
	scanning when K consecutive variables have failed to find an
	improvement, then this switch would stop after K*N consecutive
	failures.

	* Added the "-z N" switch to "bb".  This forces the target size of
	the constraint pool (in non-zeros) to be N.  On difficult
	problems, the convergence rate can improve by keeping more
	constraints in the pool.  N can be suffixed with a single letter
	specifying a multiplier.  The suffixes/multipliers permitted are
	k=1000, K=1024, m=1000000, M=1024*1024.  The new atoi_suf routine
	performs this conversion of optionally suffixed decimal integers,
	and is now used for all integer switch operands.

	* Now always allocating root node, bbinfo, bbtree, lpmem bbstats,
	etc. on the heap so that they can always be freed.

	* Created new routine create_bbtree() to encapsulate all of the
	details of creating/initializing an empty branch and bound tree.

	* Initial lower bound of root node is now -DBL_MAX instead of 0.0
	to make code work properly with negative objective coefficients.

	* Save and restore the setting of the CPLEX "OBJULIM" parameter
	across calls to branch_and_cut.  This makes branch_and_cut a bit
	more re-entrant.  (Too bad all the CPLEX parameters are global and
	not local to each problem...  This forces us to multiplex them all
	when switching back and forth between problems that need different
	parameter settings.)

	* Rotate the main loop of branch_and_cut so that all nodes are
	inactive upon entry.  The very top of the loop now selects the
	next inactive node to activate and process.

	* The choose_branching_variable() routine can now choose variable
	-1, which means that branching of the node has been aborted.  This
	happens when strong branching discovers one (or more) fractional
	variables that cutoff on at least one of their two branches.  Such
	variables are fixed to the opposite polarity and branching aborts.
	Instead of branching, the main branch_and_cut loop either cuts the
	node off (if the node's updated objective permits), or suspends
	the node.  When resumed, constraint generation for this node
	continues.

	* Major changes to carefully_choose_branching_variable().  It now
	uses the branch-heuristic values to sort all candidate (i.e.,
	fractional) branching variables in order from most-promising to
	least-promising.  The bheur values are lowest for variables that
	have been "stuck" at the same value for the longest time.  These
	values are adjusted for the "complexity" of the variable's
	fractional value -- as determined using a Closest Rational
	Approximation routine (new file cra.c).  Before moving on to the
	expensive testing of candidate branch variables (by solving each
	branch) we now first "estimate" the best of all fractional
	variables using the node's "zlb" values.  The "strong" testing
	commences using this pessimistic estimate of the best candidate.
	Rather than perform a "strong" test on every variable, we now test
	only the most promising ones, stopping after a certain number of
	consecutively less promising variables actually fail to improve on
	the best branch variable seen so far.  If nfrac < 20, the failure
	limit is nfrac and all candidates are tested.  Otherwise the
	failure limit is 2*N*floor(log2(nfrac)), where N is from the "-T
	N" switch.  The strong branching loop can also now be aborted
	using the "kill -15" signal.  Using the new "eval_branch_var()"
	routine that encapsulates everything we need to do for testing
	both branches of a single variable.  This routine also takes a
	"test_2nd_val" threshold value that controls whether or not to
	even evaluate the second branch.  eval_branch_var() also returns a
	status indicating whether or not it was able to FIX the given
	variable.  If so, then the strong branching loop aborts with no
	branch variable chosen.  The new routine compare_branch_vars()
	encapsulates all of the current branch variable selection
	criteria, and the method of picking "test_2nd_val" threshold
	values.  The new eval_branch_var() routine also runs the upper
	bound heuristic on each LP solution obtained while doing "strong"
	testing of branch vars, and also performs variable fixing whenever
	a cutoff is achieved.

	* Make eval_branch_var() unscale objective values coming from
	try_branch() when using CPLEX.  We really ought to make try_branch
	do this, but its calling convention does not permit this.

	* The new compare_branch_vars() routine currently implements 3
	different branch variable selection (i.e., comparison) policies.
	Policy 0 is a naive maximum of of each variable's minimum branch
	objective.  Policy 1 (the default) is a smarter lexicographic
	version of the same.  When the variable's minimum branches are
	very close, it compares the maximum branches.  Policy 2 compares
	the product of the improvements provided by both branches, and
	uses policy 1 to break very close ties.

	* Now using a new store_double() routine (in utils.c) to fix the
	Intel FPU problem in check_for_better_IFS().  Darn compilers keep
	getting smarter than we would like them to sometimes...

	* Node suspend and resume messages now display the objective value
	of the node being suspended or resumed.

	* Increased size of various "sprintf" buffers to avoid overflow
	with large numbers or wide strings.

	* Moved update_lp_solution_history() from bb.c into constrnt.c.
	It is now called during each iteration of
	solve_LP_over_constraint_pool() instead of once upon return from
	this routine.  It now updates the "zlb", "x", and "bheur" values
	instead of the xhist array (which has gone away).

	* Because of bugs in lp_solve, we now wait until all separation
	routines have been run (and violations discovered) before calling
	delete_slack_rows_from_LP() when running with lp_solve.  Deleting
	slack rows from lp_solve can cause the current basis to become
	invalid.  If we return to the main branch_and_cut loop with an
	invalid basis, then the lp_solve version of try_branch will croak