Typical mistakes · In summary¶

31.13 Typical mistakes¶

Warning

Forgetting that a local optimum depends on the neighbourhood. The \(LPT\) solution is a local optimum for move, but not for swap.
Using the number of bins as the only objective. It is blind: most neighbours have the same value, and the search stops on a plateau; the auxiliary objective \(SQ\) tells them apart.
Ignoring the order of examination. The moves are examined in a fixed order and ties go to the first one examined (in Example 31.6 item \(3\) comes before item \(5\)).
Computing the wrong \(\Delta\) for a 2-opt move. Only the two removed and the two added edges count; the two edges cannot share a city.
Concluding that a local optimum is optimal. Only a dual bound can say so.

In summary

A local search moves to a better neighbour until none exists: it returns a local optimum, a better primal bound.
First improvement is faster per step, best improvement takes the largest gain; both stop in a local optimum of the neighbourhood.
Incremental evaluation, auxiliary objectives and penalties make the search fast and able to cross plateaus and infeasible regions.
Variable neighbourhood descent and multi-start enlarge what the search can reach, but the restarts have no memory.

Dashboard of the reference instances. Starting solution and local optimum:

problem	start	local search	\(z(I)\)
TSP	\(25\) (\(NN\))	\(18\) (2-opt)	\(18\)
\(P\,\|\|\,C_{\max}\)	\(11\) (\(LPT\))	\(9\) (swap, \(=\mathrm{LB}(I)\))	\(9\)
BPP	\(4\) (\(FF\))	\(3\) (move, \(SQ\))	\(3\)

The dual bounds come from the chapter «Heuristic algorithms: definitions»: the local search alone does not certify its result.

Exercises on this chapter: Local search