METODI DI OTTIMIZZAZIONE
Anno accademico e docente
Non hai trovato la Scheda dell'insegnamento riferita a un anno accademico precedente?
Ecco come fare >>
- English course description
- Anno accademico
- 2021/2022
- Docente
- MADDALENA NONATO
- Crediti formativi
- 6
- Periodo didattico
- Secondo Semestre
- SSD
- MAT/09
Obiettivi formativi
- Il corso propone lo studio dei principali strumenti metodologici della programmazione matematica per risolvere problemi di ottimizzazione a variabili miste (discrete e continue), con vincoli lineari e funzione obiettivo lineari (modelli MILP, Mixed Integer Linear Programming).
Particolare enfasi verrà posta sulla costruzione dei modelli matematici, prendendo come esempio anche problemi di ottimizzazione tipici dell'ambito delle TLC.
Parte del corso si terrà in laboratorio, utilizzando un solver state of the art per la soluzione di modelli di ottimizzazione.
Conoscenze Acquisite:
Il corso introduce gli studenti alla modellizzazione dei problemi di ottimizzazione combinatoria attraverso un processo di astrazione che mira ad individuare variabili, vincoli e funzione obiettivo di un modello MILP.
Lo studente viene guidato in questa esperienza dalla conoscenza: delle famiglie di vincoli utilizzate per la descrizione delle relazioni più comuni fra entità, delle potenzialità espressive delle variabili binarie, delle proprietà matematiche del politopo associato alle diverse famiglie di vincoli, delle tecniche implementate dai solvers per la soluzione di modelli MILP.
Abilità:
Alla fine del corso lo studente sarà in grado di formulare un modello matematico MILP di un problema di ottimizzazione combinatoria, di codificare tale modello astratto nel linguaggio algebrico di riferimento (A.A. 2019/20 Mosel), e di individuare le tecniche più adatte per velocizzarne la soluzione da parte del MILP solver (A.A. 2019/20 XPressMP) Prerequisiti
- algebra lineare, fondamenti di programmazione e strutture dati
Contenuti del corso
- Introduzione alla programmazione matematica (ottimizzazione convessa, vincolata/non vincolata, ottimi locali/globali).
Programmazione lineare (interpretazione geometrica, condizioni di ottimalità, algoritmo del simplesso primale, dualità, simplesso duale)
Programmazione lineare intera (matrici totalmente unimodulari, rilassamento continuo, disuguaglianze di Chvatal Gomory, algoritmo cutting plane, descrizione poliedrale, Branch and Bound, problema di separazione)
Rilassamenti (rilassamento lineare, rilassamento per cancellazione di vincoli, rilassamento surrogato, rilassamento Lagrangeano e decomposizione Lagrangeana, nesso tra rilassamento Lagrangeano e dualità).
Tecniche di decomposizione: generazione di colonne, Branch and Cut, Branch and Price, decomposizione di Benders.
Ottimizzazione bilivello e Stackelberg game, reaction set e condizioni di esistenza di una soluzione.
Ottimizzazione non lineare (solo per brevi cenni):
ottimizzazione non vincolata: ottimizzazione lungo una direzione (Fibonacci, Interpolazione quadratica, Newton like),
ottimizzazione di funzioni differenziabili (gradiente, gradienti coniugati), e non differenziabili (metodo del subgradiente e metodi bundle); ottimizzazione vincolata, condizioni di ottimo di KKT.
Per la ripartizione oraria degli argomenti si rimanda al file "Programma del Corso". Metodi didattici
- Lezioni teoriche frontali/esercitazioni.
Il corso si svolge prevalentemente in laboratorio, dove le metodologie precedentemente introdotte a livello teorico, vengono applicati alla soluzione di problemi classici di ottimizzazione combinatoria, attraverso lo sviluppo di modelli matematici nel linguaggio MOSEL sfruttando le funzionalità del solver XPressMP (FICO Optimization). Modalità di verifica dell'apprendimento
- - L'esame consiste in una prova orale che si compone di due parti, che hanno luogo consecutivamente nello stesso giorno.
La prima parte consiste nell'esposizione da parte dello studente di un elaborato che può essere, a scelta, o un progettino sperimentale o una relazione.
Il progettino viene svolto individualmente o a gruppi di 2/3 persone, su argomenti concordati col docente, e prevede una parte implementativa e una sperimentale.
In alternativa al progetto sperimentale lo studente redige una relazione in cui approfondisce un argomento svolto a lezione, concordandolo col docente (relazione).
Si incoraggiano gli studenti ad avvalersi di strumenti di presentazione come Power Point o Prezi per illustrare il proprio lavoro.
Il progettino viene valutato dal docente in funzione di quanto il candidato ha saputo fare proprie ed applicare al problema in esame le metodologie esposte nel corso. Nel caso della relazione, si valuta organizzazione dell'elaborato, completezza e livello di dettaglio.
In entrambi i casi la seconda parte della prova orale consiste in una interrogazione tradizionale con domande sul programma svolto.
Il voto finale è dato dalla somma del voto del progetto (fino a 21/30 per il progetto sperimentale, fino a 17/30 per la relazione) e dell'orale (fino a 11/30).
La lode si ottiene con 32/30.
Il superamento dell'esame è prova di aver acquisito le conoscenze e le abilità specificate negli obiettivi formativi dell'insegnamento.
Su richiesta l'esame si può sostenere in lingua inglese. Testi di riferimento
- Si ipotizza di erogare il corso in modalità mista, sia in presenza che in streaming.
Copia delle slides del corso redatte a cura del docente, caricate sul sito.
Materiale di riferimento caricato dal docente sul sito web del corso sia sugli argomenti teorici che di documentazione del software utilizzato.
Lezioni di Ricerca Operativa, Matteo Fischetti, Ed. Libreria Progetto Padova.
Gli argomenti più avanzati (generazione di colonne, problema di separazione, rilassamento lagrangeano) sono trattati in questo testo, utile anche per eventuali approfondimenti:
Integer Programming, L. Wolsey, Wiley Interscience
