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 following are the main topics of the course: optimization problems, example models, linear programming, graphs and graph models, integer linear programming.

Readings/Bibliography

Paolo Serafini. Ricerca Operativa. Springer, 2009

Teaching methods

Lectures and exercise sessions.

Assessment methods

The exam at the end of the course aims to assess the achievement of the following learning objectives by the student:

• Knowing the concept of optimization problem, with particular emphasis to linear programming.
• Being able to model concrete problems as linear programming problems.
• Know the main algorithms for maximum flow and minimum cost flow on graphs.
• To know and apply the simplex algorithm and the branch-and-bound method, together with the associated theory.

The final grade for the course is defined by means of a written exam (lasting two hours), an oral test which can be followed at the discretion of the teacher. During the written exams, students are not allowed to consult any teaching material.

Teaching tools

Students will be provided with slides used by the teacher, and with an exercise book.

Office hours

See the website of Ugo Dal Lago