In combinatorial optimization, Lin–Kernighan is one of the best heuristics for solving the symmetric travelling salesman problem.
[citation needed] 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.
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
It is however easier to do those tests in the opposite order: first search for plausible
Hence (essentially by Hierholzer's algorithm for finding Eulerian circuits) the graph
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.
, then there is a cyclic permutation of these numbers such that all partial sums are positive as well, i.e., there is some
Here the lemma implies that there for every closed alternating trail with positive gain exists at least one starting vertex
will be found when the search explores the branch of alternating trails starting at
starting at other vertices but backed out because some subtrail failed the positive gain constraint.)
This yields the following algorithm for finding all closed, positive gain alternating trails in the graph.
As an enumeration algorithm this is slightly flawed, because it may report the same trail multiple times, with different starting points, but Lin–Kernighan does not care because it mostly aborts the enumeration after finding the first hit.
, and the final round of the algorithm may have to check all of them before concluding that the current tour is locally optimal, we get
in the average overall running time for their algorithm, but other implementors have had trouble reproducing that result.
[2] In terms of a stack as above, the algorithm is: The length of the alternating trails considered are thus not explicitly bounded, but beyond the backtracking depth
no more than one way of extending the current trail is considered, which in principle stops those explorations from raising the exponent in the runtime complexity.
The closed alternating trails found by the above method are all connected, but the symmetric difference
The literature on the Lin–Kernighan heuristic uses the term sequential exchanges for those that are described by a single alternating trail.
In at least one implementation by Lin & Kernighan there was an extra final step considering such non-sequential exchanges of 4 edges before declaring a tour locally optimal, which would mean the tours produced are 4-opt unless one introduces further constraints on the search (which Lin and Kernighan in fact did).
The literature is vague on exactly what is included in the Lin–Kernighan heuristic proper, and what constitutes further refinements.
For the asymmetric TSP, the idea of using positive gain alternating trails to find favourable exchanges is less useful, because there are fewer ways in which pieces of a tour can be rearranged to yield new tours when one may not reverse the orientation of a piece.
Three pieces can be patched together to form a different tour in one way only, and the corresponding alternating trail does not extend to a closed trail for rearranging four pieces into a new tour.
at two points: obviously when deciding whether a better tour has been found, but also as a constraint to descending in the search tree, as controlled via the infeasibility depth
If naively posing this subproblem as giving a subroutine the set of
as the time complexity for this check, since it is necessary to walk around the full tour before being able to determine that it is in fact a Hamiltonian cycle.
If keeping track of more information, the test can instead be carried out in constant time.
A useful degree of freedom here is that one may choose the order in which step 2.3.2 iterates over all vertices; in particular, one may follow the known tour
is concerned, the outcome of this test can be inherited information rather than something that has to be computed fresh.