Don't Look Bits (DLB) – general idea

The idea

A local improvement algorithm can be made faster when we notice that the running time includes the time to needed perform the move, but also the time needed to examine possible good moves and find an improving move (if there is one).

If for a given city X1 we previously did not find any improving move and it still has the same neighbors (none of the links between this city and its neighbors has been changed), then chances that we will find an improving move for this city in current iteration are small (although non-zero, see below).

The concept based on this observation is known as don’t look bits (DLB). We use special flag for each of the cities. Initially all the flags are turned off, which means that we allow searching for improving moves starting from given city. When a search for improving move starting from city C fails, then the bit for this city is turned on. When a move is performed in which this city is involved as one of the endpoints of the exchanged links, then the bit for this city is turned off. When we consider candidates for X1, the first city of an improving move, we skip all cities which have their don’t-look bits set to on.

Comments

Consider also what happens with DLB when we examine moves “in one direction” only (see 2-opt basic algorithn). In such case we consider only one of the two links of X1, that is the link to its successor, the link between tour[i] and tour[i+1]. If we failed to found any improving move, then we turn the don’t-look bit for X1 on. If then in some subsequent iteration a move is performed in which X1 is one of the endpoints of the exchanged links, then we turn the don’t-look bit off. It works as expected. But what if a move changes the orientation of the segment in which X1 is inside, but is not at one of its ends? The don’t-look bit remains unchanged, although now the previous predecessor of X1 is its current successor, and we examined X1 only with its succcessor to verify that there are no improvements for X1. So now there could be some improving move for X1 in “forward” orientation, but it will not be examined, because the don’t-look bit for this city is still on.

That is why in the code below we consider both tour neighbors of a given city.

For the same reason of not missing improving moves we do not limit searching to the cases where j>i, but cosider all possible pairs of (i, j).

Aside from the above, it may seem impossible that new, improving move for given city could appear when both neighbors of this city remain unchanged, but let us take a closer look:

However we should notice that in this case cities Y1 and Z1 have their don’t-look bits set to off after making the move. Therefore the new, possibly improving move: from X0 and involving the link between Y1 and Z1, will be examined in one of the subsequent iterations, that is as a move from Y1 or as a move from Z1.

Using Dont' Looks Bits with a simple 2-opt

type
  DLB_Array = array[City_Number, bool]
  Orientation = enum forward, backward

proc LS_2_Opt_DLB_General_Idea(tour: var Tour_Array) =
  ## Optimizes the given tour using 2-opt with Don't Look Bits (DLB) 
  var
    locallyOptimal: bool = false
    i, j: Tour_Index
    pos_2_Limit: Tour_Index
    X1, X2, Y1, Y2: City_Number
    DontLook: DLB_Array

  for city in 0 .. N-1:
    DontLook[city] = false

  while not locallyOptimal:
    locallyOptimal = true
    block three_loops:
      for counter_1 in 0 .. N-1:

        if DontLook[tour[counter_1]]:
          continue

        for direction in [forward, backward]:  # NOTE: both tour neighbors
          # consider link between t[i] and t[i+1],
          # then between t[i-1] and t[i]
          if direction == forward:
            i  = counter_1
          else:
            i  = (N + counter_1 - 1) mod N
          X1 = tour[i]
          X2 = tour[(i+1) mod N]

          for counter_2 in 0 .. N-1:
            j = counter_2  # 2nd cut between t[j] and t[j+1]
            Y1 = tour[j]
            Y2 = tour[(j+1) mod N]
            if (X1 == Y1) or (X2 == Y1) or (Y2 == X1):
              # the same city or adjacent cities
              continue

            if Gain_From_2_Opt(X1, X2, Y1, Y2) > 0:
              DontLook[X1] = false
              DontLook[X2] = false
              DontLook[Y1] = false
              DontLook[Y2] = false
              Make_2_Opt_Move(tour, i, j)
              locallyOptimal = false
              break three_loops
        # end_for backward loop
        DontLook[tour[counter_1]] = true
      # end_for counter_1 loop

It is expected that the resulting tours will be different from the ones from 2-opt First Take procedure.

See also an alternative

Instead of don't look bits speedup we can use an array indexed by city numbers, in which each element contains length of tour after improving from given city. This would make implementation simpler, but would require more memory, because of storing numbers (lengths), which are longer than booleans.

Some simple statistics

Relative time, best length, average length and worst length for all tours created by NN heuristic and improved by 2-opt and 2-opt with DLBs algorithms. Random planar problems, N=100.

Problem #	Method	Time	Best	Avg	Worst
1	NN	100	100.00	112.31	122.36
	NN + 2opt	1146	93.09	97.73	104.89
	NN + 2opt-DLB	313	94.42	99.86	104.98
2	NN	100	100.00	108.83	124.17
	NN + 2opt	1462	86.16	90.20	97.26
	NN + 2opt-DLB	293	87.82	91.26	96.06
3	NN	100	100.00	106.21	115.53
	NN + 2opt	1566	82.19	85.77	89.56
	NN + 2opt-DLB	313	82.66	87.39	92.24
4	NN	100	100.00	105.83	112.36
	NN + 2opt	1146	90.02	94.78	98.19
	NN + 2opt-DLB	213	91.64	94.91	99.78
5	NN	100	100.00	111.19	119.81
	NN + 2opt	781	91.91	95.43	99.81
	NN + 2opt-DLB	293	91.81	96.31	102.66
6	NN	100	100.00	112.89	126.03
	NN + 2opt	1360	94.35	99.05	104.02
	NN + 2opt-DLB	206	96.02	99.56	105.29
7	NN	100	100.00	109.35	117.75
	NN + 2opt	1146	90.47	93.28	99.21
	NN + 2opt-DLB	313	90.55	93.80	99.71
8	NN	100	100.00	109.02	120.22
	NN + 2opt	1253	86.50	91.88	98.31
	NN + 2opt-DLB	313	88.45	92.64	95.84
9	NN	100	100.00	108.79	116.77
	NN + 2opt	940	95.46	97.58	101.63
	NN + 2opt-DLB	420	95.50	98.14	102.77
10	NN	100	100.00	105.40	113.11
	NN + 2opt	1268	82.12	85.66	89.87
	NN + 2opt-DLB	293	81.78	86.40	90.22