C9581 - DISCRETE AND NETWORK OPTIMIZATION PROBLEMS M

Learning outcomes

The course introduces students to classical combinatorial optimization problems and to problems involving graphs and networks, as well as to the related algorithmic techniques. At the end of the course, students will have gained skills in modeling real-world problems that can be represented through integer variables, graphs or flow networks, and in the main methodologies 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.

Program:

Basic problems on graphs
Shortest spanning tree
Shortest path problems


Flows in networks
Maximum flow problems
Minimum cost flow problems
Mathematical models for graph and network problems

TSP and Vehicle Routing

Packing

Vertex Coloring

Solution of exponential size models

Readings/Bibliography

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

 

Lecture Notes

Teaching methods

Lessons and Exercises.

Assessment methods

Written exam and oral assessment.

Office hours

See the website of Enrico Malaguti

See the website of Michele Monaci