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.