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:
|
ABCD ABCd ABcD ABcd AbCD AbCd AbcD Abcd |
ACBD ACBd ACbD ACbd AcBD AcBd AcbD Acbd |
ADBC ADBc ADbC ADbc AdBC AdBc AdbC Adbc |
ABDC ABDc ABdC ABdc AbDC AbDc AbdC Abdc |
ACDB ACDb ACdB ACdb AcDB AcDb AcdB Acdb |
ADCB ADCb ADcB ADcb AdCB AdCb AdcB Adcb |
| equals original tour | ||
| ABCD | ||
| equivalent to a single 2-opt move | ||
| ABCd | ABcD | AbCD |
| AcbD | ABdc | Adcb |
| equivalent to a single 3-opt move | ||
| ABcd | AbcD | ACBD |
| ACbD | AcBD | Acbd |
| ADBC | AdBC | ABDC |
| ABDc | ABdC | |
| ACDB | ACDb | ADcb |
| AdcB | ||
| pure 4-opt moves | ||
| A. sequential 4-opt moves | ||
| Abcd | ACBd | ACbd |
| AcBd | ADBc | ADbC |
| AdBc | AdbC | Adbc |
| AbDC | AbDc | AbdC |
| ACdB | ACdb | AcDB |
| AcDb | Acdb | ADCb |
| ADcB | AdCB | |
| B. non-sequential 4-opt moves | ||
| AbCd | ADbc | AcdB |
| ADCB | AdCb | |
I'm curious about the non-sequential 4-opt moves. Four of them (not ADCB) can be reconstructed from two 2-opt moves. If a graph is 2-optimized, is there any benefit to trying these four moves?
ReplyDeleteActually, you discussed this in a later post! Thanks so much, this is a wonderful blog.
DeleteI found this blog when struggling with Lin-Kernighan algorithm. I am very grateful to the author, wish you post more useful algorithm tutorials. I have a question, if we have 4 segments and we need to discover every case of 4-opt (48 cases). Is it possible if a 2-opt or a 3-opt case produces a better gain than a pure 4-opt case?
ReplyDeleteThank you for nice comment.
ReplyDeleteYes, it is possible that for given 4 segment a pure 2-opt or a pure 3-opt case produces a better gain than a pure 4-opt case. Sometimes, though rarely, cascading processing is used:
1. Apply all improving pure 2-opts
2. Apply all improving pure 3-opts
3. Apply all improving pure 4-opts
4. Return to step 1 until no more improvements in steps 2-3 is found.
Thank you for your quick comment. I have an idea in the research but I'm not sure if it's OK or not (my professor is not LK expert). Could you give me some comments before coding? The idea is as follows:
DeleteSuppose that in LK with k=4, we find out a 3-opt or a 4-opt with positive gain. After that, we check every case of this opt and choose the best combination to exchange links (this opt will be bypassed if all gainFromCloseUp<0) . I think this will increase running time but it can avoid the complicated backtracking process. It also allows to deal with non-sequential moves (4-opt). We can reduce running time by checking pure 3-opt or 4-opt only.
This approach misses 2-opt improving moves, I suppose?
DeleteMoreover it would be not LK algorithm, because 'k' in LK is *not* constant. The strenght of LK is that it is k-opt with unlimited 'k': value of 'k' increases *automatically* during processing until the partial gain is positive.
For example lets consider full 3opt: how does it differ from LK based on 3-opt as first move? Not by using partial gain criterion, because we can use it in any sequential k-opt, to skip unpromising moves. Full 3-opt algorithm stops for given starting city when there are no improving moves starting from this city. Now, LK algorithm does more: it checks if the partial gain is still positive for any of *non-improving* moves. Then it temporarily makes such move and extends the sequence by using 2opt (or 3opt and so on). This way it now uses limited 4opt searching. When extended sequence cannot be closed with gainFromCloseUp>0, but partial gain is still positive, it extends it further (k=5), until improving move is found or partial gain is negative (or zero). If at the end of process partial gain is negative (or zero) and improving move has not been found, LK rollbacks all 'temporary' moves.
Thank you, sorry for my poor expression. I mean I use the strategy that at current opt, tour T* will replace tour T as soon as a gainFromCloseUp>0 is found. For example, at 2-opt i=2), if we have a gain>0 and gainFromCloseUp>0, we set T:=T* and reset the process from beginning. If gain>0 and gainFromCloseUp<=0, we continue to find a gain with 3-Opt. If a gain is found, this time we check every case of 3-opt based on segments of this gain and choose the best one with gainFromCloseUp>0 to replace T. If not, we continue the process with 4-Opt and so on until k-opt is reached. By using this method, I hope we can find the best tour T* among possible cases of current-opt instead of checking only one case (the case that we close up T by connect c1 with for example, c6 of 3-opt. This case sometime do not guaranty gainFromCloseUp>0 but another case may yield a chance). I also hope to eliminate the complicated backtracking process because we don't have to care about tour direction when checking cases of i-opt (the only thing we care is total length of removed edges - total length of added edges>0).
DeleteYes, backtracking in LK algorithm is the hard part. Your idea is good, but please keep in mind, that the original LK (as described in 1973) does use backtracking: because longer sequence can bring better gain from close-up than the first encountered sequence that gives any gain. We do not know it in advance. However, if given LK implementation is strong enough then backracking makes only very small differences in results.
DeleteThank you, I'll try both cases of with and without backtracking to compare. Hope to receive more advice from you when coding this algorithm.
Delete