lk.w,v

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

     Toronto, Ontario
     M5S 3G4
     Canada
}
\medskip


\noindent\hbox{}\hrule\hbox{}\penalty-1000
\vskip0.5cm\relax



@@i webdefs.w
@@i types.w

{\obeylines
$Log: lk.w,v $
Revision 1.274  1998/10/16 20:42:04  neto
Better held-karp handling.
lk.w is licensed under the LGPL, not the GPL.

Revision 1.273  1998/10/10 19:36:27  neto
Fixed speling mysteak

Revision 1.272  1998/09/26 16:37:56  neto
Better docs about option -s

Revision 1.271  1998/08/29 20:01:24  neto
upper bound value is double, not lenght t.  Fixed print spec.

Revision 1.270  1998/08/28 18:51:29  neto
Array lengths is of length t type, not double.

Revision 1.269  1998/08/22 18:24:06  neto
MST output should also include the instance name.
Futhermore, the mst structure records the number of edges in the tree,
not the number of vertices.  So we were always missing the last one.

Revision 1.268  1998/08/21 17:20:37  neto
Changed --mst-edge-lengths-only to --mst-only.
Print the MST out in DIMACS matching input format.

Revision 1.267  1998/08/20 18:35:04  neto
Added rcs info for tabuhash.

Revision 1.266  1998/08/09 21:08:56  neto
Fixed up handling of greedydet.
(printing and testing)

Revision 1.265  1998/08/08 19:58:03  neto
Made option greedy be randomized greedy
Added greedydet option.

Revision 1.264  1998/08/08 18:30:35  neto
random seed is a long ,not an int.

Revision 1.263  1998/08/08 18:15:16  neto
Fixed a TeXo
Added a --seed option.
Pass the random seed to construction routine.

Revision 1.262  1998/08/08 15:57:28  neto
Added option for extra backtracking (old behaviour) and
no extra backtracking (JBMR t7 and t8 behaviour).

Revision 1.261  1998/08/07 23:35:27  neto
We print rcs ids for some modules we don't import otherwise.

Revision 1.260  1998/08/07 22:58:04  neto
Free the prng we pass to the optimization routines.

Revision 1.259  1998/08/07 15:55:07  neto
Define USE\_MISC only if it isn't already defined.
Also, updated the banner rcs id printout.

Revision 1.258  1998/07/31 18:38:30  neto
Needed a newline in help.

Revision 1.257  1998/07/24 19:25:17  neto
Allow the read module to remove the "odd" vertex in case of perfect matching.

Revision 1.256  1998/07/24 17:28:44  neto
Fixed the --maxdepth help for --help.

Revision 1.255  1998/07/23 16:51:08  neto
Fixed more of the --help output.

Revision 1.254  1998/07/23 16:34:09  neto
Missed the --help about iterated LK being unimmplemented.

Revision 1.253  1998/07/23 16:29:41  neto
Added my boilerplate.

Revision 1.252  1998/07/23 16:27:18  neto
Fixed comments about what is and isn't implemented

Revision 1.251  1998/07/16 21:58:55  neto
Added the LGPL notice in each file.

Revision 1.250  1998/06/19 16:39:17  neto
Check that the upper bound is given when computing held karp lower bounds.
Of course, I could always compute it on the fly....

Revision 1.249  1998/05/29 21:01:10  neto
Off by a factor of 100 in calculation of percentage for Held Karp.

Revision 1.248  1998/05/23 18:23:32  neto
Doh.  Was discarding the held karp bound. Fixed. I hope

Revision 1.247  1998/05/23 18:09:57  neto
Needed casts around length t stuff in held karp bounds.

Revision 1.246  1998/05/23 17:31:25  neto
This now compiles to .o.
(The cleanup function needs access to do weighted perfect matching.
But it doesn't handle held karp only...)

Revision 1.245  1998/05/23 16:22:53  neto
Added proper setup of held-karp lower bound.
Added options for upper bound.  Change -b to -l, a lower bound.
Added options for held karp computations.

Revision 1.244  1998/05/21 15:46:08  neto
New interface to match run

Revision 1.243  1998/04/10 15:13:31  neto
Made safe for non-E2 instances

Revision 1.242  1998/02/21 04:05:19  neto
Added support for Iterated LK (for TSP).
Also fixed some output stuff for matching.

Revision 1.241  1998/01/23  21:04:55  neto
Now it compiles well with match module.
Fixed some printing minor errors.

Revision 1.240  1997/12/20 20:44:12  neto
Changed variable "start tour" to "construction algorithm".
It's more descriptive and more accurate.

Revision 1.239  1997/12/20 20:31:25  neto
Import the matching header.
Fix raw lengths if CEIL 2D.
Export comparison functions for double and length t.

Revision 1.238  1997/12/20 18:38:16  neto
Added first draft of support for doing minimum weighted perfect matchings.

Revision 1.237  1997/12/19  20:46:37  neto
Fixed the calls to decluster mst and preprocess: I was passing the
instance to the wrong procedure.

Revision 1.236  1997/12/13 21:31:04  neto
Ooops, I put it in the wrong place!

Revision 1.235  1997/12/13 21:28:15  neto
decluster mst now takes the tsp instance argument instead of relying on
a global variable.

Revision 1.234  1997/12/13 16:47:54  neto
Updated to new interface with error module.
Made all module names upper case.

Revision 1.233  1997/12/05  21:42:32  neto
It's Moore's curve, dodo.  :)

Revision 1.232  1997/11/14  22:53:44  neto
Output starting tour if verbose is high and postscript is on.

Revision 1.231  1997/10/18  18:09:11  neto
Convert to new protocol for nearest neighbours.

Revision 1.230  1997/10/18 14:47:50  neto
Now we use E2 supports() for more intelligent construction or non-construction
of 2-d trees.

Revision 1.229  1997/10/17  21:48:15  neto
Changed coord\_2d structure.

Revision 1.228  1997/10/17  21:01:11  neto
Added begin data structures mark.

Revision 1.227  1997/09/27 18:06:21  neto
Fixed RCS log behaviour.

Revision 1.226  1997/09/12  21:30:04  neto
Code wasn't included! This caused seg faults.  (This is a CWEB scripto-level
bug.  oops).

Revision 1.225  1997/08/15  20:18:25  neto
Added Index major section.

Revision 1.224  1997/08/15  16:59:29  neto
Print the MST to PostScript as well.

Revision 1.223  1997/08/15  16:19:19  neto
Added -m (--mst-only) to print the edge lengths and quit

Revision 1.222  1997/08/14  20:19:46  neto
Added symbol BUILD DECLUSTER STRUCTURES to internal conditional compilation.

Revision 1.221  1997/06/19  19:41:34  neto
Be a little more friendly on initial tour length.

Revision 1.220  1997/06/17  21:45:20  neto
Put declustering configuration info in the version banner.

Revision 1.219  1997/06/17  21:32:47  neto
Must include declevel.h

Revision 1.218  1997/06/17  20:28:42  neto
Added support for milestones.
Made declustering stuff conditional.

Revision 1.217  1997/06/16  20:45:00  neto
I need to remember the mst space.

Revision 1.216  1997/06/16  20:24:52  neto
A first cut at doing declustering.

Revision 1.215  1997/06/16  17:35:12  neto
Cleaned up output (again).

Revision 1.214  1997/06/16  17:20:52  neto
Split the validation and print section.

Revision 1.213  1997/06/16  16:38:10  neto
I removed an extraneous print line (Edit bug).

Revision 1.212  1997/06/16  16:33:44  neto
Print no decimal points when no-round option is *not* used.
(i.e. the right thing)

Revision 1.211  1997/06/16  16:07:26  neto
Print length in double format when verbose < 10.

Revision 1.210  1997/06/13  22:12:45  neto
Fixed a spelling mistake.

Revision 1.209  1997/06/13  21:59:58  neto
Refine verbose levels for some output.

Revision 1.208  1997/06/13  21:49:29  neto
Make 5 the default verbose.
Some things that were printed at verbose level 2 now pushed up to 10.

Revision 1.207  1997/06/13  21:39:08  neto
Fixed comments.
Prettied up some TeX stuff.
Terminate columns of numbers in printing tour.
Make sure tour is printed if given -t option, no matter what verbose
setting is.

Revision 1.206  1997/06/13  21:16:06  neto
Fixed comment about main.
put starting braces of functions in column 1.
Updated a section name to reflect reality (report results in only
one place).

Revision 1.205  1997/06/13  21:01:59  neto
Fixed a variable name

Revision 1.204  1997/06/13  20:59:29  neto
Make verbose==1 output only the length of the tour.
Make verbose==2 the default, and it's quite quiet.

Revision 1.203  1997/06/13  20:32:09  neto
Don't print starting incumbent len if verbose==0

Revision 1.202  1997/06/13  20:28:08  neto
Removed flushes of stdout after resource mark calls.
Made checking kd tree quieter if verbose==0

Revision 1.201  1997/06/13  20:16:23  neto
Sorted, minor editing on help text.
Made it really quiet when verbose==0.

Revision 1.200  1997/06/13  19:49:27  neto
Made it a little quiter.

Revision 1.199  1997/06/13  18:44:11  neto
Fixed up the parens matching hack (for editors).

Revision 1.198  1997/06/13  18:17:30  neto
It's not Neto's curve, it's Moore's curve.
I've moved the origin to 6 o'clock instead of at the origin.  This
may help cache behaviour.
(Because the 0/1 boundary is at the edge of the square instead of
right in the middle.).

Revision 1.197  1997/05/16  21:15:06  neto
Now I don't need special behaviour for Linux regarding getpagesize.

Revision 1.196  1997/05/16  21:13:33  neto
Now I don't need special behaviour for Linux regarding gethostname.

Revision 1.195  1997/05/16  20:37:20  neto
Put in some support from configure.

Revision 1.194  1997/05/16  18:11:41  neto
Break locks by david and neto.
Include <config.h> and "lkconfig.h"

Revision 1.193  1997/05/16  18:09:40  neto
Include <config.h> and lkconfig.h

Revision 1.192  1997/02/11  16:08:50  neto
Fixed parsing of start tour.

Revision 1.191  1997/02/10  19:32:36  neto
Added a grestore to close out postscript .

Revision 1.190  97/01/27  16:43:48  neto
Made lk cleanup prototype and definition match in storage class modifier.

Revision 1.189  97/01/27  16:41:02  neto
Better output of intermediate PostScript.

Revision 1.188  1997/01/21  22:30:17  david
Fixed an errorif call.

Revision 1.187  1997/01/21  21:55:55  david
Added standard copyright notice by including copyrt.w

Revision 1.186  1997/01/21  17:48:24  david
Output the tour to the PostScript output stream, if open.

Revision 1.184  1997/01/21  17:23:46  david
Fixed printing out of start tour option, w.r.t. canonical.

Revision 1.183  1997/01/21  16:33:44  david
Added canonical back again.
Fixed error messages about sorting options.

Revision 1.182  1997/01/21  16:22:34  david
Make printing of SFC results optional.

Revision 1.180  1997/01/21  16:10:23  david
Fixed ordering and normalization in SFC comparison function.

Revision 1.179  1997/01/21  15:37:41  david
Fixed the rewrite rule and the comparison rule for SFC when a and
b compare as different.

Revision 1.177  1997/01/21  00:18:10  david
Fail if --maxdepth option given without proper compilation flag.

Revision 1.176  1997/01/20  23:49:31  david
Changed max\_probe\_depth to max\_generic\_flips

Revision 1.175  1997/01/20  19:50:46  david
Fixed setting probe depth.

Revision 1.174  1997/01/20  19:45:56  david
Fixed limit.h to limits.h

Revision 1.173  1997/01/20  19:44:31  david
Added a maxdepth option.

Revision 1.172  1997/01/17  22:11:41  neto
Modifying sfc comparison function.  Still buggy.
Need to use both bits at the same time (x and y) and use table
lookup.
Added printing of labels to the postscript debugging output.

Revision 1.170  1997/01/17  19:43:19  neto
MAXHOSTNAMELEN not defined under Solaris.

Revision 1.169  1997/01/16  22:19:02  neto
Print the wall clock time afterward too.

Revision 1.168  97/01/16  14:20:22  neto
Added space filling curve code.

Revision 1.167  96/12/16  16:56:30  neto
Now it passes gcc with lots of warnings turned on.

Revision 1.166  96/12/13  15:14:03  neto
Fixed a parameter mistake in printing.

Revision 1.165  96/12/13  15:08:50  neto
Fixed typo on variable name.

Revision 1.164  96/12/13  14:49:28  neto
Added raw length computation.

Revision 1.163  96/12/12  14:01:35  neto
Fixed a CWEB typo.

Revision 1.162  96/12/12  14:01:09  neto
Print the current time, too.

Revision 1.161  96/12/05  16:13:54  neto
Free the lengths array.

Revision 1.160  96/12/05  16:00:59  neto
Fixed printf.

Revision 1.159  96/12/05  15:57:08  neto
Fixed prototype for double\_cmp, and made it a module subroutine so that
it would be defined before used.

Revision 1.158  96/12/05  15:55:57  neto
Add the lengths in smallest-to-largest order.   This is the best
numerically-wise.

Revision 1.157  96/12/05  15:35:46  neto
Seem to have fixed the validation routine.

Revision 1.156  96/12/05  15:29:19  neto
Dumb dumb dubm.  +=

Revision 1.155  96/12/05  15:27:51  neto
Need more casts.
.l

Revision 1.154  96/12/05  15:25:37  neto
Need to cast the cost function to double.

Revision 1.153  96/12/05  15:00:38  neto
Changed validation to use compute both a length\_t validation variable
and a double-valued validation variable.  For now, use the double-valued
one to do the check.

Revision 1.152  96/12/05  14:54:59  neto
Added name and comment to output.

Revision 1.151  96/12/05  14:41:05  neto
Added option --noround

Revision 1.150  96/11/08  15:49:55  neto
Added some length\_t\_pcast in places.

Revision 1.149  96/09/19  15:41:47  neto
Added string.h to header list.
Removed assert.h

Revision 1.148  96/09/18  17:16:52  neto
Better name for upper limit on resource marks: last\_resource\_mark.
Also, report a summary from the very beginning to the very end.

Revision 1.147  96/09/18  16:42:38  neto
Fixed calling problem with resource\_report.  Duh.

Revision 1.146  96/09/18  16:39:49  neto
Be a little more intelligent about reporting resource statistics.

Revision 1.145  96/09/18  16:22:10  neto
Added a resource mark at the very beginning of the run, to capture
memory usage of the read routine.

Revision 1.144  96/09/17  14:28:52  neto
More feedback about shutdown sequence.  It seems to take a while.

Revision 1.143  96/09/17  14:07:18  neto
Added conditional compilation if structure around a use of 
a twolevel debugging name.

Revision 1.142  96/09/12  14:15:07  neto
Fixed an unterminated preprocessor else.

Revision 1.141  96/09/12  14:08:10  neto
Removed duplicate const in prototype.

Revision 1.140  96/09/12  14:05:44  neto
Added twolevel debugging routines.

Revision 1.139  96/09/11  16:37:48  neto
Strengthened tour\_set prototype.

Revision 1.138  96/09/10  16:21:26  neto
Added handling of two-level representation.

Revision 1.137  96/08/23  17:24:32  david
Removed the period from the etal macro

Revision 1.136  1996/08/23  15:40:41  david
Fixed for linux.  Unistd declares gethostname and getpagesize only
if \_\_USE\_BSD is defined.  So I doit manually.

Revision 1.135  96/08/20  11:30:40  neto
Added unistd.h for gethostname

Revision 1.134  96/08/16  16:59:37  neto
Report the fixincludes rcs id only if we actually compiled it in.

Revision 1.133  96/08/16  16:56:43  neto
Was including fixincludes twice erroneously.

Revision 1.132  96/08/16  16:49:58  neto
Added fixincludes to the rcs list

Revision 1.131  96/08/16  13:36:01  neto
only need gethostname

Revision 1.130  96/08/16  13:32:04  neto