30.11 What constructive heuristics give, and what they do not¶
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
- The table collects the results on the four reference instances, with the dual bounds of the chapter «Heuristic algorithms: definitions» (\(\UB\) for the KP, \(\LB\) for the other problems) and the gap of the best heuristic solution.
| problem | heuristic | values | dual bound | gap | \(z(I)\) |
|---|---|---|---|---|---|
| KP | \(GR_p\), \(GR\), \(GR_w\) | \(17\), \(16\), \(10\) | \(\UB=17\) | \(0\%\) | \(17\) |
| BPP | FF, FFD, BFD | \(4\), \(3\), \(3\) | \(\LB=3\) | \(0\%\) | \(3\) |
| \(P\,||\,C_{\max}\) | \(LIST\) (reverse list), \(LPT\) | \(12\), \(11\) | \(\LB=9\) | \(22.2\%\) | \(9\) |
| TSP | \(NN\), multi-start \(NN\), \(NI\), \(FI\), \(CI\) | \(25\), \(18\), \(18\), \(18\), \(18\) | \(\LB=17\) | \(5.9\%\) | \(18\) |
-
A primal bound, and nothing more. A constructive heuristic returns a feasible solution, and its value is a primal bound. For the KP and the BPP the best heuristic value meets the dual bound, and the solution is proved optimal; for the TSP the tour of length \(18\) is optimal, but the dual bound \(17\) cannot prove it; for \(P\,||\,C_{\max}\) the gap of \(22.2\%\) is real. The heuristic itself never knows in which of these situations it is.
-
A choice is never revised. Every heuristic of these notes stops as soon as the solution is complete, and every decision taken along the way is final. In the \(LPT\) schedule, job \(7\) is put on machine \(1\) when the three loads are equal, and the makespan \(11\) is fixed at that moment; in the \(NN\) tour from city \(1\), the edge \((5,1)\) of length \(9\) is the consequence of the very first choices. Looking at the Gantt chart or at the tour, a better solution seems close; but a constructive heuristic has no mechanism to go back.
-
The order decides everything. The examples of these notes show the same lesson on four problems: sorting the elements in the right order (efficiency, decreasing weights, longest jobs first) is the main design choice; still, no order is the best on every instance (Example 30.1, Example 30.4), and running several orders, several starting points or several randomized constructions, and keeping the best solution, is a cheap and effective protection.
-
Cheap, and useful as a start. Constructive heuristics are fast, and they are rarely used alone: their solutions are the starting points of the methods that try to improve a complete solution.
A constructive heuristic builds one solution, one element at a time, choosing at each step the element that looks best now. The order of the choices decides the quality of the result, and a choice, once made, is never revised.