Ottimizzazione Combinatoria e Reti: AA413, 6 crediti
Stefano Pallottino e Antonio Frangioni
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.
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.
PROGRAMMA DEL CORSO
- Introduzione (6 ore):
- Reti di comunicazione e l'Ottimizzazione Combinatoria.
- Problemi di instradamento (routing), progetto di reti
(network design) e progetto+instradamento (design + routing).
- Problemi di localizzazione.
- Problemi polinomiali e problemi NP-ardui; Ottimizzazione
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.
- 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.
- 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 indicate comprendono lezioni e esercitazioni.
Parti degli appunti non sviluppate durante il corso:
- 5.1.1.4 Ordinamento di lavori su macchine con minimizzazione del
tempo di completamento.
- 5.1.1.5 Ordinamento di lavori su macchine con minimizzazione del
numero delle macchine.
- 5.1.2.2 Gli algoritmi SPT e LPT per (MMMS)
- 5.1.2.4 Un algoritmo Greedy per il Weighted Vertex Cover
- 5.1.3 Matroidi
- 5.2.1.2 Ordinamento di lavori su macchine con minimizzazione del
tempo di completamento.
- 5.2.1.5 Dislocazione ottima di impianti
- 5.2.2 Intorni di grande dimensione
- 5.2.3.3 Ricerca Taboo
- 6.2.0.6 Il problema (TSP)
- 6.3.2 Algoritmi per il rilassamento Lagrangiano
- 6.3.3 Informazione generata dal rilassamento Lagrangiano
- 7.1.2.3 Regole di dominanza
Testi di riferimento
L. Wolsey "Integer Programming" Wiley-Interscience, 1998
R.K. Ahuja, T. L. Magnanti, J. B. Orlin "Network flows. Algorithms
and applications" Prentice-Hall, 1993
Appunti: forniti dai docenti
Propedeuticità
Ricerca Operativa