Operational research complements
A.A. 2022/2023
Learning objectives
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.
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
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.
Professor(s)