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

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

- the concepts of recognition problems and reduction
- the definitions of the problem classes NP, P, and NP-complete
- the implications for a computational problem to be NP-complete or NP-hard.

 

Applying knowledge and understanding

 

The students will be able to:

- build optimization models starting from the decision problem descriptions, solve them using a mathematical modeling language 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.  

3. Basics of computational complexity

Recognition problems, classes P and NP, NP-complete and NP-hard problems. Traveling salesman problem, Integer Linear Programming and other examples.

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

5. 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: introduction to heuristic algorithms (greedy and local search).

 


Prerequisiti

Basic knowledge of Multivariate Calculus and Linear Algebra.


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 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 obbligatoriaSlides of the lectures, material for the exercise and computer laboratory sessions, past exam questions http://home.deib.polimi.it/amaldi/FOR-18-19.html
Note:

The material will be made available progressively during the semester

Risorsa bibliografica obbligatoriaLecture notes and slides (English and Italian) http://home.deib.polimi.it/malucell/didattica/appunti/materiale.html
Risorsa bibliografica obbligatoriaExercises from past exams (English and Italian) http://home.deib.polimi.it/malucell/didattica/esercizi/esercizi.html
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 facoltativaD. Bertsimas, J. Tsitsiklis, Introduction to linear optimization, Editore: Athena Scientific, Anno edizione: 1997
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


Forme didattiche
Tipo Forma Didattica Ore di attività svolte in aula
(hh:mm)
Ore di studio autonome
(hh:mm)
Lezione
34:00
51:00
Esercitazione
14:00
21:00
Laboratorio Informatico
4:00
1:00
Laboratorio Sperimentale
0:00
0:00
Laboratorio Di Progetto
0:00
0:00
Totale 52:00 73: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.6.1 / 1.6.1
Area Servizi ICT
20/11/2019