Servizi per la didattica

PORTALE DELLA DIDATTICA

01RLDPH

A.A. 2019/20

Course Language

Inglese

Course degree

Master of science-level of the Bologna process in Engineering And Management - Torino

Course structure

Teaching | Hours |
---|---|

Lezioni | 50 |

Esercitazioni in aula | 30 |

Teachers

Teacher | Status | SSD | h.Les | h.Ex | h.Lab | h.Tut | Years teaching |
---|---|---|---|---|---|---|---|

Della Croce Di Dojola Federico | Professore Ordinario | MAT/09 | 20 | 10 | 0 | 0 | 5 |

Teaching assistant

Context

SSD | CFU | Activities | Area context |
---|---|---|---|

MAT/09 | 8 | D - A scelta dello studente | A scelta dello studente |

2019/20

Quantitative methods seek in building up rational models for the representation of complex problems and in devising the related solution algorithms. Objective of the course is to deepen the student skills on several major topics of operations research with emphasis on computational complexity, combinatorial optimization and multi-criteria analysis.

Quantitative methods seek in building up rational models for the representation of complex problems and in devising the related solution algorithms. Objective of the course is to deepen the student skills on several major topics of operations research with emphasis on computational complexity, combinatorial optimization and multi-criteria analysis. The final aim is to provide students with theoretical and operational tools for modeling and solving real life decision making and optimization problems.

At the end of the course the student must be able to determine the computational complexity of given algorithms, to design exact and heuristic algorithms for real world combinatorial optimization problem, to know methods of multi-criteria analysis and use them in relation to specific decision problem situations.

At the end of the course the student is expected to be able to determine the computational complexity of a given algorithm, to design exact and heuristic approaches for real world combinatorial optimization problems, to master the main multi-criteria analysis approaches and be able to apply them in relation to specific decision problem situations.

Bases of operations research with emphasis on linear programming.

Bases of operations research with emphasis on linear programming.

Computational complexity.
Elements of graph theory.
Combinatorial optimization: exact methods, heuristic approaches, approximation algorithms.
Multi-criteria analysis: introduction to multiobjective optimization (pareto-optimality, solution approaches) and to multicriteria outranking methods, ELECTRE methods for sorting decision problems.

Computational complexity: complexity analysis of polynomial time algorithms with emphasis on basic graph theory algorithms, complexity classes, polynomial time reductions.
Combinatorial optimization: exact approaches with emphasis on search-tree algorithms and dynamic programming, heuristic approaches with emphasis on constructive procedures, neighborhood search, meta-heuristics, evolutionary algorithms, mat-heuristics.
Multi-criteria analysis: introduction to multiobjective optimization (pareto-optimality, solution approaches) and to multicriteria outranking methods, ELECTRE methods for sorting decision problems.

The exercise classes are related to the topics presented in the course. In the laboratories commercial software tools are used to deal with more complex problems.

The exercise classes are related to the topics presented in the course. The flow is such that 2 exercise classes are proposed every 5 teaching classes. Exercise classes are provided both in class and in laboratories. In the laboratories commercial software tools are used to deal with more complex problems.

Slides will be provided directly by the teacher.
Reference textbooks that contain part of the topics presented in the course are among others
• M.R. Garey, D.S. Johnson (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co.
• C.H. Papadimitriou, K. Steiglitz (1982), Combinatorial Optimization. Algorithms and Complexity, Prentice Hall.
• V. Vazirani (2001), Approximation Algorithms, Springer.
• P. Vincke (1992), Multicriteria decision-Aid, Wiley, Chichester.
• L.A. Wolsey (1999), Integer Programming and Combinatorial Optimization, Wiley.

Slides will be provided directly by the instructors.
Reference textbooks that contain part of the topics presented in the course are among others
- M.R. Garey, D.S. Johnson (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co.
- V.Th Paschos (Editor) Concepts of Combinatorial Optimization, 2nd Edition, Wiley-ISTE, 2014.
- P. Vincke (1992), Multicriteria decision-Aid, Wiley, Chichester.
- L.A. Wolsey (1999), Integer Programming and Combinatorial Optimization, Wiley.

Written exam.

The assessment is composed of two parts: the written test (60% of the final grade and the assignment (40% of the final grade). The assignment consists in the development and implementation by the students subdivided into groups of a heuristic procedure for a given combinatorial optimization problem. The assignment foresees also a description (by means of slides) of the proposed procedure including the relevant complexity analysis. The written test covers the multicriteria analysis part and is an open-book exam consisting of numerical exercises plus questions related to the analysis of applications of multicriteria methods. The typical exam duration is 1.5h.

© Politecnico di Torino

Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY

Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY