The problems and the assumptions · The greedy paradigm¶
Part 4 · Heuristic algorithms · Chapter 30 · Chapter 30: Constructive heuristics · Lecture notes, volume 4 (PDF) · Slides (1/2) · Slides (2/2) · Exercises: Constructive heuristics · App: Bin packing heuristics · App: List scheduling and LPT · App: Vertex coloring: greedy and DSATUR · App: TSP: nearest neighbour and 2-opt
30.2 The problems and the assumptions¶
-
The heuristics 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}\); the greedy coloring and \(DSATUR\) are applied to the vertex coloring problem (VCP). Their definitions and assumptions are on their pages; we recall the notation.
-
As in the other notes, \(\mathscr{A}(I)\) denotes the value of the solution computed by the heuristic \(\mathscr{A}\) on the instance \(I\), and \(z(I)\) the optimal value. For \(P\,||\,C_{\max}\), \(L_h=\sum_{j\in J_h}t_j\) is the load of machine \(h\), and the vector \(mach\) stores the machine \(mach_j\) of every job \(j\); for the BPP, the vector \(bin\) stores the bin \(bin_j\) of every item \(j\), and \(rc\) denotes a residual capacity.
-
The examples use the four reference instances of the chapter «Heuristic algorithms: definitions», whose optimal values are known:
| problem | reference instance | optimum |
|---|---|---|
| KP | \(p=(10,7,6,4)\), \(w=(5,4,3,3)\), \(c=9\) | \(\{1,2\}\), \(z(I)=17\) |
| BPP | \(w=(4,4,5,3,2,3)\), \(c=7\) | \(\{1,4\},\{2,6\},\{3,5\}\), \(z(I)=3\) |
| \(P\,||\,C_{\max}\) | \(t=(5,5,4,4,3,3,3)\), \(m=3\) | \(\{1,3\},\{2,4\},\{5,6,7\}\), \(z(I)=9\) |
| TSP | \(5\) cities, distances below | \(\sigma=(1,3,5,2,4)\), \(z(I)=18\) |
- In the figures, the five cities of the TSP reference instance are always drawn in the same positions, on a pentagon, in the order \((1,3,5,2,4)\) of the optimal tour: the optimal tour is then the boundary of the pentagon, and every tour that uses a diagonal is visibly different from it. The figure shows the distances of the instance and, in bold, its optimal tour.
30.3 The greedy paradigm¶
-
A solution of each of the four problems is made of elements: the items selected for the knapsack, the assignments of items to bins and of jobs to machines, the edges of a tour. A constructive heuristic starts from the empty partial solution and adds one element at a time.
-
At every step three questions must be answered: which elements can be added (the candidates), which one is added (the selection criterion), and whether the result can still be completed to a feasible solution (the feasibility test). A greedy heuristic answers the second question in the simplest way: it adds the candidate that looks best now, according to a criterion that measures the immediate benefit of the element.
Definition 30.2: Greedy algorithm
A greedy algorithm is a constructive heuristic that builds a solution by repeatedly selecting, among the candidate elements, the one that is best according to a selection criterion; the element is added to the partial solution if the feasibility test allows it, and is discarded otherwise.
In a greedy algorithm each decision is taken once and for all: a choice, once made, is never revised.
- The pseudo-code below is a template rather than an algorithm: the set of candidates, the criterion and the test are the three parts that every specific heuristic of these notes fills in.
Algorithm: Greedy template
-
The order decides everything. The template examines the elements in the order induced by the selection criterion, and an element rejected or accepted early cannot be reconsidered later. Two greedy heuristics with the same candidates and the same feasibility test, but with different criteria, can produce very different solutions: changing the criterion is the main design decision.
-
Static and dynamic criteria. A criterion is static if the value of an element does not depend on the partial solution: the elements can then be sorted once at the beginning, and the heuristic scans the sorted list (efficiency of the KP items, weight of the BPP items, processing time of the jobs). A criterion is dynamic if the value of an element changes as the solution grows, and it must be recomputed at every step (distance from the last city of a partial tour, residual capacity of the bins, load of the machines).
-
Myopia. The criterion looks only at the immediate effect of a choice, not at its consequences on the choices still to be made. This is what makes greedy heuristics fast, and also what makes them fail: a choice that is good now can force bad choices later.
-
Running time. With a static criterion the running time is typically dominated by the sorting, \(O(n\log n)\), plus the cost of the feasibility tests; with a dynamic criterion it is the number of steps times the cost of re-evaluating the candidates, typically \(O(n^2)\) or \(O(n^3)\).
-
When greedy is exact. For some problems a greedy algorithm always finds an optimal solution: Kruskal's algorithm for the minimum spanning tree problem examines the edges by non-decreasing cost and accepts an edge if it does not close a cycle; the fractional knapsack problem is solved optimally by taking the items by non-increasing efficiency. For the four NP-hard problems of these notes no greedy algorithm is exact, and the question becomes which criterion gives good solutions.
-
The following table shows how the template is filled in for the four problems; the sections that follow study each of them.
| problem | element | selection criterion | feasibility test |
|---|---|---|---|
| KP | an item | profit, weight or efficiency (static) | the item fits into the residual capacity |
| BPP | an item and a bin | item: input order or weight (static); bin: first, best, worst (dynamic) | the item fits into the bin |
| \(P\,||\,C_{\max}\) | a job and a machine | job: input order or processing time (static); machine: least loaded (dynamic) | always feasible |
| TSP | a city and its position | nearest, farthest, cheapest (dynamic) | always feasible |