| | | |  corso | | | |
Ottimizzazione Combinatoria e reti
| Codice: | AA413 | Crediti: | 6 | Semestre: | 2 | Sigla: | OCR | |
| |
| Settore disciplinare: | MAT/09 - Ricerca Operativa |
Docente
Stefano Pallottino
Prerequisiti
Ricerca Operativa
Obiettivi di apprendimento
Il corso è rivolto a presentare agli studenti le principali problematiche algoritmiche che nascono nella gestione e nel progetto di reti di comunicazione; si propone quindi di fornire gli strumenti algoritmici dell'Ottimizzazione Combinatoria e dell'Ottimizzazione di Reti.
Descrizione
Vengono presentate le tecniche fondamentali per la soluzione dei problemi "di base" dell'Ottimizzazione di Reti, non sviluppate nel corso di Ricerca Operativa, e di problemi "difficili" dell'Ottimizzazione Combinatoria, mostrando l'applicazione di tali metodi alla soluzione di problemi di progettazione e gestione di reti di comunicazione.
English Description
The Network and Combinatorial Optimization algorithms are the core of the course; they are presented and motivated to handle the classical problems of designing communication networks and of routing information in them. The "basic" Network Algorithms, not developed in the Operations Research course, and the methods to solve "difficult" Combinatorial Optimization problems are presented.
Programma
- Introduzione al corso (6 ore)
- Reti di comunicazione e l'Ottimizzazione Combinatoria;
- Problemi di instradamento (routing), progetto di reti (network design) e progetto+instradamento (design + routing);
- Esempi;
- problemi di localizzazione;
- Problemi polinomiali e problemi NP-ardui; Ottimizzazine Combinatoria, Programmazione Lineare a numeri Interi e Programmazione Lineare Mista;
- Poliedro, inviluppo convesso, disuguaglianze valide.
- Algoritmi polinomiali di ottimizzazione di reti (10 ore)
- algoritmo distribuito per il problema dei cammini minimi;
- cammini minimi bicriterio: costo minimo e numero minimo di hop;
- algoritmo preflow-push distribuito per il problema del flusso massimo;
- l'algoritmo del simplesso su reti per il problema del flusso di costo minimo;
- problemi di accoppiamento su grafi bipartiti: metodi e algoritmi.
- Approcci euristici (6 ore)
- l'algoritmo greedy: formalizzazione e esemplificazioni;
- valutazione delle prestazioni: algoritmi approssimati, errore relativo:
- la ricerca locale: formalizzazione ed esemplificazioni;
- un esempio di metaeuristica: il "simulated annealing".
- Tecniche di rilassamento (10 ore)
- il rilassamento continuo: formalizzazione ed esemplificazioni;
- gestione dell'informazione: soluzione primale e soluzione duale;
- il rilassamento Lagrangiano: formalizzazione, proprieta` ed esemplificazioni;
- metodo del subgradiente;
- euristiche Lagrangiane;
- rilassamenti per eliminazione e surrogati.
- Algoritmi esatti per problemi NP-ardui (10 ore)
- tecnica del Branch and Bound per l'enumerazione implicita;
- strategie di visita, tecniche di separazione, cenni implementativi, esemplificazioni;
- piani di taglio nell'enumerazione implicita;
- programmazione dinamica per cammini bicriterio.
Note: Le ore comprendono lezioni e esercitazioni
Bibliografia
Appunti del docente
L. Wolsey "Integer Programming" Wiley-Interscience, 1998
"Network flows", Ahuja, Magnanti, Orlin (1993)
Modalità di esame
Scritto ed orale, possibilità di sviluppo di progetti
