Operational research complements
A.A. 2020/2021
Obiettivi formativi
Il corso si propone di illustrare alcune tecniche algoritmiche della Ricerca Operativa, per la soluzione di problemi di programmazione matematica lineari misto-interi e non-lineari.
Risultati apprendimento attesi
Conoscenza dei metodi algoritmici per risolvere problemi di ottimizzazione NP-hard.
Periodo: Primo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
Programma e organizzazione didattica
Edizione unica
Responsabile
Periodo
Primo semestre
Le lezioni svolte in modalità sincrona verranno video-registrate e rese disponibili on-line per la fruizione asincrona. Alcune lezioni potranno essere registrate preventivamente; in tal caso, le lezioni previste dall'orario costituiranno momento di revisione e approfondimento di quanto proposto in modalità asincrona.
Programma
1. Programmazione lineare intera e misto-intera.
· Richiami di programmazione lineare.
· Interpretazione geometrica della PLI, teoria poliedrale.
· Metodo dei piani di taglio
2. Algoritmi di enumerazione implicita
· Branch-and-bound e branch-and-cut.
· Algoritmo di Balas per PLI 0-1
· Programmazione dinamica.
3. Rilassamento Lagrangeano
4. Column generation e branch-and-price
5. Programmazione non-lineare
· Ottimizzazione non vincolata
· Ottimizzazione vincolata
· Richiami di programmazione lineare.
· Interpretazione geometrica della PLI, teoria poliedrale.
· Metodo dei piani di taglio
2. Algoritmi di enumerazione implicita
· Branch-and-bound e branch-and-cut.
· Algoritmo di Balas per PLI 0-1
· Programmazione dinamica.
3. Rilassamento Lagrangeano
4. Column generation e branch-and-price
5. Programmazione non-lineare
· Ottimizzazione non vincolata
· Ottimizzazione vincolata
Prerequisiti
Programmazione dei calcolatori, Algoritmi e strutture dati, Ricerca operativa.
Metodi didattici
Lezioni frontali.
Materiale di riferimento
· F. Maffioli: "Elementi di programmazione matematica", Casa Editrice Ambrosiana, 2000.
· G. Nemhauser, L. Wolsey, "Integer and Combinatorial Optimization", Wiley 1999.
· G. Nemhauser, L. Wolsey, "Integer and Combinatorial Optimization", Wiley 1999.
Modalità di verifica dell’apprendimento e criteri di valutazione
Progetto e prova orale. Il progetto consiste nel realizzare un algoritmo di ottimizzazione per un problema combinatorio e nel valutarne sperimentalmente le prestazioni. La prova orale verte su tutto il programma del corso.
Siti didattici
Docente/i