# Lin-Kernighan TSP edge choice

Step 4a of the original paper describing the Lin-Kernighan TSP algorithm states that the choice of edge $$x_i = (t_{2i}, t_{2i+1})$$ to be deleted is uniquely determined by the choice of edge $$y_{i-1} = (t_{2i-1}, t_{2i})$$ previously added. Helsgaun elaborates on this by saying:

"... only one of these makes it possible to ‘close’ the tour (by the addition of $$y_i$$). The other choice results in two disconnected subtours"

Can somebody explain why this is the case, and how to tell which choice of $$x_i / t_{2i}$$ given some $$y_{2i-1}$$ is correct?

I have an idea (that I'm not sure is correct) of a way to test if a tour contains disconnected subtours*, but doing so would force you to build a tour $$T'$$ from $$T, X, Y$$ at every step of a k-opt move, which is inefficient.

*if tour is a list of cities containing a disconnected subtour then some city must be visited twice, so you could do something like len(set(tour)) == len(tour) in python

• This question reminds me of a question I asked a couple of months ago or.stackexchange.com/questions/6729/… Apr 19, 2022 at 21:53
• Interesting. Did you make any progress? Apr 20, 2022 at 14:50
• No, but I didn't spend a lot of time on it Apr 20, 2022 at 15:00

It might help to refer to Figure 3(a) in the Lin-Kernigan paper. Assume that you started out with the tour oriented so that the nodes were visited in the order $$t_1 \rightarrow t_2 \rightarrow \dots \rightarrow t_4 \rightarrow t_3 \rightarrow \hat{t} \dots -\rightarrow t_1,$$where $$\hat{t}$$ is the unlabeled endpoint of the $$y_2$$ edge opposite $$t_4.$$ You choice of $$y_1$$ put the focus on node $$t_3,$$ forcing you to choose for deletion one of the two edges ($$(t_3, t_4)$$ or $$(t_3, \hat{t})$$) incident to $$t_3$$ and present in the original tour. The key is that $$t_4$$ occurs between $$t_2$$ and $$t_3$$ in the original tour, and $$\hat{t}$$ does not. You are going to add the edge $$y_1 = (t_2,t_4)$$ to the tour. If you leave $$(t_3,t_4)$$ in the tour while adding $$y_1$$, you end up with a subtour $$t_2\rightarrow \dots \rightarrow t_4 \rightarrow t_3 \rightarrow t_2$$ (the last arc courtesy of $$y_1$$).

More generally, if you delete an arc $$t_i \rightarrow t_j$$ and add an arc $$t_j \rightarrow t_k$$, then the arc incident at $$t_k$$ that you delete is the one whose other endpoint was between $$t_j$$ and $$t_k$$ before the changes when the tour is oriented $$t_i \rightarrow t_j \rightarrow \dots \rightarrow t_k \rightarrow \dots \rightarrow t_i.$$

• Thanks! I get the impression that the best approach is to apply swaps $x_i, y_i$ as they come, rather than only maintaining $X, Y$, to make it easier to check which side of the tour some $t_{2i}$ belongs to. Apr 20, 2022 at 14:53
• Let's say that you number the nodes in initial tour from 1 to $n$, and let $x_h$ be the number assigned to node $t_h$. When you are looking at deleting arc $t_i \rightarrow t_j,$ compute new numbers $y_h = x_h - x_i (\textrm{mod } n),$ which results in $y_i = 0,$ $y_j = 1$ and $y_k > 1.$ Now you just have to pick the neighbor $t_\ell$ of $t_k$ for which $y_\ell \le y_k.$ That should make shopping for swaps pretty easy. Once you execute a swap, though, you have to renumber the tour (reset the $x_h$ values).
– prubin
Apr 20, 2022 at 15:42
• Thank you, that makes perfect sense Apr 21, 2022 at 11:02

In Section 5.3 of

K. Helsgaun, General k-opt submoves for the Lin-Kernighan TSP heuristic. Mathematical Programming Computation, 1(2-3):119-163 (2009).

it is demonstrated how the feasibility of a k-opt move can be determined in O(k log k) time.

• Great! I think this answers my question Apr 24, 2022 at 17:04