Errori tipici · In sintesi¶

30.12 Errori tipici¶

Attenzione

Aspettarsi che il greedy per efficienza sia ottimo. Può essere arbitrariamente cattivo, e così ciascuno degli altri due ordinamenti: le note contengono una famiglia di istanze per ognuno di essi.
Credere che ordinare aiuti sempre. FFD può essere peggiore di FF (Esempio 30.4).
Risolvere i pareggi nel modo sbagliato. Ogni esempio usa una regola fissata (indice minimo, primo contenitore in cui l'oggetto entra, contenitore più pieno per BF): cambiarla cambia la soluzione.
Dimenticare l'arco di chiusura. La lunghezza di un giro include l'arco dall'ultima città di ritorno alla prima; il costo di un inserimento è \(d_{ik}+d_{kj}-d_{ij}\), e va provata ogni posizione, arco di chiusura compreso.
Leggere \(\mathscr{A}(I)\) come un bound su \(z(I)\). È solo un bound primale.

In sintesi

Un'euristica costruttiva costruisce una soluzione, un elemento alla volta, e non rivede mai una scelta.
L'ordine delle scelte è la principale scelta di progetto: efficienza per il KP, pesi decrescenti per il BPP, prima i lavori più lunghi per \(P\,||\,C_{\max}\); nessun ordine vince su ogni istanza.
Più ordini, punti di partenza o costruzioni randomizzate, tenendo la soluzione migliore, sono una protezione economica.
Le soluzioni sono punti di partenza per la ricerca locale.

Quadro delle istanze di riferimento. Miglior valore costruttivo e bound duale:

problema	miglior valore euristico	bound duale	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\)

Esercizi su questo capitolo: Euristiche costruttive