Lin–Kernighan heuristic

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 [math]\displaystyle{ (G,c) }[/math] 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 [math]\displaystyle{ T \subset \mathrm{E}(G) }[/math] and are looking for new tour [math]\displaystyle{ T' \subset \mathrm{E}(G) }[/math] such that the symmetric difference [math]\displaystyle{ F = T \mathbin{\triangle} T' }[/math] is not too large and the length [math]\displaystyle{ \sum_{e \in T'} c(e) }[/math] of the new tour is less than the length [math]\displaystyle{ \sum_{e \in T} c(e) }[/math] of the current tour. Since [math]\displaystyle{ F }[/math] is typically much smaller than [math]\displaystyle{ T }[/math] and [math]\displaystyle{ T' }[/math], it is convenient to consider the quantity

[math]\displaystyle{ g(F) = \sum_{e \in F \cap T} c(e) - \sum_{e \in F \setminus T} c(e) \quad }[/math] — the gain of using [math]\displaystyle{ F \subseteq \mathrm{E}(G) }[/math] when switching from [math]\displaystyle{ T }[/math] —

since [math]\displaystyle{ g(T \mathbin{\triangle} T') = \sum_{e \in T} c(e) - \sum_{e \in T'} c(e) }[/math]: how much longer the current tour [math]\displaystyle{ T }[/math] is than the new tour [math]\displaystyle{ T' }[/math]. Naively [math]\displaystyle{ k }[/math]-opt can be regarded as examining all [math]\displaystyle{ F \subseteq \mathrm{E}(G) }[/math] with exactly [math]\displaystyle{ 2k }[/math] elements ([math]\displaystyle{ k }[/math] in [math]\displaystyle{ T }[/math] but not in [math]\displaystyle{ T' }[/math], and another [math]\displaystyle{ k }[/math] in [math]\displaystyle{ T' }[/math] but not in [math]\displaystyle{ T }[/math]) such that [math]\displaystyle{ T \mathbin{\triangle} F }[/math] is again a tour, looking for such a set which has [math]\displaystyle{ g(F) \gt 0 }[/math]. It is however easier to do those tests in the opposite order: first search for plausible [math]\displaystyle{ F }[/math] with positive gain, and only second check if [math]\displaystyle{ T \mathbin{\triangle} F }[/math] is in fact a tour.

Define a trail in [math]\displaystyle{ G }[/math] to be alternating (with respect to [math]\displaystyle{ T }[/math]) if its edges are alternatingly in [math]\displaystyle{ T }[/math] and not in [math]\displaystyle{ T }[/math], respectively. Because the subgraphs [math]\displaystyle{ \bigl( \mathrm{V}(G),T \bigr) }[/math] and [math]\displaystyle{ \bigl( \mathrm{V}(G),T' \bigr) }[/math] are [math]\displaystyle{ 2 }[/math]-regular, the subgraph [math]\displaystyle{ G[T \mathbin{\triangle} T'] = \bigl( \mathrm{V}(G),T \mathbin{\triangle} T'\bigr) }[/math] will have vertices of degree [math]\displaystyle{ 0 }[/math], [math]\displaystyle{ 2 }[/math], and [math]\displaystyle{ 4 }[/math] only, and at each vertex there are as many incident edges from [math]\displaystyle{ T }[/math] as there are from [math]\displaystyle{ T' }[/math]. Hence (essentially by Hierholzer's algorithm for finding Eulerian circuits) the graph [math]\displaystyle{ G[T \mathbin{\triangle} T'] }[/math] decomposes into closed alternating trails. Sets [math]\displaystyle{ F \subseteq \mathrm{E}(G) }[/math] that may satisfy [math]\displaystyle{ F = T \mathbin{\triangle} T' }[/math] for some tour [math]\displaystyle{ T' }[/math] may thus be found by enumerating closed alternating trails in [math]\displaystyle{ G }[/math], even if not every closed alternating trail [math]\displaystyle{ F }[/math] makes [math]\displaystyle{ T \mathbin{\triangle} F }[/math] into a tour; it could alternatively turn out to be a disconnected [math]\displaystyle{ 2 }[/math]-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 [math]\displaystyle{ T }[/math], 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 [math]\displaystyle{ \leq 0 }[/math]. This does not prevent finding every closed trail with positive gain, thanks to the following lemma.

Lemma. If [math]\displaystyle{ a_0,\dotsc,a_{n-1} }[/math] are numbers such that [math]\displaystyle{ \sum_{i=0}^{n-1} a_i \gt 0 }[/math], then there is a cyclic permutation of these numbers such that all partial sums are positive as well, i.e., there is some [math]\displaystyle{ k }[/math] such that

[math]\displaystyle{ \sum_{i=0}^r a_{(k+i) \bmod n} \gt 0 }[/math] for all [math]\displaystyle{ r=0,1,\dotsc,n-1 }[/math].

For a closed alternating trail [math]\displaystyle{ F = e_0 \, e_1 \, \dots \, e_{n-1} }[/math], one may define [math]\displaystyle{ a_i = c(e_i) }[/math] if [math]\displaystyle{ e_i \in T }[/math] and [math]\displaystyle{ a_i = -c(e_i) }[/math] if [math]\displaystyle{ e_i \notin T }[/math]; the sum [math]\displaystyle{ \sum\nolimits_{i=0}^{n-1} a_i }[/math] is then the gain [math]\displaystyle{ g(F) }[/math]. Here the lemma implies that there for every closed alternating trail with positive gain exists at least one starting vertex [math]\displaystyle{ v_0 }[/math] for which all the gains of the partial trails are positive as well, so [math]\displaystyle{ F }[/math] will be found when the search explores the branch of alternating trails starting at [math]\displaystyle{ v_0 }[/math]. (Prior to that the search may have considered other subtrails of [math]\displaystyle{ F }[/math] 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 [math]\displaystyle{ (u,i,g) }[/math], where [math]\displaystyle{ u \in \mathrm{V}(G) }[/math] is a vertex, [math]\displaystyle{ i \geq 0 }[/math] is the current number of edges in the trail, and [math]\displaystyle{ g }[/math] is the current trail gain.

1. For all [math]\displaystyle{ u \in \mathrm{V}(G) }[/math], push [math]\displaystyle{ (u,0,0) }[/math] onto the stack.
2. While the stack is nonempty:
   1. Pop [math]\displaystyle{ (u,i,g) }[/math] off the stack and let [math]\displaystyle{ v_i := u }[/math]. The current alternating trail is now [math]\displaystyle{ F = \{ v_0 v_1, v_1 v_2, \dotsc, v_{i-1} v_i \} }[/math].
   2. If [math]\displaystyle{ i }[/math] is even then:

      For each [math]\displaystyle{ u \in \mathrm{V}(G) }[/math] such that [math]\displaystyle{ v_i u \in T \setminus \{ v_0 v_1, v_1 v_2, \dotsc, v_{i-1} v_i \} }[/math] (there are at most two of these), push [math]\displaystyle{ \bigl( u, i+1, g+c(v_i u) \bigr) }[/math] onto the stack.

   3. If instead [math]\displaystyle{ i }[/math] is odd then:
      1. If [math]\displaystyle{ g \gt c(v_i v_0) }[/math] then report [math]\displaystyle{ \{ v_0 v_1, v_1 v_2, \dotsc, v_{i-1} v_i, v_i v_0 \} }[/math] as a closed alternating trail with gain [math]\displaystyle{ g - c(v_i v_0) \gt 0 }[/math].
      2. For each [math]\displaystyle{ u \in \mathrm{V}(G) }[/math] such that [math]\displaystyle{ g \gt c(v_i u) }[/math] and [math]\displaystyle{ v_i u \notin T \cup \{ v_0 v_1, v_1 v_2, \dotsc, v_{i-1} v_i \} }[/math] (there may be [math]\displaystyle{ O(n) }[/math] of these, or there could be none), push [math]\displaystyle{ \bigl( u, i+1, g-c(v_i u) \bigr) }[/math] onto the stack.
3. Stop

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. It should however be remarked that:

• Lin–Kernighan is not satisfied with just having found a closed alternating trail [math]\displaystyle{ F }[/math] of positive gain, it additionally requires that [math]\displaystyle{ T \mathbin{\triangle} F }[/math] is a tour.
• Lin–Kernighan also restricts the search in various ways, most obviously regarding the search depth (but not only in that way). The above unrestricted search still terminates because at [math]\displaystyle{ i = 2n }[/math] there is no longer any unpicked edge remaining in [math]\displaystyle{ T }[/math], but that is far beyond what is practical to explore.
• In most iterations one wishes to quickly find a better tour [math]\displaystyle{ T' }[/math], so rather than actually listing all siblings in the search tree before exploring the first of them, one may wish to generate these siblings lazily.

Basic Lin–Kernighan algorithm

The basic form of the Lin–Kernighan algorithm not only does a local search counterpart of the above enumeration, but it also introduces two parameters that narrow the search.

• The backtracking depth [math]\displaystyle{ p_1 }[/math] is an upper bound on the length of the alternating trail after backtracking; beyond this depth, the algorithm explores at most one way of extending the alternating trail. Standard value is that [math]\displaystyle{ p_1 = 5 }[/math].
• The infeasibility depth [math]\displaystyle{ p_2 }[/math] is an alternating path length beyond which it begins to be required that closing the current trail (regardless of the gain of doing so) yields an exchange to a new tour. Standard value is that [math]\displaystyle{ p_2 = 2 }[/math].

Because there are [math]\displaystyle{ O( n^{\lfloor p_1/2 \rfloor} ) }[/math] alternating trails of length [math]\displaystyle{ p_1 }[/math], 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 [math]\displaystyle{ \lfloor p_1/2 \rfloor }[/math] (standard value [math]\displaystyle{ 2 }[/math]) as a lower bound on the exponent of the algorithm complexity. Lin & Kernighan report [math]\displaystyle{ 2.2 }[/math] as an empirical exponent of [math]\displaystyle{ n }[/math] in the average overall running time for their algorithm, but other implementors have had trouble reproducing that result. It appears unlikely that the worst-case running time is polynomial.

In terms of a stack as above, the algorithm is:

Input: an instance [math]\displaystyle{ (G,c) }[/math] of the travelling salesman problem, and a tour [math]\displaystyle{ T \subset \mathrm{E}(G) }[/math]

Output: a locally optimal tour

Variables:

a stack of triples [math]\displaystyle{ (u,i,g) }[/math], where [math]\displaystyle{ u \in \mathrm{V}(G) }[/math] is a vertex, [math]\displaystyle{ i \geq 0 }[/math] is the current number of edges in the trail, and [math]\displaystyle{ g }[/math] is the current trail gain,

the sequence [math]\displaystyle{ v_0, v_1, \dotsc }[/math] of vertices in the current alternating trail,

the best set [math]\displaystyle{ F }[/math] of exchange edges found for current tour, and its corresponding gain [math]\displaystyle{ g^* }[/math].

Initialise the stack to being empty.

Repeat

Set [math]\displaystyle{ g^* := 0 }[/math] and [math]\displaystyle{ F := \varnothing }[/math].

For all [math]\displaystyle{ u \in \mathrm{V}(G) }[/math], push [math]\displaystyle{ (u,0,0) }[/math] onto the stack.

While the stack is nonempty:

Pop [math]\displaystyle{ (u,i,g) }[/math] off the stack and let [math]\displaystyle{ v_i := u }[/math].

If [math]\displaystyle{ i }[/math] is even then

for each [math]\displaystyle{ u \in \mathrm{V}(G) }[/math] such that [math]\displaystyle{ v_i u \in T \setminus \{ v_0 v_1, v_1 v_2, \dotsc, v_{i-1} v_i \} }[/math],

push [math]\displaystyle{ \bigl( u, i+1, g+c(v_i u) \bigr) }[/math] onto the stack if: [math]\displaystyle{ i \leq p_2 }[/math], or [math]\displaystyle{ u v_0 \notin T \cup \{ v_0 v_1, v_1 v_2, \dotsc, v_{i-1} v_i, v_i u \} }[/math] and [math]\displaystyle{ T \mathbin{\triangle} \{ v_0 v_1, v_1 v_2, \dotsc, v_{i-1} v_i, v_i u, u v_0 \} }[/math] is a tour (Hamiltonicity check)

else ([math]\displaystyle{ i }[/math] is odd):

If [math]\displaystyle{ g \gt c(v_i v_0) }[/math], [math]\displaystyle{ g - c(v_i v_0) \gt g^* }[/math], and [math]\displaystyle{ T \mathbin{\triangle} \{ v_0 v_1, v_1 v_2, \dotsc, v_{i-1} v_i, v_i v_0 \} }[/math] is a tour (Hamiltonicity check) then let [math]\displaystyle{ F := \{ v_0 v_1, v_1 v_2, \dotsc, v_{i-1} v_i, v_i v_0 \} }[/math] and [math]\displaystyle{ g^* := g - c(v_i v_0) }[/math].

For each [math]\displaystyle{ u \in \mathrm{V}(G) }[/math] such that [math]\displaystyle{ g \gt c(v_i u) }[/math] and [math]\displaystyle{ v_i u \notin T \cup \{ v_0 v_1, v_1 v_2, \dotsc, v_{i-1} v_i \} }[/math], push [math]\displaystyle{ \bigl( u, i+1, g-c(v_i u) \bigr) }[/math] onto the stack.

End if.

Let [math]\displaystyle{ (u,j,g) }[/math] be the top element on the stack (peek, not pop). If [math]\displaystyle{ i \leq j }[/math] then

if [math]\displaystyle{ g^* \gt 0 }[/math] then

set [math]\displaystyle{ T := T \mathbin{\triangle} F }[/math] (update current tour) and clear the stack.

else if [math]\displaystyle{ i \gt p_1 }[/math] then

pop all elements [math]\displaystyle{ (u,j,g) }[/math] off the stack that have [math]\displaystyle{ j \gt p_1 }[/math]

end if

end if

end while

until [math]\displaystyle{ g^*=0 }[/math].

Return [math]\displaystyle{ T }[/math]

The length of the alternating trails considered are thus not explicitly bounded, but beyond the backtracking depth [math]\displaystyle{ p_1 }[/math] 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.

Limitations

The closed alternating trails found by the above method are all connected, but the symmetric difference [math]\displaystyle{ T \mathbin{\triangle} T' }[/math] of two tours need not be, so in general this method of alternating trails cannot explore the full neighbourhood of a trail [math]\displaystyle{ T }[/math]. The literature on the Lin–Kernighan heuristic uses the term sequential exchanges for those that are described by a single alternating trail. The smallest non-sequential exchange would however replace 4 edges and consist of two cycles of 4 edges each (2 edges added, 2 removed), so it is long compared to the typical Lin–Kernighan exchange, and there are few of these compared to the full set of 4-edge exchanges.

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. Two pieces can only be patched together to reproduce the original tour. 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. To rearrange four pieces, one needs a non-sequential exchange.

Checking Hamiltonicity

The Lin–Kernighan heuristic checks the validity of tour candidates [math]\displaystyle{ T \mathbin{\triangle} F }[/math] 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 [math]\displaystyle{ p_2 }[/math]. Concretely, at larger depths in the search a vertex [math]\displaystyle{ v_{2k+1} }[/math] is only appended to the alternating trail if [math]\displaystyle{ T \mathbin{\triangle} \{ v_0 v_1, v_1 v_2, \dotsc, v_{2k} v_{2k+1}, v_{2k+1} v_0 \} }[/math] is a tour. By design that set of edges constitutes a 2-factor in [math]\displaystyle{ G }[/math], so what needs to be determined is whether that 2-factor consists of a single Hamiltonian cycle, or instead is made up of several cycles.

If naively posing this subproblem as giving a subroutine the set of [math]\displaystyle{ n }[/math] edges as input, one ends up with [math]\displaystyle{ O(n) }[/math] 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. That is too slow for the second usage of this test, which gets carried out for every alternating trail with more than [math]\displaystyle{ 2 }[/math] edges from [math]\displaystyle{ T }[/math]. 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 [math]\displaystyle{ T }[/math]. After picking [math]\displaystyle{ k }[/math] edges from [math]\displaystyle{ T }[/math], the remaining subgraph [math]\displaystyle{ \bigl( \mathrm{V}(G), T \setminus \{ v_0 v_1, \dotsc, v_{2k-2} v_{2k-1} \} \bigr) }[/math] consists of [math]\displaystyle{ k }[/math] paths. The outcome of the Hamiltonicity test done when considering the [math]\displaystyle{ (k+1) }[/math]th edge [math]\displaystyle{ v_{2k} v_{2k+1} }[/math] depends only on in which of these paths that [math]\displaystyle{ v_{2k} }[/math] resides and whether [math]\displaystyle{ v_{2k+1} }[/math] is before or after [math]\displaystyle{ v_{2k} }[/math]. Hence it would be sufficient to examine [math]\displaystyle{ 2k }[/math] different cases as part of performing step 2.3.2 for [math]\displaystyle{ v_{2k-1} }[/math]; as far as [math]\displaystyle{ v_{2k+1} }[/math] is concerned, the outcome of this test can be inherited information rather than something that has to be computed fresh.

References

• Lin, Shen; Kernighan, B. W. (1973). "An Effective Heuristic Algorithm for the Traveling-Salesman Problem". Operations Research 21 (2): 498–516. doi:10.1287/opre.21.2.498. 
• K. Helsgaun (2000). "An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic". European Journal of Operational Research 126 (1): 106–130. doi:10.1016/S0377-2217(99)00284-2. 
• Johnson, David S.; McGeoch, Lyle A. (1997). "The Traveling Salesman Problem: A Case Study in Local Optimization". in E. H. L. Aarts. Local Search in Combinatorial Optimization. London: John Wiley and Sons. pp. 215–310. http://www.research.att.com/~dsj/papers/TSPchapter.pdf. 

External links

• LKH implementation
• Concorde TSP implementation
• LK Heuristic in Python