Syllabus del corso
Obiettivi formativi
Il corso affronta alcuni importanti problemi di ottimizzazione che si presentano in diversi ambiti applicativi, quali la gestione della produzione, i trasporti e la logistica. L’obiettivo del corso è fornire agli studenti una classificazione dei problemi di ottimizzazione relativi alle reti e ad altre applicazioni. Inoltre, il corso mira a fornire agli studenti la conoscenza di un’ampia gamma di modelli e metodi di ottimizzazione. Gli studenti impareranno a modellare i problemi di ottimizzazione che si presentano nelle applicazioni della vita reale, a rappresentarli come casi particolari di problemi di ottimizzazione ben noti e ad affrontarli applicando sia approcci esatti che euristici. Oltre alle conoscenze teoriche, il corso fornirà esperienza pratica nello sviluppo e nell’applicazione delle tecniche di ottimizzazione. Durante le sessioni di esercitazione, agli studenti verrà chiesto di applicare le proprie conoscenze teoriche per risolvere problemi reali mediante il software AMPL.
Contenuti sintetici
- Problemi di flusso su reti.
- Problemi di instradamento dei flussi e di progettazione di reti a costo fisso.
- Problemi di localizzazione.
- Problemi di scheduling.
Programma esteso
- Problemi di flusso su reti: flusso massimo, flusso di costo minimo, albero di copertura di costo minimo, problema del commesso viaggiatore.
- Problemi di instradamento dei flussi e di progettazione di reti a costo fisso: flussi divisibili vs non divisibili, percorsi singoli vs multipli, flussi multicommodity, costi fissi per nodo e per arco. Modelli ILP basati sugli archi e sui percorsi. Problemi di instradamento dei veicoli.
- Problemi di localizzazione: copertura e partizionamento di insiemi, problemi del p-centro e della p-mediana, problemi di localizzazione di strutture con e senza vincoli di capacità, assegnazione singola e assegnazione multipla.
- Problemi di scheduling. Problemi su macchina singola con diverse funzioni obiettivo (tempo totale ponderato di completamento, makespan, ritardi, ritardi accumulati), problemi su macchine parallele, flow shop, job shop.
Prerequisiti
Conoscenze di base di programmazione lineare e del metodo del simplesso.
Metodi didattici
L'insegnamento prevedere una attività didattica di 42 ore suddivise nel modo seguente:
- 28 ore di lezione frontali svolte in modalità erogativa in presenza;
- 14 ore di esercitazione svolte in modalità interattiva in presenza.
Modalità di verifica dell'apprendimento
L'esame consiste in una prova scritta obbligatoria (esercizi come controllo delle competenze di problem solving disciplinare) ed una prova orale facoltativa (colloquio sugli argomenti svolti a lezione). La prova scritta ha lo scopo di verificare la conoscenza delle tecniche di modellazione e risoluzione di problemi decisionali introdotti durante il corso e la capacità di implementare modelli di ottimizzazione mediante il software AMPL.
Testi di riferimento
Testi di consultazione e di approfondimento:
- F. Schoen, Optimization Models, 2024.
- R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network flows, Prentice Hall, 1993.
- M.S. Bazaraa, J.J. Jarvis, H.D. Sherali, Linear programming and network flows, Wiley and Sons, 1990.
- Z. Drezner, H.W. Hamacher, Facility Location: Applications and Theory, Springer, 2004.
- S. Martello, P. Toth, Knapsack problems, Wiley, 1990.
- M.L. Pinedo, Scheduling - Theory, Algorithms, and Systems, Springer, 2016.
Ulteriore materiale verrà fornito durante il corso in forma di slide ed esercizi svolti.
Periodo di erogazione dell'insegnamento
Primo semestre.
Lingua di insegnamento
Italiano.
Sustainable Development Goals
Learning objectives
The course deals with some important optimization problems arising in several fields of application such as manufacturing management, transportation and logistics. The aim of the course is to provide students with a classification of optimization problems related to networks and other applications. Further, the course aims at providing the students with the knowledge of a wide range of optimization models and methods. The students will learn to model optimization problems arising in real life applications, to represent them as particular case of well known optimization problems, and to deal with them applying both exact and heuristic approaches. Beside theoretical knowledge, the course will provide practical experience in developing and applying the optimization techniques. During the practical sessions, students will be asked to apply their theoretical knowledge to solve real-world problems using the AMPL software.
Contents
- Network flow problems.
- Flow routing and Fixed Charge Network Design problems.
- Location problems.
- Scheduling problems.
Detailed program
- Network flow problems: maximum flow, minimum cost flow, minimum spanning tree, travelling salesman problem.
- Flow routing and Fixed Charge Network Design problems: splittable vs unsplittable flow, single vs multiple paths, multicommodity flows, node and arc fixed costs. Arc-based and path-based ILP models.Vehicle routing problems.
- Location problems: set covering and set partitioning, p-center and p-median problems, uncapacitated and capacitated facility location problems, single assignment and multiple assignment.
- Scheduling problems. Single machine scheduling with different objective functions (total weighted completion time, makespan, lateness, tardiness), parallel machines scheduling problems, flow shop, job shop.
Prerequisites
Basic knowledge of linear programming and simplex method are required.
Teaching methods
The course will provide a teaching activity of 42 hours divided as follows:
- 28 hours of face-to-face lectures conducted in in-person delivery mode;
- 14 hours of exercises conducted in interactive in-presence mode.
Assessment methods
The exam consists of a compulsory written test (exercises as a check on disciplinary problem solving skills) and an optional oral test (interview on topics covered in class). The written test is designed to test knowledge of modeling and decision problem solving techniques introduced during the course and the ability to implement optimization models using AMPL software.
Textbooks and Reading Materials
Reference books:
- F. Schoen, Optimization Models, 2024.
- R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network flows, Prentice Hall, 1993.
- M.S. Bazaraa, J.J. Jarvis, H.D. Sherali, Linear programming and network flows, Wiley and Sons, 1990.
- Z. Drezner, H.W. Hamacher, Facility Location: Applications and Theory, Springer, 2004.
- S. Martello, P. Toth, Knapsack problems, Wiley, 1990.
- M.L. Pinedo, Scheduling - Theory, Algorithms, and Systems, Springer, 2016.
Additional material will be provided during the course in the form of slides and solved exercises.
Semester
First semester.
Teaching language
Italian.
Sustainable Development Goals
Staff
-
Mauro Passacantando
