|
METODI
DI OTTIMIZZAZIONE – mod. ottimizzazione combinatoria
Il corso ha
lo scopo di fornire strumenti matematici per la formulazione e la
soluzione di problemi di ottimizzazione su grafi e combinatori.
Docente Alessandro Agnetis
Vai alla homepage del docente.
Programma
a.a. 2011/12
- Richiami sulla programmazione lineare e sulla
complessità computazionale
- Problemi di cammino minimo, algoritmi di
Dijkstra, Floyd-Warshall
- Problema del massimo flusso, algoritmo di
Ford-Fulkerson
- Problemi di matching
- Formulazione di problemi in termini di ottimizzazione su grafi
- Formulazione di problemi come PLI
- Formulazioni ideali, piani di taglio, Metodo dei piani di Gomory
- Branch and bound
- Branch and cut
- Metodi basati sul rilassamento lagrangiano
- Metodi basati sulla generazione di colonne
- Problemi di knapsack, TSP, scheduling
- Formulazione di problemi come Programmazione Lineare Intera (PLI).
Modalità
d'esame del modulo Ottimizzazione Combinatoria
Sono
previste due prove in itinere: una a metà e una al termine del corso.
Gli studenti che riportano un voto sufficiente nelle due prove sono
ammessi alla prova orale. La prova orale è obbligatoria.
Durante il
primo appello (e solo durante il primo appello) sarà possibile
recuperare una delle due prove in itinere.
Per chi non svolge o non supera le prove in itinere, l’esame segue le
modalità standard, consistenti in una prova scritta e una prova
orale.
Calendario
del corso
Le lezioni
si svolgeranno in aula 149, il lunedi (14-18) e il mercoledi (16-18).
Sono
previste di norma 6 ore a settimana, secondo il seguente calendario.
Eventuali modifiche a questo calendario saranno rese note durante il
corso.
- 28
settembre 2011 14-18
- 30
settembre 16-18
- 5 ottobre 14-18
- 7 ottobre 16-18
- 12 ottobre 16-18
- 14 ottobre 16-18
- 19 ottobre 14-18
- 21 ottobre 16-18
- 26 ottobre 14-18
- 28 ottobre 16-18
- 2 novembre 14-18
- 4 novembre 16-18
- 9 novembre 14-18 – prima prova in corso d’anno
- 11 novembre 16-18
- 16 novembre 14-18
- 18 novembre 16-18
- 23 novembre 14-18
- 25 novembre 16-18
- 30 novembre 14-18
- 9 dicembre 16-18
- 14 dicembre 14-18
- 11 gennaio 2012 14-18 – lezione di riepilogo
- 13 gennaio 16-18 – seconda prova in corso d’anno
Orario
di ricevimento
Lunedi 11-13
stanza R101. Si consiglia di contattare preventivamente per telefono
o email.
Il prof.
Agnetis sarà assente per l’intero mese di giugno 2012, e sarà
nuovamente in ufficio il giorno 3 luglio 2012.
Materiale
didattico
- Fischetti,
M., Lezioni di Ricerca Operativa, Libreria progetto, Padova. In
particolare, per gli argomenti oggetto di questo modulo: capp. 4.7, 5
(tutto), 6.1, 6.2, 6.3, 6.5, 6.6, 6.7
Problemi di matching
Duale del massimo flusso
Appunti sulle classi di complessità
Generazione di colonne
Ottimizzazione di grafi: esercizi di
formulazione
Raccolta di esercizi di PLI svolti
Altri problemi di formulazione
Rilassamento lagrangiano
|
