- Docente: Ugo Dal Lago
- Credits: 6
- SSD: INF/01
- Language: Italian
- Teaching Mode: Traditional lectures
- Campus: Bologna
-
Corso:
Second cycle degree programme (LM) in
Physics (cod. 9245)
Also valid for First cycle degree programme (L) in Computer Science (cod. 8009)
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 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, together with the associated theory.
Office hours
See the website of Ugo Dal Lago
SDGs
This teaching activity contributes to the achievement of the Sustainable Development Goals of the UN 2030 Agenda.