Saturday, October 21, 2017

Double Bridge as an improving 4-opt move, part 2

In previous part we have found such cF1...cF4 that replacing links cF1-cF2 and cF3-cF4 with links cF2-cF3 and cF4-cF1 disjoins tour, but gives gain:

We can expect that segment from cF2 to cF3 contains relatively small number of cities. Therefore we will look for d1 by examining one by one all cities between cF2 and cF3, and then look for d3 among these neighbors of given d1 that are in the other segment, that is between cF4 and cF1. If total gain from set of all eight cities obtained this way is positive, then we have found improving non-sequential move.

But what if segment from cF2 to cF3 contains more cities than the other one?

Then we can simply "rename" cities before using the procedure described above:

So we use:

if (2 * Segment_Size(cF2,cF3)) > N:
(cF1, cF2, cF3, cF4) = (cF3, cF4, cF1, cF2)


where:

proc Segment_Size(cityStart, cityEnd: City_Number): int =
## Returns number of cities in segment given by the two cities.
## Note that order of parameters is important to distinguish
## between two possible segments
result = (N + position[cityEnd] + 1 - position[cityStart]) mod N


Rest of the code implements the idea described above:

proc LK_Bridge_A1(c1, c2, c3, c4: City_Number;
G0: Length_Gain): bool =
var
improved: bool
cF1, cF2, cF3, cF4: City_Number
d1, d2: City_Number
Ga, G1a: Length_Gain
goodSuffix: Suffix
goodSufficesList: seq[Suffix]

improved = false
# order cities 'forward':
if (c2 == t_succ(c1)):
(cF1, cF2, cF3, cF4) = (c1, c2, c3, c4)
else:
(cF1, cF2, cF3, cF4) = (c2, c1, c4, c3)
#end_if
# we want segment [cF2,cF3] to be the shorter one
if (2 * Segment_Size(cF2,cF3)) > N:
(cF1, cF2, cF3, cF4) = (cF3, cF4, cF1, cF2)

block find_promising_moves:
goodSufficesList = @[]  # empty list (sequence)
d1 = cF2
d2 = t_succ(d1)
while d2 != cF3:
G1a = G0 + distance(d1, d2)
goodSuffix = Suffix(c2iplus1: d1, c2iplus2: d2, Ga: G1a)
d1 = d2
d2 = t_succ(d1)
#end_loop while d2 != cF3
#end_block find_promising_moves

block evaluate_promising_moves:
if len(goodSufficesList) == 0:
break evaluate_promising_moves
SortSufficesByGain(goodSufficesList)
for mve in 0 .. breadth-1:
goodSuffix = goodSufficesList[mve]
d1 = goodSuffix.c2iplus1
d2 = goodSuffix.c2iplus2
Ga = goodSuffix.Ga
improved = LK_Bridge_A2(cF1, cF2, cF3, cF4, d1, d2, Ga)
if improved:
break evaluate_promising_moves
#end_block evaluate_promising_moves

result = improved


and:

proc LK_Bridge_A2(c1, c2, c3, c4, d1, d2: City_Number;
G1a: Length_Gain): bool =
var
improved: bool
d3, d4: City_Number
d2_pred, d2_succ: City_Number
d3_pred, d3_succ: City_Number
G1, G2a, gainFromCloseUp: Length_Gain
goodSuffix: Suffix
goodSufficesList: seq[Suffix]
tourOrder: int
tried_c3: int = 0

improved = false

# find d3 as a candidate for end of link (d2,d3) to add
d2_succ = t_succ(d2)
d2_pred = t_pred(d2)

block find_promising_moves:
goodSufficesList = @[]  # empty list (sequence)
for d3 in neighbors(d2):
break find_promising_moves
if (d3 == d2_succ) or (d3 == d2_pred):
continue
if inOrder(c2, d3, c3, true):
# d3 should not be between c2 and c3
continue

G1 = G1a - distance(d2, d3)
# choose d4 as one of the two tour neighbors of d3:
d3_succ = t_succ(d3)
d3_pred = t_pred(d3)
for d4 in [d3_succ, d3_pred]:
if d4 == d2:
continue
if (d3 == c1) and (d4 == c2)  or
(d3 == c2) and (d4 == c1):
continue
if (d3 == c3) and (d4 == c4)  or
(d3 == c4) and (d4 == c3):
continue

G2a = G1 + distance(d3, d4)
if (d4 == t_succ(d3)):
else:
tourOrder = TO_AxcxdB  # 'AcdB' (||X)
#end_if
goodSuffix = Suffix(c2iplus1: d3, c2iplus2: d4,
tourOrder: tourOrder, Ga: G2a)
tried_c3 = tried_c3 + 1
#end_loop for d4
#end_loop for d3
#end_block find_promising_moves

block evaluate_promising_moves:
if len(goodSufficesList) == 0:
break evaluate_promising_moves
SortSufficesByGain(goodSufficesList)
for mve in 0 .. breadth-1:
goodSuffix = goodSufficesList[mve]
d3 = goodSuffix.c2iplus1
d4 = goodSuffix.c2iplus2
G2a = goodSuffix.Ga
gainFromCloseUp = G2a - distance(d4, d1)
if gainFromCloseUp > 0: # improving move found
improved = true
Make_4opt_NS_Move(c1, c2, c3, c4,
d1, d2, d3, d4, tourOrder)
tourLen = tourLen - gainFromCloseUp
Set_DLB_off(DontLook, [c1, c2, c3, c4,
d1, d2, d3, d4])
break evaluate_promising_moves
#end_block evaluate_promising_moves

result = improved


Monday, October 9, 2017

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:

 c1 c2 d1 d2 d3 d4 c3 c4 c1 c2 d1 d2 d3 d4 c3 c4

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)
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

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):
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)
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)
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.