ID:
76920
Tipo Insegnamento:
Opzionale
Durata (ore):
48
CFU:
6
SSD:
RICERCA OPERATIVA
Url:
MATEMATICA/Percorso Comune Anno: 1
MATEMATICA/Percorso Comune Anno: 2
Anno:
2024
Dati Generali
Periodo di attività
Secondo Semestre (24/02/2025 - 06/06/2025)
Syllabus
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 (i.e., Mosel), e di individuare le tecniche più adatte per velocizzarne la soluzione da parte del MILP solver (i.e., XPressMP)
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 (i.e., Mosel), e di individuare le tecniche più adatte per velocizzarne la soluzione da parte del MILP solver (i.e., XPressMP)
Prerequisiti
algebra lineare, fondamenti di programmazione e strutture dati
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).
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).
Verifica 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 lavorando in modo individuale, in cui approfondisce un argomento svolto a lezione e le sue ricadute applicative, 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, padronanza del linguaggio tecnico.
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 10/30).
La lode si ottiene con 31/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.
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 lavorando in modo individuale, in cui approfondisce un argomento svolto a lezione e le sue ricadute applicative, 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, padronanza del linguaggio tecnico.
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 10/30).
La lode si ottiene con 31/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
Si ipotizza di erogare il corso in modalità mista, sia in presenza che in streaming ma gli studenti sono fortemente incoraggiati a partecipare in presenza per favorire l'apprendimento attraverso il confronto col docente e i colleghi.
Copia delle slides del corso redatte a cura del docente, caricate su Classroom.
Materiale di riferimento caricato dal docente su classroom, sia sugli argomenti teorici che di documentazione del software utilizzato.
Testo base di riferimento:
Lezioni di Ricerca Operativa, Matteo Fischetti, Ed. Libreria Progetto Padova.
Gli argomenti più avanzati (generazione di colonne, problema di separazione, rilassamento lagrangeano) sono trattati nel seguente testo, utile anche per eventuali approfondimenti:
Integer Programming, L. Wolsey, Wiley Interscience
Copia delle slides del corso redatte a cura del docente, caricate su Classroom.
Materiale di riferimento caricato dal docente su classroom, sia sugli argomenti teorici che di documentazione del software utilizzato.
Testo base di riferimento:
Lezioni di Ricerca Operativa, Matteo Fischetti, Ed. Libreria Progetto Padova.
Gli argomenti più avanzati (generazione di colonne, problema di separazione, rilassamento lagrangeano) sono trattati nel seguente testo, utile anche per eventuali approfondimenti:
Integer Programming, L. Wolsey, Wiley Interscience
Contenuti
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".
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".
Lingua Insegnamento
ITALIANO
Corsi
Corsi
MATEMATICA
Laurea Magistrale
2 anni
No Results Found
Persone
Persone
No Results Found