Corso di Studi in Ingegneria Informatica

SCHEDA DELL'INSEGNAMENTO (SI)
SSD MAT/09

 

LAUREA MAGISTRALE IN INGEGNERIA INFORMATICA

ANNO ACCADEMICO: 2022-2023

 

DOCENTE: MAURIZIO BOCCIA
TELEFONO: 081 7683247
EMAIL: Questo indirizzo email è protetto dagli spambots. È necessario abilitare JavaScript per vederlo.

 

INSEGNAMENTO INTEGRATO (EVENTUALE): 
MODULO (EVENTUALE):
CANALE (EVENTUALE):
ANNO DI CORSO (I, II, III): I
SEMESTRE (I, II): II
CFU: 9

 

...................................................................................................................................................

 

...................................................................................................................................................

 

Il corso ha l’obiettivo di fornire agli studenti gli strumenti metodologici per analizzare e risolvere problemi di programmazione matematica con particolare riferimento ai problemi di ottimizzazione combinatoria e di ottimizzazione su rete. Vengono presentate metodologie risolutive sia per taluni problemi "di base" dell'ottimizzazione su reti, sia per problemi "difficili" di ottimizzazione combinatoria e su reti. Al termine del corso lo studente avrà acquisito la capacità di formulare un modello astratto di un problema di ottimizzazione combinatoria, la capacità di individuare le strutture presenti su cui articolare un approccio risolutivo di tipo euristico, oppure, di applicare un algoritmo ad hoc per la sua soluzione esatta.

 

Conoscenza e capacità di comprensione
Il percorso formativo ha l’obiettivo di fornire agli studenti le metodologie di ottimizzazione combinatoria e di ottimizzazione su rete necessarie per la modellazione e la risoluzione esatta e/o euristica di problemi decisione che possono presentarsi in ambito ingegneristico e industriale. Al termine del corso, lo studente dovrà dimostrare di conoscere e di saper utilizzare gli strumenti necessari a formulare un problema di ottimizzazione combinatoria e di ottimizzazione su reti. Deve inoltre essere in grado di decidere, in relazione alle caratteristiche e alla complessità del problema, se la risoluzione del problema possa avvenire mediante l’utilizzo dei pacchetti software e delle librerie di ottimizzazione più diffusi, oppure occorra sviluppare un algoritmo ad hoc per la sua soluzione. Deve quindi dimostrare di conoscere le principali metodologie meta-euristiche per la risoluzione di problemi di ottimizzazione combinatoria e saper scegliere la metodologia più adatta al problema da affrontare.

Capacità di applicare conoscenza e comprensione
Il percorso formativo è orientato a trasmettere agli studenti gli strumenti metodologici e operativi necessari alla formulazione e alla soluzione di problemi di ottimizzazione combinatoria e di problemi di ottimizzazione su reti. In particolare, lo studente deve dimostrare di saper formulare un problema di ottimizzazione. Deve inoltre dimostrare di saperlo risolvere, quando possibile, in maniera esatta utilizzando una delle principali librerie di ottimizzazione, oppure in maniera approssimata utilizzando un approccio di tipo euristico. Infine, deve essere in grado di implementare e sperimentare i diversi approcci euristici e meta-euristici allo scopo di decidere l’approccio più adatto al particolare problema.

 

I Modelli della Ricerca Operativa
­ L’approccio modellistico
­ Modelli di Ottimizzazione

Programmazione Lineare continua e intera
­ Introduzione alla Programmazione Lineare
­ Esempi di modelli di programmazione lineare
­ Rappresentazione grafica di un problema di P.L.
­ Formulazioni.
­ Il metodo Branch and Bound
­ Il metodo dei piano di taglio
­ Il metodo Branch and Cut

Software per la Programmazione Matematica
­ Utilizzo della libreria Gurobi per la soluzione di problemi di PL e PLI.
­ Esempi d’utilizzo della libreria: pianificazione della produzione, gestione delle scorte, problemi su reti, problemi di localizzazione, problemi di distribuzione.

Euristiche per la soluzione di problemi di ottimizzazione combinatoria
­ L’ottimizzazione combinatoria
­ Euristiche di tipo greedy
­ Ricerca locale e tabù search
­ Algoritmi genetici

Elementi di teoria dei grafi
­ Forme di rappresentazione di un grafo
­ Algoritmi di visita di un grafo

Il problema di instradamento e flussi su rete
­ Classificazione dei problemi e degli algoritmi di minimo percorso
­ Il modello del minimo percorso
­ Algoritmi per il calcolo dei minimi percorsi
­ Problemi di flusso Single e Multi-Commodity
­ Politiche di instradamento e bilanciamento di una rete

Problemi di design, localizzazione e clustering
­ Problemi di localizzazione su nodi e su archi
­ Euristica costruttive e migliorative
­ Il problema di clustering
­ Algoritmo k-means per il problema di clustering

Il problema del Commesso Viaggiatore (TSP)
­ Complessità del problema
­ Un algoritmo di row generation
­ Euristiche greedy e di ricerca locale
­ Il problema di orienteering come variante del TSP

Il problema di Vehicle Routing
­ Definizione del problema e delle sue varianti
­ Euristiche greedy e di ricerca locale

 

- M. Caramia, S. Giordani, F. Guerriero, R. Musmanno, D. Pacciarelli, "Ricerca Operativa", Isedi, Italia, 2014.
- H. Paul Williams, Model Building in Mathematical Programming, John Wiley & Sons, Ltd.
- F. S. Hillier, G. J. Lieberman, Ricerca operativa - Fondamenti, 9/ed., McGraw-Hill, 2010.
- A. Sforza, Modelli e Metodi della Ricerca Operativa, 3a ed., ESI, Napoli, 2018.
- G. Bruno, Operations Management. Modelli e metodi per la logistica, ESI – Edizioni Scientifiche Italiane.
- Materiale didattico integrativo fornito durante il corso.

 

Il docente utilizzerà: lezioni frontali (65%), seminari (5%), esercitazioni di tipo numerico (10%), esercitazioni di utilizzo di librerie di ottimizzazione (25%). Il materiale del corso sarà reso disponibile on-line agli studenti.

 

a) Modalità di esame:

L'esame si articola in prova:
Scritta e orale
Solo scritta
Solo orale
Discussione di elaborato progettuale
Altro

 

In caso di prova scritta i quesiti sono (*):
A risposta multipla
A risposta libera
Esercizi numerici

  

 b) Modalità di valutazione:
La prova scritta è volta a verificare le capacità di formulazione di problemi di ottimizzazione e la comprensione degli algoritmi di risoluzione di problemi PL e PLI. Lo studente ha a disposizione 2 ore per la prova scritta. L’esame prevede inoltre lo svolgimento di un elaborato progettuale in cui lo studente deve implementare e sperimentale un algoritmo esatto e/o euristico per la soluzione di un problema di ottimizzazione combinatoria. Il colloquio orale avrà come oggetto sia la discussione dell’elaborato progettuale che l’accertamento dell’acquisizione dei concetti e delle metodologie illustrati durante le lezioni.

 

c) Modalità di valutazione:
L’esito della prova scritta è vincolante ai fine dell’accesso alla prova orale. La prova scritta e quella orale con la descrizione dell’elaborato finale contribuiscono rispettivamente per il 40% e il 60% della valutazione finale. Il superamento della prova scritta non è sufficiente per il superamento dell’esame.