Academic Year 2019/2020

  • Docente: Ugo Dal Lago
  • Credits: 6
  • SSD: INF/01
  • Language: Italian
  • Teaching Mode: Traditional lectures
  • Campus: Bologna
  • Corso: First cycle degree programme (L) in Computer Science (cod. 8009)

    Also valid for Second cycle degree programme (LM) in Physics (cod. 9245)

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, optimality with many objectives, linear programming, graphs and graph models, integer linear programming, path models, peculiar linear programming models.

Readings/Bibliography

Paolo Serafini. Ricerca Operativa. Springer, 2009

Teaching methods

Lectures.

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, together with the associated theory.
The final grade for the course is defined by means of a written exam, an oral test which can be followed at the discretion of the teacher. Written exam, followed by an oral exam.

Office hours

See the website of Ugo Dal Lago