Operational research complements

A.A. 2020/2021
6
Crediti massimi
48
Ore totali
SSD
MAT/09
Lingua
Inglese
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.
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
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.
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.
MAT/09 - RICERCA OPERATIVA - CFU: 6
Lezioni: 48 ore
Docente/i
Ricevimento:
su appuntamento
Crema, via Bramante 65