logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2023/2024
Scuola Scuola di Ingegneria Industriale e dell'Informazione
Insegnamento 088983 - FOUNDATIONS OF OPERATIONS RESEARCH
Cfu 5.00 Tipo insegnamento Monodisciplinare
Docente Malucelli Federico

Corso di Studi Codice Piano di Studio preventivamente approvato Da (compreso) A (escluso) Insegnamento
Ing Ind - Inf (Mag.)(ord. 270) - CR (263) MUSIC AND ACOUSTIC ENGINEERING*AE088983 - FOUNDATIONS OF OPERATIONS RESEARCH
Ing Ind - Inf (Mag.)(ord. 270) - MI (471) BIOMEDICAL ENGINEERING - INGEGNERIA BIOMEDICA*AE088983 - FOUNDATIONS OF OPERATIONS RESEARCH
Ing Ind - Inf (Mag.)(ord. 270) - MI (474) TELECOMMUNICATION ENGINEERING - INGEGNERIA DELLE TELECOMUNICAZIONI*AE088983 - FOUNDATIONS OF OPERATIONS RESEARCH
052481 - NETWORK DESIGN
Ing Ind - Inf (Mag.)(ord. 270) - MI (481) COMPUTER SCIENCE AND ENGINEERING - INGEGNERIA INFORMATICA*AE088983 - FOUNDATIONS OF OPERATIONS RESEARCH

Obiettivi dell'insegnamento

 

Operations Research (O.R.) is the branch of applied mathematics dealing with quantitative methods to analyze and solve complex real-world decision-making problems. The course covers some of the fundamental concepts and methods of O.R. pertaining to graph optimization, linear programming and integer linear programming. The emphasis is on optimization models and efficient algorithms with a wide range of important applications in engineering and management.  

 


Risultati di apprendimento attesi
 
Knowledge and understanding
 
The students will learn:

- the mathematical language of optimization models and some important classes of models

- the main properties and algorithms (including the worst case complexity) of/for the following graph optimization problems: minimum cost spanning tree, shortest path and maximum flow
- the critical path method for project scheduling

- the geometrical and algebraic aspects of Linear Programming (LP), and an LP algorithm
- the main properties of LP duality, including weak/strong duality and the complementary slackness optimality conditions
- the economical interpretation of the dual of some LP problems

- the main characteristics of Integer Linear Programming (ILP) problems
- the cutting plane method with fractional Gomory cuts
- the Branch-and-Bound method for ILP and other combinatorial optimization problems.

 

Applying knowledge and understanding

 

The students will be able to:

- build optimization models starting from the decision problem descriptions, solve them using Python and a state-of-the-art solver, and interpret the output.
- identify an appropriate graph optimization algorithm to tackle a given decision problem and apply it to small examples
- apply the LP method to textbook examples
- construct the dual of LP problems in explicit and parametric form
- apply the studied ILP methods (Branch-and-Bound method, cutting plane method with fractional Gomory cuts) to small examples

- leverage on the acquired theoretical and algorithmic knowledge to answer simple questions.

 

Learning skills

 

The students will learn how to tackle complex decision-making problems with a solid mathematical and algorithmic approach, which can be adapted and extended to deal with a variety of real-world problems.

 


Argomenti trattati

 

1. Introduction

Decision-making problems. Main steps of an O.R. study. Different types of optimization (mathematical programming) problems. Optimization models (decision variables, objective function, constraints) and modeling techniques.

2. Graph and network optimization

Optimum spanning trees. Shortest path problems: algorithms for the main variants (including Dynamic programming for acyclic graphs). Application to project scheduling: critial path method and Gantt diagrams. Maximum flows: Ford-Fulkerson algorithm and maximum flow-minimum cut theorem. Minimum cost flows, matching in bipartite graphs. An example of NP-hard network optimization problems: the Traveling salesman problem.


3. Linear Programming (LP)

LP models. Geometric aspects (vertices of the feasible region) and algebraic aspects (basic feasible solutions). Fundamental properties of linear programming. The Simplex method. LP duality theory: pair of dual problems, weak and strong duality, complementary slackness conditions. Economic interpretation. Sensitivity analysis. Special cases: assignment and transportation problems.

4. Integer Linear Programming (ILP)

ILP models for, among others, transportation, routing, scheduling and location problems. Formulations and linear programming relaxation. Exact methods: Branch-and-Bound algorithm, cutting plane method with fractional Gomory cuts. 

 

Time permitting we will provide/review some basics of computational complexity (recognition problems, classes P and NP, polynomial-time reductions, NP-complete and NP-hard problems) and introduce basic heuristic algorithms (greedy and local search).

 

A couple of topics will be assigned for independent study (e.g. LP sensitivity analysis) prior to sessions devoted to exercises or computer laboratory activities. There will be computer lab meetings and computer lab assignments.


Prerequisiti

Basic knowledge of Multivariate Calculus, Linear Algebra and Algorithms.


Modalità di valutazione

 

A written exam which covers all the material presented in the lectures, the sessions devoted to the exercises, and the computer laboratory sessions and assignments. The first part of the written exam will be closed book and the last part will be open book. A few points will be assigned based on some formative assesments during the semester, further details will be provided at the beginning of the course.

The exam consists of several questions aimed at evaluating the level of (applying) knowledge and understanding of the main concepts, models, results and methods covered in the course as specified in the expected learning outcomes. In particular, it includes modeling questions, the solution of numerical problems using appropriate algorithms, and theoretical questions related to the main concepts, methods and results.

 


Bibliografia
Risorsa bibliografica obbligatoriaAll the course information and material will be available on WeBeep.
Risorsa bibliografica facoltativaR.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network flows. Theory, algorithms and applications, Editore: Prentice Hall, Anno edizione: 1993
Risorsa bibliografica facoltativaM.S. Bazaraa, J.J. Jarvis, H.D. Sherali,, Linear Programming and Network Flows, Editore: John Wiley & Sons, Anno edizione: 2010
Note:

4th Edition

Risorsa bibliografica facoltativaD. Bertsimas, J. Tsitsiklis, Introduction to linear optimization, Editore: Athena Scientific, Anno edizione: 1997
Risorsa bibliografica facoltativaM. Fischetti, Introduction to Mathematical Optimization, Anno edizione: 2019
Risorsa bibliografica facoltativaF. Hillier, G.J. Lieberman, Introduction to Operations Research, Editore: Ninth edition, McGraw-Hill, Anno edizione: 2010
Risorsa bibliografica facoltativaC.H. Papadimitrou, K. Steiglitz, Combinatorial optimization: Algorithms and complexity, Editore: Dover, 1998, Anno edizione: 1998
Note:

First edition: Prentice Hall, 1982


Software utilizzato
Nessun software richiesto

Forme didattiche
Tipo Forma Didattica Ore di attività svolte in aula
(hh:mm)
Ore di studio autonome
(hh:mm)
Lezione
33:00
52:00
Esercitazione
13:00
19:00
Laboratorio Informatico
4:00
4:00
Laboratorio Sperimentale
0:00
0:00
Laboratorio Di Progetto
0:00
0:00
Totale 50:00 75:00

Informazioni in lingua inglese a supporto dell'internazionalizzazione
Insegnamento erogato in lingua Inglese
Disponibilità di materiale didattico/slides in lingua inglese
Disponibilità di libri di testo/bibliografia in lingua inglese
Possibilità di sostenere l'esame in lingua inglese
Disponibilità di supporto didattico in lingua inglese
schedaincarico v. 1.9.1 / 1.9.1
Area Servizi ICT
23/04/2024