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, @ 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 @: 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.