Scheme of LK with non-sequential moves

proc LK_scheme() =
  var
    locallyOptimal: bool = false
    improved: bool
    baseCity: City_Number

  position = Create_Position_In_Tour(tour)
  Set_DLB_off(DontLook, tour)  
  # calculate initial length of tour
  tourLen = distance(tour[N-1], tour[0])
  for pos in 0 .. N-2:
    tourLen = tourLen + distance(tour[pos], tour[pos+1])

  while not locallyOptimal:
    locallyOptimal = true
    for baseCity in 0 .. N-1:
      if isDLB_on(DontLook, baseCity):
         continue 

      ClearPromisingMoves()
      # first move:
      improved = LK_1Move(baseCity)
      # subsequent moves:
      if not improved:
        improved = LK_1SubsequentMoves()
      # non-sequential moves:
      if not improved:
        improved = LK_1NS_Move(baseCity)

      if improved:
        locallyOptimal = false
      else:
        Set_DLB_on(DontLook, baseCity)
      tourLenArr[baseCity] = tourLen

    #end_loop for baseCity
  #end_while not locallyOptimal

Non-sequential 4-opt moves – part 4 of 4

Double Bridge as an improving 4-opt move, part 2

In previous part we have found such cF1...cF4 that replacing links cF1-cF2 and cF3-cF4 with links cF2-cF3 and cF4-cF1 disjoins tour, but gives gain:

We can expect that segment from cF2 to cF3 contains relatively small number of cities. Therefore we will look for d1 by examining one by one all cities between cF2 and cF3, and then look for d3 among these neighbors of given d1 that are in the other segment, that is between cF4 and cF1. If total gain from set of all eight cities obtained this way is positive, then we have found improving non-sequential move.

But what if segment from cF2 to cF3 contains more cities than the other one?

Then we can simply "rename" cities before using the procedure described above:

So we use:

if (2 * Segment_Size(cF2,cF3)) > N:
  (cF1, cF2, cF3, cF4) = (cF3, cF4, cF1, cF2)

where:

proc Segment_Size(cityStart, cityEnd: City_Number): int =
  ## Returns number of cities in segment given by the two cities.
  ## Note that order of parameters is important to distinguish
  ## between two possible segments
  result = (N + position[cityEnd] + 1 - position[cityStart]) mod N

Rest of the code implements the idea described above:

proc LK_Bridge_A1(c1, c2, c3, c4: City_Number;
                  G0: Length_Gain): bool =
  var
    improved: bool
    cF1, cF2, cF3, cF4: City_Number
    d1, d2: City_Number
    Ga, G1a: Length_Gain
    goodSuffix: Suffix
    goodSufficesList: seq[Suffix]
    breadth: int

  improved = false
  # order cities 'forward':
  if (c2 == t_succ(c1)):
    (cF1, cF2, cF3, cF4) = (c1, c2, c3, c4)
  else:
    (cF1, cF2, cF3, cF4) = (c2, c1, c4, c3)
  #end_if
  # we want segment [cF2,cF3] to be the shorter one
  if (2 * Segment_Size(cF2,cF3)) > N:
    (cF1, cF2, cF3, cF4) = (cF3, cF4, cF1, cF2)

  block find_promising_moves:
    goodSufficesList = @[]  # empty list (sequence)
    d1 = cF2
    d2 = t_succ(d1)
    while d2 != cF3:
      G1a = G0 + distance(d1, d2)
      goodSuffix = Suffix(c2iplus1: d1, c2iplus2: d2, Ga: G1a)
      goodSufficesList.add(goodSuffix)
      d1 = d2
      d2 = t_succ(d1)
    #end_loop while d2 != cF3
  #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]
      d1 = goodSuffix.c2iplus1
      d2 = goodSuffix.c2iplus2     
      Ga = goodSuffix.Ga
      improved = LK_Bridge_A2(cF1, cF2, cF3, cF4, d1, d2, Ga)
      if improved:
        break evaluate_promising_moves
  #end_block evaluate_promising_moves

  result = improved

and:

proc LK_Bridge_A2(c1, c2, c3, c4, d1, d2: City_Number;
                  G1a: Length_Gain): 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
  
  # find d3 as a candidate for end of link (d2,d3) to add
  d2_succ = t_succ(d2)
  d2_pred = t_pred(d2)
  
  block find_promising_moves:
    goodSufficesList = @[]  # empty list (sequence)
    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):
        # d3 should not be between c2 and 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

        G2a = G1 + distance(d3, d4)
        if (d4 == t_succ(d3)):
          tourOrder = TO_ADBC    # 'ADBC' (||=)
        else:
          tourOrder = TO_AxcxdB  # 'AcdB' (||X)
        #end_if
        goodSuffix = Suffix(c2iplus1: d3, c2iplus2: d4,
                            tourOrder: tourOrder, Ga: G2a)
        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
      gainFromCloseUp = G2a - distance(d4, d1)
      if gainFromCloseUp > 0: # improving move found
        improved = true
        Make_4opt_NS_Move(c1, c2, c3, c4,
                          d1, d2, d3, d4, tourOrder)
        tourLen = tourLen - gainFromCloseUp
        Set_DLB_off(DontLook, [c1, c2, c3, c4,
                               d1, d2, d3, d4])
        break evaluate_promising_moves 
  #end_block evaluate_promising_moves

  result = improved

Non-sequential 4-opt moves – part 3 of 4

Double Bridge as an improving 4-opt move, part 1

Instead of treating double bridge as a mean of perturbation we could see it as one of the cases of valid 4-opt moves to consider. Then we should look for an improving double bridge move (or any other non-sequential 4-opt move).

So we want to find an improving 4-opt non-sequential move, where one of the links to remove is the link between given baseCity or c1 and one of its tour neighbors. Then we would need to find three more links to remove from remaining N-1 links of tour. We can avoid lot of searching when we notice that a move we are looking for starts with some 2-exchange:

Moreover, since we are looking for an improving move, we can try to use some techniques used in searching for sequential improving moves which make it fast. We would use neighbors as candidates and the idea of a promising move, that is a move with positive partial gain. The first steps are similar to the ones used for sequential moves:

proc LK_1NS_Move(c1: City_Number): bool =
  # returns true if improvement has been found and applied
  var
    improved: bool
    c2: City_Number
    c1_pred, c1_succ: City_Number
    G1a: Length_Gain

  improved = false
  c1_succ = t_succ(c1)
  c1_pred = t_pred(c1)
  for c2 in [c1_succ, c1_pred]:
    G1a = distance(c1, c2)
    improved = LK_2NS_Move(c1, c2, G1a)
    if improved:
      break
  #end_for loop
  result = improved

In the subsequent proc LK_2NS_Move() we gather all promising and "good" (see below) 2-exchanges, sort them by descending partial gain and then try to use them one by one as initial parts of a full move in the next step, in proc LK_3NS_Move(), until an improvement is found.

To simplify our task we narrow searching to these cases only when the first part of move we look for gives some gain (sum of lengths of two links removed so far is greater than sum of lengths of two links added so far).

del_Length = distance(c1, c2) + distance(c3, c4)
add_Length = distance(c2, c3) + distance(c4, c1)
gain = del_Length - add_Length
if gain > 0:
  # search for d1, d2, d3, d4 to build non-sequential move
else:
  # do not consider

This would simplify the algorithm and make it faster, while still providing some flexibility, because the second part itself, exchange of links between d's cities, need not to be improving and can use up some of this gain.

On the other hand this has also other important consequence. If we look for improving non-sequential 4-opt moves after we have made all possible improving sequential moves starting from c1, it means that we know that now the tour cannot be improved by any sequential move starting from c1. However when we start from situation shown on the right side of diagram (which is the first part of ADbc move) and then additionally require that there must be a gain from this first part, then we in fact require that these c1, c2, c3, c4 must form an improving 2-opt move. Which cannot happen when the tour is already optimized by all possible 4-opt sequential moves, because 2-opt is a specific case of 4-opt. So using this approach means that searching for improving ADbc move would be useless.

Accepting this we see that it is sufficient to consider only disjoining moves for possible first part of our non-sequential move:

proc LK_2NS_Move(c1, c2: City_Number;
                 G1a: Length_Gain): bool =
  # returns true if improvement has been found and applied
  var
    improved: bool
    c3, c4: City_Number
    c2_pred, c2_succ: City_Number
    fwd: bool
    G1, G2a, G2M, Ga: Length_Gain
    goodSuffix: Suffix
    goodSufficesList: seq[Suffix]
    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:
      if fwd:
        c4 = t_succ(c3)
      else:
        c4 = t_pred(c3)
      if c4 == c1:  # NOTE
        continue
      G2a = G1 + distance(c3, c4)
      G2M = G2a - distance(c4, c1)
      if G2M > 0:
        goodSuffix = Suffix(c2iplus1: c3, c2iplus2: c4, Ga: G2M)
        goodSufficesList.add(goodSuffix)
        tried_c3 = tried_c3 + 1
    #end_loop for neighbor_number
  #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
      improved = LK_Bridge_A1(c1, c2, c3, c4, Ga)
      if improved:
        break evaluate_promising_moves
  #end_block evaluate_promising_moves
  result = improved

Now the key to efficient search for a double bridge is to find a good method of finding d1 and then d3 that together with c1...c4 make an improving move. Cities d2 and d4 are easy to find as tour neighbors of d1 and d3.

Important

We should not forget that c2 we considered so far can be a tour predecessor of c1 (then fwd is false). To avoid further annoyances we can start next step, in proc LK_Bridge_A1(), with "normalizing" the direction in which we would like to number the four cities obtained so far, and set it to "forward":

proc LK_Bridge_A1(c1, c2, c3, c4: City_Number;
                 G2a: Length_Gain): bool =
  var
    cF1, cF2, cF3, cF4: City_Number  # c1..c4 cities in forward direction
  ...
  if (c2 == t_succ(c1)): # forward
    (cF1, cF2, cF3, cF4) = (c1, c2, c3, c4)
  else:
    (cF1, cF2, cF3, cF4) = (c2, c1, c4, c3)
  #end_if

Now we are sure that the cities have labels exactly in order and direction shown on diagram above, that is: cF2 is a tour successor of cF1 and so on.