Costituisce scopo del corso sviluppare le nozioni di base del corso di
Ricerca Operativa introducendo lo studente all'Ottimizzazione
combinatoria e alle principali tecniche per la risoluzione esatta e
approssimata dei problemi di ottimizzazione lineare intera. Particolare
attenzione verrà dedicata all'aspetto algoritmico e alle applicazioni.
Introduzione all'ottimizzazione combinatoria. Problemi polinomiali su reti.
Algoritmi esatti. Algoritmi euristici e meta-eustisici. Algoritmi
approssimati ed analisi del caso peggiore. Applicazione delle tecniche
apprese a problemi di node routing e arc routing.
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.
G. AUSIELLO, P. CRESCENZI, G. GAMBOSI, V. KANN, A. MARCHETTISPACCAMELA,
M. PROTASI, Complexity and Approximation,Springer
Verlag 1999.
C.PAPADIMITRIOU, K.STEIGLITZ, Combinatorial Optimization, Prentice
Hall, 1982.
M. GAREY, D. JOHNSON, Computers and Intractability: a Guide to the
Theory of NP-Completeness, Freeman, 1979.
Lezioni di teoria affiancate da esercitazioni. Soluzione in aula di problemi
applicativi. Assegnazione di un progetto corrispondente alla risoluzione di
un problema applicativo da svolgere in gruppo. Presentazione in itinere
delle proposte risolutive e dei risultati ottenuti dai gruppi. Discussione in
aula sulle difficoltà incontrate nella risoluzione.
L'esame prevede una prova scritta e una prova orale focalizzata sulla
discussione dei risultati ottenuti nel progetto assegnato all'inizio del
corso.
Nessuna