Local search: the scheme · Neighbourhoods for the four problems¶
Part 4 · Heuristic algorithms · Chapter 31 · Chapter 31: Local search · Lecture notes, volume 4 (PDF) · Slides (1/2) · Slides (2/2) · Exercises: Local search · App: TSP: nearest neighbour and 2-opt
31.3 Local search: the scheme¶
- The pseudo-code of \(LS\) reads as follows. The function \(\textit{Improve}\) explores the neighbourhood and returns an improving neighbour of \(x\), or \(\textit{NULL}\) if there is none.
Algorithm: Local search
-
A local search is defined by four ingredients:
-
the starting solution \(x^0\), computed by a constructive heuristic or at random;
-
the neighbourhood \(N\), i.e., the family of moves, which depends on the representation of the solutions;
-
the acceptance criterion: here, a neighbour is accepted only if it is strictly better than the current solution;
-
the stopping criterion: here, the search stops in the first local optimum; in practice a time limit is often added.
-
-
The function \(f\) that decides whether a neighbour is “better” is usually the objective of the problem, but it does not have to be: the search may be guided by a different function, as long as the solution it returns is feasible.
Proposition 31.2
For every starting solution, \(LS\) stops after a finite number of moves, in a local optimum with respect to \(N\). If the objective function takes integer values and the problem is a minimization problem, the number of moves is at most \(f(x^0)-z(I)\); for a maximization problem, at most \(z(I)-f(x^0)\).
Proof
Every move strictly improves the objective, hence the sequence of the visited solutions never visits the same solution twice. The set of the feasible solutions is finite, so the sequence is finite. When it stops, \(\textit{Improve}\) has returned \(\textit{NULL}\), i.e., no neighbour is better: the last solution is a local optimum. If \(f\) takes integer values, every move improves \(f\) by at least \(1\), and \(f\) can never go beyond \(z(I)\), which gives the bounds on the number of moves. □
-
On the TSP reference instance, a local search starting from the tour of \(NN\) (length \(25\)) makes at most \(25-18=7\) moves. On large instances this bound is weak, and for some neighbourhoods there are instances on which the number of moves grows exponentially with \(n\) (for the 2-opt neighbourhood of the TSP, see Englert, Röglin, Vöcking, Algorithmica 68, 2014). In practice, the number of moves is small, and the running time is dominated by the exploration of the neighbourhoods.
-
Local search intensifies: it moves downhill until it reaches the bottom of the valley in which it started. Which valley, and therefore which local optimum, depends on the starting solution, on the neighbourhood and on the rule used to choose the move.
31.4 Neighbourhoods for the four problems¶
- The neighbourhoods are defined by small modifications of the representation of the solutions. Only feasible neighbours belong to the neighbourhood: a modification that produces an infeasible object is not a move. For every neighbourhood we fix the order in which the moves are examined, which matters when the search accepts the first improving neighbour it finds.
31.4.1 KP: flip and swap¶
-
The flip neighbourhood, defined in the chapter «Heuristic algorithms: definitions», changes one component of \(x\), i.e., adds or removes one item; it has \(n\) elements before the feasibility test. The flips are examined for \(j=1,2,\dots,n\).
-
The swap neighbourhood removes one selected item \(j\) and adds one unselected item \(k\). If \(S\) is the set of the selected items, it has \(|S|\,(n-|S|)\le n^2/4\) elements; the swaps are examined for \(j\in S\) in increasing order and, for each \(j\), for \(k\notin S\) in increasing order.
-
The two neighbourhoods are complementary: a flip changes the number of selected items, a swap keeps it. The neighbourhood flip+swap is their union, with the flips examined first.
31.4.2 BPP: move and swap¶
-
The move neighbourhood moves one item \(j\) from its bin \(a=bin_j\) to another non-empty bin \(b\) with \(L_b+w_j\le c\). It has at most \(n\,(nb-1)\) elements; the moves are examined for \(j=1,2,\dots,n\) and, for each \(j\), for the bins in increasing order of their label.
-
Moving an item into an empty bin is never useful: it cannot decrease the number of bins. The bins keep the labels of the starting solution; a bin emptied by a move simply disappears.
-
The swap neighbourhood exchanges two items \(j<k\) in different bins, provided that both bins remain feasible: \(L_{bin_j}-w_j+w_k\le c\) and \(L_{bin_k}-w_k+w_j\le c\). Exchanging two items of equal weight does not change any load, and is not considered. It has at most \(\frac{n(n-1)}{2}\) elements, examined for \(j=1,\dots,n\) and \(k=j+1,\dots,n\).
31.4.3 TSP: 2-opt and Or-opt¶
-
A tour is a permutation \(\sigma=(\sigma_1,\sigma_2,\dots,\sigma_n)\) of the cities, with \(\sigma_{n+1}=\sigma_1\). We keep city \(1\) in the first position, \(\sigma_1=1\).
-
The 2-opt move with positions \(i<j\) removes the two edges \(\{\sigma_i,\sigma_{i+1}\}\) and \(\{\sigma_j,\sigma_{j+1}\}\), and reconnects the tour in the only other possible way: with the edges \(\{\sigma_i,\sigma_j\}\) and \(\{\sigma_{i+1},\sigma_{j+1}\}\), travelling the path \(\sigma_{i+1},\dots,\sigma_j\) in the opposite direction (Croes, Operations Research 6, 1958):
\[ \begin{gathered} (\sigma_1,\dots,\sigma_i,\ \underbrace{\sigma_{i+1},\sigma_{i+2},\dots,\sigma_j}_{\text{path}},\ \sigma_{j+1},\dots,\sigma_n)\\ \downarrow\\ (\sigma_1,\dots,\sigma_i,\ \underbrace{\sigma_j,\dots,\sigma_{i+2},\sigma_{i+1}}_{\text{reversed path}},\ \sigma_{j+1},\dots,\sigma_n). \end{gathered} \]
-
The moves are examined for \(i=1,\dots,n-2\) and \(j=i+2,\dots,n\), excluding \(i=1\), \(j=n\) (the two edges would share city \(\sigma_1\)). The 2-opt neighbourhood has \(\frac{n(n-3)}{2}\) elements: \(5\) for the reference instance.
-
The Or-opt move (Or, PhD thesis, Northwestern University, 1976) takes a segment of \(\ell\in\{1,2,3\}\) consecutive cities \(\sigma_i,\dots,\sigma_{i+\ell-1}\) (\(2\le i\), \(i+\ell-1\le n\)) and inserts it, with the same orientation, between two consecutive cities \(\sigma_k\) and \(\sigma_{k+1}\) outside the segment (\(k\notin\{i-1,\dots,i+\ell-1\}\)). Let \(p=\sigma_{i-1}\) and \(q=\sigma_{i+\ell}\) be the cities before and after the segment, \(s_1=\sigma_i\) and \(s_\ell=\sigma_{i+\ell-1}\) its first and last city, \(a=\sigma_k\) and \(b=\sigma_{k+1}\):
-
The moves are examined for \(\ell=1,2,3\), then for \(i=2,\dots,n-\ell+1\), then for \(k=1,\dots,n\). For every \(\ell\) there are \(n-\ell\) segments and \(n-\ell-1\) insertion points, so the neighbourhood has \(\sum_{\ell=1}^{3}(n-\ell)(n-\ell-1)\) elements, i.e., \(O(n^2)\): \(170\) for \(n=10\). Some of these moves give the same tour (moving a single city forward by one position is the same as moving its successor backward by one position).
-
An Or-opt move removes three edges, \(\{p,s_1\}\), \(\{s_\ell,q\}\) and \(\{a,b\}\). The 3-opt neighbourhood (Lin, Bell System Technical Journal 44, 1965) contains all the ways of removing three edges and reconnecting the three paths: it has \(O(n^3)\) elements, and Or-opt is the part of it that can be explored in \(O(n^2)\) time.
31.4.4 \(P\,||\,C_{\max}\): move and swap¶
-
The move neighbourhood moves one job \(j\) from its machine \(a=mach_j\) to another machine \(h\ne a\). Every move is feasible, and the neighbourhood has \(n\,(m-1)\) elements, examined for \(j=1,\dots,n\) and, for each \(j\), for \(h=1,\dots,m\).
-
The swap neighbourhood exchanges the machines of two jobs \(j<k\) on different machines with \(t_j\ne t_k\) (otherwise no load changes). It has at most \(\frac{n(n-1)}{2}\) elements, examined for \(j=1,\dots,n\) and \(k=j+1,\dots,n\). A swap never changes the number of jobs on a machine.
31.4.5 Summary¶
| problem | neighbourhood | move | size |
|---|---|---|---|
| KP | flip | add or remove item \(j\) | \(n\) |
| KP | swap | item \(j\) out, item \(k\) in | \(|S|(n-|S|)\le \frac{n^2}{4}\) |
| BPP | move | item \(j\) to another bin | \(\le n\,(nb-1)\) |
| BPP | swap | exchange items \(j\) and \(k\) | \(\le \frac{n(n-1)}{2}\) |
| TSP | 2-opt | remove \(2\) edges, reverse a path | \(\frac{n(n-3)}{2}\) |
| TSP | Or-opt | move a segment of \(1\), \(2\) or \(3\) cities | \(\sum_{\ell=1}^{3}(n-\ell)(n-\ell-1)\) |
| TSP | 3-opt | remove \(3\) edges, reconnect | \(O(n^3)\) |
| \(P\,||\,C_{\max}\) | move | job \(j\) to another machine | \(n\,(m-1)\) |
| \(P\,||\,C_{\max}\) | swap | exchange jobs \(j\) and \(k\) | \(\le\frac{n(n-1)}{2}\) |
- The sizes are those before the feasibility test (KP, BPP) and include moves that do not change the objective. The size of a neighbourhood is the number of neighbours to evaluate at every iteration, so it determines the cost of an iteration.