Lin-Kernighan algorithm basics – part 9

So far we have built a set of nested procs for starting move:

LK_1Move()  # level 0: c1, c2
   LK_2Move()  # level 1: c1, c2, c3, c4
      LK_3Move()  # level 2: c1, c2, c3, c4, c5, c6
        LK_4Move()  # level 3: c1, c2, c3, c4, c5, c6, c7, c8

While they are sufficient to obtain a solution for sequential 4-opt optimization, the main goal of Lin-Kernighan algorithm is to search beyond k-optimization for some fixed k. When the process of searching reaches level 3 there are two possibilities:

1. There is no c7 candidate with positive G3. Then this is the end of searching for improving sequence. There are no more promising moves for given base city and control returns to previous level, then finally to level 0.
2. There is some c7 with positive G3.

When G3 is positive, then it is possible that there would be some promising move also at subsequent level, that is: with positive G4. Regardless whether at level 3 exists such c8 (tour neighbor of c7) that resulting move is improving.

                      G3 = G2 + distance(c5, c6) - distance(c6, c7)
gainFromCloseUp_atLevel3 = G3 + distance(c7, c8) - distance(c8, c1)
...
                      G4 = G3 + distance(c7, c8) - distance(c8, c9)

We need a general way to try to extend the sequence by one exchange. Our code for starting move is for maximum 4-opt, we will use general proc for subsequent moves.

Move = StartingMove [+ SubsequentMove [+ SubsequentMove ...]]

The simplest general move for subsequent steps of sequence is 2-opt, and this one is actually used in original Lin-Kernighan algorithm. It differs from the usual 2-opt procedure in that it has to fulfill additional conditions:

1. It must continue construction of sequential move.
2. It must be designed to be used recursively or in a loop.

What would our LK_SubsequentMove() need to continue any sequence? It must:

1. continue given sequence, continue the process of calculating and checking partial sum of gains (that is: it takes value of G obtained so far, for given sequence, instead of starting with G equal G0=distance(c1, c2)).
2. continue given sequence, for the same base city (that is: if starting move starts with c1, then the first subsequent move must start with c1),
3. continue given sequence, from the last city used (that is: if starting move ends with c8, then the first subsequent move must start with breaking the link (c8, c1) as if it was (c2, c1) in starting move).
4. continue given sequence, with its restrictions on links (that is: it must not remove links added previously, during construction of sequence).

So general idea of using subsequent moves in 4-opt would be (note that we have used don't look bits):

var
  SubseqLvl: int  # let us make it global for further changes in the code

proc LK_4Move(...) =
...
  var
    c2subseq, cLast:  City_Number
    Ga: Length_Gain
...
...
        if moveType != move_type_0:
          gainFromCloseUp = G4a - distance(c8, c1)
          if gainFromCloseUp > 0:
            # improving move found
            improved = true
            Make_4opt_Move(c1, c2, c3, c4, c5, c6, c7, c8,
                           tourOrder)
            tourLen = tourLen - gainFromCloseUp
            Set_DLB_off(DontLook, [c1, c2, c3, c4, c5, c6, c7, c8])
            break find_promising_moves

        when not OPT_5_IMPLEMENTED:
          # here we should try to use general subsequent move
          # after temporary applying 4-opt move
          c2subseq = c8
          cLast = c8
          Ga = G4a
          Save_Tour()
          Save_DLB()
          LinksAddedClear()
          AddtoLinksAdded(c2, c3)
          AddtoLinksAdded(c4, c5)
          AddtoLinksAdded(c6, c7)
          Make_4opt_Move(c1, c2, c3, c4, c5, c6, c7, c8,
                         tourOrder)
          tourLen = tourLen - gainFromCloseUp
          Set_DLB_off(DontLook,
                      [c1, c2, c3, c4, c5, c6, c7, c8])
          searching = true
          SubseqLvl = 0
          while searching:
            SubseqLvl = SubseqLvl + 2
            # above 2 since each 2-opt subsequent move exchanges 2 links
            improved = LK_SubsequentMove(c1, c2subseq,
                                         Ga, cLast)
            if improved:
              break find_promising_moves
            else:
              if c2subseq == cLast: # end of promising moves
                Restore_Tour()
                Restore_DLB()
                searching = false
              else:
                c2subseq = cLast
            if SubseqLvl > Max_Depth:
              LinksAddedClear()
          #end_while searching
        #end_when not OPT_5_IMPLEMENTED
...

We need a proc for subsequent moves:

proc LK_SubsequentMove(c1, c2: City_Number;
                       G1a: var Length_Gain;
                       cLast: var City_Number): bool =
  # cLast is set to c4 when promising move has been found and applied
  var
    improved: bool
    c3, c4: City_Number
    c2_pred, c2_succ: City_Number
    fwd: bool
    G1, Ga: Length_Gain
    G2a, gainFromCloseUp: Length_Gain

  improved = false
  fwd = (c2 == t_succ(c1))
  c2_succ = t_succ(c2)
  c2_pred = t_pred(c2)
  block find_promising_moves:
    for c3 in neighbors(c2):
      if (c3 == c2_succ) or (c3 == c2_pred):
        continue
      if isLinkAdded(c2, c3):
        continue

      G1 = G1a - distance(c2, c3)
      if G1 <= 0:
        break

      # only one choice of c4 gives closed tour
      if fwd:
        c4 = t_pred(c3)
      else:
        c4 = t_succ(c3)
      if isLinkAdded(c4, c1):
        continue
      G2a = G1 + distance(c3, c4)
      gainFromCloseUp = G2a - distance(c4, c1)
      if gainFromCloseUp > 0:
        improved = true
      # apply promising (or even improving) move
      Make_2opt_Move(c1, c2, c3, c4)
      tourLen = tourLen - gainFromCloseUp
      G1a = G2a
      cLast = c4
      AddtoLinksAdded(c3, c4)
      # don't look bits for c1, c2 should be set at previous level
      Set_DLB_off(DontLook, [c3, c4])
      # breadth for subsequent general moves is equal 1, so:
      break find_promising_moves
    #end_loop for neighbor_number
  #end_block find_promising_moves

  result = improved