PORTALE DELLA DIDATTICA

### Decision making and optimization

01TXCSM

A.A. 2020/21

Course Language

Inglese

Course degree

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

Borrow

01OUVOV

Course structure
Teaching Hours
Lezioni 70
Esercitazioni in aula 10
Teachers
Teacher Status SSD h.Les h.Ex h.Lab h.Tut Years teaching
Tadei Roberto     70 10 0 0 2
Teaching assistant
Context
SSD CFU Activities Area context
MAT/09 8 C - Affini o integrative Attività formative affini o integrative
2020/21
The aim of the course is to provide students with theoretical and operational tools for modeling and solving decision making and optimization problems in data science and engineering. Those tools are powerful mathematical methods (models, algorithms, and software) to solve complex problems involving the minimization (or maximization) of objective functions, subject to given constraints. Starting from real-life optimization problems in data science and engineering, methods and algorithms for solving them will be studied. Particular attention will be paid to the computational complexity of the problems and the required solution methods.
The course aims to provide students with theoretical and operational tools to model and solve decision making and optimization problems in data science and engineering. Those tools are powerful mathematical methods (models, algorithms, and software) able to solve complex problems, which concern the minimization (or maximization) of objective functions, subject to given constraints. Starting from real-life optimization problems in data science and engineering, we will study methods and algorithms for solving them. We will pay particular attention to the computational complexity of the problems and the required solution methods. A section of the course will be devoted to optimization under uncertainty, i.e., where the decision problems have stochastic parameters.
Expected knowledge: Students will study methods and algorithms for solving constrained optimization problems. They will learn how to use existing linear continuous, linear integer and nonlinear solution methods and develop new ones. Particular attention will be given to optimization on graphs and networks. The computational complexity of optimization problems, which affects the choice of suitable solution algorithms, will be studied. The considered solution methods are both exact (Branch and Bound, Cutting Planes, Dynamic Programming) and approximated (heuristics and metaheuristics: tabu search, simulated annealing, genetic algorithms and other). Expected skills: Skills developed by students will consist of the construction of a problem solving mentality. This mentality will be based on mathematical models and related algorithms to solve decision making and optimization problems in data science and engineering.
Expected knowledge: Students will study methods and algorithms for solving constrained optimization problems. They will learn how to use existing linear continuous, linear integer, and nonlinear solution methods. We will give particular attention to optimization on graphs and networks. The computational complexity of optimization problems, which affects the choice of suitable solution algorithms, will be studied. The considered solution methods are both exact (Branch and Bound, Cutting Planes, Dynamic Programming) and approximated (heuristics and metaheuristics: tabu search, simulated annealing, genetic algorithms, and other). Attention will be devoted to methods for solving stochastic problems. Expected skills: Skills developed by students will consist of the construction of a problem-solving mentality. This mentality will be based on mathematical models and related algorithms to solve decision making and optimization problems in data science and engineering.
Prerequisites - Students must know at least one of the following programming languages: C, C++, Java, R, and Python.
None
1. Linear programming: modeling techniques, basic concepts of the Simplex method and duality (10% of the course). 2. Computational complexity: problem classes P, NP, NP-complete, and CoNP-complete (5% of the course). 3. Exact optimization methods: Branch and Bound, Cutting Planes, and Dynamic Programming (20% of the course). 4. Heuristic optimization methods: greedy algorithms, GRASP, Beam Search, meta-heuristics (Tabu Search, Simulated Annealing, Genetic Algorithms, ACO, VNS, RBS), and math-heuristics (30% of the course). 5. Network flow problems: min cost flow and max flow (5% of the course). 6. Decision making under uncertainty: Stochastic Programming with recourse, Measures for Stochastic Programming, Progressive Hedging method (10% of the course). 7. Nonlinear Programming: theoretical conditions for unconstrained and constrained optimization, algorithms for unconstrained and constrained optimization (20%).
1. Linear programming: modeling techniques, basic concepts of the Simplex Method, and duality (10% of the course). 2. Computational complexity: problem classes P, NP, NP-complete, and CoNP-complete (10% of the course). 3. Exact optimization methods: Branch and Bound, Cutting Planes, and Dynamic Programming (20% of the course). 4. Heuristic optimization methods: greedy algorithms, GRASP, Beam Search, meta-heuristics (Tabu Search, Simulated Annealing, Genetic Algorithms, ACO, VNS, RBS), and math-heuristics (30% of the course). 5. Decision making under uncertainty: Stochastic Programming with recourse, Measures for Stochastic Programming, Progressive Hedging method (10% of the course). 6. Nonlinear Programming: theoretical conditions for unconstrained and constrained optimization, algorithms for unconstrained and constrained optimization (20%).
The course integrates hours of teaching and hours of practice, to the extent of about 60% and 40% of the course, respectively. Practice is carried out in the classroom and follows the lecture topics. In the laboratory LADISPE http://www.ladispe.polito.it/ up-to-date optimization solvers to solve real-size problems are available to the students. Instructions for their use will be provided in the classroom. Students are requested to form groups and prepare an assignment during the course. The assignment consists of developing a heuristic and related software for solving a given real-life optimization problem. The assignment results will be presented by each group to the whole class at the end of the course. Student who belong to the same group may work together using long distance communication tools (i.e. Skype, email etc.), so that also working or non-attending students can prepare the assignment. Moreover, it is not necessary that the final presentation of the assignment results is given by the whole group (at least half of the group is enough).
The course uses a teaching and learning model supported by digital content. The work pattern is reversed compared to traditional methods. This model is known as the Peer Instruction Flipped Classroom. In the Peer Instruction Flipped Classroom model, there are two steps. The first step consists of autonomous learning by each student, through the available video lessons of the course and other material available on the course portal, online or on paper. The second step provides that the hours of lessons are used to carry out teaching that is strongly oriented towards understanding and deepening the knowledge previously learned, where the collaboration and cooperation of the students are particularly important aspects. The students, organized in groups, discuss the conceptual knots learned in the first moment of study during the lesson. This debate is based on a series of slides prepared by each group on the topics studied. The teacher moderates the discussion. In practice, after some initial introductory lessons to the course that are held by the teacher, all students are subdivided into groups. Each group is assigned, about two weeks in advance, a topic of the course to be studied and then presented to the other students. Most of the lesson hours will be divided into the following three phases: a. At the beginning of the lesson, a question is asked to all students on the topic of the lesson itself. The lesson topic must have been seen in advance by all students. To answer this question, students can use the academic material available. Students have 15 minutes to give their answers. b. The group to which the current subject has been assigned presents, using slides, a lesson to the remaining students lasting about 30 minutes. In this lesson, students must, above all, highlight the aspects they found most problematic. At the end of the group lesson, the debate opens between the group and the remaining students, animated and moderated by the teacher. c. In the final part of the lesson, the teacher clarifies any unclear points, delves into some important concepts of the topic, and wrap-up.
R. Tadei, F. Della Croce, A. Grosso, Fondamenti di Ottimizzazione, Progetto Leonardo, Editrice Esculapio, Bologna, 2005. R. Tadei, F. Della Croce, Elementi di Ricerca Operativa, Progetto Leonardo, Editrice Esculapio, Bologna, 2010. M. Ghirardi, A. Grosso, G. Perboli, Esercizi Svolti di Ricerca Operativa, Progetto Leonardo, Editrice Esculapio, Bologna, 2009. R.K. Ahuja et al., Network Flows, Prentice Hall, New Jersey, 1993. J.R. Birge, F. Louveaux, Introduction to Stochastic Programming, Springer, 2011. D. J. Luenberger, Linear and Nonlinear Programming, Springer, 3rd ed., 2008. G.L. Nemhauser, L.A. Wolsey, Integer and Combinatorial Optimization, Wiley, 1988. A. Ruszcynski, Nonlinear Optimization, Princeton Univeristy Press, 2006. Other learning material and examples of previous exams will be available on the course website.
Video-lessons of the course available in the course portal. R. Tadei, F. Della Croce, A. Grosso, Fondamenti di Ottimizzazione, Progetto Leonardo, Editrice Esculapio, Bologna, 2005. R. Tadei, F. Della Croce, Elementi di Ricerca Operativa, Progetto Leonardo, Editrice Esculapio, Bologna, 2010. M. Ghirardi, A. Grosso, G. Perboli, Esercizi Svolti di Ricerca Operativa, Progetto Leonardo, Editrice Esculapio, Bologna, 2009. R.K. Ahuja et al., Network Flows, Prentice-Hall, New Jersey, 1993. J.R. Birge, F. Louveaux, Introduction to Stochastic Programming, Springer, 2011. D. J. Luenberger, Linear and Nonlinear Programming, Springer, 3rd ed., 2008. G.L. Nemhauser, L.A. Wolsey, Integer and Combinatorial Optimization, Wiley, 1988. A. Ruszcynski, Nonlinear Optimization, Princeton University Press, 2006. Other learning material and examples of previous exams will be available on the course website and online.
Modalità di esame: Prova scritta tramite PC con l'utilizzo della piattaforma di ateneo;