Network Optimization

Course objectives

The course aims to provide the basic notions of Network Optimization. The expected learning outcomes consist of the ability to: 1. recognize Network Optimization problems in the application fields, also knowing how to evaluate their complexity and characteristics; 2. develop the mathematical modeling of the identified problems, writing optimization models for them; 3. practically solve the considered optimization models, by appropriately choosing the algorithms and solution software; 4. know how to interpret the solutions found in terms of the original application problems. In particular, referring to the Dublin Descriptors: Knowledge and understanding: On completion of the course, the students should have acquired knowledge of Network Optimization, in particular with regards to the different types of mathematical models, solution algorithms and software solvers. Skills and abilities: On completion of the course, the students should be able to: - identify Network Optimization problems; - write an optimization model of an identified problem; - select an algorithm and a solution software to solve in practice the considered model. Judgement and communication skills: On completion of the course, the students should be able to: - judge the computational complexity of a Network Optimization problem and explain this to other colleagues without specific training on the subject; - judge whether a solution approach can practically obtain the solution; - understand the practical meaning of an obtained solution and explain it to other colleagues without specific training on the subject. Learning abilities: On completion of the course, the students should be able to learn and understand new types of models, algorithms and solution software to extend his/her skills in Optimization.

Channel 1
ANNA LIVIA CROELLA Lecturers' profile

Program - Frequency - Exams

Course program
The course aims to delve into typical topics of network optimization problems and the basic notions of Combinatorial Optimization. The program focuses on the following topics: - Introduction to the course and exam methods - Introduction to network models and a review of linear programming theory - Linear models for network optimization problems: formulations, bounds, and algorithms - Introduction to graph theory - Overview of computational complexity - Problems on graphs - Traversal algorithms and applications - Optimal spanning trees - Network flow problems, duality theory - Maximum flow problems - Shortest and longest path problems - Introduction to the use of software tools (dedicated seminars).
Prerequisites
Natural prerequisites for this course are the fundamental topics of Operations Research.
Books
The lecture slides are available. Further Reading: - Caramia M., Giordani S., Guerriero F., Musmanno R., Pacciarelli D., *Ottimizzazione su rete. Modelli e Algoritmi*, ISEDI, 2019. - Ahuja R.K., Magnanti T., Orlin J., *Network Flows: Theory, Algorithms, and Applications*, Prentice Hall, 1993. Exercise Books: - Meloni C., *Esercizi di ottimizzazione combinatoria*, CISU, 2022.
Frequency
Attendance is not mandatory.
Exam mode
The exam is written and lasts 1 hour and 30 minutes. The test is conducted without educational materials and consists of 3 questions, generally divided into multiple parts. The questions cover all parts of the course and require demonstrating the ability to apply the tools, models, and methods discussed in the course. They may address both theoretical and practical aspects and may include numerical exercises, formulation tasks, or topics related to the use of dedicated software. The overall grade for the test is obtained by summing the scores of the individual questions. If the total score exceeds 30, a score of 30 cum laude is awarded. Registration on INFOSTUD is strictly necessary to take the exam, with no exceptions allowed.
Lesson mode
The course is conducted in the classroom for 60 hours of frontal lectures (6 credits).
  • Lesson code10600549
  • Academic year2024/2025
  • CourseManagement Engineering
  • CurriculumIngegneria Gestionale (percorso valido anche ai fini del conseguimento del doppio titolo italo-venezuelano)
  • Year3rd year
  • Semester1st semester
  • SSDMAT/09
  • CFU6
  • Subject areaAttività formative affini o integrative