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.