Schemes of all 4-opt moves

Why there are exactly 48 types of 4-opt move

4-opt move consists of breaking four links, thus breaking tour into four segments to reconnect them into new tour. Let capital letters A, B, C, D represent the four segments of tour. Then ABCD denotes the original tour. We permutate the letters to obtain new tours, for example ABDC or ACBD. Note that tour is cyclic, so ABDC and BDCA denote the same tour. Therefore to avoid repeating the same configurations of segments but written in some alternative ways, we always start recording a new tour from the same segment A, in its original order, and put its letter on the first position. That is why we permute only the set of three remaining segments: B, C and D:
$$P(k-1) = (k-1)! = 3! = 6$$

But we should not forget that each segment has its original direction in tour, from its begin to its end, and can be connected either as it is, in its original order of cities, or reversed. So we use lower letters b, c, d to indicate that given segment is reversed in new tour. Each of three segments can be used in one of two states (original or reversed order), so permutations with repetition:
$$V^2(k-1) = 2^{k-1} = 2^3 = 8$$

Overall number of possible connections of our segments is equal:
$$MoveTypes(k) = P(k-1)*V^2(k-1) = (k-1)! * 2^{k-1}= 6 * 8 = 48$$

ABCD ABCd ABcD ABcd AbCD AbCd AbcD Abcd

ACBD ACBd ACbD ACbd AcBD AcBd AcbD Acbd

ADBC ADBc ADbC ADbc AdBC AdBc AdbC Adbc

ABDC ABDc ABdC ABdc AbDC AbDc AbdC Abdc

ACDB ACDb ACdB ACdb AcDB AcDb AcdB Acdb

ADCB ADCb ADcB ADcb AdCB AdCb AdcB Adcb

 

4-opt move cases.
Lower letter denote that segment is reversed.

equals original tour
ABCD
equivalent to a single 2-opt move
ABCd	ABcD	AbCD
AcbD	ABdc	Adcb
equivalent to a single 3-opt move
ABcd	AbcD	ACBD
ACbD	AcBD	Acbd
ADBC	AdBC	ABDC
ABDc	ABdC	/td>
ACDB	ACDb	ADcb
AdcB
pure 4-opt moves
A. sequential 4-opt moves
Abcd	ACBd	ACbd
AcBd	ADBc	ADbC
AdBc	AdbC	Adbc
AbDC	AbDc	AbdC
ACdB	ACdb	AcDB
AcDb	Acdb	ADCb
ADcB	AdCB
B. non-sequential 4-opt moves
AbCd	ADbc	AcdB
ADCB	AdCb

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.

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)