# Helsgaun's $k$-Opt moves

In his 2009 paper General k-opt submoves for the Lin–Kernighan TSP heuristic, Helsgaun defines the local tour improvements on which the LKH heuristics are based as: with a cycle defined here: which clearly rules out multiple occurences of vertices in cycles, disproving user197309's claim that uniqueness of vertices can't be concluded from the definition of cycles.
Uniqueness of vertices in cycles also reflects common understanding in the sense of what definitions in publictions amount to.

several questions arise from that definition of admissible $$k$$-Opt moves:

• Where is the proof that the set of exchanged edges must form a cycle?
• Why aren't adjacent tour edges considered as exchange candidates?

Here is a simple counter example to the neessity of the single-cycle conjecture and to the non-adjacent tour edges assumption plus is it a cheaper $$3$$-Opt move than the ones requiring non-adjacent tour edges: • One pair of the red tour edges that are exchanged with the solid black edges is adjacent.
• The union of exchanged tour-edges with the replacement edges consists of two vertex-disjoint cycles depicted by the thin ellipses.
• The exchange of the edges resembles a transition between tours.
• I’m voting to close this question because, of your 5 questions, only 2 are mathematical. The others might belong on AcademiaSE. Apr 26, 2021 at 15:16

• @AlexM. Helsgaun's definition of a cycle that is found in th the linked paper on article page 120 (pdf: 2) is "A cycle is a set of edges $\lbrace (i_1,i_2),(i_2,i_3),\dots,(i_k,i_1)\rbrace$ with $i_p\ne i_q$ for $p\ne q$. That IMHO clearly proves that the PO is indeed right. It disappoints me a bit that the trollish answer was upvoted that much... Jan 7, 2022 at 15:36