Non-sequential 5-opt moves – part 7 of 7

Disjoining 3-exchanges as base for 5-opt non-sequential moves, part 4

The last part is looking for such pair (d3, d4) that constructed move improves the tour:

proc LK_Bridge_B2(c1, c2, c3, c4, c5, c6, d1, d2: City_Number;
                  G1a: Length_Gain,
                  d1_is_inside_c2_c3: bool): bool =
  var
    improved: bool
    d3, d4: City_Number
    d2_pred, d2_succ: City_Number
    d3_pred, d3_succ: City_Number
    G1, G2a, gainFromCloseUp: Length_Gain
    goodSuffix: Suffix
    goodSufficesList: seq[Suffix]
    tourOrder: int
    tried_c3: int = 0
    breadth: int
    
  improved = false
  d2_succ = t_succ(d2)
  d2_pred = t_pred(d2)
  block find_promising_moves:
    # find d3 as a candidate for end of link (d2,d3) to add
    goodSufficesList = @[]  # empty list 
    for d3 in neighbors(d2):
      if tried_c3 >= 2*Max_Breadth_1:
        break find_promising_moves
      if (d3 == d2_succ) or (d3 == d2_pred):
        continue
      if inOrder(c2, d3, c3, true) == d1_is_inside_c2_c3:
        continue

      G1 = G1a - distance(d2, d3)
      # choose d4 as one of the two tour neighbors of d3:
      d3_succ = t_succ(d3)
      d3_pred = t_pred(d3)
      for d4 in [d3_succ, d3_pred]:
        if d4 == d2:
          continue
        if (d3 == c1) and (d4 == c2)  or
           (d3 == c2) and (d4 == c1):
          continue
        if (d3 == c3) and (d4 == c4)  or
           (d3 == c4) and (d4 == c3):
          continue          
        if (d3 == c5) and (d4 == c6)  or
           (d3 == c6) and (d4 == c5):
          continue

        G2a = G1 + distance(d3, d4)

        if inOrder(c4, d1, c6, true) or
           inOrder(c4, d3, c6, true):
           if inOrder(d1, d3, d4, true):
             tourOrder = TO_AExcDB   # AEcDB
           else:
             tourOrder = TO_AdCxeB   # AdCeB
        else:
           # inOrder(c5, d1, c1, true) or
           # inOrder(c5, d3, c1, true)
           if inOrder(d1, d3, d4, true):
             tourOrder = TO_ADxeCB   # ADeCB
           else:
             tourOrder = TO_AxcExdB  # AcEdB

        goodSuffix = Suffix(c2iplus1: d3, c2iplus2: d4,
                            Ga: G2a, tourOrder: tourOrder)
        goodSufficesList.add(goodSuffix)
        tried_c3 = tried_c3 + 1
      #end_loop for d4
    #end_loop for d3
  #end_block find_promising_moves

  block evaluate_promising_moves:
    if len(goodSufficesList) == 0:
      break evaluate_promising_moves
    SortSufficesByGain(goodSufficesList)
    breadth = min(len(goodSufficesList), Max_Breadth_1)
    for mve in 0 .. breadth-1:
      goodSuffix = goodSufficesList[mve]
      d3 = goodSuffix.c2iplus1
      d4 = goodSuffix.c2iplus2
      G2a = goodSuffix.Ga
      tourOrder = goodSuffix.tourOrder
      gainFromCloseUp = G2a - distance(d4, d1)
      if gainFromCloseUp > 0: # improving move found
        improved = true
        Make_5opt_NS_MoveB(c1, c2, c3, c4, c5, c6,
                           d1, d2, d3, d4,
                           tourOrder)
        tourLen = tourLen - gainFromCloseUp
        Set_DLB_off(DontLook, [c1, c2, c3, c4, c5, c6,
                               d1, d2, d3, d4])
        break evaluate_promising_moves
  #end_block evaluate_promising_moves

  result = improved

Finally we need a proc for actually making the move we have found:

proc Make_5opt_NS_MoveB(c1, c2, c3, c4, c5, c6,
                        d1, d2, d3, d4: City_Number;
                        tourOrder: int) =

  case tourOrder
  of TO_AExcDB, TO_AxcExdB:
    Exchange_Links(c1, c2, c5, c6)
    Exchange_Links(d1, d2, d4, d3)
    Exchange_Links(c3, c4, c5, c2)
    Exchange_Links(d1, d3, d2, d4)

  of TO_ADxeCB, TO_AdCxeB:
    Exchange_Links(c1, c2, c5, c6)
    Exchange_Links(d1, d2, d3, d4)
    Exchange_Links(c3, c4, c5, c2)

  else:
    echo "Unknown 5-opt non-sequential move: ", tourOrder
    quit 1

Non-sequential 5-opt moves – part 6 of 7

Disjoining 3-exchanges as base for 5-opt non-sequential moves, part 3

Now we look for two links to remove: (d1, d2) and (d3, d4). (We can also say that we look for two pairs of cities adjacent to each other on tour, determining these links.)

In case of 12-34-65 move type one of these pairs should be inside [c2, c3] segment. For the second we should consider two options: it can be inside [c5, c1] segment:

12-34-65	AEcDB	AdCeB

or inside [c4, c6] segment:

12-34-65	ADeCB	AcEdB

But we san simplify our task and treat [c4, c6] and [c5, c1] as one segment of consecutive cities: from c4 to c1, with additional condition that link to remove cannot be the same as (c5, c6).

We can use the same reasoning for 12-43-56 and 12-65-43 move types. Then we would have:

  var
    cFrom, cTo: City_Number  # ends of segment with first link to remove
    canBreakLink: bool
...
  case tourOrder
  of TO_123465:
    if (2 * Segment_Size(cF2,cF3)) <= N:    
      (cFrom, cTo) = (cF2, cF3)
    else:
      (cFrom, cTo) = (cF4, cF1)
  of TO_124356:
    if (2 * Segment_Size(cF6,cF1)) <= N:    
      (cFrom, cTo) = (cF6, cF1)
    else:
      (cFrom, cTo) = (cF2, cF5)
  of TO_126543:
    if (2 * Segment_Size(cF5,cF4)) <= N:    
      (cFrom, cTo) = (cF2, cF3)
    else:
      (cFrom, cTo) = (cF3, cF6)
  else:
    discard
  #end_case
  
  block find_promising_moves:
    goodSufficesList = @[]  # empty list
    d1 = cFrom
    d2 = t_succ(d1)
    while d2 != cTo:
      canBreakLink = true
      if (d1==cF1) and (d2==cF2)  or
         (d1==cF2) and (d2==cF1):
        canBreakLink = false
      if (d1==cF3) and (d2==cF4)  or
         (d1==cF4) and (d2==cF3):
        canBreakLink = false
      if (d1==cF5) and (d2==cF6)  or
         (d1==cF6) and (d2==cF5):
        canBreakLink = false

      if canBreakLink:
        G1a = G0 + distance(d1, d2)
        goodSuffix = Suffix(c2iplus1: d1, c2iplus2: d2,
                            Ga: G1a, tourOrder: tourOrder)
        goodSufficesList.add(goodSuffix)
      d1 = d2
      d2 = t_succ(d1)
    #end_loop while d2 != cTo
  #end_block find_promising_moves
  ...

On the other hand we can simplify the code by taking advantage of the fact that 12-43-56 and 12-65-43 are just rotated versions of 12-34-65. Then we obtain:

proc LK_Bridge_B1(c1, c2, c3, c4, c5, c6: City_Number;
                  G0: Length_Gain;
                  tourOrder: int): bool =
  var
    improved: bool
    fwd: bool
    cF1, cF2, cF3, cF4, cF5, cF6: City_Number
    cFrom, cTo: City_Number  # ends of segment with first link to remove
    d1_is_inside_c2_c3: bool
    d1, d2: City_Number
    Ga, G1a: Length_Gain
    goodSuffix: Suffix
    goodSufficesList: seq[Suffix]
    breadth: int

  improved = false  # rotate all other types of move to use only TO_123465
  fwd = (c2 == t_succ(c1))
  case tourOrder
  of TO_123465:
    if fwd:
      (cF1, cF2, cF3, cF4, cF5, cF6) = (c1, c2, c3, c4, c5, c6)
    else:
      (cF1, cF2, cF3, cF4, cF5, cF6) = (c4, c3, c2, c1, c6, c5)
  of TO_124356:
    if fwd:
      (cF1, cF2, cF3, cF4, cF5, cF6) = (c5, c6, c1, c2, c3, c4)
    else:
      (cF1, cF2, cF3, cF4, cF5, cF6) = (c2, c1, c6, c5, c4, c3)
  of TO_126543:
    if fwd:
      (cF1, cF2, cF3, cF4, cF5, cF6) = (c6, c5, c4, c3, c2, c1)
    else:
      (cF1, cF2, cF3, cF4, cF5, cF6) = (c3, c4, c5, c6, c1, c2)
  else:
    discard
  #end_case

  # we want to scan shorter segment
  if (2 * Segment_Size(cF2,cF3)) <= N:
    (cFrom, cTo) = (cF2, cF3)
    d1_is_inside_c2_c3 = true
  else:
    (cFrom, cTo) = (cF4, cF1)
    d1_is_inside_c2_c3 = false
  #end_if
    
  block find_promising_moves:
    goodSufficesList = @[]  # empty list
    d1 = cFrom
    d2 = t_succ(d1)
    while d1 != cTo and d2 != cTo:
      if (d1==cF5) and (d2==cF6)  or
         (d1==cF6) and (d2==cF5):
        discard
      else:
        G1a = G0 + distance(d1, d2)
        goodSuffix = Suffix(c2iplus1: d1, c2iplus2: d2, Ga: G1a)
        goodSufficesList.add(goodSuffix)
      #end_if
      d1 = d2
      d2 = t_succ(d1)
    #end_loop while d2 != cTo
  #end_block find_promising_moves

  block evaluate_promising_moves:
    if len(goodSufficesList) == 0:
      break evaluate_promising_moves
    SortSufficesByGain(goodSufficesList)
    #breadth = len(goodSufficesList) # NOTE!!!
    breadth = min(len(goodSufficesList), Max_Breadth_1)
    for mve in 0 .. breadth-1:
      goodSuffix = goodSufficesList[mve]
      d1 = goodSuffix.c2iplus1
      d2 = goodSuffix.c2iplus2
      Ga = goodSuffix.Ga
      improved = LK_Bridge_B2(cF1, cF2, cF3, cF4, cF5, cF6,
                              d1, d2, Ga, d1_is_inside_c2_c3)
      if improved:
        break evaluate_promising_moves
  #end_block evaluate_promising_moves

  result = improved

Non-sequential 5-opt moves – part 5 of 7

Disjoining 3-exchanges as base for 5-opt non-sequential moves, part 2

For obtaining a code for this kind of 5-opt non-sequential moves we can modify a proc for non-sequential 4-opt moves this way:

proc LK_2NS_Move(c1, c2: City_Number;
                 G1a: Length_Gain): bool =
  var
    improved: bool
    c3, c4: City_Number
    c2_pred, c2_succ: City_Number
    c3_pred, c3_succ: City_Number
    c4_A, c4_B: City_Number
    fwd: bool
    G1, G2a, Ga: Length_Gain
    gainFromCloseUp: Length_Gain
    goodSuffix: Suffix
    goodSufficesList: seq[Suffix]    
    tourOrder: int
    tried_c3: int = 0
    breadth: int

  improved = false
  fwd = (c2 == t_succ(c1))
  c2_succ = t_succ(c2)
  c2_pred = t_pred(c2)
  block find_promising_moves:
    goodSufficesList = @[]  # empty list (sequence)
    for c3 in neighbors(c2):
      if tried_c3 >= 2*Max_Breadth_1:
        break find_promising_moves
      if (c3 == c2_succ) or (c3 == c2_pred):
        continue
      G1 = G1a - distance(c2, c3)
      if G1 <= 0:
        break

      # if G1 > 0:
      c3_succ = t_succ(c3)
      c3_pred = t_pred(c3)
      if fwd:
        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 c4 == c1:  # NOTE
          continue
        G2a = G1 + distance(c3, c4)
        if G2a > 0:
          goodSuffix = Suffix(c2iplus1: c3, c2iplus2: c4,
                              Ga: G2a)
          goodSufficesList.add(goodSuffix)
          tried_c3 = tried_c3 + 1
      #end_loop for c4
    #end_loop for c3
  #end_block find_promising_moves

  block evaluate_promising_moves:
    if len(goodSufficesList) == 0:
      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
      gainFromCloseUp = Ga - distance(c4, c1)
      if gainFromCloseUp > 0:
        if fwd and (c4 == t_succ(c3))  or
           not fwd and (c4 == t_pred(c3)):
          # disconnecting 2-move (||)
          if LK_Bridge_A1(c1, c2, c3, c4, gainFromCloseUp):
            improved = true
            break evaluate_promising_moves
        else:
          # connecting 2-move (X)
          improved = true
          Make_2opt_Move(c1, c2, c3, c4)
          tourLen = tourLen - gainFromCloseUp
          Set_DLB_off(DontLook, [c1, c2, c3, c4])
          break evaluate_promising_moves
      #end_if gainFromCloseUp > 0

      # improving move has not been found;
      # extend current 2-move ('X' or '||') to 3-move
      # (disconnecting or connecting) and keep trying
      if fwd and (c4 == t_succ(c3))  or
         not fwd and (c4 == t_pred(c3)):
        tourOrder = TO_1234
      else:
        tourOrder = TO_1243
      #end_if
      if LK_3NS_Move(c1, c2, c3, c4, Ga, tourOrder):
        improved = true
        break evaluate_promising_moves

  #end_block evaluate_promising_moves
  result = improved

proc LK_3NS_Move(c1, c2, c3, c4: City_Number;
                 G2a: Length_Gain;
                 tourOrderPrev: int): bool =
  var
    improved: bool
    c5, c6: City_Number
    c4_pred, c4_succ: City_Number
    c5_pred, c5_succ: City_Number
    fwd: bool
    G2, Ga: Length_Gain
    G3a, gainFromCloseUp: Length_Gain
    goodSuffix: Suffix
    goodSufficesList: seq[Suffix]
    tried_c5: int = 0
    breadth: int
    tourOrder: int

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

  block find_promising_moves:
    goodSufficesList = @[]  # empty list (sequence)
    for c5 in neighbors(c4):
      if tried_c5 >= 2*Max_Breadth_2:
        break find_promising_moves
      if (c5 == c4_succ) or (c5 == c4_pred):
        continue
      G2 = G2a - distance(c4, c5)
      if G2  <= 0:
        break

      # if G2 > 0:
      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(c2, c5, c3, fwd):
             if (c6 == c1):
                continue
             if inOrder(c2, c6, c5, fwd):
                tourOrder = TO_126534
             else:
                tourOrder = TO_125634
          else:
             if (c6 == c2):
                continue
             if inOrder(c4, c5, c6, fwd):
                tourOrder = TO_123456 # disconnecting
             else:
                tourOrder = TO_123465 # disconnecting

        of TO_1243:
          if inOrder(c2, c5, c4, fwd):
             if inOrder(c2, c6, c5, fwd):
                tourOrder = TO_126543 # disconnecting
             else:
                if (c5 == c1) and (c6 == c2) or
                   (c5 == c2) and (c6 == c1):
                   continue
                tourOrder = TO_125643
          else:
             if inOrder(c3, c6, c5, fwd):
                tourOrder = TO_124365
             else:
                if (c5 == c1) and (c6 == c2) or
                   (c5 == c2) and (c6 == c1):
                   continue
                tourOrder = TO_124356 # disconnecting
        else:
          continue # no more possibilities
        #end_case tourOrderPrev

        tried_c5 = tried_c5 + 1
        G3a = G2 + distance(c5, c6)
        goodSuffix = Suffix(c2iplus1: c5, c2iplus2: c6,
                            Ga: G3a, tourOrder: tourOrder)
        goodSufficesList.add(goodSuffix)
      #end_loop for c6
    #end_loop for c5
  #end_block find_promising_moves

  block evaluate_promising_moves:
    if len(goodSufficesList) == 0:
      # no promising moves
      break evaluate_promising_moves
    SortSufficesByGain(goodSufficesList)
    # pass promising moves, one by one, to next level
    # to check them there
    breadth = min(len(goodSufficesList), Max_Breadth_2)
    for mve in 0 .. breadth-1:
      goodSuffix = goodSufficesList[mve]
      c5 = goodSuffix.c2iplus1
      c6 = goodSuffix.c2iplus2     
      Ga = goodSuffix.Ga
      tourOrder = goodSuffix.tourOrder
      gainFromCloseUp = Ga - distance(c6, c1)
      if gainFromCloseUp > 0:
        case tourOrder
        of TO_125634, TO_126534, TO_125643, TO_124365:
          # pure 3-opt move
          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 evaluate_promising_moves

        of TO_123465, TO_124356, TO_126543:
          # disconnecting into 2 parts, use 2-exchange to connect
          ...
          if LK_Bridge_B1(...):
            improved = true
            break evaluate_promising_moves

        else: # TO_123456
          continue
        #end_case

  #end_block evaluate_promising_moves
  result = improved