PORTALE DELLA DIDATTICA

### Decision making and optimization

01TXCSM

A.A. 2021/22

2021/22

Decision making and optimization

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.

Decision making and optimization

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. Stemming from real-life optimization problems in data science and engineering, we will study suitable methods and algorithms for their solution. Particular attention will be devoted to the computational complexity analysis of the considered problems.

Decision making and optimization

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.

Decision making and optimization

Expected knowledge: Students will study methods and algorithms for solving constrained optimization problems. They will learn how to use existing continuous and integer mathematical programming 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 (e.g. Branch and Bound, Branch and Cut, Dynamic Programming) and heuristic (constructive approaches and metaheuristics such as tabu search, simulated annealing, variable neighborhood search and others). Attention will be devoted to approximation algorithms with performance guarantee. Expected skills: Students are expected to develop a problem-solving mindset and skills in mastering mathematical models and related algorithms for the solution of decision making and optimization problems in data science and engineering.

Decision making and optimization

Prerequisites - Students must know at least one of the following programming languages: C, C++, Java, R, and Python.

Decision making and optimization

None

Decision making and optimization

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

Decision making and optimization

1. Linear programming: modeling techniques, basic properties of continuous linear programming and the Simplex Method. 2. Computational complexity: problem classes P, NP, NP-complete, NP-Hard; polynomial time reductions. 3. Exact optimization methods: Branch and Bound, Branch and Cut, Dynamic Programming. 4. Heuristic optimization methods: greedy algorithms, GRASP, Beam Search, meta-heuristics (Tabu Search, Simulated Annealing, Genetic Algorithms, VNS, RBS), and math-heuristics. 5. Approximation: polynomial and fully polynomial time approximation schemes, inapproximability, algorithms achieving constant approximation ratios. 6. Multiobjective optimization: non dominated solutions, goal programming, epsilon-constrained approach.

Decision making and optimization

Decision making and optimization

Decision making and optimization

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

Decision making and optimization

The course foresees teaching and exercises classes. Typically an exercise class is foreseen every two teaching classes. In the last week a mockup test is foreseen to allow the students a self-evaluation of their competences on the course topics.

Decision making and optimization

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.

Decision making and optimization

Video-lessons of the course available in the course website. Slides and other learning material provided by the instructor. Below a list of relevant books on the course topics. R.K. Ahuja, T. L. Magnanti, J. B. Orlin, Network Flows, Prentice-Hall, New Jersey, 1993. D. J. Luenberger, Linear and Nonlinear Programming, Springer, 3rd ed., 2008. G.L. Nemhauser, L.A. Wolsey, Integer and Combinatorial Optimization, Wiley, 1999. G. Ausiello, A. Marchetti-Spaccamela, P. Crescenzi, G. Gambosi,M. Protasi, V. Kann, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer, 2003, 2nd edition. V. Vazirani, Approximation algorithms, Springer, 2003. Examples of previous exams will be available on the course website and online.

Decision making and optimization

Modalità di esame: Prova scritta (in aula);

Decision making and optimization

The assessment is composed of two parts: the written test (2/3 of the final grade, i.e. up to 20/30) and the assignment (1/3 of the final grade, i.e. up to 10/30). The assignment consists of developing a heuristic and related software (in C, C++, or preferably in Java or Python) to solve a given real-life optimization problem. It will be developed by students subdivided into groups. The assignment will start the second week of the course. The results of the assignment will be presented by each group to the entire class and evaluated at the end of the course. The outcome of the assignment will be communicated within the date of the first exam call. A scale of 0 to 10 points will be used for the evaluation of the assignment. An assignment bonus is foreseen for the best groups. The validity of the assignment evaluation lasts for the current academic year. For the written test, the students will be asked, in writing, 3 theoretical and practical questions concerning specific topics of the whole program. The first question will consist of the construction of a mathematical model related to a given optimization problem. The candidate's level of preparation will be assessed in terms of achieving the following objectives (consistently with the expected learning outcomes): - knowledge of the optimization modeling techniques; - capacity to derive the main optimization algorithms. The written test has a duration of 1.5 hours. During the written test it will not be possible to consult texts, lecture notes, and forms. Furthermore, multimedia devices with access to the web (for example, smartphones, smartwatches, and tablets) are not allowed in the classroom. The outcome of the written test will be communicated to the students through a notice on the teaching portal. Students can view their written test and its assessment during a general meeting. The date of this meeting will be communicated to the students through a notice on the teaching portal in conjunction with the publication of the results of the written test. A scale of 0 to 22 points will be used for the evaluation of the written test. The exam is passed if the sum of the grade of the written test and the assignment is greater than or equal to 18/30. The honors will be awarded if that sum is 32/30.

Decision making and optimization

Exam: Written test;

Decision making and optimization

The assessment is composed of a written test The students will have to answer to 5-6 theoretical and practical questions concerning specific topics of the whole program. The candidate's competences will be assessed in terms of achieving the following objectives (consistently with the expected learning outcomes): - knowledge of the optimization modeling techniques; - capability in deriving the main optimization algorithms. The written test lasts approximately 1.5 hours. During the written test it will not be possible to consult texts, lecture notes and forms. Multimedia devices with access to the web (e.g., smartphones, smartwatches, and tablets) are not allowed in the classroom. The outcome of the written test will be communicated to the students through a notice on the course website. Students can view their written test and its assessment during a general meeting. The date of this meeting will be communicated to the students through a notice on the course website together with the publication of the written test grades. A scale of up to 33 points will be used for the evaluation of the written exam. The exam is passed in case of a mark greater than or equal to 18/30. The honors will be awarded in case of a mark greater than or equal to 32/30.

Decision making and optimization

Modalità di esame: Prova scritta a risposta aperta o chiusa tramite PC con l'utilizzo della piattaforma di ateneo Exam integrata con strumenti di proctoring (Respondus);

Decision making and optimization

Decision making and optimization

Exam: Computer-based written test with open-ended questions or multiple-choice questions using the Exam platform and proctoring tools (Respondus);

Decision making and optimization

Decision making and optimization

Modalità di esame: Prova scritta (in aula); Prova scritta a risposta aperta o chiusa tramite PC con l'utilizzo della piattaforma di ateneo Exam integrata con strumenti di proctoring (Respondus);

Decision making and optimization

See "Assessment and grading criteria up to 2019/20 a.y." for the onsite exam. See "Assessment and grading criteria for online exam" for the online exam.

Decision making and optimization

Exam: Written test; Computer-based written test with open-ended questions or multiple-choice questions using the Exam platform and proctoring tools (Respondus);

Decision making and optimization

Online exam: See "Assessment and grading criteria for online exam". Onsite exam: As for the online exam, where the exam takes place in a classroom.