Servizi per la didattica
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
Espandi

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;
The exam takes place with the help of the Exam platform (accessible from the student page, in the "Esami in remoto" section, 30 minutes before the start of the appeal to which you are enrolled), the Virtual Classroom and the Elaborati section (tab accessible from the main web page of the course). Besides, the Respondus software is used to inhibit any software in addition to the browser on the student computer. The exam program and its structure remain unchanged compared to what is written in the Study Manifesto. Furthermore, due to possible complications introduced by the remote mode, the exam difficulty and length are reduced, so that it can be completed in one hour and a half instead of in two hours, as in previous years. The remaining hour, of the two and a half hours available for the exam, will be devoted to perform Phases I and III (see below). Equipment needed • A computer (hereafter PC) equipped with a webcam, microphone, speakers, and internet access [will mainly serve to view the exam text]. The "Respondus LockDown Browser" program must be installed on the PC. The PC must be connected to the power outlet for the duration of the test. • A mobile device, such as a mobile phone or tablet (henceforth CELL), equipped with a camera and internet access [will be used to interface with the teacher and for the final scan/upload of the homework]. An app for creating pdfs from camera images must be installed on the CELL (CamScanner is recommended). The CELL must be connected to the power outlet for the duration of the test. All on-screen notifications must be disabled (e.g., WhatsApp, Telegram, email messages, etc.). • Pen and enough white sheets. The use of any other electronic device, accessory or peripheral (e.g., earphones, headphones, smartwatches, cell phones, additional screens, etc.) is not allowed. The use and consultation of books, notes, or other materials are not allowed. However, the use of pencils, erasers, and rulers is allowed. It is also possible to have something to drink (e.g., a bottle of water). The exam must be carried out in a quiet and adequately lit place in your home, free of other people for the duration of the test. The CELL must be positioned in such a way that a good and full camera frames the student's torso/face and position (hands and sheets). Furthermore, the CELL must not be reachable by the student when sitting at the desk. We recommend finding the best location in advance. Conduct of the test The conduct of the test, lasting a total of two and a half hours, involves the following steps in sequence. PHASE I - Appeal and checks [maximum 40 min] The student connects to the Virtual Classroom through the CELL within the time indicated for the exam, keeping the webcam and microphone temporarily disabled, and awaits the teacher's instructions. The invitation to the Virtual Classroom will be sent 30 minutes before the exam begins. The student also connects to Exam via PC, where the exam topic will be present (but will not be accessible because it is password protected). The teacher starts the registration and carries out the appeal. The student who, for any reason, will not respond to the appeal within 15 minutes of its start will be considered "absent". The teacher then interacts with each student (who will activate the CELL webcam and microphone). The student will be asked to: • show a valid identification document • show the compliance of the workplace and the surrounding environment • position the CELL and stabilize the frame, which must be maintained for the whole duration of the exam. The CELL is muted, and the student sits at the station, waiting for the start of the test. PHASE II - Examination procedure [1 hour and a half] 1. The teacher orally communicates the password to all those present. 2. The student starts the exam (this involves Respondus blocking the browser) and carries out the test. 3. At the end of the time, notified by the teacher, all students immediately stop writing. The student who finishes first must still wait for the deadline. PHASE III - Loading the homework [maximum 20 min] 1. Upon instruction from the teacher, students stop the browser block (Respondus) on the PC and the audio/video streaming on Virtual Classroom from the CELL and access the Virtual Classroom via PC (with webcam and audio-activated). 2. Through the CELL, the student scans his/her assignment and uploads it to the portal in the appropriate "Processed" section (see the upload and format of the assignment). Students are advised to recheck by downloading it to the PC from the "Elaborati" section, that the uploaded file is readable, correct, and complete. If not, delete the old version and upload a new one. 3. The student, satisfied with its uploading, communicates it to the teacher. The teacher makes sure of the delivery and communicates to the student that he/she is free to leave the Virtual Classroom, ending the exam. Students, who for any reason, have not been able to upload their assignment will be considered "withdrawn". Only the parts of the homework delivered will be evaluated. Uploads/cancellations of exams after the end of the exam will not be evaluated. Other important clarifications Homework upload and format Each sheet of the assignment must include the student's family name, name, and registration number. The student must upload ONE SINGLE FILE, in pdf format and named "FamilynameName.pdf", obtained by aggregating the photographs of the different sheets through a particular app (e.g., CamScanner). The behavior to be maintained for the duration of the test • the audio/video streaming both in and out of the CELL must be active; • it is not possible to get up or move away from the position; • it is not possible to contact/communicate with other people outside the teacher; • no one must enter the student's room; • it is not possible to use the CELL except during the initial control or final loading phases of the homework, and only for those operations; • it is not possible to eat. Maximum silence is recommended so as not to disturb other students. Anyone wishing to ask a question during the test can do so by specifying their family ame and name first. Withdrawals A student can withdraw from the exam at any time. In that case, however, the student must have the following behavior: • communicate their decision to the teacher, who will notify the withdrawal. This decision will be permanent; • must remain connected to the Virtual Classroom and comply with the above rules until the end of Phase II. At that point, must not upload any files and can abandon the Virtual Classroom. Infringements The exam is invalidated for anyone, for any reason, who does not comply with even one of the rules above or who is discovered (even later with the aid of the registrations) in behaviors that do not comply with them. If these violations occur during the test, students must withdraw at the request of the teacher, and they must behave as in "Withdrawals". Based on the gravity of the infringement, the teacher may decide whether to communicate this behavior to the appropriate University disciplinary commissions. Special Needs Students who request Special Needs will have 30% more time (therefore, half an hour more) available for the test. In any case, at the end of PHASE II, those students will also temporarily stop writing, so that the teacher can devote himself to the delivery by the other students, and they are not disturbed by these operations. Once the delivery is over, and silence returns, those students can resume their test. Emergencies For any emergency during the exam, students can call the following mobile numbers: Prof. Roberto Tadei 335 6604376 Prof. Daniele Manerba 339 5454453. Honor code At least 48 hours before the start of the exam and not earlier than 7 days from the day of the exam, students enrolled in the exam must upload a file in pdf format on the course portal under "Elaborati", called "SurnameName_codeofhonour.pdf" , containing the form "CODE-OF-HONOR-STATEMENT ON WRITTEN & ORAL EXAMS IN REMOTE MODE", duly completed and signed. Students who do not upload the file within the scheduled time cannot take the exam. Rating As usual, students will receive notification of the test result via the portal. At the same time, the date and time of the vision of the homework will be communicated, which will take place through Virtual Classroom. The registration of the exam will immediately follow the vision of the homework. Students, who wish to reject their mark, even after viewing the assignment, must communicate it by email to Prof. Tadei (roberto.tadei@polito.it) by the date of registration.
Exam: Computer-based written test using the PoliTo platform;
The student's assessment is subdivided into three parts: a. Answers to the questions during lessons: maximum 6/30 (to access the 6 points at least 3/4 of the questions must be answered) b. Group lesson: maximum 6/30 (the grade is the same for all the members of the group) c. Final written test: maximum 21/30. For the written test, the students will be asked, in writing, three 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. The outcome of the written test will be communicated to the students through a notice on the teaching portal. Students can view their written tests 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 21 points will be used for the evaluation of the written test. The exam is passed if the sum of the grade of the answers (item a.), group lesson (item b.), and written test (item c.) is greater than or equal to 18/30. The honors will be awarded if that sum is greater or equal to 32/30. The written test takes place with the help of the Exam platform (accessible from the student page, in the "Esami in remoto" section, 30 minutes before the start of the appeal to which you are enrolled), the Virtual Classroom and the Elaborati section (tab accessible from the main web page of the course). Besides, the Respondus software is used to inhibit any software in addition to the browser on the student computer. The exam program and its structure remain unchanged compared to what is written in the Study Manifesto. Furthermore, due to possible complications introduced by the remote mode, the exam difficulty and length are reduced, so that it can be completed in one hour and a half instead of in two hours, as in previous years. The remaining hour, of the two and a half hours available for the exam, will be devoted to performing Phases I and III (see below). Equipment needed • A computer (hereafter PC) equipped with a webcam, microphone, speakers, and internet access [will mainly serve to view the exam text]. The "Respondus LockDown Browser" program must be installed on the PC. The PC must be connected to the power outlet for the duration of the test. • A mobile device, such as a mobile phone or tablet (henceforth CELL), equipped with a camera and internet access [will be used to interface with the teacher and for the final scan/upload of the homework]. An app for creating pdfs from camera images must be installed on the CELL (CamScanner is recommended). The CELL must be connected to the power outlet for the duration of the test. All on-screen notifications must be disabled (e.g., WhatsApp, Telegram, email messages, etc.). • Pen and enough white sheets. The use of any other electronic device, accessory or peripheral (e.g., earphones, headphones, smartwatches, cell phones, additional screens, etc.) is not allowed. The use and consultation of books, notes, or other materials are not allowed. However, the use of pencils, erasers, and rulers is permitted. It is also possible to have something to drink (e.g., a bottle of water). The exam must be carried out in a quiet and adequately lit place in your home, free of other people for the duration of the test. The CELL must be positioned in such a way that a good and full camera frames the student's torso/face and position (hands and sheets). Furthermore, the CELL must not be reachable by the student when sitting at the desk. We recommend finding the best location in advance. Conduct of the test The conduct of the test, lasting a total of two and a half hours, involves the following steps in sequence. PHASE I - Appeal and checks [maximum 40 min] The student connects to the Virtual Classroom through the CELL within the time indicated for the exam, keeping the webcam and microphone temporarily disabled, and awaits the teacher's instructions. The invitation to the Virtual Classroom will be sent 30 minutes before the exam begins. The student also connects to Exam via PC, where the exam topic will be present (but will not be accessible because it is password protected). The teacher starts the registration and carries out the appeal. The student who, for any reason, will not respond to the appeal within 15 minutes of its start will be considered "absent". The teacher then interacts with each student (who will activate the CELL webcam and microphone). The student will be asked to: • show a valid identification document • show the compliance of the workplace and the surrounding environment • position the CELL and stabilize the frame, which must be maintained for the whole duration of the exam. The CELL is muted, and the student sits at the station, waiting for the start of the test. PHASE II - Examination procedure [1 hour and a half] 1. The teacher orally communicates the password to all those present. 2. The student starts the exam (this involves Respondus blocking the browser) and carries out the test. 3. At the end of the time, notified by the teacher, all students immediately stop writing. The student who finishes first must still wait for the deadline. PHASE III - Loading the homework [maximum 20 min] 1. Upon instruction from the teacher, students stop the browser block (Respondus) on the PC and the audio/video streaming on Virtual Classroom from the CELL and access the Virtual Classroom via PC (with webcam and audio-activated). 2. Through the CELL, the student scans his/her assignment and uploads it to the portal in the appropriate "Elaborati" section (see the upload and format of the assignment). Students are advised to recheck by downloading it to the PC from the "Elaborati" section, that the uploaded file is readable, correct, and complete. If not, delete the old version and upload a new one. 3. The student, satisfied with its uploading, communicates it to the teacher. The teacher makes sure of the delivery and talks to the student that he/she is free to leave the Virtual Classroom, ending the exam. Students, who for any reason, have not been able to upload their assignment will be considered "withdrawn". Only the parts of the homework delivered will be evaluated. Uploads/cancellations of assignments after the end of the exam will not be evaluated. Other important clarifications Homework upload and format Each sheet of the assignment must include the student's family name, name, and registration number. The student must upload ONE SINGLE FILE, in pdf format and named "FamilynameName.pdf", obtained by aggregating the photographs of the different sheets through a particular app (e.g., CamScanner). The behavior to be maintained for the duration of the test • the audio/video streaming both in and out of the CELL must be active; • it is not possible to get up or move away from the position; • it is not possible to contact/communicate with other people outside the teacher; • no one must enter the student's room; • it is not possible to use the CELL except during the initial control or final loading phases of the homework, and only for those operations; • it is not possible to eat. Maximum silence is recommended so as not to disturb other students. Anyone wishing to ask a question during the test can do so by specifying their family name and name first. Withdrawals A student can withdraw from the exam at any time. In that case, however, the student must have the following behavior: • communicate their decision to the teacher, who will notify the withdrawal. This decision will be permanent; • must remain connected to the Virtual Classroom and comply with the above rules until the end of Phase II. At that point, the student must not upload any files and can abandon the Virtual Classroom. Infringements The exam is invalidated for anyone, for any reason, who does not comply with even one of the rules above or who is discovered (even later with the aid of the registrations) in behaviors that do not comply with them. If these violations occur during the test, students must withdraw at the request of the teacher, and they must behave as in "Withdrawals". Based on the gravity of the infringement, the teacher may decide whether to communicate this behavior to the appropriate University disciplinary commissions. Special Needs Students who request Special Needs will have 30% more time (therefore, half an hour more) available for the test. In any case, at the end of PHASE II, those students will also temporarily stop writing, so that the teacher can devote himself to the delivery by the other students, and they are not disturbed by these operations. Once the delivery is over, and silence returns, those students can resume their test. Emergencies For any emergency during the exam, students can call the following mobile numbers: Prof. Roberto Tadei 335 6604376 Prof. Daniele Manerba 339 5454453. Honor code At least 48 hours before the start of the exam and not earlier than 7 days from the day of the exam, students enrolled in the exam must upload a file in pdf format on the course portal under "Elaborati", called "SurnameName_codeofhonour.pdf" , containing the form "CODE-OF-HONOR-STATEMENT ON WRITTEN & ORAL EXAMS IN REMOTE MODE", duly completed and signed. Students who do not upload the file within the scheduled time cannot take the exam. Rating As usual, students will receive notification of the test result via the portal. At the same time, the date and time of the vision of the homework will be communicated, which will take place through Virtual Classroom. The registration of the exam will immediately follow the vision of the homework. Students, who wish to reject their mark, even after viewing the assignment, must communicate it by email to Prof. Tadei (roberto.tadei@polito.it) by the date of registration.
Modalità di esame: Prova scritta (in aula); Prova scritta tramite PC con l'utilizzo della piattaforma di ateneo;
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.
Exam: Written test; Computer-based written test using the PoliTo platform;
Online exam: See "Assessment and grading criteria for online exam". Onsite exam: As for the online exam, where the exam test is done in the classroom instead of online.
Esporta Word


© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
Contatti