31.2 The problems, the assumptions and the starting solutions¶
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
- The algorithms are illustrated on the four problems of the chapter «Heuristic algorithms: definitions»: the 0/1 knapsack problem (KP), the bin packing problem (BPP), the travelling salesman problem (TSP) and \(P\,||\,C_{\max}\). Their definitions and assumptions are on their pages; the table recalls the notation.
| problem | data | representation of a solution | objective |
|---|---|---|---|
| KP | \(p_j\), \(w_j\) (\(j\in\mathscr{I}\)), capacity \(c\) | binary vector \(x\) | max profit |
| BPP | \(w_j\) (\(j\in\mathscr{I}\)), capacity \(c\) | vector \(bin\), packing patterns \(P_b\) | min number of bins \(nb\) |
| TSP | \(d_{ij}\) (\(i,j\in\mathscr{V}\)) | tour \(\sigma\) | min length \(L(\sigma)\) |
| \(P\,||\,C_{\max}\) | \(t_j\) (\(j\in\mathscr{J}\)), \(m\) machines | vector \(mach\), sets \(J_h\) | min makespan \(C_{\max}\) |
-
For \(P\,||\,C_{\max}\), \(L_h=\sum_{j\in J_h} t_j\) is the load of machine \(h\) and \(C_{\max}=\max_h L_h\). For the BPP, \(L_b=\sum_{j\in P_b} w_j\) is the load of bin \(b\). A machine (or a bin) whose load equals the objective value is called critical.
-
The reference instances are those of the chapter «Heuristic algorithms: definitions»: the KP with \(p=(10,7,6,4)\), \(w=(5,4,3,3)\), \(c=9\); the BPP with \(w=(4,4,5,3,2,3)\), \(c=7\); the TSP with \(5\) cities; \(P\,||\,C_{\max}\) with \(t=(5,5,4,4,3,3,3)\) and \(m=3\). Their optimal values are \(17\), \(3\), \(18\) and \(9\).
31.2.1 Starting solutions¶
- A local search needs a feasible starting solution. We use the solutions computed in the chapter «Constructive heuristics», recalled below.
| problem | algorithm | starting solution | value | \(z(I)\) |
|---|---|---|---|---|
| KP | \(GR\) (greedy by efficiency) | \(x=(1,0,1,0)\), items \(\{1,3\}\) | \(16\) | \(17\) |
| KP | greedy by weight \(GR_w\) | \(x=(0,0,1,1)\), items \(\{3,4\}\) | \(10\) | \(17\) |
| BPP | \(NF\) | \(\{1\},\{2\},\{3\},\{4,5\},\{6\}\) | \(5\) | \(3\) |
| BPP | \(FF\) | \(\{1,4\},\{2,5\},\{3\},\{6\}\) | \(4\) | \(3\) |
| BPP | \(FFD\) | \(\{3,5\},\{1,4\},\{2,6\}\) | \(3\) | \(3\) |
| TSP | \(NN\) from city \(1\) | \(\sigma=(1,3,2,4,5)\) | \(25\) | \(18\) |
| \(P\,||\,C_{\max}\) | \(LPT\) | \(J_1=\{1,5,7\}\), \(J_2=\{2,6\}\), \(J_3=\{3,4\}\) | \(11\) | \(9\) |
-
The solution of \(FFD\) is already optimal, so no local search can improve it: for the BPP we start from the solutions of \(NF\) and \(FF\).
-
To study the behaviour of a local search on many starting solutions we also use random starting solutions. They are generated with the Park–Miller minimal standard generator: given an integer seed \(s_0\in\{1,\dots,2^{31}-2\}\), the \(k\)-th pseudo-random number is
and a pseudo-random integer in \(\{0,1,\dots,q-1\}\) is \(\lfloor q\, u_k\rfloor\).
- The sequence is completely determined by the seed: the same seed gives the same starting solutions, in the notes, in the exercises and in the code. A random tour keeps city \(1\) in the first position and shuffles the other cities (Fisher–Yates: for \(k=n,n-1,\dots,3\), the city in position \(k\) is exchanged with the city in a random position among \(2,\dots,k\)); a random assignment of the jobs draws the machine of the jobs \(1,2,\dots,n\) in this order; a random BPP solution is computed by \(FF\) on a random order of the items (Fisher–Yates on all the positions: for \(k=n,n-1,\dots,2\), the item in position \(k\) is exchanged with the item in a random position among \(1,\dots,k\)).
Next: Local search: the scheme · Neighbourhoods for the four problems