In combinatorial optimization, Lin–Kernighan is one of the best heuristics for solving the symmetric travelling salesman problem. It belongs to the class of local search algorithms, which take a tour (Hamiltonian cycle) as part of the input and attempt to improve it by searching in the neighbourhood of the given tour for one that is shorter, and upon finding one repeats the process from that new one, until encountering a local minimum. As in the case of the related 2-opt and 3-opt algorithms, the relevant measure of "distance" between two tours is the number of edges which are in one but not the other; new tours are built by reassembling pieces of the old tour in a different order, sometimes changing the direction in which a sub-tour is traversed. Lin–Kernighan is adaptive and has no fixed number of edges to replace at a step, but favours small numbers such as 2 or 3.
Derivation
For a given instance of the travelling salesman problem, tours are uniquely determined by their sets of edges, so we may as well encode them as such. In the main loop of the local search, we have a current tour and are looking for new tour such that the symmetric difference is not too large and the length of the new tour is less than the length of the current tour. Since is typically much smaller than and , it is convenient to consider the quantity — the gain of using when switching from — since : how much longer the current tour is than the new tour . Naively -opt can be regarded as examining all with exactly elements ( in but not in , and another in but not in ) such that is again a tour, looking for such a set which has . It is however easier to do those tests in the opposite order: first search for plausible with positive gain, and only second check if is in fact a tour.
Define a trail in to be alternating (with respect to ) if its edges are alternatingly in and not in , respectively. Because the subgraphs and are -regular, the subgraph will have vertices of degree , , and only, and at each vertex there are as many incident edges from as there are from . Hence (essentially by Hierholzer's algorithm for finding Eulerian circuits) the graph decomposes into closed alternating trails. Sets that may satisfy for some tour may thus be found by enumerating closed alternating trails in , even if not every closed alternating trail makes into a tour; it could alternatively turn out to be a disconnected -regular subgraph.
Key idea
Alternating trails (closed or open) are built by extending a shorter alternating trail, so when exploring the neighbourhood of the current tour , one is exploring a search tree of alternating trails. The key idea of the Lin–Kernighan algorithm is to remove from this tree all alternating trails which have gain . This does not prevent finding every closed trail with positive gain, thanks to the following lemma.
Lemma. If are numbers such that , then there is a cyclic permutation of these numbers such that all partial sums are positive as well, i.e., there is some such that for all .
For a closed alternating trail , one may define if and if ; the sum is then the gain . Here the lemma implies that there for every closed alternating trail with positive gain exists at least one starting vertex for which all the gains of the partial trails are positive as well, so will be found when the search explores the branch of alternating trails starting at . (Prior to that the search may have considered other subtrails of starting at other vertices but backed out because some subtrail failed the positive gain constraint.) Reducing the number of branches to explore translates directly to a reduction in runtime, and the sooner a branch can be pruned, the better.
This yields the following algorithm for finding all closed, positive gain alternating trails in the graph.
State: a stack of triples , where is a vertex, is the current number of edges in the trail, and is the current trail gain. For all , push onto the stack. While the stack is nonempty: Pop off the stack and let . The current alternating trail is now . If is even then: For each such that (there are at most two of these), push onto the stack. If instead is odd then: If then report as a closed alternating trail with gain . For each such that and (there may be of these, or there could be none), push onto the stack. Stop