Typical mistakes · In summary¶

30.12 Typical mistakes¶

Warning

Expecting the greedy by efficiency to be optimal. It can be arbitrarily bad, and so can each of the other two orders: the notes contain a family of instances for each of them.
Believing that sorting always helps. FFD can be worse than FF (Example 30.4).
Breaking ties in the wrong way. Every example uses one fixed rule (smallest index, first bin that fits, fullest bin for BF): changing it changes the solution.
Forgetting the closing edge. The length of a tour includes the edge from the last city back to the first one; the cost of an insertion is \(d_{ik}+d_{kj}-d_{ij}\), and every position, closing edge included, must be tried.
Reading \(\mathscr{A}(I)\) as a bound on \(z(I)\). It is only a primal bound.

In summary

A constructive heuristic builds one solution, one element at a time, and never revises a choice.
The order of the choices is the main design decision: efficiency for the KP, decreasing weights for the BPP, longest jobs first for \(P\,||\,C_{\max}\); no order wins on every instance.
Several orders, starting points or randomized constructions, keeping the best solution, are a cheap protection.
The solutions are starting points for local search.

Dashboard of the reference instances. Best constructive value and dual bound:

problem	best heuristic value	dual bound	gap	\(z(I)\)
KP (max)	\(17\) (\(GR_p\))	\(\mathrm{UB}(I)=17\)	\(0\%\)	\(17\)
BPP (min)	\(3\) (FFD, BFD)	\(\mathrm{LB}(I)=3\)	\(0\%\)	\(3\)
\(P\,\|\|\,C_{\max}\) (min)	\(11\) (\(LPT\))	\(\mathrm{LB}(I)=9\)	\(22.2\%\)	\(9\)
TSP (min)	\(18\) (multi-start \(NN\), \(NI\), \(FI\), \(CI\))	\(\mathrm{LB}(I)=17\)	\(5.9\%\)	\(18\)

Exercises on this chapter: Constructive heuristics