01RLDPH

A.A. 2021/22

Course Language

Inglese

Degree programme(s)

Master of science-level of the Bologna process in Ingegneria Gestionale (Engineering And Management) - Torino

Course structure

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

Lezioni | 50 |

Esercitazioni in aula | 30 |

Lecturers

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

Perboli Guido | Professore Ordinario | MAT/09 | 50 | 0 | 0 | 0 | 1 |

Co-lectuers

Context

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

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

2021/22

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's skills on several major topics of operations management with emphasis on combinatorial optimization, computational complexity and exact/heuristic solution approaches. 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 design exact and/or heuristic solution approaches for real-world combinatorial optimization problems, to determine the computational complexity of a given algorithm and to be able to apply these approaches 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.

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, math-heuristics.
Computational complexity: complexity analysis of polynomial-time algorithms with emphasis on basic graph theory algorithms, complexity classes, polynomial-time reductions, approximation.

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. Some classes will be devoted the development of workgroups through interactive lab-classes with the instructors. Workgroups are such that real-life combinatorial optimization problems provided by the instructors will be approached by means of the methodologies presented in the first part of the course. The output of each workgroup will be the design and the implementation of a solution procedure for the considered real-life problem.

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
- V.Th Paschos (Editor) Concepts of Combinatorial Optimization, 2nd Edition, Wiley-ISTE, 2014.
- L.A. Wolsey (1999), Integer Programming and Combinatorial Optimization, Wiley.
- H. P. Williams, Model building in Mathematical Programming, 4th ed., Wiley, 1999.

...
Written exam.

Gli studenti e le studentesse con disabilità o con Disturbi Specifici di Apprendimento (DSA), oltre alla segnalazione tramite procedura informatizzata, sono invitati a comunicare anche direttamente al/la docente titolare dell'insegnamento, con un preavviso non inferiore ad una settimana dall'avvio della sessione d'esame, gli strumenti compensativi concordati con l'Unità Special Needs, al fine di permettere al/la docente la declinazione più idonea in riferimento alla specifica tipologia di esame.

The assessment is composed by an individual written test, a workgroup covering the solution of a realistic problem and periodical assessments during the course. The groups are made by 3 students at most.
In details, the final grade is computed as follows:
- Individual test (written, 1h, usage of notes, slides and books not allowed): max 11 points, minimum to pass 4 points, usage of notes, slides and books not allowed
- Workgroup (written report to be submitted in the "Elaborati" section of the course website by a deadline given at the beginning of the course, usage of notes, slides and books allowed): max 10 points
- Workgroup presentation (oral presentation, 20 minutes, usage of notes, slides and books not allowed): max 6 points
- Mid-term assessment (written, 2 hours, usage of notes, slides and books allowed): max 2 points
- Review of a scientific paper (written report to be submitted in the "Elaborati" section of the course website by a deadline given at the beginning of the course, usage of notes, slides and books allowed): max 2 points

In addition to the message sent by the online system, students with disabilities or Specific Learning Disorders (SLD) are invited to directly inform the professor in charge of the course about the special arrangements for the exam that have been agreed with the Special Needs Unit. The professor has to be informed at least one week before the beginning of the examination session in order to provide students with the most suitable arrangements for each specific type of exam.

The assessment is composed of two parts: the written test (50% of the final grade) and the assignment (50% 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 is a closed-book exam consisting of numerical exercises plus questions related to the topics presented in the course. The typical written exam duration is approximately 1h.

The assessment is composed by an individual written test, a workgroup covering the solution of a realistic problem and periodical assessments during the course. The groups are made by 3 students at most.
In details, the final grade is computed as follows:
- Individual test (written, 1h, Exam online platform, usage of notes, slides and books not allowed): max 11 points, minimum to pass 4 points, usage of notes, slides and books not allowed
- Workgroup (written report to be submitted in the "Elaborati" section of the course website by a deadline given at the beginning of the course, usage of notes, slides and books allowed): max 10 points
- Workgroup presentation (oral presentation, 20 minutes, video conf, usage of notes, slides and books not allowed): max 6 points
- Mid-term assessment (written, 2 hours, usage of notes, slides and books allowed): max 2 points
- Review of a scientific paper (written report to be submitted by a deadline given at the beginning of the course, usage of notes, slides and books allowed): max 2 points

The assessment is composed of two parts: the written test (50% of the final grade) and the assignment (50% 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 is a closed-book exam consisting of numerical exercises plus questions related to the topics presented in the course. The typical written exam duration is approximately 1h.

The assessment is composed by an individual written test, a workgroup covering the solution of a realistic problem and periodical assessments during the course. The groups are made by 3 students at most.
In details, the final grade is computed as follows:
- Individual test (written, 1h, Exam online platform, usage of notes, slides and books not allowed): max 11 points, minimum to pass 4 points, usage of notes, slides and books not allowed
- Workgroup (written report to be submitted in the "Elaborati" section of the course website by a deadline given at the beginning of the course, usage of notes, slides and books allowed): max 10 points
- Workgroup presentation (oral presentation, 20 minutes, video conf, usage of notes, slides and books not allowed): max 6 points
- Mid-term assessment (written, 2 hours, usage of notes, slides and books allowed): max 2 points
- Review of a scientific paper (written report to be submitted by a deadline given at the beginning of the course, usage of notes, slides and books allowed): max 2 points

© Politecnico di Torino

Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY

Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY