readme

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

This code is not yet suitable for inclusion in a library, as there are
a number of global structures that would have to be encapsulated.  It
will take some cleaning up and some rearchitecting before this
happens.  That's not a high priority for me right now.  I'd rather
finish my thesis.

There are a number of experimental coding techniques I tried for the
first time with this implementation.  Aside from scripts, all the
coding was done in CWEB.  That was just great from a developmental
point of view as the code almost entirely self-documenting.  However, I
took great stylistic liberties in coding tricks and techniques afforded
by CWEB's section-oriented programming model.  (As opposed to C's
function-oriented programming model.)  For instance, module jbmr.w is
over 4000 lines of CWEB, but it is almost entirely the implementation
of a single function, jbmr_run.  That module also extensively uses
multiple section nesting together with preprocessor tricks to weave
code together.  After cweave'ing, the resulting jbmr.c file is over
45000 lines long, with much of it effectively #ifdef'd out.  But still
it makes for a very large C function.  It's as if all the code were
inlined together.  I'm relying on the optimizer in the C compiler to do
a good job.  The code speed will likely be reduced on register-poor
architectures, and on machines with small instruction caches.

My initial intention was to run Lin-Kernighan in parallel, so I chose C
over C++ so that I could be assured of greater control over memory
allocation.  That's also why jbmr.w is coded as one big function:  all
the local variables are available with known local addresses, and they
wouldn't conflict with other processes running the same procedure. As a
side effect, this design saves indirection in accesses to local
variables.  If I knew I'd be running this code only in sequential mode,
then I might have used C++ instead.

Some distance functions are not yet implemented.  For example, I haven't
been able to validate my implementation of the GEO distance metric
from TSPLIB. (Fixed in lk-0.4.17/src/read.w.  We follow Concorde behaviour.)

Also, the kd-trees handle only 2-d instances.  3-d and beyond would not
be hard to implement.

Hash tables can be used for the tabu list and check in jbmr.w
and match.w.  But the distributions of tabu list lengths are so
skewed that you might want to stick to the plain linear time tabu check.
You choose at compile time between the two.

Yes, I know splay trees can be slow.  But I implemented my dictionaries
in terms of splay trees because I wanted to remind myself of the
details of the splay tree algorithms in preparation for implementing
the oriented tours based on splay trees.  I still haven't done that
implementation.  Also, early on I had some ideas about splay trees
relating to parallelism for Lin-Kernighan, but that has fallen by the
wayside in the meantime.

Also, I often write "declustering" when I mean "cluster compensation".
The latter is a better description of what is going on.

Yes, I know C++.  Perhaps not as well as I should.
C++ and its standard library was not finalized when I started this code.  
C++ environments were not complete or entirely compatible when I started this
code.  A C++ version of this code seems like a natural step.


Copyrights and Licences
=======================

David Neto is the author of LK and holds its copyright.  However, LK is
free software.   Since I intend LK to evolve into a library, I am
licensing it under the terms of the GNU Library General Public
License.  See the file COPYING.LIB in this directory.

In this distribution, the "preferred form of the work for making
modifications to it" is the .w file, not the .c and .h files.  The .c
and .h files are generated from the .w file by cweave (a CWEB tool).
The only exception is src/lkconfig.h, which is not generated from
a .w file.

In the interest of supporting forensic software engineering, I strongly
suggest that you also distribute the RCS files as I have.  At some
point in the future, this will likely become impractical, so I have not
included the RCS file as part of the "prefered editing form" of a
source file.  However, any source file derived from the RCS file is 
derived from the original standalone file, and hence is covered by 
my copyright and the associated license.

Each source file I have written contains the following notice.

   Copyright (C) 1994, 1995, 1996, 1997, 1998 David Neto

   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.

   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.

   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.

   You may contact David Neto via email at [e-mail], or with
   greater latency at
     Department of Computer Science
     University of Toronto
     10 King's College Rd.
     Toronto, Ontario
     M5S 3G4
     Canada 


Two source files in this distribution are exceptions:

Donald Knuth is the author of src/gb_flip.w, the random number generator 
of The Stanford GraphBase (ftp://labrea.stanford.edu/pub/sgb);
see also _The Stanford GraphBase: A platform for combinatorial computing_,
ISBN 0-201-54275-7, Addison-Wesley, 1993.  As per the copying terms,
gb_flip.w has not been changed from its original distribution.  Changes for
use in LK are made in gb_flip.ch and automatically incorporated by the 
CWEB tools.

Knuth (and perhaps others) is the author of the file cwebmac.tex in the
src directory.  It is required only if you want to typeset CWEB programs 
in that directory.  In that case, you may have to modify your TEXINPUTS 
environment variable so that TeX can find it.


References
==========

@phdthesis { Neto1999,
	fullauthor = "David~M.~Neto",
	author = "D.~M.~Neto",
	title = {Efficient Cluster Compensation For Lin-Kernighan Heuristics},
	school = {Department of Computer Science, University of Toronto},
	month = {May},
	year = 1999
}

@article { LinKernighan1973,
    author = "S.~Lin and B.~W.~Kernighan",
    title = {An effective heuristic algorithm for the traveling salesman
        problem},
    journal = "Operations Research",
    volume = 21,
    year = 1973,
    pages = "498--516"
}


@incollection { JohnsonMcGeoch1997,
    fullauthor = "David S.~Johnson and Lyle A.~McGeoch",
    author = "D.~S.~Johnson and L.~A.~McGeoch",
    title = {{The traveling salesman problem}:
            a case study},
    booktitle = {Local Search in Combinatorial Optimization},
    publisher = {John Wiley \& Sons},
    chapter = 8,
    year = 1997,
    fulleditor = {Emile Aarts and Jan Karel Lenstra},
    editor = {E.~Aarts and J.~K.~Lenstra},
    pages = "215--310",
    series = {Wiley Interscience series in discrete mathematics
        and optimziation}
}


@book { Knuth1993,
    fullauthor = "Donald~E.~Knuth",
    author = "D.~E.~Knuth",
    title = {The {Stanford} {GraphBase}: A Platform for
        Combinatorial Computing},
    publisher = "Addison-Wesley",
    year = 1993
}

@Article{SPE::BentleyM1993,
  title =        "Engineering a Sort Function",
  author =       "Jon Louis Bentley and M. Douglas McIlroy",
  journal =      "Software---Practice and Experience",
  pages =        "1249--1265",
  month =        nov,
  year =         "1993",
  volume =       "23",
  number =       "11",
}


@article{ FredmanJohnsonMcGeochOstheimer1995,
    author = {M.~L.~Fredman and D.~S.~Johnson and L.~A.~McGeoch and
        G.~Ostheimer},
    title = {Data structures for traveling salesmen},
    journal = {Journal of Algorithms},
    volume = 18,
    pages = "432--479",
    year = 1995
}


@article { Bentley1992,
    fullauthor = "Jon Louis Bentley",
    author = "J.~L.~Bentley",
    title = "Fast algorithms for geometric traveling salesman problems",
    journal = "ORSA Journal on Computing",
    volume = 4,
    number = 4,
    month = "Fall",
    year = 1992,
    pages = "387--411"
}

@InProceedings{Bentley90c,
  author =       "J. L. Bentley",
  title =        "{K}-d Trees for Semidynamic Point Sets",
  booktitle =    "Proceedings of the 6th Annual Symposium on
                 Computational Geometry",
  pages =        "187--197",
  month =        jun,
  year =         "1990",
}


@article { HeldKarp1970,
    fullauthor = "Michael Held and Richard Karp",
    author = "M.~Held and R.~Karp",
    title = "The Traveling Salesman Problem and Minimum Spanning Trees",
    journal = "Operations Research",
    volume = 18,
    pages = "1138--1162",
    year = 1970
}

@article { HeldKarp1971,
    fullauthor = "Michael Held and Richard Karp",
    author = "M.~Held and R.~Karp",
    title = {The Traveling Salesman Problem and Minimum Spanning Trees:
        Part {II}},
    journal = "Mathematical Programming",
    volume = 1,
    pages = "6--25",
    year = 1971
}


@InCollection{Schieber1993,
    fullauthor =   "Baruch Schieber",
    author =       "B.~Schieber",
    title =        "Parallel Lowest Common Ancestor Computation",
    booktitle =    "Synthesis of Parallel Algorithms",
    editor = "John H. Reif",
    publisher =   "Morgan Kaufmann",
    year =         "1993",
    chapter = "6",
    pages = "259--273"
}