Sillabo dell'insegnamento

• MAT - Crediti di MATEMATICA
MAT/09 - Ricerca Operativa
Definizione delle principali varianti fra i problemi di vehicle routing; la formulazione matematica per tre varianti del problema; principali metodi euristici e meta-euristici per il problema nella sua versione generale e per il problema con time-windows.
MAT/09 - Ricerca Operativa
TSP su grafi qualsiasi, TSP grafico, Grafi hamiltoniani e semihamiltoniani, TSP simmetrico e asimmetrico, il postino rurale, Cammino hamiltoniano minimo, TSP collo di bottiglia.
MAT/09 - Ricerca Operativa
Il problema del Commesso Viaggiatore (TSP): due formulazioni matematiche ed un algoritmo Branch and Bound per il TSP. Il D-TSP: un algoritmo 2-approssimato per il D-TSP; Algoritmo di Christofides. Medoti euristici per il TSP: a inserimento con diversi criteri di scelta; ricerca locale (2-opt exchange, 3-opt, k-opt, OR-opt); algoritmi per istanze geometriche (inviluppo convesso, a sezioni).
MAT/09 - Ricerca Operativa
Algoritmi euristici e meta-euristici: Simulated Annealing; Tabù Search; Algoritmi Genetici; GRASP; Algoritmi di Ricerca Locale.
MAT/09 - Ricerca Operativa
Classi di complessità P, NP, NP-hard e NP-completi. Classificazione dei metodi risolutivi (metodi esatti, metodi di approssimazione e metodi euristici). Classi di approssimazione (NPO, APX, PTAS, FPTAS, PO). Riduzioni nelle classi di approssimazione e la riduzione PTAS.
MAT/09 - Ricerca Operativa
Algoritmi on-line per il problema del Bin-packing: Next Fit, First fit, Best Fit, Any Fit, HarmonicM.