Sunday, May 28, 2017

Sequential moves: connecting and disconnecting

The simplest sequential move consist of two steps, that is of two link exchanges. Obvious example of such move is 2-opt move. We can describe it using tour order notation:

2-opt move = 12-43
c1 c2 c4 c3

The following question arises: does any combination of numbers 1,2,3,4 describe some sequential move? Let us take for example: 13-24. This cannot be a sequential move, because by definition first pair of cities in sequential move must be a pair of tour neighbors. The same for second and every other pair. This means that each pair of numbers in the record must contain two consecutive numbers, in one or the other order.

Therefore there are only four combinations of numbers 1,2,3,4 that actually describe sequential moves:

First pair
1221
Second
pair
3412-3421-34
4312-4321-43

The corresponding diagrams are as follows:

Forward
Move 12-34Move 12-43
c1 c2 c3 c4 c1 c2 c3 c4
Backward
Move 21-34Move 21-43
c1 c2 c4 c3 c1 c2 c3 c4

As we can see, moves starting with 21- are "backward moves" and their schemes are simply mirror images of their "forward" counterparts. Therefore we will no longer consider features of "backward" moves and we will focus on "forward" moves, that is moves which notation begins with 12-.

So there are only two sequential moves consisting of two steps, that is of two link exchanges: 12-34 and 12-43.

Move 12-43 is 2-opt move; we already know it and it does not require further comments.

Move 12-23 is a sequential move, despite the fact that it disconnects tour into two disjoint cycles. It may seem not useful and tempting to change the definition of a sequential move, but moves of this kind, although not producing valid tours, can be a part of connecting sequential move.

Let us take pure 3-opt moves. As we have already seen, there are exactly three pure 3-opt moves:

Pure 3-opt moves as sequential moves
Asymmetric
Move 12-43-65Move 12-56-43Move 12-65-34
c1 c2 c4 c3 c6 c5 c1 c2 c5 c6 c4 c3 c1 c2 c6 c5 c3 c4
Symmetric
Move 12-56-34
c1 c2 c5 c6 c3 c4

If we look closer to these diagrams we can notice that only two pure 3-opt moves: 12-43-65 and 12-56-43 come from 12-43 sequential move, that is from 2-opt move. The other two moves: asymmetric 12-65-34 and symmetric 12-56-34 come from disconnecting 12-34 sequential move. That is why we do not narrow the definition of a sequential move and actually consider disconnecting sequential moves — to have a consistent method of extending 2-exchange moves into full set of 3-moves, 3-moves to 4-moves and so on.

Origins of pure 3-opt moves from shorter sequential moves
12-34 12-65-34
12-56-34
12-43 12-56-43
12-43-65

We can notice that above table does not contain all possibilities of inserting a pair (5,6) or (6,5) into sequences 12-34 and 12-43. Moves 12-34-56, 12-34-65, 12-65-43 and 12-43-56 are missing, because they do not describe valid (connecting) 3-opt moves. Let us take a look at the last of them:

12-43-56
c1 c2 c4 c3 c5 c6

This is a disconnecting sequential move and we would not consider it when we want to narrow our searching to valid 2-opt and 3-opt moves. On the other way it leads to four valid sequential 4-opt moves (12-87-43-56, 12-78-43-56, 12-43-78-56, 12-43-87-56), so if we would like to consider all valid sequential 4-opt moves, then we should not omit it while building a sequential move step by step.

Saturday, May 27, 2017

Sequential moves and tour order

Let us take a look at diagrams of two 3-opt sequential moves:

Move AMove B
c1 c2 c4 c3 c5 c6 c1 c2 c5 c6 c3 c4

In both cases, A and B, the same set of cities is used to make a move: {c1, c2, c3, c4, c5, c6}, or: the same set of positions in tour. However, schemes for each of these two moves are different, and therefore the results would be different.

How can we distinguish between move of type A and of type B then?

We can use simple and unambiguous notation: by indicating the tour order of cities involved, starting from c1.

Let us take move A: we start from c1 and move along the tour clockwise. The next city from the set is c2 (second city engaged in move), then we encounter c4 (that is: fourth city of move), c3 (third city of move), c6 (sixth city of move) and c5 (fifth city of move). The tour order of cities in this sequential move is: c1, c2, c4, c3, c6, c5, so the move can be described as 12-43-65.

Move A = 12-43-65Move B = 12-56-43
c1 c2 c4 c3 c5 c6 c1 c2 c5 c6 c3 c4

In move B the tour order of cities is: c1, c2, c5, c6, c4, c3, so this move can be described as 12-56-43.

This notation is simple, unambiguous and natural. Thanks to it we no longer need to use some arbitrary numbers as labels for each type of 3-opt move, not saying anything about scheme of given move. Moreover, this notation can be used to identify a scheme of any other sequential move, for example sequential 4-opt moves, 5-opts and so on.

Three examples of 4-opt sequential moves
Move 12-87-43-65Move 12-78-56-43Move 12-43-65-87
c1 c2 c4 c3 c5 c6 c7 c8 c1 c2 c5 c6 c3 c4 c8 c7 c1 c2 c6 c5 c7 c8 c3 c4

Friday, May 26, 2017

Sequential moves

2-opt as a sequential move

Let us consider 2-opt move described in the following way:

  1. Step 0:
    1. Start from certain city c1 on tour.
c1
  1. Step 1:
    1. Remove link between c1 and one of its tour neighbors, c2.
    2. Add link between c2 and some other city c3.
c1 c2
c1 c2 c3
  1. Step 2:
    1. Remove link between c3 and its tour neighbor c4.
    2. Add link between c4 and the first city c1, to close the tour.
c1 c2 c4 c3
c1 c2 c4 c3

Note that steps 1 and 2 have the same scheme: remove a link between a city and its tour neighbor and then add link between this neighbor and some other city. Each step exchanges two links.

Example of 3-opt sequential move

We can extend 2-opt move to 3-opt move using the same scheme. Step 1 would be the same as in 2-opt move, so we show the procedure from step 2. Note that the only difference is in part B of this step:

  1. Step 2:
    1. Remove link between c3 and its tour neighbor c4.
    2. Add link between c4 and the some other city c5.
c1 c2 c4 c3
c1 c2 c4 c3 c5
  1. Step 3:
    1. Remove link between c5 and its tour neighbor c6.
    2. Add link between c6 and the first city c1, to close the tour.
c1 c2 c4 c3 c5 c6
c1 c2 c4 c3 c5 c6

Example of 4-opt sequential move

  1. Step 3:
    1. Remove link between c5 and its tour neighbor c6.
    2. Add link between c6 and the some other city c7.
c1 c2 c4 c3 c5 c6
c1 c2 c4 c3 c5 c6 c7
  1. Step 4:
    1. Remove link between c7 and its tour neighbor c8.
    2. Add link between c8 and the first city c1, to close the tour.
c1 c2 c4 c3 c5 c6 c7 c8
c1 c2 c4 c3 c5 c6 c7 c8

General scheme of a sequential move

As we can see the general scheme of sequential move is as follows:

  1. Step 1
    1. Remove link between c1 and its tour neighbor c2.
    2. Add link between c2 and some c3.
  2. Step 2
    1. Remove link between c3 and its tour neighbor c4.
    2. Add link between c4 and some c5.
  3. ...
  4. Last step can close the tour this way:
    1. Remove link between c_2k1 and its tour neighbor c_2k.
    2. Add link between c_2k and the first city c1, to close the tour.

The result of all steps is:

remove: (c1,c2) (c3,c4) (c5,c6) ... (c_2k1, c_2k)
add:    (c2,c3) (c4,c5) (c6,c7) ... (c_2k, c1)

Wednesday, May 17, 2017

3-opt symmetric move speedup

p1 p2 p3 p4 p5 p6 A B C
p1 p2 p3 p4 p5 p6
proc Make_3_Opt_Sym_Move_Fast(tour: var Tour_Array;
                              p1, p2, p3, p4, p5, p6: Tour_Index;
                              position: var City_Position_In_Tour) =

  let size_A = (N + p1 - p6 + 1) mod N
  let size_B = (N + p3 - p2 + 1) mod N
  let size_C = (N + p5 - p4 + 1) mod N

  if size_A > size_B + size_C:
    Swap_Segments(tour, p2, p3, p4, p5, position)
  elif size_B > size_A + size_C:
    Swap_Segments(tour, p4, p5, p6, p1, position)
  elif size_C > size_A + size_B:
    Swap_Segments(tour, p6, p1, p2, p3, position)
  else:
    Reverse_Segment(tour, p2, p3, position)
    Reverse_Segment(tour, p4, p5, position)
    Reverse_Segment(tour, p6, p1, position)

Monday, May 15, 2017

3-opt asymmetric move speedup

p1 p2 p3 p4 p5 p6 A B C
p1 p2 p3 p4 p5 p6

The cyclic tour before 3-opt asymmetric move can be described as consisting of three consecutive segments:

A B C  =  B C A  =  C A B

The 3-opt asymmetric move showed on the diagram transforms the tour into the form:

A' B' C

where symbol prime (') after a letter means that the segment is reversed.

Reversing whole tour doesn't change it, only its natural orientation is reversed, so:

A' B' C  =  (A' B' C)'  =  (C)' (B')' (A')'  =  C' B A

Tour is cyclic, therefore:

C' B A  =  A C' B  =  B A C'

This shows us three methods of obtaining result from 3-opt move:

A B C ==> A' B' C
C A B ==> A  C' B
B C A ==> C' B  A

In each method different segment remains unchanged in its original place, so we can use this fact to speed up the procedure of making the move.

proc Make_3_Opt_Asym_Move_Fast(tour: var Tour_Array;
                               p1, p2, p3, p4, p5, p6: Tour_Index;
                               position: var City_Position_In_Tour) =
    var
      city: City_Number
      left, right: Tour_Index
      segment: seq[City_Number]  # max. N/2 elements
      move_method: int

    # the tour consists of three consecutive segments:
    #   [p6,p1] [p2,p3] [p4,p5] == A B C
    #    A B C == B C A == C A B
    # there are three ways of *performing* the very same
    # 3-opt asymmetric move, in each different segment remains
    # intact in its original place:
    #   1) A B C ==> A' B' C  -- doesn't touch C 
    #   2) C A B ==> A  C' B  -- doesn't touch B
    #   3) B C A ==> C' B  A  -- doesn't touch A
    # Method 1, used so far, is default, but when segment B or A
    # has many cities compared to segment C then we choose
    # method 2 or 3, to not change the longest segment
    
    let size_A = (N + p1 - p6 + 1) mod N
    let size_B = (N + p3 - p2 + 1) mod N
    let size_C = (N + p5 - p4 + 1) mod N
    let sizeMax = max(size_A, max(size_B, size_C))

    move_method = 1
    if sizeMax == size_B:
      move_method = 2
    elif sizeMax == size_A:
      move_method = 3

    case move_method
    of 1:  # default method, not changing segment C
      ...
    of 2:  # not changing segment B
      ...
    of 3:  # not changing segment B
      ...
    else: # we use only 3 methods of performing asym. 3-opt move
      discard

The first, traditional method is as follows:

A B C p6 p1 p2 p3 p4 p5
A' B' C (rev.) (rev.)
    case move_method
    of 1:  # default method, not changing segment C
      #     A B C ==> A' B' C
      # reverse segment A in place:
      left  = p6
      right = p1
      for counter in 1 .. size_A div 2:
        city        = tour[right]
        tour[right] = tour[left]
        tour[left]  = city
        position[tour[left]]  = left
        position[tour[right]] = right
        left  = t_succ(left)
        right = t_pred(right)
      # reverse segment B in place:
      left  = p2
      right = p3
      for counter in 1 .. size_B div 2:
        city        = tour[right]
        tour[right] = tour[left]
        tour[left]  = city
        position[tour[left]]  = left
        position[tour[right]] = right
        left  = t_succ(left)
        right = t_pred(right)

The second method is:

C A B p4 p5 p6 p1 p2 p3
A C' B (rev.)
    case move_method
    ...
    of 2:  # not changing segment B
      #     C A B ==> A C' B
      # make a copy of segment C=[p4,p5]:
      segment = newSeq[City_Number](size_C)
      left = p4
      for pos in 0 .. size_C-1:
        segment[pos] = tour[left]
        left = t_succ(left)
      # move segment A backward, it should end at p4:
      left  = p6
      right = p4
      for counter in 1 .. size_A:
        tour[right] = tour[left]
        position[tour[right]] = right
        left  = t_succ(left)
        right = t_succ(right)
      # put copy of reversed C before B in tour:
      right = p1
      for pos in 0 .. size_C-1:
        tour[right] = segment[pos]
        position[tour[right]] = right
        right = t_pred(right)

The third method is:

B C A p2 p3 p4 p5 p6 p1
C' B A (rev.)
    case move_method
    ...
    of 3:  # not changing segment A
      #     B C A ==> C' B A
      # make a copy of reversed segment C=[p4,p5]:
      segment = newSeq[City_Number](size_C)
      right = p5
      for pos in 0 .. size_C-1:
        segment[pos] = tour[right]
        right = t_pred(right)
      # shift segment B forward, it should end at p5:
      left  = p3
      right = p5
      for counter in 1 .. size_B:
        tour[right] = tour[left]
        position[tour[right]] = right
        left  = t_pred(left)
        right = t_pred(right)
      # put the copy of reversed C in its new place in tour:
      left = p2
      for pos in 0 .. size_C-1:
        tour[left] = segment[pos]
        position[tour[left]] = left
        left = t_succ(left)

Alternative version

Above solution has two disadvantages. Firstly, it is quite complex. Secondly, methods 2 and 3 have to use temporary variable to store whole segment C during shifting segment A or B.

Thanks to properties of inversion operation the second disadvantage can be eliminated:

(C A')'  =  (A')' C' = A C'

Therefore we can replace method 2 by:

C A B p4 p5 p6 p1 p2 p3
C A' B (rev.)
A C' B (rev.)
    case move_method
    ...
    of 2:  # not changing segment B
      #     C A B ==> ==> C A' B ==> A C' B
      # reverse segment A in place:
      left  = p6
      right = p1
      for counter in 1 .. size_A div 2:
        city        = tour[right]
        tour[right] = tour[left]
        tour[left]  = city
        left  = t_succ(left)
        right = t_pred(right)
      # reverse segment (A'C) in place:
      left  = p4
      right = p1
      for counter in 1 .. (size_A+size_C) div 2:
        city        = tour[right]
        tour[right] = tour[left]
        tour[left]  = city
        left  = t_succ(left)
        right = t_pred(right)
      # update position[] array:
      left = p4
      for pos in 0 .. size_A+size_C:
        position[tour[left]] = left
        left  = t_succ(left)

and method 3 by:

B C A p2 p3 p4 p5 p6 p1
B' C A (rev.)
C' B A (rev.)
    case move_method
    ...
    of 3:  # not changing segment A
      #     B C A ==> B' C A ==> C' B A
      # reverse segment B in place:
      left  = p2
      right = p3
      for counter in 1 .. size_B div 2:
        city        = tour[right]
        tour[right] = tour[left]
        tour[left]  = city
        left  = t_succ(left)
        right = t_pred(right)
      # reverse segment (B'C) in place:
      left  = p2
      right = p5
      for counter in 1 .. (size_B+size_C) div 2:
        city        = tour[right]
        tour[right] = tour[left]
        tour[left]  = city
        left  = t_succ(left)
        right = t_pred(right)
      # update position[] array:
      left = p2
      for pos in 0 .. size_B+size_C:
        position[tour[left]] = left
        left  = t_succ(left))

This alternative versions of speedup methods, although does not need additional memory for segment variable, could be somewhat slower than more complex versions shown first, and in fact is not very elegant.

Final version

We can use Swap_Segments() procedure to make the implementation of this speedup both concise and clear, although probably slightly slower than the complex version shown first and still using additional variable to store a segment during swap:


      case move_method
      of 1:  # default method, not changing segment C
        Reverse_Segment(tour, p6, p1, position)
        Reverse_Segment(tour, p2, p3, position)
      of 2:  # not changing segment B
        Reverse_Segment(tour, p4, p5, position)
        Swap_Segments(tour, p4, p5, p6, p1, position)
      of 3:  # not changing segment A
        Reverse_Segment(tour, p4, p5, position)
        Swap_Segments(tour, p2, p3, p4, p5, position)
      else: # we use only 3 methods of performing asym. 3-opt move
        discard

Friday, May 12, 2017

Swapping segments

s1 e1 s2 e2 A B
B A
proc Swap_Segments(tour: var Tour_Array;
                   start_1, end_1, start_2, end_2: Tour_Index;
                   position: var City_Position_In_Tour) =
  ## Swaps two consecutive segments of tour:
  ## [start_1, end_1] and [start_2, end_2]
  ## NOTE: start_2 should be tour successor of end_1
  var
    left, right: Tour_Index
    segment: seq[City_Number]

  let size_1 = (N + end_1 - start_1 + 1) mod N
  let size_2 = (N + end_2 - start_2 + 1) mod N
    
  # make a copy of first segment:
  segment = newSeq[City_Number](size_1)
  right = end_1
  for pos in 0 .. size_1-1:
    segment[pos] = tour[right]
    right = t_pred(right)

  # move second segment backward, it should start at start_1:
  left  = start_2
  right = start_1
  for counter in 1 .. size_2:
    tour[right] = tour[left]
    position[tour[right]] = right
    left  = t_succ(left)
    right = t_succ(right)

  # put the copy of first segment in its new place in tour:
  left = end_2
  for pos in 0 .. size_1-1:
    tour[left] = segment[pos]
    position[tour[left]] = left
    left = t_pred(left)

Monday, May 8, 2017

2-opt move speedup

If segment reversing is used as an independent 2-opt move, not as a part of sequence (e.g. to apply 3-opt move), then we can take advantage of the fact that the tour is cyclic. Therefore reversing a segment has the same effect as reversing its complementary segment and changing "natural orientation" of the tour array.

p1 p2 p3 p4
p1 p2 p3 p4

Using array representation of tour causes that reversing a segment is done by swapping elements of array. The number of swaps (thus the amount of time) needed to reverse a segment is proportional to the number of cities the segment consists of. So when the segment to reverse is longer than half of tour, then can we reverse the complementary segment to speed-up the transformation.

proc t_pred(pos: Tour_Index): Tour_Index {.inline.} =
  ## returns position of tour predecessor for given position 
  result = (N + pos - 1) mod N

proc t_succ(pos: Tour_Index): Tour_Index {.inline.} =
  ## returns position of tour successor for given position 
  result = (pos + 1) mod N
proc Make_2_Opt_Move_Fast(tour: var Tour_Array;
                          p1, p2, p3, p4: Tour_Index;
                          position: var City_Position_In_Tour) =
  ## Reverses order of elements in segment [p2, p3] of tour:
  ## if the complementary segment is shorter, reverses the complementary
  # Assumes: p1==t_pred(p2), p4==t_succ(p3)
  var
    city: City_Number
    left, right: Tour_Index
    inversionSize: int

  inversionSize = (p3 - p2 + 1)
  if inversionSize < 0:
    inversionSize = inversionSize + N

  if (2 * inversionSize > N):  # segment longer than half of tour
    left  = p4  # t_succ(p3)
    right = p1  # t_pred(p2)
    inversionSize = N - inversionSize
  else:
    left  = p2
    right = p3

  inversionSize = inversionSize div 2

  for counter in 1 .. inversionSize:
    city        = tour[right]
    tour[right] = tour[left]
    tour[left]  = city

    position[tour[left]]  = left
    position[tour[right]] = right

    left  = t_succ(left)
    right = t_pred(right)
  #end_for counter loop