jbmr.w,v

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

1.113
date	96.08.07.15.33.50;	author neto;	state Exp;
branches;
next	1.112;

1.112
date	96.08.07.15.18.44;	author neto;	state Exp;
branches;
next	1.111;

1.111
date	96.07.29.17.09.07;	author neto;	state Exp;
branches;
next	1.110;

1.110
date	96.07.29.16.19.50;	author neto;	state Exp;
branches;
next	1.109;

1.109
date	96.07.25.13.30.36;	author neto;	state Exp;
branches;
next	1.108;

1.108
date	96.07.05.18.18.46;	author david;	state Exp;
branches;
next	1.107;

1.107
date	96.06.28.12.18.42;	author neto;	state Exp;
branches;
next	1.106;

1.106
date	96.06.24.16.18.01;	author neto;	state Exp;
branches;
next	1.105;

1.105
date	96.06.20.16.11.58;	author neto;	state Exp;
branches;
next	1.104;

1.104
date	96.06.19.14.12.31;	author neto;	state Exp;
branches;
next	1.103;

1.103
date	96.06.04.12.41.58;	author neto;	state Exp;
branches;
next	1.102;

1.102
date	96.06.03.15.36.34;	author neto;	state Exp;
branches;
next	1.101;

1.101
date	96.05.31.17.07.05;	author neto;	state Exp;
branches;
next	1.100;

1.100
date	96.05.29.11.13.12;	author neto;	state Exp;
branches;
next	1.47;

1.47
date	96.05.28.11.52.53;	author neto;	state Exp;
branches;
next	1.46;

1.46
date	96.05.24.17.44.11;	author neto;	state Exp;
branches;
next	1.45;

1.45
date	96.05.23.14.49.36;	author neto;	state Exp;
branches;
next	1.44;

1.44
date	96.05.23.12.17.25;	author neto;	state Exp;
branches;
next	1.43;

1.43
date	96.05.23.11.46.44;	author neto;	state Exp;
branches;
next	1.42;

1.42
date	96.05.22.17.22.09;	author neto;	state Exp;
branches;
next	1.41;

1.41
date	96.05.22.16.40.22;	author neto;	state Exp;
branches;
next	1.40;

1.40
date	96.05.22.16.34.08;	author neto;	state Exp;
branches;
next	1.39;

1.39
date	96.05.22.15.49.08;	author neto;	state Exp;
branches;
next	1.38;

1.38
date	96.05.22.15.46.34;	author neto;	state Exp;
branches;
next	1.37;

1.37
date	96.05.22.15.39.12;	author neto;	state Exp;
branches;
next	1.36;

1.36
date	96.05.22.14.36.46;	author neto;	state Exp;
branches;
next	1.35;

1.35
date	96.05.22.14.16.14;	author neto;	state Exp;
branches;
next	1.34;

1.34
date	96.05.22.13.38.10;	author neto;	state Exp;
branches;
next	1.33;

1.33
date	96.05.21.13.55.57;	author neto;	state Exp;
branches;
next	1.32;

1.32
date	96.05.21.13.30.11;	author neto;	state Exp;
branches;
next	1.31;

1.31
date	96.05.21.12.49.15;	author neto;	state Exp;
branches;
next	1.30;

1.30
date	96.05.21.12.24.30;	author neto;	state Exp;
branches;
next	1.29;

1.29
date	96.05.16.15.42.54;	author neto;	state Exp;
branches;
next	1.28;

1.28
date	96.05.16.15.31.15;	author neto;	state Exp;
branches;
next	1.27;

1.27
date	96.05.16.15.25.20;	author neto;	state Exp;
branches;
next	1.26;

1.26
date	96.05.16.15.10.02;	author neto;	state Exp;
branches;
next	1.25;

1.25
date	96.05.16.15.01.20;	author neto;	state Exp;
branches;
next	1.24;

1.24
date	96.05.16.13.40.09;	author neto;	state Exp;
branches;
next	1.23;

1.23
date	96.05.16.12.58.26;	author neto;	state Exp;
branches;
next	1.22;

1.22
date	96.05.16.12.47.18;	author neto;	state Exp;
branches;
next	1.21;

1.21
date	96.05.16.12.36.15;	author neto;	state Exp;
branches;
next	1.20;

1.20
date	96.05.16.12.03.39;	author neto;	state Exp;
branches;
next	1.19;

1.19
date	96.05.16.11.55.45;	author neto;	state Exp;
branches;
next	1.18;

1.18
date	96.05.15.14.55.21;	author neto;	state Exp;
branches;
next	1.17;

1.17
date	96.05.15.14.28.10;	author neto;	state Exp;
branches;
next	1.16;

1.16
date	96.05.15.14.00.11;	author neto;	state Exp;
branches;
next	1.15;

1.15
date	96.05.15.13.54.06;	author neto;	state Exp;
branches;
next	1.14;

1.14
date	96.05.15.13.17.34;	author neto;	state Exp;
branches;
next	1.13;

1.13
date	96.05.14.17.49.26;	author neto;	state Exp;
branches;
next	1.12;

1.12
date	96.05.14.17.20.56;	author neto;	state Exp;
branches;
next	1.11;

1.11
date	96.05.14.17.20.11;	author neto;	state Exp;
branches;
next	1.10;

1.10
date	96.05.14.17.18.58;	author neto;	state Exp;
branches;
next	1.9;

1.9
date	96.05.14.17.18.07;	author neto;	state Exp;
branches;
next	1.8;

1.8
date	96.05.14.17.10.07;	author neto;	state Exp;
branches;
next	1.7;

1.7
date	96.05.14.16.40.20;	author neto;	state Exp;
branches;
next	1.6;

1.6
date	96.05.14.16.24.51;	author neto;	state Exp;
branches;
next	1.5;

1.5
date	96.05.13.16.51.10;	author neto;	state Exp;
branches;
next	1.4;

1.4
date	96.04.29.16.26.17;	author neto;	state Exp;
branches;
next	1.3;

1.3
date	96.03.15.15.59.43;	author neto;	state Exp;
branches;
next	1.2;

1.2
date	96.03.12.15.58.35;	author neto;	state Exp;
branches;
next	1.1;

1.1
date	96.03.04.13.53.58;	author neto;	state Exp;
branches;
next	;


desc
@My implementation of the Johnson, Bentley, McGeoch, and Rothberg version
of the Lin-Kernighan algorithm.
@


1.206
log
@Fixed memory corruption bug: resizing change_log was incorrect.
@
text
@

   
\noindent Copyright \copyright 1994, 1995, 1996, 1997, 1998 David Neto
\smallskip

\noindent 
   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Library General Public
   License as published by the Free Software Foundation; either
   version 2 of the License, or (at your option) any later version.
\smallskip

\noindent 
   This library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Library General Public License for more details.
\smallskip

\noindent   
   You should have received a copy of the GNU Library General Public
   License along with this library; if not, write to the
   Free Software Foundation, Inc., 59 Temple Place - Suite 330,
   Boston, MA  02111-1307, USA.
\smallskip

\noindent   
   You may contact David Neto via email at {\tt netod@@@@acm.org}, or with
   greater latency at
\smallskip
\noindent{\obeylines
     Department of Computer Science
     University of Toronto
     10 King's College Rd.
     Toronto, Ontario
     M5S 3G4
     Canada
}
\medskip


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

{\obeylines
$Log: jbmr.w,v $
Revision 1.205  1999/01/14 21:44:05  neto
Fixed the test on max index to write for probe and move depths.

Revision 1.204  1999/01/14 18:48:26  neto
Report 0 depths that have non-zero depths after them.
This is so we can get fair graphs in all cases.

Revision 1.203  1998/10/02 19:14:06  neto
Use external modules for milestone checking.

Revision 1.202  1998/08/29 19:54:39  neto
When doing cluster compensation, change the rejection test:
	cum2 < clust dist + bestgain
to the inclusive inequality:
	cum2 <= clust dist + bestgain.
I was having problems when cum2>0 and clustdist=cum2 and bestgain=0.
Then it would catch itself in Go deeper, knowing it should not be
proceeding.

I also simplified the search for the maximum in Go deeper.  We already
know there is an element that is valid (and positive), so we take it
as the start value in the max over the list.  That should speed things
a wee bit.

Revision 1.201  1998/08/21 17:24:12  neto
Get rid of warning about useless LHS of comma op.
Added a joke. (check the index)

Revision 1.200  1998/08/20 17:50:02  neto
Slightly better literature references.
Added TABU HASH functionality
Corrected long-standing stupidities with verbose printing in Iterated LK case.

Revision 1.199  1998/08/14 18:01:33  neto
Now no extra backtrack means at most 1, not at most 2.
(I bungled the mod slightly last time.)
Must try to compile this.

Revision 1.198  1998/08/09 21:42:09  neto
Slightly better handling of probe and move depths tracking arrays.

Revision 1.197  1998/08/08 15:29:32  neto
Implement the shortcut in backtracking at level BL==2

Revision 1.196  1998/08/07 22:35:39  neto
Factored out the dirty set work to module dirty.

Revision 1.195  1998/08/07 22:10:24  neto
Intermediate stage of adding active set (i.e. dirty set) queues.

Revision 1.194  1998/08/06 20:21:54  neto
I forgot to mention that I added postscript figures to the scheme array.
I hope it helps...

Revision 1.193  1998/08/06 20:11:47  neto
Added year to my "see my research notes" comments.
1996 is a long time ago...

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

Revision 1.191  1998/05/23 16:49:20  neto
Change bound value to lower bound value, etc.

Revision 1.190  1998/05/09 22:51:39  neto
Give two decimal points in milestones.

Revision 1.189  1998/02/27 21:40:36  neto
Lowered verbose level of end of LK step.
Fixed CWEB syntax of printing double bridge edge section.

Revision 1.188  1998/02/27 19:43:14  neto
Made printing for iterated Lin-Kernighan respect verbose rules.

Revision 1.187  1998/02/26 21:37:37  neto
Fixed an old bug!  Wasn't checking tabu condition in generic search for
the new edge to be removed being the new edge being proposed to be added.
Fixed a bug in reverting code: must use tour flip arb instead of just
tour flip.
Fixed a conceptual bug: the change log must also encode the scheme id
used in that improvement, and the reverting must undo those scheme changes.
Removed some debugging output.
Implement the double-bridge mutation in three flips instead of four.

This seems to work.  Now I'll remove some of the debugging output.

Revision 1.186  1998/02/21 04:04:36  neto
Added most of the support for Iterated Lin-Kernighan.

Revision 1.185  1998/01/24  20:47:43  neto
Fixed comment on CAREFUL OP

Revision 1.184  1997/11/07  22:35:57  neto
Added verbose message to say when we hit the max depth.
Adjusted verbose values so less is printed at 50.

Revision 1.183  1997/11/06  22:47:54  neto
I wasn't marking cities dirty for 4-changes or lambda-changes!
Ouch.

Revision 1.182  1997/10/18 18:08:13  neto
Convert to new neighbour list protocol.

Revision 1.181  1997/10/17  21:50:10  neto
Show Start and end milestones, and times for preprocessing as well.

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

Revision 1.179  1997/09/12  21:52:46  neto
Don't cause a seg fault in my verbose output: I was calling decluster d
even when I hadn't built the data structures!

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

Revision 1.177  1997/07/02  20:48:23  neto