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.
I've been planning all along to release my code to the world.
But I was prompted to do it now by the announcement
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
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?
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
I intend to eventually encapsulate it as a library, so the LGPL seems
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.