Algoritmi euristici¶
Parte 4 del corso, volume 4 delle dispense: capitoli 29–33.
Algoritmi euristici: euristiche costruttive, ricerca locale, metaeuristiche ed euristiche basate sulla programmazione lineare intera, applicate ai problemi del corso.
-
29. Algoritmi euristici: definizioni
I problemi e le ipotesi · Bound primali e duali · Classificazione degli algoritmi euristici · Rappresentazione delle soluzioni e spazio di ricerca
-
30. Euristiche costruttive
I problemi e le ipotesi · Il paradigma greedy · Il problema dello zaino 0/1: quale ordinamento? · Il problema del bin packing: prima ordinare, poi riempire
-
31. Ricerca locale
I problemi, le ipotesi e le soluzioni di partenza · Ricerca locale: lo schema · Intorni per i quattro problemi · First improvement e best improvement
-
32. Metaeuristiche
I problemi e le ipotesi · Come uscire da un ottimo locale · Simulated annealing · Tabu search
-
33. Euristiche MIP per i problemi classici
Euristiche basate sulla PLI · I problemi e i loro modelli MIP · Arrotondamento · Diving