Ing - Civ (Mag.)(ord. 270) - MI (495) GEOINFORMATICS ENGINEERING - INGEGNERIA GEOINFORMATICA

*

A

ZZZZ

088983 - FOUNDATIONS OF OPERATIONS RESEARCH

Ing Ind - Inf (Mag.)(ord. 270) - MI (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

*

M

ZZZZ

052481 - NETWORK DESIGN

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

A couple of topics will be assigned for independent study prior to sessions devoted to exercises or computer laboratory activities.

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

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