| | | |  corso | | | |
Ottimizzazione Combinatoria e reti
| Codice: | AA413 | Crediti: | 6 | Semestre: | 1 | Sigla: | OCR | |
| |
| Settore disciplinare: | MAT/09 - Ricerca Operativa |
Docente
Maria Grazia Scutellà
Tel. 0502212771Ultima versione disponibile: programma da confermare per l’a.a. 2009/2010
Prerequisiti
Ricerca Operativa
Obiettivi di apprendimento
Obiettivo del corso è presentare agli studenti le principali
problematiche algoritmiche che nascono nella gestione e nel progetto di
reti di comunicazione.
Descrizione
Vengono presentate metodologie risolutive sia per taluni problemi
"di base" dell'Ottimizzazione su Reti, non sviluppate nel corso di Ricerca
Operativa, sia per problemi "difficili" di Ottimizzazione Combinatoria e
Reti. Le metodologie descritte verranno esemplificate nell'ambito di
problemi di progetto e gestione di reti di comunicazione.
English Description
Network and Combinatorial Optimization algorithms are the core of the course. They are presented and motivated to handle classical problems of designing communication networks and routing information along them. "Basic" network algorithms, not developed in the course Operations Research, and methods to solve "difficult" Combinatorial Optimization problems are presented.
Programma
- Introduzione (4 ore):
- Reti di comunicazione e l'Ottimizzazione Combinatoria.
- Problemi polinomiali e problemi NP-ardui; Ottimizzazione
Combinatoria, Programmazione Lineare a numeri Interi e
Programmazione Lineare Mista.
- Poliedro, inviluppo convesso, disuguaglianze valide.
- Problemi base di ottimizzazione su rete (8 ore):
- Algoritmo preflow-push per il problema del flusso
massimo.
- Il problema di flusso di costo minimo.
- Algoritmo basato su cammini minimi successivi per il problema di
flusso di costo minimo.
- Algoritmo basato su cancellazione di cicli per il problema di
flusso di costo minimo.
- Problemi di instradamento e progetto ottimo su reti (6 ore):
- Problemi di instradamento (routing), progetto di reti
(network design) e progetto+instradamento (design + routing).
- Problemi di localizzazione.
- Cammini minimi bicriterio: costo minimo e numero minimo di hop.
- Approcci euristici (6 ore):
- Algoritmi 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.
- Utilizzo dell'informazione primale e duale.
- Il rilassamento Lagrangiano: formalizzazione,
proprietà ed esemplificazioni.
- Algoritmo basato su piani di taglio.
- 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.
Note: Le ore comprendono lezioni e esercitazioni
Bibliografia
Modalità di esame
Scritto ed orale
