CdSINGEGNERIA GESTIONALE
Codice749AA
CFU6
PeriodoPrimo semestre
LinguaItaliano
| Moduli | Settore/i | Tipo | Ore | Docente/i | |
| RICERCA OPERATIVA II | MAT/09 | LEZIONI | 60 |
|
Al termine del corso lo studente avrà acquisito conoscenze relative a metodi di ottimizzazione matematica basati sulla programmazione lineare intera (mista) per problemi decisionali nell'ambito della gestione delle risorse.
Students are expected to acquire knowledge of:
- how integer programming is used to formulate discrete optimization models and in particular, what makes one model “better” than another; basic concepts of complexity theory; the theory of valid inequalities; some exact methods for (mixed) integer linear programming; some important classes of (mixed) integer linear programming problems; decomposition-based techniques for large-scale problems; optimization SW tools.
Lo studente sarà valutato rispetto alla sua abilità nel formulare problemi di tipo decisionale per mezzo della programmazione lineare intera (mista), proporre e analizzare formulazioni alternative, nonché metodi risolutivi e relativa complessità computazionale.
Lo studente dovrà dimostrare di aver compreso ed essere capace di utilizzare i contenuti dell’insegnamento, di applicare i modelli e le metodologie ad esempi nuovi (non visti in aula), e di presentare la teoria in modo chiaro e conciso.
Il superamento dell’esame sarà garantito agli studenti che dimostreranno padronanza e capacità operativa in relazione ai concetti chiave illustrati nell’insegnamento, e dimostreranno una sufficiente capacità di applicare i modelli e le metodologie ad esempi nuovi (non visti in aula).
The student will be assessed on his/her demonstrated ability to solve problems and discuss concepts and applications of Operation Research. The student will be assessed on his/her demonstrated ability to formulate discrete optimization problems using (mixed) integer linear programming, propose and analyse alternative formulations as well as solution methods.
Al termine del corso
- lo studente sarà in grado di modellare problemi decisionali mediante programmazione lineare intera
- lo studente sarà in grado di progettare algoritmi per problemi di ottimizzazione combinatoria
- lo studente sarà in grado di analizzare la complessità di un problema di ottimizzazione combinatoria e il tempo di calcolo di un algoritmo
- lo studente conoscerà e saprà utilizzare strumenti SW per risolvere tali problemi
The course aims at providing an appreciation of the types of combinatorial problems that arise in Operational Research, and providing knowledge of the main approaches for tackling such problems.
At the end of the course:
- the student will be able to formulate a mathematical optimization model for a decision problem
- the student will be able to design a solution algorithm for the optimization model
- the student will be able to analyse the complexity of an optimization problem and of an algorithm
- the student will be able to use optimization SW tools to solve an optimization problem
Data la descrizione di un problema decisionale, lo studente dovrà realizzare modelli e proporre algoritmi risolutivi per gli stessi, oltre ad analizzare la complessità.
The student will be given the description of a decision problem and will be asked to formulate it using MILP, to design a solution algorithm and evaluate the complexity of the problem.
Il corso permetterà di gestire problemi di tipo decisionale mediante metodi di ottimizzazione matematica.
Il corso permetterà allo studente di:
- sviluppare capacità di formalizzazione matematica di problemi di tipo decisionale nell'ambito della gestionae delle risorse
- conoscere gli algoritmi di base per risolvere tali problemi e relativa complessità
- sapere risolvere tali problemi con alcuni tool software per l'ottimizzazione matematica
On completion of the course, the student will be expected to:
- formulate an optimization problem using (mixed) Integer Programming;
- understand the basics of complexity theory and be able to provide proofs that certain problems are NP-hard;
- analyse the worst-case running time of an algorithm;
- have an appreciation of the main types of approaches that can be used for tackling combinatorial optimization problems, together with their limitations;
- understand the principles behind branch-and-cut and branch-and-price, and be able to apply these approaches to new problems;
- have an overview of how combinatorial optimization techniques can be applied in an area such as data science.
Durante le sessioni di esame, saranno verificate le fasi di modellazione, realizzazione di un algoritmo e analisi della complessità.
During the exams, the student will be assessed over his/her attitude from the formulation of an optimization model, implementation of a solution algorithm, and complexity analysis.
Ci si aspetta che lo studente conosca i concetti e le idee di base della ricerca operativa, quali quelle contenute nel corso di Ricerca Operativa I. Inoltre sono richieste una buona conoscenza dell'algebra lineare e della matematica di base.
The student is required to know and master basic concepts and ideas of operational research, as those provided in the basic course of Operational research I.
Il corso consiste in lezioni frontali ed esercitazioni.
Il materiale didattico è reso disponibile sulla pagina Moodle del corso.
Face to face lectures and exercises.
Teaching material is available on the Moodle page.
Il corso riguarda problemi di ottimizzazione in ambito decisionale con particolare attenzione ai problemi di Ottimizzazione Combinatoria. Il primo obiettivo è introdurre la Programmazione Lineare (mista) Intera e insegnare come formulare modelli matematici per problemi di ottimizzazione appartenenti a tali categorie. La prima parte del corso presentarà quindi alcuni problemi classici di Programmazione Lineare Intera (mista) e relative formulazioni.
Il secondo obiettivo e' presentare algoritmi per la risoluzione di tali problemi. Inoltre, vengono introdotti i concetti di base della complessita' computazionale. La seconda parte del corso tratta dunque di qualità di una formulazione e metodi risolutivi. Inizieremo da modelli di programmazione lineare intera per problemi di ottimizzazione combinatoria classici, ponendo particolare enfasi sulla qualità del rilassamento continuo dei modelli. Discuteremo metodi risolutivi per modelli di dimensione esponenziale.
L'ultima parte del corso e' dedicata alle applicazioni pratiche: vengono presentate applicazioni reali di ottimizzazione e si mostra l'utilizzo di software di ottimizzazione. Saranno discusse alcune applicazioni complesse, modellate con un numero esponenziale di variabili e vincoli.
- Service design;
- Routing;
- Cutting and packing;
- ...
1.Introduction. Types of problems (for example, machine scheduling, vehicle routing and the travelling salesman problem, cutting and packing, set covering and partitioning). Integer programming formulations.
2.Computational Complexity. Analysis of worst-case running time of algorithms (sorting, matrix multiplication, divide and conquer, dynamic programming). NP-completeness, reducibility.
3.General Solution Approaches. Branch and bound, dynamic programming, constraint satisfaction, Lagrangean relaxation.
4.Branch and cut. Valid inequalities, polyhedra and facets, separation, computational aspects.
5.Danzig Wolfe Decomposition. Formulations using column generation, pricing algorithms, branching strategies.
6.Benders Decomposition.
9.Applications in Data Analysis and Prescriptive Analytics.
- L. Galli, note disponibili sulla pagina moodle del corso
- basic OR notes
Per approfondimenti:
- Christos H. Papadimitriou and Ken Steiglitz, Combinatorial optimization: algorithms and complexity. Dover, 1998.
- A. Wolsey Integer programming John Wiley & Sons
- L. Galli, moodle web page of the course
- basic OR notes
For further reading:
- Christos H. Papadimitriou and Ken Steiglitz, Combinatorial optimization: algorithms and complexity. Dover, 1998.
- A. Wolsey Integer programming John Wiley & Sons
L'esame consiste in un compito scritto in cui lo studente risolve alcuni esercizi sugli argomenti visti nel corso (durata circa 2 ore).
Gli esercizi possono comprendere anche domande di teoria e dimostrazioni.
Non è consentito consultare libri/appunti o altro.
Written exam (about 2 hours) with exercises and theory questions, no books/notes or anything else is allowed during the exam.