CdSINFORMATICA
Codice029AA
CFU6
PeriodoPrimo semestre
LinguaItaliano
| Moduli | Settore/i | Tipo | Ore | Docente/i | |
| RICERCA OPERATIVA | MAT/09 | LEZIONI | 48 |
|
Il corso presenta gli strumenti necessari alla costruzione e alla risoluzione di modelli analitici di ottimizzazione per problemi di gestione ed allocazione delle risorse, con applicaizioni in moltissimi campi della scienza e dell'ingegneria ed attività economiche (logistica, trasporti, telecomunicazioni, finanza, energia, salute, ...). Verrà innanzi tutto introdotto il concetto di modellazione matematica per due classi particolarmente rilevanti di problemi di ottimizzazione, la Programmazione Lineare e la Programmazione Lineare Intera, mostrando come sia possibile attraverso di esse costruire modelli di moltissime situazioni reali (o realistiche, o anche completamente immaginarie). Verranno poi illustrate le proprietà teoriche ed alcune delle principali tecniche algoritmiche per la soluzione di tre grandi classi di problemi di ottimizzazione: problemi di flusso su reti, di programmazione lineare e di programmazione lineare intera.
The course introduces the fundamental tools for the construction and solution of analytical optimization models for management and resource allocation problems, with applications in many fields of science and engineering and economic activities (logistics, transport, telecommunications, finance, energy, health, ...). Two particularly relevant classes of optimization problems, Linear Programming and Integer Linear Programming, will be introduced and modelling techniques will be described showing how it is possible to build models of many real (or realistic, or even completely imaginary) situations. The theoretical properties and some of the main algorithmic techniques for the solution of three major classes of optimization problems will then be illustrated: flow problems on networks, linear programming and integer linear programming.
Esame scritto seguito da prova orale. Sono previste verifiche intermedie (tipicamente tre) che sostituiscono l'esame scritto.
Written exam plus oral exam. Intermediate written assessments (typically, three) will be held whose successful completion substitutes for the written exam.
Lo studente sarà in grado di sviluppare modelli di situazioni reali (o realistiche, o anche del tutto immaginarie) sotto forma di problemi di Programmazione Lineare o Programmazione Lineare Intera. Lo studente sarà quindi in grado di analizzare e sviluppare algoritmi risolutivi per problemi appartenenti a queste classi, tra cui quelli a flusso di rete.
The student will be able to develop models of real (or realistic, or even completely imaginary) situations under the form of Linear Programs or Integer Linear Programs. The student will then be able to analyse and develop solvution algorithms for problems belonging to these classes, among which netwrok flow ones.
Le capacità di modellazione che quelle di analisi e sviuppo di algoritmi saranno verificate sia attraverso l'esame scritto che attraverso l'esame orale.
Lo studente potrà sviluppare capacità critiche, sia a livello modellistico che algoritmico, per affrontare problemi di ottimizzazione del mondo reale (o realistici, o anche del tutto immaginari), che risulteranno rilevanti in svariati ambiti lavorativi, sia a livello progettuale che implementativo.
The student will be able to develop critical modelling and algorithmic skills on real-world (or realistic, or even completely imaginary) optimization problems, which will be relevant to several work areas, both at design and implementation level.
Le capacità critiche dello studente per affrontare problemi di ottimizzazione del mondo reale (o realistici, o anche del tutto immaginari) saranno valutate durante le sessioni di esercitazioni.
The student's critical skills in dealing with real-world (or realistic, or even completely imaginary) optimization problems will be assessed during the tutorial sessions.
- Logica elementare: connettivi logici, proposizioni, principio di induzione, metodi di dimostrazione
- Spazi vettoriali: spazi, semispazi, vettori, combinazioni lineari, indipendenza lineare, basi, coordinate
- Geometria del piano e dello spazio tridimensionale: sottospazi affini, equazione di rette, piani e semispazi
- Prodotto scalare euclideo, ortogonalità
- Matrici: operazioni con le matrici, determinante, invertibilità
- Concetto di funzione, funzioni lineari (ed affini)
- Sistemi lineari di equazioni e loro risoluzione
- Cosa è un algoritmo
- Complessità di un algoritmo
- Classi P e NP
- Strutture dati: fila, pila, deque, code di priorità, heap
- Grafi: nodi, archi, alberi, cammini, cicli
- Grafi: rappresentazione e visite (DFS e BFS)
- Alberi: rappresentazioni e visite
- Ricerca dei punti di massimo e minimo di funzioni di una variabile
- Boolean logic: operators, propositions, induction principle, proof methods
- Vector spaces: spaces, semi-spaces, vectors, linear combinations, linear independence, bases, coordinates
- Geometry of the two and three-dimensional spaces: affine subspaces, equations of lines, planes and half-spaces
- Euclidean product, orthogonality
- Matrices: operations with the matrices, determinant, invertibility
- Affine and linear functions
- Linear systems of equations and their resolution
- What is an Algorithm
- Complexity of an algorithm
- Classes P and NP
- Data structures: row, stack, deque, priority queues, heap
- Graphs: nodes, arcs, trees, paths, cycles
- Graphs: representation and visits (DFS and BFS)
- Trees: representations and visits
- Maximum and minimum points for functions of one variable
Modalità: lezioni frontali, possibilmente con l'aiuto di slides, e sessioni di esercitazioni.
Sito di elearning del corso: download di materiali didattici, pubblicazione di test per esercizi a casa (con relative soluzioni).
Attività di apprendimento: partecipazione alle lezioni e studio individuale.
Frequenza: consigliata
Delivery: Frontal lessons, possily with the help of slides, exercise sessions.
Course elearning site: download teaching materials, publication of tests for home exercises.
Learning activities: attending lectures, individual study.
Attendance: Advised
Introduzione (2 ore)
- Problemi decisionali e problemi di ottimizzazione
- Classi di problemi ed esempi
Modelli e loro formulazione (6 ore)
- Tipi di variabili: quantitative, logiche, continue, discrete
- Formulazione di vincoli
- Formulazione della funzione obiettivo
Grafi e Reti di flusso (16 ore)
- Modello generale dei problemi di flusso
- Alberi, cammini e tagli, visite di grafi e alberi
- Il problema dei cammini minimi
- Il problema del flusso massimo
- Il problema del flusso di costo minimo
- Il problema dell'albero di copertura di costo minimo
Programmazione Lineare (16 ore)
- Geometria della programmazione lineare e teorema fondamentale
- Dualità e scarti complementari
- Basi: complementarità, degenericità ed ottimalità
- Algoritmi del simplesso primale e duale
Programmazione Lineare Intera (8 ore)
- Metodi poliedrali: tagli ed algoritmo di Gomory
- Metodi enumerativi: l'algoritmo "Branch&Bound"
- Implementazioni ad-hoc per i problemi dello zaino e del commesso viaggiatore
Introduction (2 hours)
- Decision-making and optimization problems
- Classes of problems and examples
Optimization models (6 hours)
- Variables: quantitative, logical, continuous, discrete
- Constraints formulation
- Objective function formulation
Graphs and network flows (16 hours)
- General model for network flow problems
- Trees, paths and cuts, graph search
- Shortest path problem
- Maximum flow problem
- Minimum cost flow problem
- Minimum spanning tree problem
Linear Programming (16 hours)
- Geometry and fundamental theorem of LP
- Duality and complementary slackness conditions
- Bases: complementarity, degeneracy and optimality
- Primal and dual simplex algorithms
Integer Linear Programming (8 hours)
- Polyhedral methods: Gomory cuts
- Enumeration methods: the "Branch & Bound" method
- Ad-hoc implementations of the "Branch & Bound" method for the knapsack problem and the travelling salesman problem
Testi di base: Appunti di Ricerca Operativa rilasciati dai docenti.
Altro possibile materiale didattico:- Jon Lee A First Course in Linear Optimization Reex Press, 2013
- Fabio Schoen Optimization Models, free e-book version, 2022
- D. Simchi-Levi, X. Chen and J. Bramel Logic of Logistics: Theory, algorithms, and applications for logistics and supply chain Springer-Verlag, 2004
- M.S.Bazaraa, J.J.Jarvis, H.D.Sherali Linear programming and network flows John Wiley & Sons
- L.A. Wolsey Integer programming John Wiley & Sons
- G. Ghiani, R. Musmanno Modelli e Metodi per l'Organizzazione dei Sistemi Logistici Pitagora, 2000
- R.K. Ahuja, T.L. Magnanti, J. Orlin Network flows. Theory, algorithms and applications Prentice Hall, 1993
- F.S. Hillier, G.J. Lieberman Ricerca Operativa - Fondamenti McGraw-Hill, 2010
- C. Vercellis Ottimizzazione. Teoria, metodi, applicazioni McGraw Hill, 2008
- The Computational Infrastructure for Operations Research (COIN-OR)
- The SMS++ Structured Modelling System
- The SCIP (Solver Constraint Integer Programs) solver
- The IBM/ILOG CPLEX solver
- The Gurobi solver
- The Mosek solver
- The Pyomo python modelling system
- The PuLP python modelling system
- The JuMP Julia modelling system
- The YALMIP Matlab modelling system
- The MCFClass project
Basic material: Lectures in Operations Research (in Italian) released by the lecturers.
Other possible textbooks:- Jon Lee A First Course in Linear Optimization Reex Press, 2013
- Fabio Schoen Optimization Models, free e-book version, 2022
- D. Simchi-Levi, X. Chen and J. Bramel Logic of Logistics: Theory, algorithms, and applications for logistics and supply chain Springer-Verlag, 2004
- M.S.Bazaraa, J.J.Jarvis, H.D.Sherali Linear programming and network flows John Wiley & Sons
- L.A. Wolsey Integer programming John Wiley & Sons
- G. Ghiani, R. Musmanno Modelli e Metodi per l'Organizzazione dei Sistemi Logistici Pitagora, 2000
- R.K. Ahuja, T.L. Magnanti, J. Orlin Network flows. Theory, algorithms and applications Prentice Hall, 1993
- F.S. Hillier, G.J. Lieberman Ricerca Operativa - Fondamenti McGraw-Hill, 2010
- C. Vercellis Ottimizzazione. Teoria, metodi, applicazioni McGraw Hill, 2008
- The Computational Infrastructure for Operations Research (COIN-OR)
- The SMS++ Structured Modelling System
- The SCIP (Solver Constraint Integer Programs) solver
- The IBM/ILOG CPLEX solver
- The Gurobi solver
- The Mosek solver
- The Pyomo python modelling system
- The PuLP python modelling system
- The JuMP Julia modelling system
- The YALMIP Matlab modelling system
- The MCFClass project
Il testo di base (gratuito) ed i testi di esame scritto (con soluzioni) forniti dai docenti sono più che sufficienti per completare il corso anche non frequentando.
The (free) base textbook and the previous written exams (with solutions) are amply sufficient to oass the course even if not attending the lectures.
Esame scritto seguito da prova orale. Sono previste verifiche intermedie (tipicamente tre) che sostituiscono l'esame scritto.
Written exam plus oral exam. Intermediate written assessments (typically, three) will be held whose successful completion substitutes for the written exam.