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
Algoritmi on-line per il problema del Bin-packing: Next Fit, First fit, Best Fit, Any Fit, HarmonicM.
MAT/09 - Ricerca Operativa
Definizione e classificazione dei problemi di ottimizzazione e dei problemi di decisione e classificazione dei relativi metodi risolutivi (metodi esatti, metodi di approssimazione e metodi euristici). Programmazione Lineare (PL): il Metodo del Simplesso
MAT/09 - Ricerca Operativa
Metodi esatti per la risoluzione dei problemi di Programmazione Lineare Intera (Branch & Bound; piani di taglio; programmazione dinamica). Esempi di problemi di PLI con matrice dei vincoli unimodulare: il problema del trasporto ed il problema dell'assegnamento
MAT/09 - Ricerca Operativa
Il problema del Vertex Cover: un algoritmo 2-approssimato per il problema del Vertex Cover. Il problema dell'albero di copertura di un grafo a costo minimo (MST): l'algoritmo di Kruskal.
MAT/09 - Ricerca Operativa
Un algoritmo Branch and Bound per il problema dello Zaino 0/1; un algoritmo greedy per il problema dello Zaino Frazionario; due algoritmi di Programmazione Dinamica per il problema dello Zaino 0/1
MAT/09 - Ricerca Operativa
Cammini in un grafo orientato: il problema della raggiungibilità (visita in ampiezza; visita in profondità). Il problema dei cammini minimi: l'algoritmo di Dijkstra; l'algoritmo di Floyd e Warshall.
MAT/09 - Ricerca Operativa
Pianificazione di progetti: il Metodo CPM. Problemi di flusso su reti: il problema del massimo flusso; teorema max-flow min-cut; algoritmo di Ford-Fulkerson.
MAT/09 - Ricerca Operativa
Algoritmi euristici e meta-euristici: Simulated Annealing; Tabù Search; Algoritmi Genetici; GRASP; Algoritmi di Ricerca Locale.
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
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
TSP su grafi qualsiasi, TSP grafico, Grafi hamiltoniani e semihamiltoniani, TSP simmetrico e asimmetrico, il postino rurale, Cammino hamiltoniano minimo, TSP collo di bottiglia.