Lin-Kernighan algorithm basics – part 2

First of all, Lin-Kernighan algorithm contains specific, justified exceptions to the four main rules. Rule number 2 requires that for each step we should be able to immediately stop adding further steps and obtain a valid tour. Naturally, this is not to be fulfilled for first step. But at the second step sequence 12-34 does not conform this rule: it is disconnecting move, producing two disjoined cycles. On the other hand, it would not be desirable to not allow this sequence, since it is needed to obtain two of all four pure 3-opt moves. Therefore original LK algorithm uses the principle of feasibility of tour starting from the third exchange, and not for the first two exchanges (2-opt level). Some variants of LK algorithm go even further and allow disconnecting moves at level of 3-opt or 4-opt moves, to examine more valid sequential 4-opt and 5-opt moves in next steps.

An outline of this part of original LK algorithm can be implemented as follows (we split code into chunks):

To make the code simple and clear we use global variables for tour and neighbor lists representation:

var
  tour: Tour_Array  # current tour
  tourLen: Length   # current length of tour
  position: City_Position_In_Tour
  neighbor: Neighbor_Matrix
  numberOfNeigbors: int
  DontLook: DLB_Array

These variables are used explicitly only in few low level procs, to keep the most of the code independent on this specific representation. Note that except these, all other procs use city numbers only, not their positions.

proc t_pred(city: City_Number): City_Number {.inline.} =
  ## returns tour predecessor for given city
  result = tour[(N + position[city] - 1) mod N]

proc t_succ(city: City_Number): City_Number {.inline.} =
  ## returns tour successor for given city
  result = tour[(position[city] + 1) mod N]

For the same reason instead of writing:

for neighbor_number in 0 .. numberOfNeigbors-1:
  c3 = neighbor[c2][neighbor_number]

we will use more abstract:

for c3 in neighbors(c2):

which in Nim language can be provided by iterator:

iterator neighbors(city: City_Number): City_Number =
  var i = 0
  while i < numberOfNeigbors:
    yield neighbor[city][i]
    inc(i)

proc LK_1Move(c1: City_Number): bool =
  const
    level = 0
  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)

  # try moves with breaking link between c1 and one of its tour
  # tour neigbors; if failed then try c1 with the other tour neighbor
  block find_improving_move:
    for c2 in [c1_succ, c1_pred]:
      # tests:
      # c2!=c1 by construction (c2 is a tour neighbor of c1)

      G1a = distance(c1, c2)
      improved = LK_2Move(c1, c2, G1a)
      if improved:
        break find_improving_move
    #end_for loop
  #end_block find_improving_move
  result = improved

(As may be noticed in above code, backtracking is limited: the alternative for c2 is examined only when no improving sequence starting with c1 and current c2 has been found.)

proc LK_2Move(c1, c2: City_Number;
              G1a: Length_Gain): bool =
  const
    level = 1
  var
    improved: bool
    c3, c4: City_Number
    c2_pred, c2_succ: City_Number
    c3_pred, c3_succ: City_Number
    fwd: bool
    G1: Length_Gain
    G2a, gainFromCloseUp: Length_Gain
    tried_c3: int = 0
    tourOrder: int
    moveType: int

  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):
      # after 2-opt move new tour would contain direct link
      # between cities c2 and c3, so we look for c3 among
      # cities that are close to city c2
      # tests:
      # when c3 is one of tour neighbors of c2,
      # then the link (c2,c3) already exists in tour
      # and we cannot *add* it to the tour
      if (c3 == c2_succ) or (c3 == c2_pred):
        continue
          
      G1 = G1a - distance(c2, c3)
      if G1 <= 0:  # c3 is too far from c2 -- no more promising moves
        break

      # if G1 > 0:

      # limit breadth to speed up searching
      tried_c3 = tried_c3 + 1
      if tried_c3 > Max_Breadth_1:
        break find_promising_moves
      
      c3_succ = t_succ(c3)
      c3_pred = t_pred(c3)          
      for c4 in [c3_pred, c3_succ]:
        # testing available variants
        if fwd and (c4 == c3_succ)  or
           not fwd and (c4 == c3_pred):
          # disconnecting move
          tourOrder = TO_1234
          moveType = move_type_0  # not a valid move
        else:
          tourOrder = TO_1243
          moveType = move_type_2  # 2-opt move

        G2a = G1 + distance(c3, c4)
        if moveType != move_type_0: # connecting move
          gainFromCloseUp = G2a - distance(c4, c1)
          if gainFromCloseUp > 0:
            # improving move found
            improved = true
            Make_2opt_Move(c1, c2, c3, c4)
            tourLen = tourLen - gainFromCloseUp
            Set_DLB_off(DontLook, [c1, c2, c3, c4])
            break find_promising_moves

        if LK_3Move(c1, c2, c3, c4,
                    G2a, tourOrder):
          improved = true
          break find_promising_moveses
      #end_loop for c4
    #end_loop for neighbor_number
  #end_block find_promising_moves

  result = improved

Note that backtracking in original LK is always limited. The alternative for c4 is examined only when no improving sequence starting with given c1, c2, c3 and current c4 has been found. Similarly, alternative candidate for c3 is examined only when no improving sequence starting with given c1, c2 and current c3 has been found.

To speed up searching without considerable loss of quality the original LK limits searching for c3 and c5 to first 5 candidates. This can be implemented by use of MaxBreadth(level) function or by some constants (program parameters):

# Maximum number of candidates to examine for endpoint
# of link added at given level of search for move.
#   1 means only one candidate should be considered
#   0 means no candidate, constructing a sequence stops at this level
# In original LK algorithm breadth is 5 for levels 1 and 2,
# and 1 for deeper levels. (They used GE-635, with speed <1 MIPS).
# Make some tests and adjust the values to your preferences.
const
  Max_Breadth_1 = 5 # for level 1
  Max_Breadth_2 = 5 # for level 2
  Max_Breadth_3 = 3 # for level 3
  Max_Breadth_4 = 3 # for level 4

Since candidate lists for c3, c5... are anyway limited and additionally the search is terminated when partial sum of gains is not positive, one may not use MaxBreadth(level), in hope of obtaining better results at cost of increased runtime.

Lin-Kernighan algorithm basics – part 1

2-opt, 3-opt or 4-opt algorithms use fixed number of links that we are going to exchange in each optimization step. When we consider k-opt, we expect that the larger k is, the better results could be achieved, and for sufficiently large k we may expect that k-optimal tour should be optimal. Unfortunately, with larger k the number of operations required to test all possible link exchanges grows very quickly. While 2-opt has complexity of O(N²), 3-opt has O(N³), 4-opt has O(N⁴) and so on. Additionally, for given set of links to remove, the number of possible reconnections also grows with k: there is only 1 type of 2-opt move to consider, but 4 types of pure 3-opt move, 25 types of pure 4-opt move, 208 types of pure 5-opt move... The value of k must be specified in advance, but we do not know, what k would be needed for given problem to obtain acceptable results of optimization. It may seem that these serious disadvantages cannot be avoided.

Lin and Kernighan proposed a remedy: k-opt algorithm with variable value of k, dynamically changed during execution. The algorithm starts from considering set of r=2 links to exchange and in each iteration step decides whether set of r+1 links should be considered.

The algorithm is based on following main principles:

1. use sequential moves^*;
2. last link to remove in a sequence must be chosen so that, if there would be no more steps in sequence, it would be possible to add a link closing up a tour (in each step we can stop and make a valid move);
3. every partial sum of gains must be positive (a move must be promising);
4. set of links removed and set of links added should be disjoined (once a link has been removed, it can no longer be added; once a link has been added, it cannot be removed; they are tabu).

* Exception: when there are no more improving sequential moves for tour, then specific non-sequential move, double bridge, is used.

A simplified version of basic algorithm to show how rules 1 and 3 can be applied is presented below. To clearly show the pattern it has been written in form of nested loops:

# looking for possible moves
# choose c1 and then...
G0 = 0
for c2 in [tour_succ(c1), tour_pred(c1)]:

  # choose c3
  for c3 in candidate_list(c2):
    g1 = distance(c1, c2) - distance(c2, c3)
    G1 = G0 + g1
    if G1 > 0:  # promising
      for c4 in [tour_succ(c3), tour_pred(c3)]:
        #... test rules 2 and 4
        gClose = distance(c3, c4) - distance(c4, c1)
        if gClose > 0:
          # improving 2-opt move found
        ...

        # choose c5
        for c5 in candidate_list(c4):
          g2 = distance(c3, c4) - distance(c4, c5)
          G2 = G1 + g2
          if G2 > 0:  # promising
            for c6 in [tour_succ(c5), tour_pred(c5)]:
              #... test rules 2 and 4
              gClose = distance(c5, c6) - distance(c6, c1)
              if gClose > 0:
                # improving 3-opt move found
          ...

              # choose c7
              for c7 in candidate_list(c6):
                g3 = distance(c, c6) - distance(c6, c7)
                G3 = G2 + g3
                if G3 > 0:  # promising
                  for c8 in [tour_succ(7), tour_pred(c7)]:
                    #... test rules 2 and 4
                    gClose = distance(c7, c8) - distance(c8, c1)
                    if gClose > 0:
                      # improving 4-opt move found
                ...

The value of k is not known in advance: we continue searching for next exchanges in sequence as long as partial gain is positive, and a sequence obtained this way may have many steps. The process requires variable number of steps (nested loops) and it would not be reasonable to have a code with dozens of nested loops. Therefore from some level we use a recursive procedure for general step. Why LK algorithm does not use recursion for all steps, starting with the first one? We put this question aside for later.

The first part of the idea can be written as follow:

0. Take initial tour T.
1. Let i = 1, the level number. Choose c₁, city we start sequence from.
2. Choose c₂, one of the two tour neighbors of c₁; that is: choose link (c₁, c₂) to remove from tour.
3. Choose c₃ such that link (c₂, c₃) to add is not in the tour and G₁ > 0. If no such c₃ exists, choose untried alternative for c₂ in Step 2.
4. Let i = i + 1.
5. Choose c_2i, one of the two tour neighbors of c_2i-1, such that
   1. link (c_2i-1, c_2i) is not in one of the links to be added,
   2. if c_2i is joined to c₁, then the result is a valid tour T'.
   ...
6. Choose c_2i+1, such that
   1. G_i > 0,
   2. link (c_2i, c_2i+1) is not one of the links to be removed,
   3. it is possible to remove link (c_2i+1, c_2i+2) from the tour in the next step.
7. If such c_2i+1 exist then goto Step 4.
8. ...

In above outline series of dots have been used to indicate intentional omissions, in places that need design decisions. What should we do when a valid improving move have been found? What should we do when G_i is not positive?

The original Lin-Kernighan algorithm uses a kind of limited "take the best move" approach. If an improvement has been found, then the algorithm does not apply this move immediately to replace tour T by shorter tour T'. Instead it records the value of the best possible improvement found so far in G^best variable, the level in k variable, and continues its steps in hope of finding even better move, starting from this found one. For example, when it founds improving 2-opt move for a sequence of some c₁, c₂, c₃, c₄, it records the gain and level and goes to the next step, to find 3-opt move starting with the same sequence of c₁, c₂, c₃, c₄, then 4-opt and so on.

Therefore there are two stopping conditions:

1. G_i ≤ G^best, or
2. no more valid steps, with G_i > 0, are possible.

When construction of sequence terminates, there are two possibilities: if G^best is equal zero, it means that no improving move starting from c₁ have been found and we should examine some untried alternative for c₁ in Step 1. If G^best is positive, then an improving move have been found during searching, so now we apply it to the tour T, thus replacing T with T', and repeat the whole process from Step 2.

While this reaction of original algorithm for finding an improving move is reasonable, it needs more complicated coding. Therefore there are LK variants, with more effective other parts, in which an improving move is applied as soon as it is found.

Sequential moves: improving and promising

Improving move condition

A move is improving when it is valid and it improves a tour. Any k-opt move that improves a tour must fulfill the condition:

Sum of lengths of links removed from tour must be greater than sum of links added to tour.

In other words:

delLength - addLength > 0

Let us take a sequential move. Then g1 defined by:

g1 = distance(c1, c2) - distance(c2, c3)

is a partial gain obtained from the first step in sequence. If a sequence consists of more than two steps, then g2 defined by:

g2 = distance(c3, c4) - distance(c4, c5)

is a gain obtained from the second step in sequence. Gain obtained so far, from these two moves, is then equal:

G_2 = g1 + g2

In general:

$$G_k = \sum_{i=1}^{k} g_i$$

g1 = distance(c1, c2) - distance(c2, c3)  # gain from step 1
g2 = distance(c3, c4) - distance(c4, c5)  # gain from step 2
g3 = distance(c5, c6) - distance(c6, c7)  # gain from step 3
...
G_k = g1 + g2 + g3 + ...

The last step of valid sequential k-opt move and then a gain from this step deviate from above pattern. This is because we must connect last city of sequence not with some next one, but with the first one:

# gain from the last, closing-up step
# Note `c1` in second distance
g_k = distance(c_2k1, c_2k) - distance(c_2k, c1)

G_k = g1 + g2 + g3 + ... + g_k

So total gain from a sequential move is sum of gains from each step of this move. Although some of g1, g2, g3... may be negative, when this sum of numbers is positive then the move is an improving move.

Promising move condition

We should note that sequential moves are cyclic: we can start from any step of move and apply them one by one, until we make them all. Lin and Kernighan noticed (1973) that:

If a sequence of numbers has a positive sum, there is a cyclic permutation of these numbers such that every partial sum is positive.

Proof

Let $m$ is the largest index for which $g_1 + ... + g_{m-1}$ is minimum. We start our permutation and partial sums from this index.

Then for each $j$:

1. a) if $j \ge m$:

   1. since

      $$g_1 + ... g_j \gt g_1 + ... g_{m-1}$$

      then

      $$G'_j = g_m + ... + g_j = (g_1 + ... g_j) - (g_1 + ... g_{m-1}) \gt 0$$

2. b) if $j \lt m$:

   1. since

      $$g_1 + ... g_j \ge g_1 + ... + g_{m-1}$$

      then

      $$G'_j = (g_m + ... + g_k) + (g_1 + ... g_j) \ge (g_m + ... g_k) + (g_1 + ... g_{m-1}) \gt 0$$

Lin and Kernighan noticed that:

In particular, then, since we are looking for sequences of gains $g_i$'s that have positive sum, we need only consider sequences of gains whose partial sum is always positive. This gain criterion enables us to reduce enormously the number of sequences we need to examine

Therefore during process of building a sequential move we check partial sum of gains. If this sum remains positive before the last, closing step, then a sequence of exchanges is promising and we can continue, even if it is not valid move now.