readme,v

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

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 netod@@acm.org, 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"
}

@


1.10
log
@light edits for version 0.4.20
@
text
@d1 4
a4 2
This is the README for lk-0.4.20.  
See ChangeLog for a summary of recent changes.
d10 1
a10 1
David Neto, netod@@acm.org, 1999/1/14
d43 5
a47 1
(I'm not finished my PhD!)
d230 5
a234 1
it as the standard of comparison.
d298 4
a301 4
Yes, I know about hash tables.  No I haven't used them.  
An obvious candidate for them is in jbmr.w, for use in doing the
tabu checking.  I suspect they might be more trouble than they are
worth, performance-wise.
d389 9
@


1.9
log
@0.4.10
@
text
@d1 1
a1 1
This is the README for lk-0.4.10.  
d8 1
a8 1
David Neto, netod@@acm.org, 1998/8/23
d72 4
a75 1
	LK 0.4.3deg
a76 1
Scripts for munging data and running experiments are in the script directory.
d119 1
a119 1
5.  I've written (most of) the code in a literate style.  I've used the
d283 1
a283 1
from TSPLIB.
d321 2
d328 1
a328 1
source file.  However, any source file derived from the RCS is 
@


1.8
log
@Update
@
text
@d1 1
a1 1
This is the README for lk-0.4.8.  
d8 1
a8 1
David Neto, netod@@acm.org, 1998/8/14
@


1.7
log
@Updated the date.
@
text
@d1 2
a2 1
This is the README for lk-0.4.3.
d8 1
a8 1
David Neto, netod@@acm.org, 1998/7/31
a21 1

@


1.6
log
@more expts mentioned
@
text
@d1 1
a1 1
This is the README for lk-0.4.0, the first public release of LK.
d7 1
a7 1
David Neto, netod@@acm.org, 1998/7/16
@


1.5
log
@Added more instructions about making the programs and suggested runs.
@
text
@d93 1
@


1.4
log
@Added a Tools section
@
text
@d13 1
d47 12
d62 30
a92 3
Mail suggestions and bug reports for LK to netod@@acm.org.  Please include
the version of `lk', which you can get by running `lk --version'.
If pertinent, include a pointer to sample inputs.
d94 2
a95 2
Programs jitter, shake, tspgen, and unifd are TSP instance generators.  
Unifd is completely trivial.  The others are the subject of active research.
d164 2
a165 2
automake.

@


1.3
log
@minor edits.
@
text
@d1 8
d14 1
d22 1
a25 2
This lk-0.4.0, the first public release of LK.

d76 6
a81 1
5.  Free software is a good thing.  By "free" I mean free to
d105 21
@


1.2
log
@Much better now.
Getting ready for public distribution.
@
text
@d134 3
d249 3
a251 1
source file.
@


1.1
log
@Initial revision
@
text
@a0 2
Program LK implements the Lin-Kernighan heuristic for the
symmetric traveling salesman problem (TSP).
d2 39
a40 22
See the famous 1973 paper (insert reference) by Shen Lin and Brian
Kernighan for the first description and motivation of this algorithm.
A more modern source is the chapter by Johnson and McGeoch (insert
reference); it describes the Lin-Kernighan algorithm in the context of
other local search algorithms for the TSP.

This implementation was written by David Neto for his doctoral work
at the University of Toronto.  It mostly follows the design outline
given by Johnson and McGeoch for the implementation due to Johnson,
Bentley, McGeoch and Rothberg (JBMR), and is tuned for two-dimensional
Euclidean instances.  It implements the algorithmic innovation described
in Neto's doctoral dissertation, Efficient Declustering for Augmenting
Path Heuristics (working title), 1998 (expected).  This innovation makes
the algorithm more robust in the face of clustered data.

This implementation is about twice as slow as the JBMR implementation.
For example, in about 2 CPU hours it can find near-optimal tours for
million-city instances.  (One SGI Challenge 150MHz MIPS R4400 processor;
using about 250MB of RAM; a million cities drawn randomly from a
uniform distribution over the unit square; distance between cities is
the Euclidean distance; within 2% of optimal, or 2.5% above the expected
Held-Karp bound.)
d42 3
d46 2
a47 1
(list publications, if any)
d50 211
a260 1
See the file INSTALL for compilation and installation instructions.
d262 13
a275 3
Mail suggestions and bug reports for LK to netod@@acm.org.  Please include
the version of `lk', which you can get by running `lk --version'.
If pertinent, include a pointer to sample inputs.
d277 1
a277 1
------
d279 1
a279 1
Donald Knuth is the author of gb_flip.w, the random number generator 
d282 4
a285 1
ISBN 0-201-54275-7, Addison-Wesley, 1993.
a291 4
David Neto is the author of LK and holds the copyright for it.
However, it is free software, containing the following notice in each
source file.  (The GNU General Public License, version 2, is included
in this distribution as the file COPYING.)
d293 2
d296 116
a411 11
   Copyright (C) 1994, 1995, 1996, 1997 David Neto

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

   This program 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 General Public License for more details.
a412 4
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
   02111-1307, USA.
@