Servizi per la didattica

PORTALE DELLA DIDATTICA

01QWTBH

A.A. 2019/20

Course Language

Inglese

Course degree

Master of science-level of the Bologna process in Ict For Smart Societies - Torino

Borrow

01QWHBG

Course structure

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

Lezioni | 60 |

Esercitazioni in aula | 5 |

Esercitazioni in laboratorio | 15 |

Teachers

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

Leonardi Emilio
Operational research |
Professore Ordinario | ING-INF/03 | 25 | 0 | 15 | 0 | 5 |

Leonardi Emilio | Professore Ordinario | ING-INF/03 | 25 | 0 | 15 | 0 | 5 |

Teaching assistant

Context

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

ING-INF/03 MAT/09 |
4 4 |
B - Caratterizzanti C - Affini o integrative |
Ingegneria delle telecomunicazioni Attività formative affini o integrative |

2019/20

The main aim of the course is to provide students with theoretical and operational tools for modeling and solving Operations Research and Optimization problems usually met in the design and the management of complex infrastructures such as computer networks. Operations Research deals with the mathematical modeling of complex problems and related solution algorithms. Modeling the problem means to write it in terms of mathematical programming, i.e. identifying an objective function (which has to be minimized or maximized) and a set of constraints to be satisfied. Solving the problem means to find a solution which maximizes or minimizes the objective function without violating the constraints, and this is accomplished by using appropriate solution algorithms. Most recent solution algorithms will be discussed for each computer network design/management problem presented in the course.
During the course, students will be asked to practice the presented methodologies in laboratories.

The main aim of the course is to provide students with theoretical and operational tools for modeling and solving Operations Research and Optimization problems usually met in the design and the management of complex infrastructures such as computer networks. Operations Research deals with the mathematical modeling of complex problems and related solution algorithms. Modeling the problem means to write it in terms of mathematical programming, i.e. identifying an objective function (which has to be minimized or maximized) and a set of constraints to be satisfied. Solving the problem means to find a solution which maximizes or minimizes the objective function without violating the constraints, and this is accomplished by using appropriate solution algorithms. Most recent solution algorithms will be discussed for each computer network design/management problem presented in the course.
During the course, students will be asked to practice the presented methodologies in laboratories.

The course aims at giving the students the correct methodologies to solve optimization problems. Linear Programming (LP) and Integer Linear Programming (ILP) will be the basic instruments to formulate constrained optimization problems.
To solve the problems students will learn to use several different methodologies,
considering both exact approaches and approximated approaches. The choice of the proper methodology will enhance students’ ability in making judgments. Particular attention will be devoted to local search heuristics as well as meta-heuristics and math-heuristics.
In addition, flow problems in graphs will be analyzed. Finally, typical problems that are met when designing a computer network, such as: infrastructure capacity planning, the optimization of the set of routes, the definition of the maximum flow a network can support will be considered. Modeling and solving practical design problems
will help students in increasing their ability in applying the acquired knowledge.
In a nutshell the student will learn how:
ì) to formulate LP and ILP optimization problems;
ii) to define and implement heuristic and meta-heuristic algorithms;
iii) to select the most suited optimization technique;
iv) to model and solve flow problems on networks.

The course aims at giving the students the correct methodologies to solve optimization problems. Linear Programming (LP) and Integer Linear Programming (ILP) will be the basic instruments to formulate constrained optimization problems.
To solve the problems students will learn to use several different methodologies,
considering both exact approaches and approximated approaches. The choice of the proper methodology will enhance students’ ability in making judgments. Particular attention will be devoted to local search heuristics as well as meta-heuristics and math-heuristics.
In addition, flow problems in graphs will be analyzed. Finally, typical problems that are met when designing a computer network, such as: infrastructure capacity planning, the optimization of the set of routes, the definition of the maximum flow a network can support will be considered. Modeling and solving practical design problems
will help students in increasing their ability in applying the acquired knowledge.
In a nutshell the student will learn how:
ì) to formulate LP and ILP optimization problems;
ii) to define and implement heuristic and meta-heuristic algorithms;
iii) to select the most suited optimization technique;
iv) to model and solve flow problems on networks.

Students must have a good mathematical background and a good knowledge of the different constraints imposed by networking technologies. Students must have a good knowledge of C programming language.

Students must have a good mathematical background and a good knowledge of the different constraints imposed by networking technologies. Students must have a good knowledge of C programming language.

• How to build mathematical models from real-life problems (9h)
• Computational complexity of optimization problems (4,5 h)
• Elements of network flows (4,5 h)
• Local search heuristics (3h)
• Meta-heuristics: Simulated Annealing, Genetic Algorithms, Tabu Search and others (7 h)
• Application to networks: (15 h)
o Routing problems (5 h)
o Topology and capacity planning problems in transport networks (10 h)

• How to build mathematical models from real-life problems (9h)
• Computational complexity of optimization problems (4,5 h)
• Elements of network flows (4,5 h)
• Local search heuristics (3h)
• Meta-heuristics: Simulated Annealing, Genetic Algorithms, Tabu Search and others (7 h)
• Application to networks: (15 h)
o Routing problems (5 h)
o Topology and capacity planning problems in transport networks (10 h)

Class exercise will be proposed and solved on the various part of the program.
Students will use the computer laboratory facilities to implement some of the proposed algorithms and run simulations. Software libraries will be offered to students to help them in implementing the proposed algorithms. Laboratories will require a good knowledge of C programming language.

Class exercise will be proposed and solved on the various part of the program.
Students will use the computer laboratory facilities to implement some of the proposed algorithms and run simulations. Software libraries will be offered to students to help them in implementing the proposed algorithms. Laboratories will require a good knowledge of C programming language.

The material related to this course will be made available in electronic format through the didattica Web site. Students will receive also some research papers that describe selected networking problems and provide some solutions.
The following books are suggested:
• R. Tadei, F. Della Croce, Elementi di Ricerca Operativa, Progetto Leonardo, Editrice Esculapio, Bologna, 2010.
• R. Tadei, F. Della Croce, A. Grosso, Fondamenti di Ottimizzazione, Progetto Leonardo, Editrice Esculapio, Bologna, 2005.
• M. Ghirardi, A. Grosso, G. Perboli, Esercizi di Ricerca Operativa, Progetto Leonardo, Editrice Esculapio, Bologna, 2009.
• D. J. Luenberger, Linear and Nonlinear Programming, Springer, 3rd ed., 2008.
• M.S. Bazaraa, J.J. Jarvis. Linear Programming and Network Flows, Wiley, 3rd ed., 2005.
• R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows, Prentice Hall, 1993.
• G.L. Nemhauser, L.A. Wolsey, Integer Programming, Wiley, 1998.

The material related to this course will be made available in electronic format through the didattica Web site. Students will receive also some research papers that describe selected networking problems and provide some solutions.
The following books are suggested:
• R. Tadei, F. Della Croce, Elementi di Ricerca Operativa, Progetto Leonardo, Editrice Esculapio, Bologna, 2010.
• R. Tadei, F. Della Croce, A. Grosso, Fondamenti di Ottimizzazione, Progetto Leonardo, Editrice Esculapio, Bologna, 2005.
• M. Ghirardi, A. Grosso, G. Perboli, Esercizi di Ricerca Operativa, Progetto Leonardo, Editrice Esculapio, Bologna, 2009.
• D. J. Luenberger, Linear and Nonlinear Programming, Springer, 3rd ed., 2008.
• M.S. Bazaraa, J.J. Jarvis. Linear Programming and Network Flows, Wiley, 3rd ed., 2005.
• R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows, Prentice Hall, 1993.
• G.L. Nemhauser, L.A. Wolsey, Integer Programming, Wiley, 1998.

The exam will be written, and it will consists of two parts.
Part 1 – theory – in which students will be asked to answer 3-4 questions or exercises dealing with the theoretical part of the course. This part permits to evaluate the student's level of mastering of concepts and methodologies.
Part 2 – application to networking – in which students will be asked to answer 2-3 (open) questions or exercises dealing with the application part.. This part permits to evaluate the ability of the student to apply the OR methodologies to solve specific problems.
No books and notes are allowed during the written exam, whose duration is about 1.5 h.
Students will have to deliver a written report on their laboratory activities. The report will be per group of 3/4 students each. The report must be delivered before the written exam,..
The final grade (on a scale of 30) is obtained as a weighed average of the marks of each individual parts. The weight of each written parts is 0.35. The weight of the lab report is 0.30.

The exam will be written, and it will consists of two parts.
Part 1 – theory – in which students will be asked to answer 3-4 questions or exercises dealing with the theoretical part of the course. This part permits to evaluate the student's level of mastering of concepts and methodologies.
Part 2 – application to networking – in which students will be asked to answer 2-3 (open) questions or exercises dealing with the application part.. This part permits to evaluate the ability of the student to apply the OR methodologies to solve specific problems.
No books and notes are allowed during the written exam, whose duration is about 1.5 h.
Students will have to deliver a written report on their laboratory activities. The report will be per group of 3/4 students each. The report must be delivered before the written exam,..
The final grade (on a scale of 30) is obtained as a weighed average of the marks of each individual parts. The weight of each written parts is 0.35. The weight of the lab report is 0.30.

© Politecnico di Torino

Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY

Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY