PORTALE DELLA DIDATTICA

### Operational research: theory and applications

01QWTBH

A.A. 2022/23

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

Course structure
Teaching Hours
Lezioni 68
Esercitazioni in aula 12
Teachers
Teacher Status SSD h.Les h.Ex h.Lab h.Tut Years teaching
Fadda Edoardo   Ricercatore L240/10 MAT/09 40 0 0 0 1
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
2022/23
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 Python 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.
The classes are organized in theoretical lectures and laboratories. During the laboratories, students will 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 require a good knowledge of Python 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 scritta (in aula); Prova orale obbligatoria; Elaborato grafico prodotto in gruppo;
Exam: Written test; Compulsory oral exam; Group graphic design project;
... 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.
Gli studenti e le studentesse con disabilità o con Disturbi Specifici di Apprendimento (DSA), oltre alla segnalazione tramite procedura informatizzata, sono invitati a comunicare anche direttamente al/la docente titolare dell'insegnamento, con un preavviso non inferiore ad una settimana dall'avvio della sessione d'esame, gli strumenti compensativi concordati con l'Unità Special Needs, al fine di permettere al/la docente la declinazione più idonea in riferimento alla specifica tipologia di esame.
Exam: Written test; Compulsory oral exam; Group graphic design project;
Students are requested to accomplish a group assignment. Groups are asked to autonomously formulate and solve a specific optimization problem, using concepts and techniques learned during the course (the goal is to test skills/capabilities i)-v) described in the expected learning outcomes section). A report on the group activities must be then delivered and group members will be called for a final discussion about the assignment. At last, a brief oral exam will complete the assessment of individual knowledge/capacities (in particular skills/capability i)-iv) ). The exam consists of a couple of questions about concepts/optimization techniques discussed in class. The relative weight of the assignment and the oral exam will be respectively 50% and 50%. Students which have difficulties attending the labs can sustain a written test.
In addition to the message sent by the online system, students with disabilities or Specific Learning Disorders (SLD) are invited to directly inform the professor in charge of the course about the special arrangements for the exam that have been agreed with the Special Needs Unit. The professor has to be informed at least one week before the beginning of the examination session in order to provide students with the most suitable arrangements for each specific type of exam.