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.



The TSP is famous. In fact, so is the Lin-Kernighan heuristic. You should know about the references in my general research page.

Why now?

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.

Why should you be interested in my code?

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.)

Downloading LK

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.

David Neto

Back to David Neto's research page
Back to David Neto's home page