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

1. Introduzione ai problemi di Ottimizzazione Combinatoria (OC).
Definizione di problema combinatorio. Modelli, proprietà e applicazioni
dei problemi di OC. Formulazioni alternative per problemi di OC.
Formulazioni strong e rilassamento continuo. Esempi di formulazioni
alternative (problema di albero ricoprente a costo minimo, problema di
Perfect Matching).

2. Cenni di Teoria della complessità computazionale. Classificazione degli algoritmi: esatti, euristici, approssimati.

3. 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.

4. Introduzione ai problemi di Arc Routing. Proprietà. Problema del Chinese Postman Problem. Complessità del problema. Problema del Rural Postman Problem. Complessità e casi particolari. Algoritmi risolutivi.

5. 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, Adaptive Large Neighborhood Search e Kernel Search. Proprietà dei metodi. Applicazione delle metodologie viste a problemi di node routing e arc routing.

6. 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.

7. 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.