PORTALE DELLA DIDATTICA

### Operational research: theory and applications

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.
Modalità di esame: Prova orale obbligatoria; Elaborato progettuale in gruppo;
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.
Exam: Compulsory oral exam; Group project;
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.
Modalità di esame: Prova orale obbligatoria; Elaborato grafico prodotto in gruppo;
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.
Exam: Compulsory oral exam; Group graphic design project;
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.