13477 - Combinatorial Optimisation

Learning outcomes

At the end of the course, the student knows the foundations of linear optimization and of integer linear optimization; he or she knows the simplex algorithm and knows when a problem has integer solutions. He or she can model a problem in terms of linear (or integer linear) constraints and objective function(s), or realize that this cannot be done. He or she is able to model combinatory problems on graphs as shortest paths, maximum flows and assignments as optimization problems, and solve them with the algorithms from the literature. Finally, he or she is able to recognize whether a given optimization problem is inherently intractable.

Course contents

The course will cover the following topics: optimization problems, examples of optimization problem models, linear programming, graphs and models on graphs, integer linear programming.

Readings/Bibliography

Paolo Serafini. Ricerca Operativa. Springer, 2009.

Teaching methods

Frontal lectures and exercises

Assessment methods

The exam aims to assess the achievement of the following educational objectives:

1. Knowledge of the concept of optimization problem, with particular reference to linear programming.

2. Be able to model concrete problems as linear or integer linear programming problems.

3. Know the main algorithms for maximum flow and minimum cost flow problems on graphs.

4. Know and be able to apply the simplex algorithm and the branch-and-bound method, together with the related theoretical bases.

The final grade of the Combinatorial Optimization Course is defined by means of a written test lasting two hours, which may be followed by an oral colloquium at the discretion of the teacher. During the written test, the consultation of material is not allowed.

Teaching tools

The slides used by the teacher and lecture notes on the main course  contents will be made available to students, together with examples of exercises carried out.

Office hours

See the website of Daniele Vigo