logo-polimi
Loading...
Funzioni disponibili
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2014/2015
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 (434) INGEGNERIA INFORMATICA* AM088983 - FOUNDATIONS OF OPERATIONS RESEARCH
Ing Ind - Inf (Mag.)(ord. 270) - MI (474) TELECOMMUNICATION ENGINEERING - INGEGNERIA DELLE TELECOMUNICAZIONI* AM096108 - NETWORK DESIGN
088983 - FOUNDATIONS OF OPERATIONS RESEARCH
Ing Ind - Inf (Mag.)(ord. 270) - MI (481) COMPUTER SCIENCE AND ENGINEERING - INGEGNERIA INFORMATICA* AM088983 - FOUNDATIONS OF OPERATIONS RESEARCH

Programma dettagliato e risultati di apprendimento attesi

Aim

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 methods of O.R. The focus is on optimization models and algorithms with important applications in computer science, telecommunications and engineering. During the computer laboratory sessions the students will learn to use the AMPL modeling language and state-of-the-art commercial solvers to tackle optimization problems arising in a variety of fields of application.


Detailed program

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

Algorithms for the optimum spanning tree and shortest path problems (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. Economical interpretation. Sensitivity analysis. Special cases: assignment and transportation problems.

5. Integer Linear Programming (ILP)

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

Time permitting: introduction to heuristic algorithms (greedy and local search).

 


Note Sulla Modalità di valutazione


The examination consists of a written exam and an optional computer laboratory exam.

The written exam, which covers all the material presented in the lectures, exercise and computer laboratory sessions, includes several problems to be solved in class during the allotted time. The maximum grade is 27. The grade remains valid during one academic year (until the September exam session).

The computer laboratory exam is optional and the maximum grade is 4. During each exam session, there will be a single call for the computer laboratory exam.

The final grade is obtained by adding the grades of the written exam and of the computer laboratory exam (if any).


Bibliografia
Risorsa bibliografica obbligatoriaLecture notes and slides (English and Italian) http://home.deib.polimi.it/malucell/didattica/appunti/materiale.html
Risorsa bibliografica obbligatoriaSlides of the lectures, material for the exercise and computer laboratory sessions, past exam questions http://home.deib.polimi.it/amaldi/FOR-14-15.html
Note:

The material will be made available progressively during the semester

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


Mix Forme Didattiche
Tipo Forma Didattica Ore didattiche
lezione
35.0
esercitazione
16.0
laboratorio informatico
10.0
laboratorio sperimentale
0.0
progetto
0.0
laboratorio di progetto
0.0

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.5.0 / 1.5.0
Area Servizi ICT
22/05/2019