ECTS - University of Pisa
| Modules | Area | Type | Hours | Teacher(s) | |
| 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:
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
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:
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:
On completion of the course, the student will be expected to:
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.
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.
Per approfondimenti:
For further reading:
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.
