View syllabus
OPERATIONS RESEARCH II
LAURA GALLI
Academic year2022/23
CourseMANAGEMENT ENGINEERING
Code749AA
Credits6
PeriodSemester 1
LanguageItalian

ModulesAreaTypeHoursTeacher(s)
RICERCA OPERATIVA IIMAT/09LEZIONI60
LAURA GALLI unimap
Obiettivi di apprendimento
Learning outcomes
Conoscenze

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.

 

Knowledge

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.
Modalità di verifica delle conoscenze

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).

Assessment criteria of knowledge

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.

 

 

Capacità

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
Skills

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
Modalità di verifica delle capacità

Data la descrizione di un problema decisionale, lo studente dovrà realizzare modelli e proporre algoritmi risolutivi per gli stessi, oltre ad analizzare la complessità.

Assessment criteria of skills

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.

Comportamenti

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
Behaviors

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.
Modalità di verifica dei comportamenti

 

Durante le sessioni di esame, saranno verificate le fasi di modellazione, realizzazione di un algoritmo e analisi della complessità.

 

Assessment criteria of behaviors

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.

Prerequisiti (conoscenze iniziali)

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.

Prerequisites

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.

Indicazioni metodologiche

Il corso consiste in lezioni frontali ed esercitazioni.
Il materiale didattico è reso disponibile sulla pagina Moodle del corso.

Teaching methods

Face to face lectures and exercises.

Teaching material is available on the Moodle page.

Programma (contenuti dell'insegnamento)

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;
  • ...

 

 

Syllabus

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. 

Bibliografia e materiale didattico
  • 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
Bibliography

For further reading:

  • Christos H. Papadimitriou and Ken Steiglitz, Combinatorial optimization: algorithms and complexity. Dover, 1998.
  • A. Wolsey Integer programming John Wiley & Sons
Modalità d'esame

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.

Assessment methods

Written exam (about 2 hours) with exercises and theory questions, no books/notes or anything else is allowed during the exam.

Updated: 08/08/2022 09:28