Servizi per la didattica
PORTALE DELLA DIDATTICA

Optimization methods and algorithms

01OUVOV, 01OUVNG

A.A. 2018/19

Course Language

English

Course degree

Master of science-level of the Bologna process in Computer Engineering - Torino
Master of science-level of the Bologna process in Mathematical Engineering - Torino

Course structure
Teaching Hours
Lezioni 45
Esercitazioni in aula 15
Teachers
Teacher Status SSD h.Les h.Ex h.Lab h.Tut Years teaching
Tadei Roberto - Corso 1 Professore Ordinario MAT/09 45 0 0 0 7
Tadei Roberto - Corso 2 Professore Ordinario MAT/09 45 0 0 0 7
Teaching assistant
Espandi

Context
SSD CFU Activities Area context
MAT/09 6 C - Affini o integrative Attività formative affini o integrative
2018/19
The course is given in English. The aim of the course is to provide students with theoretical and operational tools for modeling and solving real-life optimization problems in information and communication engineering. The optimization provides powerful mathematical methods (models, algorithms, and software) for solving complex problems involving the minimization (or maximization) of objective functions, subject to given constraints. Starting from real-life optimization problems, such as the design of computer or telecommunication networks, data base management, and network flows, methods and algorithms for solving those optimization problems will be studied. Particular attention will be paid to the computational complexity of the problems and the required solution methods.
The course is given in English. The aim of the course is to provide students with theoretical and operational tools for modeling and solving real-life optimization problems in information and communication engineering. The optimization provides powerful mathematical methods (models, algorithms, and software) for solving complex problems involving the minimization (or maximization) of objective functions, subject to given constraints. Starting from real-life optimization problems, such as the design of computer or telecommunication networks, data base management, and network flows, methods and algorithms for solving those optimization problems will be studied. Particular attention will be paid to the computational complexity of the problems and the required solution methods.
Expected knowledge: Students will study methods and algorithms for solving constrained optimization problems. They will learn how to use linear continuous and integer programming methods and develop the most suitable solution methods to solve those problems. Particular attention will be given to graph problems such as the min cost flow problem, the max flow problem, and the min cut problem. The computational complexity of optimization problems, which affects the choice of suitable solving algorithms, will be studied. The considered solution methods are both exact (Branch and Bound, Dynamic Programming) and approximated (heuristics and metaheuristics: tabu search, simulated annealing, genetic algorithms and others). Expected skills: The skills developed by students will consist of the construction of mathematical models and related algorithms for solving optimization problems of information and communication engineering, such as flows on networks, network design, location, scheduling, and routing.
Expected knowledge: Students will study methods and algorithms for solving constrained optimization problems. They will learn how to use linear continuous and integer programming methods and develop the most suitable solution methods to solve those problems. Particular attention will be given to graph problems such as the min cost flow problem, the max flow problem, and the min cut problem. The computational complexity of optimization problems, which affects the choice of suitable solving algorithms, will be studied. The considered solution methods are both exact (Branch and Bound, Dynamic Programming) and approximated (heuristics and metaheuristics: tabu search, simulated annealing, genetic algorithms and others). Expected skills: The skills developed by students will consist of the construction of mathematical models and related algorithms for solving optimization problems of information and communication engineering, such as flows on networks, network design, location, scheduling, and routing.
Prerequisites - Students must know at least one of the following programming languages: C, C++, Java, and Python.
Prerequisites - Students must know at least one of the following programming languages: C, C++, Java, and Python.
-1. Linear programming: modeling techniques, basic concepts of the Simplex method (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 and Dynamic Programming (25% 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 (45% of the course). 5. Network flow problems: min cost flow and max flow (10% of the course).
-1. Linear programming: modeling techniques, basic concepts of the Simplex method (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 and Dynamic Programming (25% 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 (45% of the course). 5. Network flow problems: min cost flow and max flow (10% of the course).
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 (in C, C++, or preferably in Java or Python) 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 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 (in C, C++, or preferably in Java or Python) 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).
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 di Ricerca Operativa, Progetto Leonardo, Editrice Esculapio, Bologna, 2009. R.K. Ahuja et al., 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 Programming, Wiley, 1998. Other learning material and examples of previous exams will be available on the course website.
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 di Ricerca Operativa, Progetto Leonardo, Editrice Esculapio, Bologna, 2009. R.K. Ahuja et al., 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 Programming, Wiley, 1998. Other learning material and examples of previous exams will be available on the course website.
Modalità di esame: prova scritta; progetto di gruppo;
The assessment is composed by 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) for solving a given real-life optimization problem. It will be developed by students organized in groups. It will start the second week of the course. The outcome will be presented by each group to the entire class and evaluated at the end of the course. For the written test, the students will be asked, in writing, 3 quantitative and qualitative questions concerning specific topics in 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 for specification of 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 the task and its assessment during a general meeting whose date will be fixed from time to time. The date of the 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. The outcome of the assignment will be communicated within the date of the first exam call. The validity of the assignment evaluation lasts for the current academic year. A scale of 0 to 22 points will be used for the evaluation of the written test. 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 exam is passed if the sum of the vote in 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.
Exam: written test; group project;
The assessment is composed by 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) for solving a given real-life optimization problem. It will be developed by students organized in groups. It will start the second week of the course. The outcome will be presented by each group to the entire class and evaluated at the end of the course. For the written test, the students will be asked, in writing, 3 quantitative and qualitative questions concerning specific topics in 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 for specification of 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 the task and its assessment during a general meeting whose date will be fixed from time to time. The date of the 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. The outcome of the assignment will be communicated within the date of the first exam call. The validity of the assignment evaluation lasts for the current academic year. A scale of 0 to 22 points will be used for the evaluation of the written test. 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 exam is passed if the sum of the vote in 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.


© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
m@il