## Friday, June 23, 2017

### 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()
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:
#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
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)
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
# 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


## Wednesday, June 21, 2017

### Lin-Kernighan algorithm basics – part 8

Sequences considered so far:

const
move_type_0 =  0  # non-connecting
move_type_2 =  2  # 2-opt
move_type_3 =  3  # 3-opt
move_type_4 =  4  # 4-opt
move_type_5 =  5  # 5-opt

const
TO_00 = 0  # unknown or unmaintained sequence

TO_1234 = 1
TO_1243 = 2  # 2-opt

# descendants of TO_1234
TO_123456 = 3
TO_123465 = 4
TO_125634 = 5  # 3-opt
TO_126534 = 6  # 3-opt
# descendants of TO_1243
TO_124356 = 7
TO_124365 = 8  # 3-opt
TO_125643 = 9  # 3-opt
TO_126543 = 10

# descendants of TO_123456
TO_12345678 = 11
TO_12345687 = 12
TO_12347856 = 13
TO_12348756 = 14
TO_12783456 = 15
TO_12873456 = 16
# descendants of TO_123465
TO_12346578 = 17
TO_12346587 = 18
TO_12347865 = 19
TO_12348765 = 20
TO_12783465 = 21  # 4-opt
TO_12873465 = 22  # 4-opt
# descendants of TO_125634
TO_12563478 = 23
TO_12563487 = 24  # 4-opt
TO_12785634 = 25
TO_12875634 = 26  # 4-opt
TO_12567834 = 27
TO_12568734 = 28  # 4-opt
# descendants of TO_126534
TO_12653478 = 29
TO_12653487 = 30  # 4-opt
TO_12657834 = 31  # 4-opt
TO_12658734 = 32
TO_12786534 = 33  # 4-opt
TO_12876534 = 34
# descendants of TO_124356
TO_12435678 = 35
TO_12435687 = 36
TO_12437856 = 37  # 4-opt
TO_12438756 = 38  # 4-opt
TO_12784356 = 39  # 4-opt
TO_12874356 = 40  # 4-opt
# descendants of TO_124365
TO_12436578 = 41
TO_12436587 = 42  # 4-opt
TO_12437865 = 43  # 4-opt
TO_12438765 = 44
TO_12784365 = 45
TO_12874365 = 46  # 4-opt
# descendants of TO_125643
TO_12564378 = 47
TO_12564387 = 48  # 4-opt
TO_12567843 = 49
TO_12568743 = 50  # 4-opt
TO_12785643 = 51  # 4-opt
TO_12875643 = 52
# descendants of TO_126543
TO_12654378 = 53
TO_12654387 = 54
TO_12657843 = 55  # 4-opt
TO_12658743 = 56  # 4-opt
TO_12786543 = 57
TO_12876543 = 58


## Monday, June 19, 2017

### Lin-Kernighan algorithm basics – part 7

Now we can make a break and check out progress made so far. Suppose that we want to stop constructing starting LK move, and even more: stop constructing LK implementation. Then we would obtain code for sequential 4-opt optimization. This would need only small piece of code:

const
OPT_5_IMPLEMENTED = false

proc LK_5Move(...): bool =
result = false


Implementation of 4-opt sequential optimization obtained this way gives better resulting tours than simple implementation 3-opt with neighbor lists and DLB shown before. Moreover, it is much faster, although it does not use DLB (which can be easily added).

### Some simple statistics

Relative time, best length, average length and worst length for all tours created by NN heuristic and improved by 3-opt and sequential 4-opt, both with neighbor lists. (Note that this 3-opt implementation uses slower method of applying moves than that in 4seq-opt.) Random planar problems, N=100.
Problem # Method Time Best Avg Worst
1NN100100.00110.42125.14
NN + 3opt-ND(24)439394.1495.3498.10
NN + 4seq-opt-ND(24)68194.1494.9196.41
2NN100100.00108.10121.20
NN + 3opt-ND(24)439386.6888.6490.28
NN + 4seq-opt-ND(24)126886.6887.7691.14
3NN100100.00109.51118.10
NN + 3opt-ND(24)449390.2591.8093.73
NN + 4seq-opt-ND(24)116889.6690.8892.49
4NN100100.00109.58118.16
NN + 3opt-ND(24)449388.7890.5593.41
NN + 4seq-opt-ND(24)185088.7890.1591.85
5NN100100.00111.02122.46
NN + 3opt-ND(24)410090.4291.9794.34
NN + 4seq-opt-ND(24)107490.4291.3892.17
6NN100100.00111.49125.67
NN + 3opt-ND(24)458787.9189.8291.69
NN + 4seq-opt-ND(24)117487.8888.6690.99
7NN100100.00108.23121.77
NN + 3opt-ND(24)449392.8293.8496.40
NN + 4seq-opt-ND(24)116892.7193.7395.80
8NN100100.00106.07119.49
NN + 3opt-ND(24)458786.0087.7490.74
NN + 4seq-opt-ND(24)146285.7786.7588.27
9NN100100.00111.77124.00
NN + 3opt-ND(24)449393.2594.1896.55
NN + 4seq-opt-ND(24)195092.8493.8295.23
10NN100100.00110.89117.01
NN + 3opt-ND(24)429390.2391.0294.77
NN + 4seq-opt-ND(24)136890.1690.6592.93

### Lin-Kernighan algorithm basics – part 6

proc Make_4opt_Move(c1, c2, c3, c4, c5, c6, c7, c8: City_Number;
tourOrder: int) =

case tourOrder # all 20 cases of sequential 4-opt move

of TO_12783465, TO_12786534:

of TO_12873465, TO_12875634, TO_12438756, TO_12564387:

of TO_12563487:

of TO_12568734, TO_12658743:

of TO_12653487:

of TO_12657834:

of TO_12437856:

of TO_12784356, TO_12785643, TO_12657843:

of TO_12874356, TO_12436587:

of TO_12437865, TO_12874365, TO_12568743:

else:
echo "Unknown 4-opt move: ", tourOrder
quit 1


Note that each of all possible sequential pure 4-opt moves is equivalent to a sequence of exactly three 2-opts. Even 12-56-34-87 which can be described as symmetric 3-opt (which is equal to three 2-opts) plus subsequent 2-opt. Moreover, these 4-opt moves together with symmetric 3-opt move make a set of all k-opt sequential moves that are equivalent to some sequence of exactly three 2-opts.

## Sunday, June 18, 2017

### Lin-Kernighan algorithm basics – part 5

Contrary to original Lin-Kernighan, considering only two types of sequential 4-opt moves, the code below deals with all twenty types of sequential 4-opt moves (there are only five types non-sequential 4-opt moves) and disjoining sequences leading to valid 5-opt moves.

proc LK_4Move(c1, c2, c3, c4, c5, c6: City_Number;
G3a: Length_Gain;
tourOrderPrev: int): bool =
const
level = 3
var
improved: bool
c7, c8: City_Number
c6_pred, c6_succ: City_Number
c7_pred, c7_succ: City_Number
fwd: bool
G3: Length_Gain
G4a, gainFromCloseUp: Length_Gain
tried_c7: int = 0
tourOrder: int
moveType: int

improved = false
fwd = (c2 == t_succ(c1))
c6_succ = t_succ(c6)
c6_pred = t_pred(c6)

best_Ga = low(Length_Gain)
block find_promising_moves:
for c7 in neighbors(c6):
# tests:
# when c7 is one of tour neighbors of c6,
# and we cannot add it to the tour
if (c7 == c6_succ) or (c7 == c6_pred):
continue
# link (c6,c7) should not be the same as (c2,c3)
if (c6 == c2) and (c7 == c3) or
(c6 == c3) and (c7 == c2):
continue

G3 = G3a - distance(c6, c7)

if G3  <= 0:  # c7 is too far from c6
break  # all subsequent candidates for c7 are even worse

# if G3 > 0:

tried_c7 = tried_c7 + 1
break find_promising_moves

c7_succ = t_succ(c7)
c7_pred = t_pred(c7)

for c8 in [c7_succ, c7_pred]:
# tests:
# link (c7,c8) should not be the same as (c1,c2)
if (c7 == c1) and (c8 == c2) or
(c7 == c2) and (c8 == c1):
continue
# link (c7,c8) should not be the same as (c3,c4)
if (c7 == c3) and (c8 == c4) or
(c7 == c4) and (c8 == c3):
continue

# testing available variants:
case tourOrderPrev

of TO_126534:
if inOrder(c4, c7, c1, fwd):
if inOrder(c4, c7, c8, fwd):
when OPT_5_IMPLEMENTED:
tourOrder = TO_12653478 # disconnecting, starts 5-opt
else:
continue
else:
tourOrder = TO_12653487
elif inOrder(c5, c7, c3, fwd):
if inOrder(c5, c7, c8, fwd):
tourOrder = TO_12657834
else:
when OPT_5_IMPLEMENTED:
tourOrder = TO_12658734 # disconnecting, starts 5-opt
else:
continue
else: #  inOrder(c2, c7, c6, fwd):
if inOrder(c2, c7, c8, fwd):
tourOrder = TO_12786534
else:
when OPT_5_IMPLEMENTED:
tourOrder = TO_12876534 # disconnecting, starts 5-opt
else:
continue

of TO_125634:
if inOrder(c4, c7, c1, fwd):
if inOrder(c4, c7, c8, fwd):
when OPT_5_IMPLEMENTED:
tourOrder = TO_12563478 # disconnecting, starts 5-opt
else:
continue
else:
tourOrder = TO_12563487
elif inOrder(c6, c7, c3, fwd):
if inOrder(c6, c7, c8, fwd):
when OPT_5_IMPLEMENTED:
tourOrder = TO_12567834 # disconnecting, starts 5-opt
else:
continue
else:
tourOrder = TO_12568734
else: #  inOrder(c2, c7, c5, fwd):
if inOrder(c2, c7, c8, fwd):
when OPT_5_IMPLEMENTED:
tourOrder = TO_12785634 # disconnecting, starts 5-opt
else:
continue
else:
tourOrder = TO_12875634

of TO_123456:
when OPT_5_IMPLEMENTED:
if inOrder(c6, c7, c1, fwd):
# TO_12345678 and TO_12345687 are not valid 4-opt moves
# and they do not lead to valid 5-opt moves
continue
elif inOrder(c4, c7, c5, fwd):
if inOrder(c4, c7, c8, fwd):
tourOrder = TO_12347856 # disconnecting, starts 5-opt
else:
tourOrder = TO_12348756 # disconnecting, starts 5-opt
else: #  inOrder(c2, c7, c3, fwd):
if inOrder(c2, c7, c8, fwd):
tourOrder = TO_12783456 # disconnecting, starts 5-opt
else:
tourOrder = TO_12873456 # disconnecting, starts 5-opt
else:
continue

of TO_125643:
if inOrder(c3, c7, c1, fwd):
if inOrder(c3, c7, c8, fwd):
when OPT_5_IMPLEMENTED:
tourOrder = TO_12564378 # disconnecting, starts 5-opt
else:
continue
else:
tourOrder = TO_12564387
elif inOrder(c6, c7, c4, fwd):
if inOrder(c6, c7, c8, fwd):
when OPT_5_IMPLEMENTED:
tourOrder = TO_12567843 # disconnecting, starts 5-opt
else:
continue
else:
tourOrder = TO_12568743
else: #  inOrder(c2, c7, c5, fwd):
if inOrder(c2, c7, c8, fwd):
tourOrder = TO_12785643
else:
when OPT_5_IMPLEMENTED:
tourOrder = TO_12875643 # disconnecting, starts 5-opt
else:
continue

of TO_124365:
if inOrder(c5, c7, c1, fwd):
if inOrder(c5, c7, c8, fwd):
when OPT_5_IMPLEMENTED:
tourOrder = TO_12436578 # disconnecting, starts 5-opt
else:
continue
else:
tourOrder = TO_12436587
elif inOrder(c3, c7, c6, fwd):
if inOrder(c3, c7, c8, fwd):
tourOrder = TO_12437865
else:
when OPT_5_IMPLEMENTED:
tourOrder = TO_12438765 # disconnecting, starts 5-opt
else:
continue
else: #  inOrder(c2, c7, c4, fwd):
if inOrder(c2, c7, c8, fwd):
when OPT_5_IMPLEMENTED:
tourOrder = TO_12784365 # disconnecting, starts 5-opt
else:
continue
else:
tourOrder = TO_12874365

of TO_123465:
if inOrder(c5, c7, c1, fwd):
when OPT_5_IMPLEMENTED:
if inOrder(c5, c7, c8, fwd):
# TO_12346578 is not valid 4-opt move
# and it does not lead to valid 5-opt move
continue
else:
tourOrder = TO_12346587 # disconnecting, starts 5-opt
else:
continue
elif inOrder(c4, c7, c6, fwd):
when OPT_5_IMPLEMENTED:
if inOrder(c4, c7, c8, fwd):
tourOrder = TO_12347865 # disconnecting, starts 5-opt
else:
tourOrder = TO_12348765 # disconnecting, starts 5-opt
else:
continue
else: #  inOrder(c2, c7, c3, fwd):
if inOrder(c2, c7, c8, fwd):
tourOrder = TO_12783465
else:
tourOrder = TO_12873465

of TO_126543:
if inOrder(c3, c7, c1, fwd):
when OPT_5_IMPLEMENTED:
if inOrder(c3, c7, c8, fwd):
continue
else:
tourOrder = TO_12654387 # disconnecting, starts 5-opt
else:
continue
elif inOrder(c5, c7, c4, fwd):
if inOrder(c5, c7, c8, fwd):
tourOrder = TO_12657843
else:
tourOrder = TO_12658743
else: #  inOrder(c2, c7, c6, fwd):
when OPT_5_IMPLEMENTED:
if inOrder(c2, c7, c8, fwd):
tourOrder = TO_12786543 # disconnecting, starts 5-opt
else:
tourOrder = TO_12876543 # disconnecting, starts 5-opt
else:
continue

of TO_124356:
if inOrder(c6, c7, c1, fwd):
if inOrder(c6, c7, c8, fwd):
# TO_12435678 is not valid 4-opt move
# and it does not lead to valid 5-opt move
continue
else:
when OPT_5_IMPLEMENTED:
tourOrder = TO_12435687 # disconnecting, starts 5-opt
else:
continue
elif inOrder(c3, c7, c5, fwd):
if inOrder(c3, c7, c8, fwd):
tourOrder = TO_12437856
else:
tourOrder = TO_12438756
else: #  inOrder(c2, c7, c4, fwd):
if inOrder(c2, c7, c8, fwd):
tourOrder = TO_12784356
else:
tourOrder = TO_12874356

else: # of tourOrderPrev
continue
#end of testing variants

if (c8 == c1):
# c8 should not be c1 when we close the tour
moveType = move_type_0
else:
case tourOrder
of TO_12786534, TO_12657834, TO_12653487, TO_12875634,
TO_12568734, TO_12563487, TO_12785643, TO_12568743,
TO_12564387, TO_12874365, TO_12437865, TO_12436587,
TO_12783465, TO_12873465, TO_12658743, TO_12657843,
TO_12874356, TO_12784356, TO_12437856, TO_12438756:
moveType = move_type_4
else:
moveType = move_type_0

G4a = G3 + distance(c7, c8)
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

when OPT_5_IMPLEMENTED:
if LK_5Move(c1, c2, c3, c4, c5, c6, c7, c8,
Ga, tourOrder):
improved = true
break find_promising_moves

#end_loop for c8
#end_loop for neighbor_number
#end_block find_promising_moves

result = improved


## Saturday, June 17, 2017

### Schemes of sequential pure 4-opt moves

 Move 12-78-34-65 Move 12-87-34-65 Move 12-56-34-87 c1 c2 c7 c8 c3 c4 c6 c5 c1 c2 c8 c7 c3 c4 c6 c5 c1 c2 c5 c6 c3 c4 c8 c7 Move 12-87-56-34 Move 12-56-87-34 Move 12-65-34-87 c1 c2 c8 c7 c5 c6 c3 c4 c1 c2 c5 c6 c8 c7 c3 c4 c1 c2 c6 c5 c3 c4 c8 c7 Move 12-65-78-34 Move 12-78-65-34 Move 12-43-78-56 c1 c2 c6 c5 c7 c8 c3 c4 c1 c2 c7 c8 c6 c5 c3 c4 c1 c2 c4 c3 c7 c8 c5 c6 Move 12-43-87-56 Move 12-78-43-56 Move 12-87-43-56 c1 c2 c4 c3 c8 c7 c5 c6 c1 c2 c7 c8 c4 c3 c5 c6 c1 c2 c8 c7 c4 c3 c5 c6 Move 12-43-65-87 Move 12-43-78-65 Move 12-87-43-65 c1 c2 c4 c3 c6 c5 c8 c7 c1 c2 c4 c3 c7 c8 c6 c5 c1 c2 c8 c7 c4 c3 c6 c5 Move 12-56-43-87 Move 12-56-87-43 Move 12-78-56-43 c1 c2 c5 c6 c4 c3 c8 c7 c1 c2 c5 c6 c8 c7 c4 c3 c1 c2 c7 c8 c5 c6 c4 c3 Move 12-65-78-43 Move 12-65-87-43 c1 c2 c6 c5 c7 c8 c4 c3 c1 c2 c6 c5 c8 c7 c4 c3

## Friday, June 16, 2017

### Why there are exactly 48 types of 4-opt move

4-opt move consists of breaking four links, thus breaking tour into four segments to reconnect them into new tour. Let capital letters A, B, C, D represent the four segments of tour. Then ABCD denotes the original tour. We permutate the letters to obtain new tours, for example ABDC or ACBD. Note that tour is cyclic, so ABDC and BDCA denote the same tour. Therefore to avoid repeating the same configurations of segments but written in some alternative ways, we always start recording a new tour from the same segment A, in its original order, and put its letter on the first position. That is why we permute only the set of three remaining segments: B, C and D:

But we should not forget that each segment has its original direction in tour, from its begin to its end, and can be connected either as it is, in its original order of cities, or reversed. So we use lower letters b, c, d to indicate that given segment is reversed in new tour. Each of three segments can be used in one of two states (original or reversed order), so permutations with repetition:

Overall number of possible connections of our segments is equal: