Portale di Ateneo - Unibs.it Portale di Ateneo - Unibs.it

Introduzione ai problemi di Ottimizzazione Combinatoria (OC)
Definizione di problema combinatorio. Modelli, proprietà e applicazioni
dei problemi di OC. Formulazioni alternative per i problemi di OC.
Formulazioni strong e rilassamento continuo. Esempi di formulazioni
alternative (problema di albero ricoprente a costo minimo, problema di
Perfect Matching). Cenni di Teoria della complessità computazionale.
Classificazione degli algoritmi: esatti, euristici, approssimati.
Problemi polinomiali su reti
Reti di flusso: definizioni fondamentali. Totale unimodularità. Problema di
Massimo Flusso: modellizzazione e proprietà. Teorema di massimo
flusso-minimo taglio. Algoritmo di Ford-Fulkerson. Applicazioni. Problemi
di flusso a costo minimo: proprietà, algoritmi risolutivi e applicazioni.
Problemi di cammino minimo: proprietà, algoritmi risolutivi e applicazioni.
Algoritmi esatti
Algoritmi poliedrali. Metodo di Branch and Bound: proprietà e limiti.
Disuguaglianze valide e problemi di separazione. Metodo di Cutting Planes. Taglio di Gomory e Taglio di Dantzig. Tagli generici e tagli
specifici: esempi. Classi di disuguaglianze valide e algoritmi di
separazione esatti e euristici. Applicazione del metodo al problema del
commesso viaggiatore e ad un problema di selezione degli indici in un
data base relazionale. Programmazione dinamica deterministica:
Principio di ottimalità. Scomposizione dei problemi in stadi e stati.
Ottimizzazione recursiva. Applicazione della metodologia al problema
dello zaino binario e al problema di cammino minimo.
Algoritmi euristici e meta-euristici
Algoritmi costruttivi e di miglioramento. Algoritmi di ricerca locale.
Algoritmi 2-opt e 3-opt. Metodi Greedy. Meta-euristiche: Tabu Search,
Variable Neighborhood Search e Kernel Search. Proprietà dei metodi.
Applicazione delle metodologie viste a problemi di node routing e arc
routing.
Algoritmi approssimati
Proprietà e caratteristiche dei metodi approssimati. Analisi del caso
peggiore. Algoritmo del Tree Algorithm per il problema del commesso
viaggiatore. Algoritmo di ordinamento per il problema di maximum
independent set. Algoritmo del Next Fit per il problema di bin packing.
Algoritmo basato sul rilassamento lineare per il problema di vertex cover.
Algoritmi greedy per il problema dello zaino binario.