Operational research complements
A.A. 2022/2023
Obiettivi formativi
L'insegnamento 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
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
· 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
Prerequisiti
Ricerca operativa. Algoritmi e strutture-dati.
Metodi didattici
Lezioni frontali.
Materiale di riferimento
· F. Maffioli: "Elementi di programmazione matematica", Casa Editrice Ambrosiana, 2000.
Modalità di verifica dell’apprendimento e criteri di valutazione
L'esame consiste in un progetto o seminario e in una prova orale.
Il progetto richiede la progettazione di un algoritmo di ottimizzazione per un problema NP-hard, la sua realizzazione in un linguaggio di programmazione a scelta e la sperimentazione su alcuni esempi. Il seminario richiede l'illustrazione e la discussione critica di un articolo scientifico. La prova orale verte su tutto il programma dell'insegnamento. Prima di avviare il progetto o il seminario può essere richiesto di svolgere una breve prova scritta per verificare se lo studente è sufficientemente preparato.
Il progetto richiede la progettazione di un algoritmo di ottimizzazione per un problema NP-hard, la sua realizzazione in un linguaggio di programmazione a scelta e la sperimentazione su alcuni esempi. Il seminario richiede l'illustrazione e la discussione critica di un articolo scientifico. La prova orale verte su tutto il programma dell'insegnamento. Prima di avviare il progetto o il seminario può essere richiesto di svolgere una breve prova scritta per verificare se lo studente è sufficientemente preparato.
Docente/i