SM/0121/EN - NETWORK FLOWS OPTIMIZATION
Academic Year 2022/2023
Free text for the University
MASSIMO DI FRANCESCO (Tit.)
- Teaching style
- Lingua Insegnamento
|[60/65] MATHEMATICS||[65/60 - Ord. 2020] MATEMATICA APPLICATA||6||48|
|[60/73] INFORMATICS||[73/00 - Ord. 2017] PERCORSO COMUNE||6||48|
1. Knowledge and understanding skills.
The course is designed for the students of the 2nd year of the Master Degree in Computer Science.
This course aims to provide students with a deep knowledge on the theory and practice of network optimization and its extensions. Network optimization problems form a subclass of mathematical programming problems with applications to Computer Science, Engineering, Economics, as well as in interdisciplinary domains such as in the transportation, logistics, manufacturing, project management. This course will survey some of the applications of network optimization and focus on key special cases of network flow problems such as the shortest path problem, the maximum flow problem, etc. The goals of the course are the following:
• To present the knowledge of the state-of-the-art in the theory and practice for solving network optimization problems.
• To provide students with a rigorous analysis of network optimization algorithms.
• To help students develop their intuition about algorithm development and analysis.
2. Ability to apply knowledge and understanding.
Students must apply these optimization methods to face a realistic problem. The problem is defined by the cooperation of the professor and is typically investigated with another student.
3. Autonomy of judgment.
Facing a realistic problem will put students in the position of critically thinking at the problem setting, evaluating which data are requested in their formulation, developing, implementing their algorithms and assessing the outcomes.
4. Communicative Skills.
The work on the problem will be illustrated in a write-up. It will enable students to develop the skills requested to present their work in an ordered and coherent way. Speaking skills will be evaluated in an oral interview, in which students must show the ability in explaining the underlying theory.
5. Learning Skills.
The course provides students with an adequate preparation to understand more advanced mathematical texts and makes them able to expand their knowledge autonomously in the future.
1. Knowledge. The course would benefit from a good understanding of the basic concepts of Linear Programming, which are learned both in the Bachelor’s Degree Program and in the Master Degree Program.
2. Skill. Students must be able to read and understand Linear Programming models and pseudocodes.
3. Competences. The ability to use a Mixed Integer Programming solver is requested.
4. Prerequisite courses. None.
• Introduction: Paths, Trees and Cycles
• Algorithm Design and Analysis
• Algorithms for Shortest-Path problems
• Algorithms for Maximum-Flow problems
• The Minimum-Cost-Flow-Problem
• Assignments and Spanning Trees
• Multy-commodity flow problems
The course consists of 48 hours of lectures held in English. They cover theoretical concepts, as well as several exercises to review and reinforce the theoretical concepts. Finally, the professor provides regular support to students throughout the course by ad-hoc meetings and e-mails.
Verification of learning
Students must demonstrate their knowledge of the specific terminology, the ability to solve a realistic problem and the theoretical concepts presented in the lectures. Students are evaluated in two stages: a project on a problem and an oral exam. The project must be approved by the Professor and is typically made in cooperation with another student. The conclusion of the project is a necessary condition to give the oral exam. It is evaluated 16 points. Two questions are typically made in the oral exam. The answers are evaluated up to 15 points.
• The final mark ranges between 18/30 and 22/30 in the case of sufficient knowledge of the specific terminology, correct application of the methodological concepts and sufficient presentation of the concepts and results.
• The final mark ranges between 22/30 and 26/30 in the case of good knowledge of the terminology, good application of the methodological concepts and a good presentation of concepts and results.
• The final mark ranges between 27/30 and 30 cum laude in the case of an excellent mastery of specific terminology, a critical application of the methodological concepts and a clear display of concepts and results.
Students are advised to check their preparation during the lectures. They will test their skills by practicing with exercises and comparing their results to those presented by the Professor.
Ravindra k. Ahuja, Thomas L. Magnanti, James B. Orlin. Network Flows. Upper Saddle River, NJ: Prentice Hall, 1993. ISBN: 9780136175490.
Matteo Fischetti. Introduction to Mathematical Optimization. Kindle Edition, 2019.
The main teaching-supporting tool is the platform elearning platform (https://elearning.unica.it/), where additional information is available (e.g. a course diary reporting the topics of each lesson and further teaching files). Additional online support will be provided according to the evolution of the COVID-19 pandemic.