Ing - Civ (Mag.)(ord. 270) - MI (495) GEOINFORMATICS ENGINEERING - INGEGNERIA GEOINFORMATICA
*
A
ZZZZ
088983 - FOUNDATIONS OF OPERATIONS RESEARCH
Ing Ind - Inf (Mag.)(ord. 270) - CR (263) MUSIC AND ACOUSTIC ENGINEERING
*
M
ZZZZ
088983 - FOUNDATIONS OF OPERATIONS RESEARCH
Ing Ind - Inf (Mag.)(ord. 270) - MI (471) BIOMEDICAL ENGINEERING - INGEGNERIA BIOMEDICA
*
M
ZZZZ
088983 - FOUNDATIONS OF OPERATIONS RESEARCH
Ing Ind - Inf (Mag.)(ord. 270) - MI (474) TELECOMMUNICATION ENGINEERING - INGEGNERIA DELLE TELECOMUNICAZIONI
*
A
ZZZZ
052481 - NETWORK DESIGN
M
ZZZZ
088983 - FOUNDATIONS OF OPERATIONS RESEARCH
Ing Ind - Inf (Mag.)(ord. 270) - MI (481) COMPUTER SCIENCE AND ENGINEERING - INGEGNERIA INFORMATICA
*
M
ZZZZ
088983 - 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.
The material will be made available progressively during the semester
Lecture notes and slides (English and Italian)http://home.deib.polimi.it/malucell/didattica/appunti/materiale.htmlExercises from past exams (English and Italian)http://home.deib.polimi.it/malucell/didattica/esercizi/esercizi.htmlR.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network flows. Theory, algorithms and applications, Editore: Prentice Hall, Anno edizione: 1993
D. Bertsimas, J. Tsitsiklis, Introduction to linear optimization, Editore: Athena Scientific, Anno edizione: 1997
F. Hillier, G.J. Lieberman, Introduction to Operations Research, Editore: Ninth edition, McGraw-Hill, Anno edizione: 2010
C.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
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
Inglese