Lin-Kernighan algorithm basics – part 11

Lin-Kernighan algorithm idea is to try the most promising sequences, therefore we should rather sort candidates by decreasing accumulated gain, not by their distance from the last city used (order of nearest neighbors). So, for example:

type
  Suffix = object
    c2iplus1, c2iplus2: City_Number
    Ga: Length_Gain
    moveType: int
    tourOrder: int

proc SortSufficesByGain(goodSufficesList: var seq[Suffix]) =
  # sort the list to have the most promising at top
  sort(goodSufficesList) do (x,y: Suffix) -> int:
       result = cmp(y.Ga, x.Ga)

proc LK_2Move(c1, c2: City_Number;
              G1a: Length_Gain): bool =
...
  var
    goodSuffix: Suffix
    goodSufficesList: seq[Suffix]
    breadth: int
...
  block find_promising_moves:
    goodSufficesList = @[]  # empty list (sequence)
    for c3 in neighbors(c2):
      if tried_c3 > 2*Max_Breadth_1: # note multiplier
        break find_promising_moves
...
    
      c3_succ = t_succ(c3)
      c3_pred = t_pred(c3)
      for c4 in [c3_pred, c3_succ]:
        if fwd and (c4 == c3_succ)  or
           not fwd and (c4 == c3_pred):
          tourOrder = TO_1234
          moveType  = move_type_0
        else:
          tourOrder = TO_1243
          moveType  = move_type_2
        #end_if fwd...
        tried_c3 = tried_c3 + 1
        G2a = G1 + distance(c3, c4)
        goodSuffix = Suffix(c2iplus1: c3, c2iplus2: c4,
                            Ga: G2a,
                            tourOrder: tourOrder, moveType: moveType)
        goodSufficesList.add(goodSuffix)
      #end_loop for c4
    #end_loop for neighbor_number
  #end_block find_promising_moves

  block evaluate_promising_moves:
    if len(goodSufficesList) == 0:
      # no promising moves
      break evaluate_promising_moves
    SortSufficesByGain(goodSufficesList)
    breadth = min(len(goodSufficesList), Max_Breadth_1)
    for mve in 0 .. breadth-1:
      goodSuffix = goodSufficesList[mve]
      c3 = goodSuffix.c2iplus1
      c4 = goodSuffix.c2iplus2     
      Ga = goodSuffix.Ga
      tourOrder = goodSuffix.tourOrder
      moveType  = goodSuffix.moveType
      if moveType != move_type_0: # connecting move
        gainFromCloseUp = Ga - distance(c4, c1)
        if gainFromCloseUp > 0:
          improved = true
          Make_2opt_Move(c1, c2, c3, c4)
          tourLen = tourLen - gainFromCloseUp
          Set_DLB_off(DontLook, [c1, c2, c3, c4])
          break evaluate_promising_moves
      if LK_3Move(c1, c2, c3, c4,
                  Ga, tourOrder):
        improved = true
        break evaluate_promising_moves
  #end_block evaluate_promising_moves

  result = improved

An alternative for sorting candidates

Instead of sorting we can use simpler solution used in original Lin-Kernighan algorithm that is: each time we consider two links to remove we should try the longer link as the first one. Then for example:

proc LK_2Move(c1, c2: City_Number;
              G1a: Length_Gain): bool =

  var
    c4_A, c4_B:  City_Number
...
  block find_promising_moves:
    for c3 in neighbors(c2):
...
      c3_succ = t_succ(c3)
      c3_pred = t_pred(c3)
      
      if distance(c3, c3_succ) > distance(c3, c3_pred):
        c4_A = c3_succ
        c4_B = c3_pred
      else:        
        c4_A = c3_pred
        c4_B = c3_succ

      for c4 in [c4_A, c4_B]:
        if fwd and (c4 == c3_succ)  or
           not fwd and (c4 == c3_pred):
          tourOrder = TO_1234
          moveType  = move_type_0
        else:
          tourOrder = TO_1243
          moveType  = move_type_2
        #end_if fwd...
        tried_c3 = tried_c3 + 1
        G2a = G1 + distance(c3, c4)
        if moveType != move_type_0: # connecting move
          gainFromCloseUp = G2a - distance(c4, c1)
          if gainFromCloseUp > 0:
            # improving move found
            improved = true
            Make_2opt_Move(c1, c2, c3, c4)
            tourLen = tourLen - gainFromCloseUp
            Set_DLB_off(DontLook, [c1, c2, c3, c4])
            break find_promising_moves

        if LK_3Move(c1, c2, c3, c4,
                    G2a, tourOrder):
          improved = true
          break find_promising_moveses
      #end_loop for c4
    #end_loop for neighbor_number
  #end_block find_promising_moves