01QWTBH

A.A. 2020/21

Course Language

Inglese

Course degree

Master of science-level of the Bologna process in Ict For Smart Societies (Ict Per La Societa' Del Futuro) - Torino

Borrow

01QWHBG

Course structure

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

Lezioni | 68 |

Esercitazioni in aula | 12 |

Teachers

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

Leonardi Emilio | Professore Ordinario | ING-INF/03 | 28 | 24 | 0 | 0 | 7 |

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 |

2020/21

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.

On-Line Exam (As long as COVID 19 emergency will force us to on-line exams):
Students are requested to accomplish a group assignment (each group is requested to autononously formulate and solve a specific optimzation problem, using concepts and techniques
learned during the course). A brief oral exam will complete the assessment of individual knowledges/capacities.

Students are requested to accomplish a group assignment (each group is requested to autonomously formulate and solve a specific optimisation problem, using concepts and techniques
learned during the course). A brief on-line oral exam (through the BBB platform) will complete the assessment of individual knowledges/capacities.

Students are requested to accomplish a group assignment (each group is requested to autonomously formulate and solve a specific optimisation problem, using concepts and techniques
learned during the course). A brief oral exam (either on-line or face-to-face) will complete the assessment of individual knowledges/capacities.

Students are requested to accomplish a group assignment (each group is requested to autonomously formulate and solve a specific optimisation problem, using concepts and techniques
learned during the course). A brief oral exam (either on-line through the BBB platform, or face-to-face) will complete the assessment of individual knowledges/capacities.

© Politecnico di Torino

Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY

Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY