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 ( G , c ) {\displaystyle (G,c)} 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 T ⊂ E ( G ) {\displaystyle T\subset \mathrm {E} (G)} and are looking for new tour T ′ ⊂ E ( G ) {\displaystyle T'\subset \mathrm {E} (G)} such that the symmetric difference F = T △ T ′ {\displaystyle F=T\mathbin {\triangle } T'} is not too large and the length ∑ e ∈ T ′ c ( e ) {\displaystyle \sum _{e\in T'}c(e)} of the new tour is less than the length ∑ e ∈ T c ( e ) {\displaystyle \sum _{e\in T}c(e)} of the current tour. Since F {\displaystyle F} is typically much smaller than T {\displaystyle T} and T ′ {\displaystyle T'} , it is convenient to consider the quantity
… excerpt ends here. Continue reading the full article.
