OPTIMIZATION MODELS AND ALGORITHMS FOR DATA SCIENCE
Stampa
Anno immatricolazione
2019/2020
Anno offerta
2019/2020
Normativa
DM270
SSD
MAT/09 (RICERCA OPERATIVA)
Dipartimento
DIPARTIMENTO DI MATEMATICA 'FELICE CASORATI'
Corso di studio
MATEMATICA
Curriculum
PERCORSO COMUNE
Anno di corso
Periodo didattico
Secondo Semestre (02/03/2020 - 09/06/2020)
Crediti
6
Ore
56 ore di attività frontale
Lingua insegnamento
INGLESE
Tipo esame
ORALE
Docente
GUALANDI STEFANO (titolare) - 6 CFU
Prerequisiti
Il corso fa parte della formazione in matematica applicata per gli studenti di matematica e ingegneria. Per seguire meglio il corso lo studente deve aver frequentato i corsi e acquisito le conoscenze nelle materie di base in programmazione, analisi e algebra lineare.
Obiettivi formativi
Il corso offre un’introduzione alla teoria, ai modelli e agli algoritmi di ottimizzazione matematica. Gli obiettivi del corso sono:

1. Presentare agli studenti lo stato dell’arte della teoria e nella pratica per la soluzione di problemi di ottimizzazione vincolata.

2. Far maturare agli studenti l’esperienza e la capacità di formulare e risolvere problemi di ottimizzazione di grandi dimensioni usando dei software di ottimizzazione.
Programma e contenuti
- Prima Parte: Modelli di Ottimizzazione

Il saper formulare dei modelli di ottimizzazione richiede la capacità di ridurre un problema di calcolo o ingegneristico complesso in un modello matematico che può essere risolto con un software di ottimizzazione. Imparando a riconoscere degli schemi ricorrenti nei modelli di ottimizzazione risolti in problemi reali, lo studente svilupperà le competenze per riuscire a capire quali problemi possono formulati e risolti utilizzando i software di ottimizzazione esistenti (come ad esempio, CPLEX e GUROBI).

- Seconda Parte: Problemi di Flusso

I problemi di flusso sono un caso particolare di problemi di programmazione lineare, che appaiono in moltissimi casi come sottoproblemi di applicazioni complesse. In questa parte del corso vedremo come formulare e risolvere i problemi di flusso fondamentali: il problema del cammino minimo, di flusso massimo, e di flusso di costo minimo.

- Terza Parte: Ottimizzazione Lineare

L’ottimizzazione lineare include i problemi in cui sia la funzione obiettivo che i vincoli sono lineari, e le variabili sono reali. Gli argomenti fondamentali trattati sono: l’algoritmo del simplesso, la teoria della dualità, l’analisi di sensitività, i metodi di punto interno, e alcuni aspetti implementativi.

- Quarta Parte: Ottimizzazione Lineare Intera

L’ottimizzazione lineare intera include i problemi in cui sia la funzione obiettivo che i vincoli sono lineari, ma alcune variabili sono vincolate ad assumere valori interi. Gli argomenti trattati sono: algoritmi di branch-and-bound, algoritmi di generazione di tagli e algoritmi euristici.
Metodi didattici
Il corso prevede lezioni frontali e esercitazioni in laboratorio informatico.
Testi di riferimento
Dispense distribuite dal docente e reperibili dal sito web del corso.


Capitoli selezionati dei seguenti libri:
• H.P. Williams. Model building in mathematical programming. John Wiley & Sons, 2013.
• R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network flows, 1988.
• D. Bertsimas and J. N. Tsitsiklis. Introduction to Linear Optimization, Athena Scientific, 1997.
• D. Bertsimas and R. Weismantel. Optimization over Integers. Belmont, MA: Dynamic Ideas, 2005.
Modalità verifica apprendimento
L'esame è orale e ha l'obiettivo di verificare il livello di apprendimento degli studenti sul programma del corso. Parte dell'esame orale sarà dedicato alla presentazione di un progetto elaborato durante lo svolgimento del corso.
Altre informazioni
Il corso è articolato in quattro parti. Durante ciascuna parte, verrano usati come esempi problemi di Biologia Computazionale (ad esempio, i problemi di Alignment of Genomic Sequencing, Metabolic Networks, Haplotype Analysis), di Pianificazione e Scheduling (ad esempio, problemi di gestione di servizi medici a domicilio, turnistica di personale ospedaliero), e di Machine Learning (ad esempio, problemi di regressione, clustering, e classificazione).