Tuesday, March 27, 2018

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

Friday, March 16, 2018

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-65AEcDBAdCeB
c1 c2 c3 c4 c6 c5 c1 c2 c3 c4 c6 c5 d1 d2 d3 d4 c1 c2 c3 c4 c6 c5 d1 d2 d4 d3

or inside [c4, c6] segment:

12-34-65ADeCBAcEdB
c1 c2 c3 c4 c6 c5 c1 c2 c3 c4 c6 c5 d1 d2 d4 d3 c1 c2 c3 c4 c6 c5 d1 d2 d3 d4

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).

c1 c2 c3 c4 c6 c5

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

Saturday, February 17, 2018

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