Operational research complements
A.A. 2020/2021
Learning objectives
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.
Expected learning outcomes
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.
Course syllabus and organization
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.
Educational website(s)
Professor(s)