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 euristica dei problemi di ottimizzazione lineare intera. Particolare
attenzione verrà dedicata all'aspetto algoritmico e alle applicazioni.
Introduzione all'ottimizzazione combinatoria. Problemi polinomiali su reti. Problemi di Node Routing e di Arc Routing. Algoritmi esatti (Branch-and-Bound, Cutting Planes, Branch-and-Cut). Algoritmi euristici e meta-euristisici (Tabu Search, Variable Neighborhood Search, Adaptive Large Neighborhood Search, Kernel Search). Applicazione delle tecniche
apprese a problemi di node routing e arc routing. Algoritmi approssimati ed analisi del caso peggiore. Introduzione all’Ottimizzazione Bilivello.
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. 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à.
3. Introduzione ai problemi di Arc e Node Routing. Proprietà e differenze. Condizioni necessarie e sufficienti per grafi euleriani. Problema del Chinese Postman Problem. Complessità del problema. Problema del Rural Postman Problem. Complessità e casi particolari. Algoritmi risolutivi.
4. 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.
5. 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.
6. 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.
7. Ottimizzazione Bilivello. Definizione e proprietà. Classi di problemi. Metodologie risolutive.
D. BERTSIMAS, J.N. TSITSIKLIS, Introduction to Linear Optimization, Athena Scientific, Belmont, Massachusetts 1997.
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. Discussione e soluzione in aula di problemi applicativi e di articoli scientifici . Attività progettuale svolta in gruppi costituiti da studenti di differente formazione. La finalità è quella di favorire l’applicazione della conoscenza acquisita e lo sviluppo delle abilità di comunicazione e giudizio critico.
L'esame prevede una prova scritta di teoria e una prova orale focalizzata sulla discussione dei risultati ottenuti nel progetto assegnato all'inizio del corso. A ciascun gruppo di studenti è inoltre assegnato un articolo tratto da letteratura scientifica riguardante modelli e algoritmi di ottimizzazione, di cui si richiede l’analisi e una presentazione in aula. Sono previsti momenti di discussione delle difficoltà incontrate nell'affrontare la risoluzione del progetto e lo studio della letteratura scientifica. Ogni studente è tenuto a sostenere una breve presentazione della propria attività svolta nel gruppo con lo scopo di verificarne l'autonomia di giudizio e la capacità di apprendimento.
Sono disponibili slide relative sia alle lezioni di teoria sia alle esercitazioni svolte in aula. Tutto il materiale didattico è disponibile sul sito di E-learning d'Ateneo (comunità didattica di ESSE3).