LK the program
Updated September 17, 2000
New (September 17, 2000): lk-0.5.0 is released with two bug fixes, one affecting only large runs.
New (October 22, 1998): lk-0.4.17 is released.
New (September 7, 1998): Added a list of some of the
known BUGS
New (August 23, 1998): lk-0.4.10 is released.
New (July 31, 1998): lk-0.4.3 is released.
New (July 23, 1998): Mention Held-Karp, give sample of
code in DVI form, and give output of lk --help
Created July 16, 1998
This is the home page for LK, a free and Open Source(tm)
implementation of the
Lin-Kernighan heuristic for the Traveling Salesman Problem (TSP)
and the minimum weight perfect matching problem.
This is one product of my research over the last few years.
Contents
Background
The TSP is famous.
In fact, so is the Lin-Kernighan heuristic.
You should know about the
references in my general
research page.
I've been planning all along to release my code to the world.
But I was prompted to do it now by the announcement
of the
source code release of Concorde.
That announcement came at the tail end of William Cook's excellent
invited talk on the TSP at the SIAM Discrete Math'98 conference in
Toronto.
Note: the Concorde software is probably faster than my code. I haven't
looked at or tested the Concorde software yet.
- It incorporates ``efficient cluster compensation'', an algorithmic
innovation designed to make Lin-Kernighan more robust in the face of
clustered inputs.
- It's free.
- It's a
literate program written using
the CWEB
toolset. As an example, the module implementing Held and Karp's
Lagrangean 1-tree relaxation for the TSP is
available in DVI form (61112 bytes).
(Module ascend was modified
a lot for lk-0.4.17. I have not updated this dvi file with the changes.)
- It's efficient enough to tackle large instances. The LK optimization
code has tackled million-city geometric instances.
For more details, see the
README
or
ChangeLog
files
for the software distribution. Also, you may be interested in the
output of lk --help.
Version lk-0.5.0 fixes some bugs from lk-0.4.17.
Here's the updated list of BUGS.
(Actually, there are just feature requests now.)
LK is free software.
It is licensed under the GNU
Library General Public
License.
I intend to eventually encapsulate it as a library, so the LGPL seems
appropriate.
The latest public release is LK 0.5.0, from 2000/9/17, the first since
I completed my PhD:
As always, you can get the first public release of LK:
Send feedback to me via email at neto at cs utoronto dot ca,
even if you only try it out.
Note that I am in the midst of writing my doctoral dissertation, so
development has slowed down accordingly. Also, I work part time in
industry on completely unrelated things.
Enjoy!
David Neto
Back to David Neto's research page
Back to David Neto's home page