Ottimizzazione Combinatoria e Reti: AA413, 6 crediti

Maria Grazia Scutellà e Antonio Frangioni

Specificatamente, verranno 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.

PROGRAMMA DEL CORSO

1. 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.

2. 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.

3. 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.

4. 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".

5. 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.

6. 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.

Testi di riferimento

Appunti di Ricerca Operativa (Capitolo 2 (Paragrafi 2.5 e 2.6))

L. Wolsey "Integer Programming" Wiley-Interscience, 1998

R.K. Ahuja, T. L. Magnanti, J. B. Orlin "Network flows. Algorithms and applications" Prentice-Hall, 1993

Parti degli Appunti di Ottimizzazione Combinatoria 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.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)
• 7.1.2.3 Regole di dominanza

Propedeuticità