73030 - Network Optimization M

Learning outcomes

The course introduces the student to graph and network problems and to the main algorithmic techniqes in this area. At the end of the course the student has the ability to model industrial problems that can be described through graphs and networks, and has competence on the main methods for their solution.

Course contents

Prerequisites:
It is required that the student has followed the course Operations Research M or an equivalent course on Operations Research.

Contents:

1. Graphs and networks theory
1.1 Introduction
1.2 Terminology

2. Basic problems on graphs
2.1 Shortest spanning tree
2.2 Shortest path problems
2.3 CPM method for project management0

3. Flows in networks
3.1 Maximum flow problems
3.2 Minimum cost flow problems
3.3 Mathematical models for graph and network problems
3.5 Matching and assignment problems

4. Optimal circuits
4.1 Hamiltonian circuits
4.2 Traveling salesman problem
4.3 Vehicle routing problems

5. Graph coloring problems.

Readings/Bibliography

S. Martello, Ricerca Operativa [http://www.editrice-esculapio.com/martello-ricerca-operativa-per-la-laurea-magistrale/], Esculapio (progetto Leonardo), Bologna, 2021.

Teaching methods

Lessons and Exercises.

Assessment methods

Written exam and oral assessment.

Teaching tools

Slides.

Office hours

See the website of Enrico Malaguti

See the website of Michele Monaci