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:

Excerpt from Helsgaun's paper

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:

Counter example to Helsgaun's k-Opt moves conjecture

  • 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.
  • 1
    $\begingroup$ I’m voting to close this question because, of your 5 questions, only 2 are mathematical. The others might belong on AcademiaSE. $\endgroup$
    – LSpice
    Apr 26 at 15:16

The criticism of the paper is wrong. The reader has erroneously assumed that the t's for a move must be different.

  • $\begingroup$ I tend to agree (with the criticism of the question). Also, Springer is a publisher and those are not in charge of peer review. $\endgroup$ Apr 26 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.