Lin-Kernighan algorithm basics – part 4

For k>3 making k-opt move by reversing segments given by positions in tour is inconvenient. In order to extend special, starting LK moves to 4- or even 5-opt, we will use implementation focused on exchanging links between cities, so the arguments passed to link exchange are city numbers, not positions:

proc Exchange_Links(c1, c2, c4, c3: City_Number) =
  var
    p1, p2, p3, p4, idx: Tour_Index
    city: City_Number
    left, right: Tour_Index
    inversionSize: int

  p1 = position[c1]
  p2 = position[c2]
  p3 = position[c3]
  p4 = position[c4]
  
  if (c2 == t_pred(c1)):
    idx = p1
    p1  = p2
    p2  = idx
  if (c4 == t_succ(c3)):
    idx = p3
    p3  = p4
    p4  = idx
   
  inversionSize = (p4 - p2 + 1)
  if inversionSize < 0:
    inversionSize = inversionSize + N
  if (2 * inversionSize > N):  # segment longer than half of tour
    left  = p3
    right = p1
    inversionSize = N - inversionSize
  else:
    left  = p2
    right = p4
  inversionSize = inversionSize div 2

  for counter in 1 .. inversionSize:
    city        = tour[right]
    tour[right] = tour[left]
    tour[left]  = city
    position[tour[left]]  = left
    position[tour[right]] = right
    left  = (left + 1) mod N
    right = (N + right - 1) mod N

Then:

proc Make_2opt_Move(c1, c2, c3, c4: City_Number) {.inline.}  =
  Exchange_Links(c1, c2, c4, c3)

and

proc Make_3opt_Move(c1, c2, c3, c4, c5, c6: City_Number;
                    tourOrder: int) =
  case tourOrder
  of TO_126534:
    Exchange_Links(c2, c1, c5, c6)
    Exchange_Links(c3, c4, c2, c5)
  of TO_125643:
    Exchange_Links(c1, c2, c4, c3)
    Exchange_Links(c5, c6, c4, c1)
  of TO_124365:
    Exchange_Links(c2, c1, c5, c6)
    Exchange_Links(c2, c5, c3, c4)
  of TO_125634:  # 3-opt symmetric
    Exchange_Links(c1, c2, c3, c4)
    Exchange_Links(c6, c5, c2, c4)
    Exchange_Links(c6, c2, c1, c3)
  else:
    echo "Unknown 3-opt move: ", tourOrder
    quit 1

(We may notice that 12-65-34 and 12-43-65 moves are obtained from the same two exchanges. The code can be shortened then.)

Note that while all 3-opt moves involve exchange of some three links between cities, only one of these moves, the symmetric one, is a sequence of three 2-opt moves. The other three moves are equivalent to sequences of only two 2-opt moves. It gets even more interesting when we consider 4-opt moves.