Tuesday, March 7, 2017

3-opt: general idea

Boundaries for loops

As in the case of 2-opt we set the boundaries of the for loops. Suppose we have i==0, then what boundaries should we set up for j and k? In 3-opt we do not exclude pairs of subsequent positions, so j can be equal i+1 or k equal j+1. In these cases we get single 2-opt move, which is a specific case of 3-opt move. For example (i, j, k) == (0, 1, 2) describes 2-opt move performed by reversing segment tour[1] .. tour[2].

0 1 2 N-1 N-2 N-3 i = 0 j = 1 ... N-3 k = j+1 .. N-1

Having set up the loops for j and k for a i==0 case, we can simply “rotate” the whole triplet (i, j, k) on the tour. This means: change i to some value and at the same time add this new value of i to j and k.

for counter_1 in 0 .. N-1:
      i = counter_1 # first cut after i
...
      for counter_2 in 1 .. N-3: 
        j = (i + counter_2) mod N # second cut after j
...
        for counter_3 in counter_2+1 .. N-1:
          k = (i + counter_3) mod N  # third cut after k
...

Preliminary version of 3-optimization code

The only remaining diference between 2- and 3-opt iterative algorithm is the need to deal with different cases of 3-opt, so one more loop is needed.

proc LS_3_Opt_General_Idea(tour: var Tour_Array) =
  ## Optimizes the given tour using 3-opt.
  # Using tour array as representation of tour shortens the tour
  # by repeating 3-opt moves until no improvement can by done:
  # in every iteration looks for and applies the first move that
  # gives positive length gain.
  var
    locallyOptimal: bool = false
    i, j, k: Tour_Index
    X1, X2, Y1, Y2, Z1, Z2: City_Number
    optCase: Reconnection_3_optCase
    gainExpected: Length_Gain

  while not locallyOptimal:
    locallyOptimal = true

    block four_loops:
      for counter_1 in 0 .. N-1:
        i = counter_1 # first cut after i
        X1 = tour[i]
        X2 = tour[(i+1) mod N]
        for counter_2 in 1 .. N-3:
          j = (i + counter_2) mod N # second cut after j
          Y1 = tour[j]
          Y2 = tour[(j+1) mod N]
          for counter_3 in counter_2+1 .. N-1:
            k = (i + counter_3) mod N  # third cut after k
            Z1 = tour[k]
            Z2 = tour[(k+1) mod N]

            for optCase in opt3_case_1 .. opt3_case_7:
              gainExpected = Gain_From_3_Opt(X1, X2,
                                             Y1, Y2,
                                             Z1, Z2,
                                             optCase)
              if gainExpected > 0:
                Make_3_Opt_Move(tour, i, j, k, optCase)
                locallyOptimal = false
                break four_loops

Redundant checks

We should not forget that a tour is cyclic and the problem is symmetric. Instead of conditional statement and making a move let's remove these lines for a while and replace them with printing loop counters, corresponding positions and gain. Among lines of output we would see for example:

c1 c2 c3   i  j  k  case gain
11 21 36   11 32 47 [4]  -809
11 21 36   11 32 47 [5] -1034
11 21 36   11 32 47 [6] -1029
11 21 36   11 32 47 [7] -1028

32 15 79   32 47 11 [4] -1029
32 15 79   32 47 11 [5]  -809
32 15 79   32 47 11 [6] -1034
32 15 79   32 47 11 [7] -1028

47 64 85   47 11 32 [4] -1034
47 64 85   47 11 32 [5] -1029
47 64 85   47 11 32 [6]  -809
47 64 85   47 11 32 [7] -1028

This is not a concidence. The output show us that there is no need to check cases 4 i 5. We make full cycle through the tour to examine possible 3-opt moves, so when considering permutations of given (i, j, k) triplet cases 4 and 5 are just rotated versions of case 6 (see: 3-opt move). Examining cases 4 and 5 takes additional time, but gives the same result.

The same happens for cases 1-3 of 3-opt, equal to single 2-moves:

c1 c2 c3   i  j  k  case gain
11 21 36   11 32 47 [1] -1070
11 21 36   11 32 47 [2]  -244
11 21 36   11 32 47 [3]  -530

32 15 79   32 47 11 [1]  -244
32 15 79   32 47 11 [2]  -530
32 15 79   32 47 11 [3] -1070

47 64 85   47 11 32 [1]  -530
47 64 85   47 11 32 [2] -1070
47 64 85   47 11 32 [3]  -244

So we should change the line:

   for optCase in opt3_case_1 .. opt3_case_7:
to:
   for optCase in [opt3_case_3, opt3_case_6, opt3_case_7]:

to increase efficiency.

7 comments:

  1. You wrote:

    For example (i, j, k) == (0, 1, 2) describes 2-opt move performed by reversing segment tour[1] .. tour[2].

    I don't understand this sentence.

    ReplyDelete
  2. Reversing a _segment_ (namely: segment containing cities from city on posisition 1 to city position 2), not 'reversing tour'.

    ReplyDelete
  3. Can you please explain only two steps of the loop as I am having trouble to understand. For example for N = 6, first iteration gives i, j, k = 0, 2, 4. I am having same cities on being repeated in the route.

    ReplyDelete
    Replies
    1. N = 6
      The first iteration:
      counter_1 = 0
      i = counter_1 = 0
      counter_2 = 1
      j = (i + counter_2) mod N = 1 mod 6 = 1
      counter_3 = counter_2 + 1 = 2
      k = (i + counter_3) mod N = 2 mod N = 2

      (i, j, k) = (0, 1, 2)

      Delete
  4. After first iteration with i, j, k = 0, 1, 2 => route X1 X2 X2 Y1 Y1 Y2.
    "(i, j, k) = 0, 1, 2"
    "(i, j, k) = 0, 1, 3"
    "(i, j, k) = 0, 1, 4"
    "(i, j, k) = 0, 1, 5"
    "(i, j, k) = 0, 2, 3"
    "(i, j, k) = 0, 2, 4"
    "(i, j, k) = 0, 2, 5"
    "(i, j, k) = 0, 3, 4"
    "(i, j, k) = 0, 3, 5"
    "(i, j, k) = 1, 2, 3"
    "(i, j, k) = 1, 2, 4"
    "(i, j, k) = 1, 2, 5"
    "(i, j, k) = 1, 2, 0"
    "(i, j, k) = 1, 3, 4"
    "(i, j, k) = 1, 3, 5"
    "(i, j, k) = 1, 3, 0"
    "(i, j, k) = 1, 4, 5"
    "(i, j, k) = 1, 4, 0"
    "(i, j, k) = 2, 3, 4"
    "(i, j, k) = 2, 3, 5"
    "(i, j, k) = 2, 3, 0"
    "(i, j, k) = 2, 3, 1"
    "(i, j, k) = 2, 4, 5"
    "(i, j, k) = 2, 4, 0"
    "(i, j, k) = 2, 4, 1"
    "(i, j, k) = 2, 5, 0"
    "(i, j, k) = 2, 5, 1"
    "(i, j, k) = 3, 4, 5"
    "(i, j, k) = 3, 4, 0"
    "(i, j, k) = 3, 4, 1"
    "(i, j, k) = 3, 4, 2"
    "(i, j, k) = 3, 5, 0"
    "(i, j, k) = 3, 5, 1"
    "(i, j, k) = 3, 5, 2"
    "(i, j, k) = 3, 0, 1"
    "(i, j, k) = 3, 0, 2"
    "(i, j, k) = 4, 5, 0"
    "(i, j, k) = 4, 5, 1"
    "(i, j, k) = 4, 5, 2"
    "(i, j, k) = 4, 5, 3"
    "(i, j, k) = 4, 0, 1"
    "(i, j, k) = 4, 0, 2"
    "(i, j, k) = 4, 0, 3"
    "(i, j, k) = 4, 1, 2"
    "(i, j, k) = 4, 1, 3"
    "(i, j, k) = 5, 0, 1"
    "(i, j, k) = 5, 0, 2"
    "(i, j, k) = 5, 0, 3"
    "(i, j, k) = 5, 0, 4"
    "(i, j, k) = 5, 1, 2"
    "(i, j, k) = 5, 1, 3"
    "(i, j, k) = 5, 1, 4"
    "(i, j, k) = 5, 2, 3"
    "(i, j, k) = 5, 2, 4"
    These is the result after all iterations + iterating for opt-cases. Is this correct?

    ReplyDelete
  5. As there is no construct for breaking multiple loops at once in programming languages, I think it would be better if you moved the calculations of i, x1, x2, j, y1, y2 inside the innermost loop(counter_3). It took me three days to debug :')

    ReplyDelete