changelog

Lin-Kernighan heuristic for the TSP and minimum weight perfect matching

lk-0.5.0:
	README: minor edits
	BUGS: listed the following bugfixes
	src/jbmr.w, src/match.w: Important bugfix:
		change_log in jbmr.w and match.w wasn't being
		grown when it should have; was corrupting dirty 
		set and then segfaulting.  Thanks Electric Fence!
	src/dirty.w: bugfix: Use ds->n instead of n when filling the dictionary
	src/jbmr.w: 
		- Report 0 depths that have non-zero depths after them.
		This is so we can get fair graphs in all cases.
		- Fixed the test on max index to write for probe and move depths.
	src/match.w: Added probe and move depth logging
	src/lk.w:
		Make PostScript title output more friendly re: length printing.
	src/lkconfig.h:
		Fixed grammar
		Added MATCH REPORT DEPTHS: Default is 1, and changed the 
		default for JBMR REPORT DEPTHS to 1
	src/Makefile.am: more programs (see below)
		clustcalc,clusternoise,infill,clusterdiscount,tsp2matrix
	src/ascend.w: Print a dot to show progress, reduce verbose level of when
		to show full 1-tree
	src/read.w: Added forced write in matrix form
	src/resource.w: Get some meaningful resident set size (RSS) 
		numbers on Linux kernel 2.2.  We have to go to the /proc filesystem.  
		But are they the *max* RSS?
	src/shake.w: Default d is pi/16
	src/tabuhash.w: Conform to new debugging-enabling dirty set.
	src/tspgen.w: Better doc
	src/tspps.w: Added option for generating EPS instead of plain PS file.
		Added better option handling
		Added squeeze factor option -s
	src/clustcalc.w: new
	src/clusternoise.w: new
	src/infill.w: new
	script/mkmountain.pl: new
	script/mktable.pl: new
	src/webdefs.w: Added an alg style


Sat Oct 17 18:33:37 EDT 1998
lk-0.4.17:
    - ascend updated majorly.
	- ...

Sat Sep 26 15:30:03 EDT 1998
Oh dear.  It looks like I've fallen behind on the ChangeLog.  Sorry.
See the NEWS file as well.

lk-0.4.14:
* construct.w: 
	- fixed a bug in non-Euclidean case. Marking a city as saturated
	wasn't working.  The inv_unsaturated array was not being updated.
	- non-Euclidean case.  Fixed subtle bug where the max distance
	value could have been garbage.
	- non-Euclidean case.  When there are fewer than sqrt(n) unsaturated
	cities left, include all of them as fresh neighbours.


lk-0.4.11
Main difference since lk-0.4.10:
- default for length_t is now int
- fixing latent bugs related to above

* script/expt.pl.in:  Allow easier reproduction of results: random number
	seed is based on a given "salt" value, instance name, and permutation
	number.

* src/jbmr.w: Rejection test: "cum2 < clust_dist + best_gain"  is now
	"cum2 <= clust_dist + best_gain".  Had problems when cum2>0,
	cum2==clust_dist and best_gain=0.  This only showed up on length_t
	being an integer because the floating types always used an epsilon.
	Also, @<Go deeper@> max-taking is simplified (and hopefully sped up).

* src/lk.w: Upper bound value is always a double, so print it as one.

* src/Makefile.am: Added program unif to generate DSJ-style uniform 2-d Euc
	instances.

* src/lkconfig.h:  
	- Default length type is now int, not double. (Would I use that in
	a real "production" mode?  Probably not...)
* src/ascend.w: Fixed array work_dist to be array of length_t, not double.
* src/lk.w: 
	- Fixed array lengths to be array of length_t, not double.
	- upper_bound_value is double, so it should get a %f print spec.
* src/match.w: Fixed array length_t_length to be array of length_t, not double.
* src/jitter.w: Print cost as length_t, not as double.

Sun Aug 23 17:41:28 EDT 1998
lk-0.4.10
* src/prolog.ps: Comments now wrap.  Moved comment and title up 0.3 inches.

* config.h.in: Added WORDS_BIGENDIAN
* configure.in: Added AC_C_BIGENDIAN
* src/length.w: Added input specs (including dubious multi-word input for
	long long).

* src/types.w: Added types edge_t and tree_t for tspgen.w.
* src/tspgen.w:
	- Input is now a weighted tree in DIMACS format.
	- Allow forcing of output instance to have an MST isomorphic to its input.
	(That is "dangle and construct".)  Or at least we try our best.
	- Added |ancestor| field to component_t, used for forcing iso, by way
	of merge-find ADT.
	- Module variables really are static now.
	- No more Global variables.

* src/lk.w (main): 
	- Changed --mst-edge-lengths-only to --mst-only
	- Output the MST in DIMACS matching 'edge' input format.
* src/length.w:
	- Added native-to-type printing spec.

* src/jbmr.w (jbmr_run): 
	- Get rid of warning about no-effect lhs of comma operator: amidst the
	bridge length changes.

Thu Aug 20 12:01:17 EDT 1998
lk-0.4.9 
* src/dirty.w: 
	- added a dirty_includes query
	- streamlined remove and make empty in the array case
* src/jbmr.w:
	- Added TABU_HASH option to use hash tables developed in src/tabuhash.w
* src/tabuhash.w: This file is new.
* src/lk.w: Include rcs id info for tabuhash.w
* src/lkconfig.h: Added option for TABUHASH_MAX_VERBOSE ; default is 0


Fri Aug 14 16:20:04 EDT 1998
lk-0.4.8
* script/expt.pl.in:
	- tspreorder is now optional.
	- Use the same random number time seed on all variations (.deg, .no_d)
	since different seeds for start tour, etc. is noise we want to eliminate. 

* src/jbmr.w: Fixed the backtrack cutoff.  It was still using 2 choices
  of pairs for t7,t8 for BL==2.  It now rightly only uses the first available
  one.  (This appears to degrade the lk.deg quality of tour.  But it still
  maintains considerable time superiority.)

Sun Aug  9 17:21:02 EDT 1998
lk-0.4.6
* src/lk.w (main): New options --extra-backtrack and --no-extra-backtrack to
control whether to backtrack over t7 and t8 (in addition to t1 through t6).
* src/jbmr.w @<Update |best_gain| and compose a list of eligible moves@>:  
	Implemented backtracking cutoff option.

* src/construct.w (construct,construct_matching): 
	Implement CONSTRUCT_GREEDY_RANDOM for both TSP and matchings.
* src/lk.w (main): 
	Added a --seed option.
	Pass random seed to construction routines.
	Changed --help output: long option names moved left
* src/match.w (match_construct): Accept and pass on the random number seed.

Fri Aug  7 19:37:10 EDT 1998
lk-0.4.5
* src/jbmr.w src/match.w:  Dirty sets factored out.
* src/dirty.w: Added.
* src/lk.w: Different handling of prngs passed to optimizers.

* rcs id changes in various src/*.w files.

* src/jbmr.w: Documentation update (include scheme figures)


Sat Aug  1 15:25:34 EDT 1998  neto
lk-0.4.4
* src/lk.w: __USE_MISC is now defined only if it isn't already defined


1998/7/31
lk-0.4.3
* script/expt.pl.in: 
	Updated input format
	Allows a require statement for version testing between script and expt.pl

* script/cfresults.pl.in: Now it works with matching runs.

* script/TSP.pm.in: 
	Changed export list, got cost functions working for 2-d instances.
	Added as_Rothberg_on, to write the instance in Rothberg format.
* script/tsplib2rothberg.pl.in:  Created

* src/lk.w (main): Tell read_tsp_file whether we're doing matching.
* src/read.w (read_tsp_file): 
	Remove the "odd" vertex if doing perfect matching.
	Change prototype for read_tsp_file, and change all callers, in
		src/distcalc.w src/tspps.w src/shake.w src/jitter.w

* src/lk.w: Documentation fixes.
* src/ascend.w: Documentation fixes.  Moved prototypes around


1998/7/16
lk-0.4.0 is the first public release of LK.
	- lk implements Lin-Kernighan for the TSP and min-weight perfect matching.
	- Most TSPLIB files are understood.  (GEO is still a mystery to me)
	- Iterated-LK is supported via the -i switch.
	- tspgen generates TSPLIB-format instances from a list of weights.
	- shake perturbs a 2-d TSPLIB-format instance by articulating some
of the large edges in a MST for that instance
	- jitter perturbs a 2-d TSPLIB-format instance by adding noise to the
coordinates of its vertices
	- ifs generates 2-d TSPLIB instances based on iterated function systems.
The input format is rather sparse and should be updated to the DIMACS IFS
format.  (I didn't know the DIMACS format existed when I wrote ifs.w.)
	- The script directory contains many useful scripts for
generating and transforming instances, for running experiments,
and for massaging the output of experiments.  There's also an embryonic
TSP Perl class.
	- The Makefile in the expt directory is godawful ugly and requires GNU
make to be functional.  It was a hack to get automatic generation of gnuplot
files from experiment logs.