jbmr.w,v

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

Add online printing of length of broken t1 and t2 edge, and some online
depth printing.

Revision 1.176  1997/07/02  17:51:20  neto
Satisfy GCC's dataflow analysis w.r.t. this time.

Revision 1.175  1997/06/20  21:48:17  neto
Better comment about CAREFUL OP
rename num decluster reject to num reject by decluster, for uniformity.
Implement declustering in test surrounding major part of
  Update best gain and compose a list of eligible moves.

Revision 1.174  1997/06/20  20:55:28  neto
Formatting improvements.

Revision 1.173  1997/06/20  20:44:35  neto
Cleared up some clutter by using a macro for careful comparisons
with best gain.

Revision 1.172  1997/06/20  19:34:02  neto
Fixed typo in section name
Fixed a BIG MISTAKE:  compute cluster distance between t1 and t2ip2
*no* between t2ip1 and t2ip2.  Duh!

Revision 1.171  1997/06/20  18:59:04  neto
Added some stats gathering (num reject by cum 1, num reject before build e)
Check for cum gain > best gain *before* entering Update
best gain and compose an eligible list of moves.
This might save a *lot* of time because we may avoid searching
an entire nn list.

Revision 1.170  1997/06/20  18:32:26  neto
A better comment about building e list.
Commented out the code bloating PREV NEXT loop.
Made cluster rejection announcement at much lower verbose level, though
context is lost.
Count number of rejections due to declustering.

Revision 1.169  1997/06/18  16:43:47  neto
Milestones every 10th of a percent from 10 percent down through zero.

Revision 1.168  1997/06/17  20:28:57  neto
Added support for milestones.

Revision 1.167  1997/06/17  14:49:32  neto
Fixed a TeX error.

Revision 1.166  1997/06/17  14:47:12  neto
Fixed an unterminated hash if

Revision 1.165  1997/06/17  14:45:14  neto
Better formatting in eligibility test.
Added cluster compensation to the greedy test (Go deeper)

Revision 1.164  1997/06/16  21:22:16  neto
More debug verbose info.

Revision 1.163  1997/06/16  21:14:23  neto
Decluster test should use the best gain with slop.

Revision 1.162  1997/06/16  21:01:11  neto
At verbose 501, print every cluster distance.

Revision 1.161  1997/06/16  20:38:58  neto
JBMR ALLOW VERBOSE is always defined.  Now decide on zero/non-zero status
instead.

Revision 1.160  1997/06/16  20:26:58  neto
Added include decluster.h

Revision 1.159  1997/06/16  20:19:20  neto
Fixed a syntax error.

Revision 1.158  1997/06/16  20:05:14  neto
Need to include declevel.h to see whether to use declustering.

Revision 1.157  1997/06/16  20:04:05  neto
First cut at integrating decluster test.  Doesn't actually reject
just yet.  It just collects data.

Revision 1.156  1997/06/16  19:15:32  neto
Make unrolling the prev next loop conditional at compile time.

Revision 1.155  1997/06/16  18:34:20  neto
Make the code compact by putting both alternatives for t2ip2 into
the body of a loop.

Revision 1.154  1997/06/16  17:36:52  neto
Fixed a TeX bug.

Revision 1.153  1997/06/16  16:57:14  neto
Don't need debugging output for SPLIT GAIN VAR anymore.

Revision 1.152  1997/06/16  16:45:51  neto
Reversed the sense of REQUEST SPLIT GAIN VAR to REQUIRE SPLIT GAIN VAR
That way the default (safe) setting happens with fewer variables set.

Revision 1.151  1997/06/13  20:59:16  neto
Made it quieter

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

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

Revision 1.148  1997/04/23  21:28:07  neto
Added elapsed time since last phase change to verbose reporting.

Revision 1.147  1997/04/23  20:44:56  neto
In verbose mode, report elapsed time since start of LK phase when
an improvement has been found.

Revision 1.146  1997/02/07  16:52:23  neto
Made every use of emphpar end with a paragraph break.

Revision 1.145  1997/01/21  22:46:47  david
Clarified conditional compilation and fixed a bug.

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

Revision 1.143  1997/01/21  19:34:36  david
Clarified use of JBMR REQUEST SPLIT GAIN VAR

Revision 1.142  1997/01/21  19:15:27  david
Fixed setting of SPLIT GAIN VAR

Revision 1.140  1997/01/21  00:22:47  david
Removed offending pritnf

Revision 1.139  1997/01/21  00:21:53  david
Report both probe and move depths.

Revision 1.137  1997/01/21  00:06:57  david
Added tracking of probe depths.

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

Revision 1.135  1997/01/20  23:47:01  david
Fixed the limiting of probe depth.

Revision 1.134  1997/01/20  19:32:54  david
Optionally limit the probe depth.

Revision 1.133  97/01/16  13:35:17  neto
Get rid of a warning about old\_t when compiling with TABU LINEAR.

Revision 1.132  96/12/23  13:07:03  neto
New variable best gain with slop.  Saves many additions.

Revision 1.131  96/12/20  17:05:13  neto
Fixed typesetting woes by simplifiyng preprocessor stuff. (moved a brace.
).

Revision 1.130  96/12/20  17:02:54  neto
Fixed TeX typos and a spelling mistake.

Revision 1.129  96/12/20  16:57:56  neto
Fixed a tex bug.

Revision 1.128  96/12/20  16:41:53  neto
Fixed typo in section name (init bookkeeping vars)

Revision 1.127  96/12/20  16:32:43  neto
First attempt at incorporating instance\_epsilon

Revision 1.126  96/12/20  13:40:39  neto
Put the unified gain variables back in.  Make it optional.

Revision 1.125  96/12/19  12:12:07  neto
Fixed a CWEB typo in the rcs log.

Revision 1.124  96/12/17  14:50:05  neto
Now it compiles when debugging output is turned on.
Also, fixed a CWEB style infelicity.

Revision 1.123  96/12/16  17:02:55  neto
Fixed a typo.
Forgot the comparison function for eligible moves; it now handles
the split representation.

Revision 1.122  96/12/16  16:38:37  neto
First attempt at separating cum\_gain into positive and negative parts.

Revision 1.121  96/08/19  18:22:01  neto
Fixed uninitialized variables.  
generic flips made being uninitialized was a *bug*!

Revision 1.120  96/08/16  16:29:59  neto
Made it pass all warning flags when "allow verbose" is on.
Added "watch this city"

Revision 1.119  96/08/16  13:04:45  neto
Added fixincludes.

Revision 1.118  96/08/16  12:40:42  neto
Converted putchar to printf.   Otherwise, I'd never get a prototype
for SunOS's \_flusbuf.

Revision 1.117  96/08/15  14:35:51  neto
Fixed a const-related warning.

Revision 1.116  96/08/15  14:18:47  neto
Make it pass more gcc warning flags.

Revision 1.115  96/08/15  13:20:57  neto
Make it pass -Wall

Revision 1.114  96/08/14  13:35:52  neto
Use sort instead of qsort.

Revision 1.113  96/08/07  15:33:50  neto
Added reasons why pointer-difference tie-breaking would break code
in several places.

Revision 1.112  96/08/07  15:18:44  neto
Make qsort optionally preserve the order of equals.

Revision 1.111  96/07/29  17:09:07  neto
Fixed to compile.

Revision 1.110  96/07/29  16:19:50  neto
Added *\_rcs\_id.
Made sure RCS log is activated within this file.

Revision 1.109  96/07/25  13:30:36  neto
Changed ALLOW\_VERBOSE to JBMR\_ALLOW\_VERBOSE

Revision 1.108  1996/07/05  18:18:46  david
Fixed log. Duh.

Revision 1.107  96/06/28  12:18:42  neto
Moved some TeX definitions to webdefs.w

Revision 1.106  96/06/24  16:18:01  neto
Fixed comment that CWEB was interpreting.

Revision 1.105  96/06/20  16:11:58  neto
Use a more math-like typeset name for t2ip1 and t2ip2

Revision 1.104  96/06/19  14:12:31  neto
Finished adding splay TABU stuff.  It's all-or-nothing, though.
It could use some experimental work to determine the right cut-off.
Also, try the LEDA dictoinaries.

Revision 1.103  96/06/04  12:41:58  neto
More TABU stuff.

Revision 1.102  96/06/03  15:36:34  neto
More tabu stuff.

Revision 1.101  96/05/31  17:07:05  neto
Added some measurements regarding tabu check in the generic phase of
the search.
Began to parameterize the code regarding tabu check.

Revision 1.100  96/05/29  11:13:12  neto
This version works.  
Needs improvement:
	command-line switches
	faster tabu check
	allow Papadimitriou tabu rule
	faster preprocessing
	different candidate lists

Revision 1.47  96/05/28  11:52:53  neto
Added a fflush

Revision 1.46  96/05/24  17:44:11  neto
Added probe statistics.

Revision 1.45  96/05/23  14:49:36  neto
Added fflushes everywhere, and a hook to examine a particular city
in detail.
This version does the full LK now.  It hasn't crashed yet.

Revision 1.43  96/05/23  11:46:44  neto
Fixed up the showing of the t array.

Revision 1.42  96/05/22  17:22:09  neto
Removed a redundant test for |best\_scheme\_id| == 13.
Added |length\_t\_pcast| where necessary.  (Ooops!)

Revision 1.40  96/05/22  16:34:08  neto
Fixed announcement of generic rollback.

Revision 1.39  96/05/22  15:49:08  neto
Added a forgotten \#endif

Revision 1.37  96/05/22  15:39:12  neto
Make debugging output rely on value of |verbose|, and only compiled in
if |ALLOW\_VERBOSE| is defined.

Revision 1.36  96/05/22  14:36:46  neto
Runon comment!!!
Terminated properly now.

Revision 1.34  96/05/22  13:38:10  neto
During backtracking, we must clean up our scheme even though best\_gain>0
because that may be due to some other scheme.
Also, add some debugging output for generic flips.

Revision 1.33  96/05/21  13:55:57  neto
Refine the case 1.2 legality test for t6.
Added some Case marker comments.

Revision 1.32  96/05/21  13:30:11  neto
Fixed the inorder query in the reverse direction.

Revision 1.30  96/05/21  12:24:30  neto
Fixed log comments.
All initial 3-changes are checked for feasibilty before we commit to
adding them.
For 4-changes, we perform the feasibility checks that are possible
with cities 1-6 before picking 7.
Added legality checks for 4-changes.
Gave intuitive-style "proofs" as to why the performed checks are necessary
and sufficient.

Revision 1.29  96/05/16  15:42:54  neto
Fixed stupidity with scheme 2 dating back to analysis time.

Revision 1.28  96/05/16  15:31:15  neto
Added missing initial flip to scheme 2 (transcribing problem).

Revision 1.27  96/05/16  15:25:20  neto
Enforce |7!=3| in scheme 2.

Revision 1.26  96/05/16  15:10:02  neto
Fixed one place where |base\_scheme[6]| wasn't properly being set.

Revision 1.25  96/05/16  15:01:20  neto
Made |base\_scheme| an array. Does this work?

Revision 1.24  96/05/16  13:40:09  neto
Optimized scheme 3 feasibility check (now legality checks are finished sooner.)
Defensive switches: add default clause to every switch.
(Caught a bug: need to restore old values of |base\_scheme| for later
backtracking.)

Revision 1.23  96/05/16  12:58:26  neto
Comment about scheme 11.

Revision 1.22  96/05/16  12:47:18  neto
Fixed scheme 10.

Revision 1.21  96/05/16  12:36:15  neto
Fixed scheme 9, including an errant last move in the sequence of lflips.

Revision 1.20  96/05/16  12:03:39  neto
Fixed scheme 6.

Revision 1.19  96/05/16  11:55:45  neto
Fixed scheme 1 (see notes)

Revision 1.18  96/05/15  14:55:21  neto
Made |a| the last city in |tour\_inorder(a,b,c,d)|.  This is how
I use it.

Revision 1.17  96/05/15  14:28:10  neto
Fixed a missing indirection error on constraints for |t[7]|.

Revision 1.16  96/05/15  14:00:11  neto
Print the tour when neighbour conditions not met.

Revision 1.15  96/05/15  13:54:06  neto
Even more debugging output.

Revision 1.14  96/05/15  13:17:34  neto
More debugging output.

Revision 1.13  96/05/14  17:49:26  neto
Added debugging output.
Somehow I'm not undoing an unsuccessful scheme.

Revision 1.12  96/05/14  17:20:56  neto
ID to Id

Revision 1.11  96/05/14  17:20:11  neto
Replaced RCS Header with Id.
}

\input epsf

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


\def\t#1ip#2{t_{#1i+#2}}
@@s t2ip1 TeX
@@s t2ip2 TeX
% The following would be cruel...
%\def\twoxi{2i}	 
%@@@@s two_i TeX

@@*Johnson, Bentley, McGeoch, and Rothberg.
This module is my implementation of my understanding of the Johnson,
Bentley, McGeoch and Rothberg description of their implementation of
the Lin-Kernighan algorithm.
I hope that's clear.  If it is, then here's some more trouble:
I haven't got their report (it wasn't available as of February 28, 1996),
so I am going by the description given in Johson and McGeoch's
chapter on local search for the TSP. 

% Format |length_t| as if it were the keyword |int|
@@s length_t int

@@ This module provides the following interface.

Procedures 
|jbmr_setup| and |jbmr_cleanup| are the usual intialization 
and shutdown routines.

Procedure |jbmr_run| does the actual local search.

@@ Procedure |jbmr_run| uses the currently registered oriented tour implementation, which is
accessed through the routines beginning with |tour_|.  It assumes a
starting tour has already been constructed.  

It also uses nearest neighbour lists, already constructed by module
\module{NN}.


@@ The outline of this module is as follows:
@@c
#include <config.h>
#include "lkconfig.h"
@@<System headers@@>@@;
@@<Early module headers@@>@@;
@@<Module headers@@>@@;

@@<Module definitions@@>@@;
@@<Module types@@>@@;
@@<Module variables@@>@@;
@@<Module subroutines@@>@@;
@@<Subroutines@@>@@;
const char *jbmr_rcs_id = "$Id: jbmr.w,v 1.205 1999/01/14 21:44:05 neto Exp neto $";

@@ We will be using many routines from external libraries.  The interfaces
to those routines are described in the following headers.

@@<System headers@@>=
#include <stdio.h>
#if !defined(__USE_MISC)
#define __USE_MISC		/* Linux needs this to get the definition of |nrand48| */
#endif
#include <stdlib.h>
#include <stddef.h>
#include <limits.h>
#include "fixincludes.h"

@@ The exported interface is contained in the \file{jbmr.h} header file,
which has the following form.

@@(jbmr.h@@>=
extern const char *jbmr_rcs_id;
@@<Exported subroutines@@>@@;

@@ To ensure consistency between the interface and the implementation,
we include our own header.
@@<Module headers@@>=
#include "prng.h"
#include "jbmr.h"


@@ 
Up front, we know we'll need interfaces to
the error checking and memory allocation
modules, the |length_t| type (from 
\module{length}), the |cost| function (from \module{read}), and
the nearest 
neighbour lists |nn_list| (from \module{nn}).  We also want the
|incumbent_len| variable (from \module{lk}), which we will be modifying.

@@<Early module headers@@>=
#include "error.h"
#include "memory.h"
#include "length.h"