Lin-Kernighan algorithm basics – part 7

Now we can make a break and check out progress made so far. Suppose that we want to stop constructing starting LK move, and even more: stop constructing LK implementation. Then we would obtain code for sequential 4-opt optimization. This would need only small piece of code:

const
  OPT_5_IMPLEMENTED = false

proc LK_5Move(...): bool =
  result = false

Implementation of 4-opt sequential optimization obtained this way gives better resulting tours than simple implementation 3-opt with neighbor lists and DLB shown before. Moreover, it is much faster, although it does not use DLB (which can be easily added).

Some simple statistics

Relative time, best length, average length and worst length for all tours created by NN heuristic and improved by 3-opt and sequential 4-opt, both with neighbor lists. (Note that this 3-opt implementation uses slower method of applying moves than that in 4seq-opt.) Random planar problems, N=100.

Problem #	Method	Time	Best	Avg	Worst
1	NN	100	100.00	110.42	125.14
	NN + 3opt-ND(24)	4393	94.14	95.34	98.10
	NN + 4seq-opt-ND(24)	681	94.14	94.91	96.41
2	NN	100	100.00	108.10	121.20
	NN + 3opt-ND(24)	4393	86.68	88.64	90.28
	NN + 4seq-opt-ND(24)	1268	86.68	87.76	91.14
3	NN	100	100.00	109.51	118.10
	NN + 3opt-ND(24)	4493	90.25	91.80	93.73
	NN + 4seq-opt-ND(24)	1168	89.66	90.88	92.49
4	NN	100	100.00	109.58	118.16
	NN + 3opt-ND(24)	4493	88.78	90.55	93.41
	NN + 4seq-opt-ND(24)	1850	88.78	90.15	91.85
5	NN	100	100.00	111.02	122.46
	NN + 3opt-ND(24)	4100	90.42	91.97	94.34
	NN + 4seq-opt-ND(24)	1074	90.42	91.38	92.17
6	NN	100	100.00	111.49	125.67
	NN + 3opt-ND(24)	4587	87.91	89.82	91.69
	NN + 4seq-opt-ND(24)	1174	87.88	88.66	90.99
7	NN	100	100.00	108.23	121.77
	NN + 3opt-ND(24)	4493	92.82	93.84	96.40
	NN + 4seq-opt-ND(24)	1168	92.71	93.73	95.80
8	NN	100	100.00	106.07	119.49
	NN + 3opt-ND(24)	4587	86.00	87.74	90.74
	NN + 4seq-opt-ND(24)	1462	85.77	86.75	88.27
9	NN	100	100.00	111.77	124.00
	NN + 3opt-ND(24)	4493	93.25	94.18	96.55
	NN + 4seq-opt-ND(24)	1950	92.84	93.82	95.23
10	NN	100	100.00	110.89	117.01
	NN + 3opt-ND(24)	4293	90.23	91.02	94.77
	NN + 4seq-opt-ND(24)	1368	90.16	90.65	92.93