Lin-Kernighan algorithm basics – part 3

Note that the code below goes further than original Lin-Kernighan algorithm because it considers more sequences, including disconnecting 3-exchanges to pass them to next levels.

proc LK_3Move(c1, c2, c3, c4: City_Number;
              G2a: Length_Gain;
              tourOrderPrev: int): bool =
  const
    level = 2
  var
    improved: bool
    c5, c6: City_Number
    c4_pred, c4_succ: City_Number
    c5_pred, c5_succ: City_Number
    fwd: bool
    G2: Length_Gain
    G3a, gainFromCloseUp: Length_Gain
    tried_c5: int = 0
    tourOrder: int
    moveType: int

  improved = false
  fwd = (c2 == t_succ(c1))
  c4_succ = t_succ(c4)
  c4_pred = t_pred(c4)

  block find_promising_moves:
    for c5 in neighbors(c4):
      # tests:
      # when c5 is one of tour neighbors of c4,
      # then the link (c4,c5) already exists in tour
      # and we cannot add it to the tour
      if (c5 == c4_succ) or (c5 == c4_pred):
        continue
      # Now, since c5 is not is a tour neighbor of c4,
      # then c5!=c3, and thus (c5,c6)!=(c3,c4) for any c6.
      # The same way (c5,c6)!=(c3,c2). Later on we make sure
      # that (c5,c6)!=(c1,c2) is also fulfilled.

      G2 = G2a - distance(c4, c5)
      if G2  <= 0:  # c5 is too far from c4
        break  # all subsequent candidates for c5 are even worse

      # if G2 > 0:

      # limit breadth to speed up searching
      tried_c5 = tried_c5 + 1
      if tried_c5 > Max_Breadth_2:
        break find_promising_moves

      c5_succ = t_succ(c5)
      c5_pred = t_pred(c5)
      for c6 in [c5_succ, c5_pred]:
        # testing available variants
        case tourOrderPrev

        of TO_1234:
          if inOrder(c4, c5, c1, fwd):
            if (c6 == c2):
              # c2!=c3, so c5==c1 and (c5,c6)==(c1,c2)
              continue
            if inOrder(c4, c5, c6, fwd):
              when OPT_5_IMPLEMENTED:
                tourOrder = TO_123456 # disconnecting, but starts 5-opt
              else:
                continue
            else:
              tourOrder = TO_123465 # disconnecting, but starts 4-opt
          else:
            if (c6 == c1):
              # c2!=c3, so c5==c2 and (c6,c5)==(c1,c2)
              continue
            if inOrder(c2, c6, c5, fwd):
              tourOrder = TO_126534
            else:
              tourOrder = TO_125634

        of TO_1243:
          if inOrder(c3, c5, c1, fwd):
            if inOrder(c3, c5, c6, fwd):
              if (c5 == c1) and (c6 == c2) or
                 (c5 == c2) and (c6 == c1):
                 # (c5,c6) == (c1,c2)
                continue
              tourOrder = TO_124356 # disconnecting, but starts 4-opt
            else:
              # c3 <= c6 < c5 <= c1 < c2
              # therefore (c6,c5)!=(c1,c2)
              tourOrder = TO_124365
          else:
            if inOrder(c2, c5, c6, fwd):
              if (c5 == c1) and (c6 == c2) or
                 (c5 == c2) and (c6 == c1):
                 # (c5,c6) == (c1,c2)
                continue
              tourOrder = TO_125643
            else:
              # c1 < c2 <= c6 < c5 < c4
              # therefore (c6,c5)!=(c1,c2)
              tourOrder = TO_126543 # disconnecting, but starts 4-opt

        else:
          continue # no more possibilities
        #end_case tourOrderPrev

        case tourOrder
        of TO_125634, TO_126534, TO_125643, TO_124365:
          moveType = move_type_3  # pure 3-opt move
        else:
          moveType = move_type_0  # not a valid move

        G3a = G2 + distance(c5, c6)
        if moveType != move_type_0: # connecting move
          gainFromCloseUp = G3a - distance(c6, c1)
          if gainFromCloseUp > 0:
            # improving move found
            improved = true
            Make_3opt_Move(c1, c2, c3, c4, c5, c6, tourOrder)
            tourLen = tourLen - gainFromCloseUp
            Set_DLB_off(DontLook, [c1, c2, c3, c4, c5, c6])
            break find_promising_moves

        if LK_4Move(c1, c2, c3, c4, c5, c6,
                    G3a, tourOrder):
          improved = true
          break find_promising_moves
      #end_loop for c6
    #end_loop for neighbor_number
  #end_block find_promising_move

  result = improved

New functions used (note that Between() is not exactly the same we used before, in 3-opt with DLB code):

proc Between(city_A, city_X, city_C: City_Number): bool =
  ## Returns true if `x` is between `a` and `c` in tour
  ## with established direction (ascending position numbers)
  ## That is: when one begins a forward traversal of tour
  ## at city `a', then city `x` is reached before city `c'.
  ## Returns true if and only if:
  ##   a <= x <= c  or  c < a <= x  or  x <= c < a
  let pA = position[city_A]
  let pX = position[city_X]
  let pC = position[city_C]
  if pA <= pC:
    result = (pX >= pA) and (pX <= pC)
  else:
    result = (pX >= pA) or  (pX <= pC)

proc inOrder(city_A, city_B, city_C: City_Number, fwd: bool): bool =
  if fwd:
    result = Between(city_A, city_B, city_C)
  else:
    result = Between(city_C, city_B, city_A)