### 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]`

.

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.

### 3-opt move reduced to a single 2-opt move

We have reduced number of cases of 3-opt move from 7 to 3. There is a question: what about case 3, equal to a single 2-opt move? What can we do with this case to simplify the code and what are the consequences?

From:

we have

This proves that case 3 move is equivalent to the two subsequent moves: of case 6 and of case 7.

Note that this does not mean that we can ommit case 3 *without affecting the performace*, but it does mean that we would not overlook a good (improving) move, even if the algorithm in this case is not very efficient (reversing segments *a* and *c* back and forth).

So we can skip the explicit checking of case 3 and change the line:

```
for optCase in [opt3_case_3, opt3_case_6, opt3_case_7]:
```

to:
```
for optCase in [opt3_case_6, opt3_case_7]:
```

Why case3 is not needed ? What if case6 or case7 (alone) will not improve tour leading to 2 subsequent moves 6 and 7 ?

ReplyDeletePS. Great blog :)

1) if case3 improves the tour

ReplyDeleteand

2) case3 is is equivalent to the two subsequent moves: of case6 and of case7

then:

gain(case3) = gain(case6) + gain(case(7) > 0

so:

3) either case6 is improving or case7 is improving, or both are improving.

thx

ReplyDeleteLet's say that tour is like on picture showing case 3 (ab'c). If we apply move variant 6 we will get a'b'c' and gain will be negative so move will not be done. If we apply move variant 7 we will get a'b'c', gain can also be negative so move will not be done. If we apply move variant 3 gain will be positive. What I'm missing here ?

ReplyDeleteNote that

ReplyDeletecase3(abc) = case7(case6(abc))

_and_

case3(abc) = case6(case7(abc))

When gain from case3(abc) is positive, then either gain from case6(abc) is positive, or gain from case7(abc) is positive, or both are positive.

If you prefer it this way: lets number cities we use from 1 to 6. And lets use concise notation of '12' for length of link between city 1 and city 2, i.e. 'distance(city_1,city_2)'. Then gain(case3) is equal (12+34)-(13+24). A scheme could be useful.

So then:

gain(case3(abc)) > 0 if 13+24 < 12+34

Now, suppose that gain(case6) is negative; it means:

gain(case6(abc)) < 0 if 12+24+56 < 14+26+35

When we summ the two inequalities up, we get:

13+24+56 < 14+26+35

But then it means that:

gain(case7(abc)) = (14+26+35) - (13+24+56) > 0.

So despite of fact that gain from case6(abc) is negative an improving case3(abc) move would be found because then case7(abc) has posivite gain.

Similarly for the other case: when gain3>0 and gain7<0.

My understanding is as follows:

ReplyDeleteLet's say that initial tour is: 1->2->3->4->5->6 (full circle) and that case3 improves the tour so tour 1->3->2->4->5->6 is shorter. It means that:

gain(case3) = 12+34+56 - (13+24+56) > 0, we delete links 12, 34, 56 and creates 13,24, 56. Equation is: deleted links - added links

Suppose that case6 is not improving tour so gain is negative:

gain(case6) = 12+34+56 - (14+26+35) < 0.

When we summ, we get:

13+24+56 < 14+26+35, we can write this as:

13+24+56 - (12+34+56) < 14+26+35 - (12+34+56) #multiply by -1

12+34+56 -(13+24+56) > 12+34+56 -(14+26+35)

gain(case3) > gain(case6)

gain(case7) is deleted links - added links:

gain(case7) = 12+34+56 - (14+36+25)

I don't see how your formula (14+26+35) - (13+24+56) describes gain(case7) ?

You are right, there is a fatal oversight here and the proof is wrong.

DeleteOne more question. Which opt3 case for (i, j, k) = (0, 1, 2) reverse tour ?

ReplyDeleteI am sorry, but I do not understand the root of your question. Reversed tour is the same tour, because we consider symmetric TSP.

DeleteYou wrote:

ReplyDeleteFor 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.

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

ReplyDelete