Academic Year 2023-2024

COMBINATORIAL OPTIMIZATION

Teachers

Franca Rinaldi
Unit Credits
6
Teaching Period
Second Period
Course Type
Supplementary
Prerequisites. Knowledge of the theory and the main techniques of linear programming and integer linear programming. Basic definitions, concepts and results in graph theory.
Teaching Methods. Theoretical lessons and exercises
Verification of Learning. The exam consists of an oral test aiming to verify the knowledge of the topics in the program and the student’s ability to present them in a complete and rigorous way. During the exam, the resolution of some exercises may be proposed to verify the student’s ability to apply their theoretical and methodological knowledge to the formulation of models, the resolution of numerical issues and the proof of simple statements.

The grades will be determined based on the criteria approved by the Course Council available at the link

https://www.uniud.it/it/didattica/corsi/area-scientifica/scienze-matematiche-informatiche-multimediali-fisiche/laurea-magistrale/matematica/corso/regolamento-corso/all-B2/2023-2024/view

More Information. ~
Objectives
At the end of the course the student will:

Knowledge and understanding: know how to apply the column generation approach to solve models with an exponential number of variables; know the theory of duality and Lagrangian methods; know the theory of network flows and the algorithms for some classical network problems; know about dynamic programming and its applications to solve combinatorial optimization problems; know the basic arguments of matroid theory and its applications in combinatorial optimization; know how to solve some classic problems on graphs.

Applying knowledge and understanding: be able to propose and solve models that require a column generation approach;

be able to solve suitable problems using the Lagrangian relaxation of constraints; be able to formulate flow models for combinatorial / applicational problems; know how to define a dynamic programming scheme and deduce a resolution algorithm for problems with particular structure; know how to apply the algorithms presented in the course to solve simple instances of the minimum path problem, the min cost flow problem, the maximum flow, the minimum spanning tree and matching problems.

Autonomy of judgment: be able to identify suitable models and algorithms for combinatorial optimization problems.

Communication skills: be able to present the subjects of the course with formal rigor and completeness.

Learning skills: be able to consult the scientific literature of the discipline.

Contents
The course presents an overview of the main theories and methodologies of mathematical optimization aimed at solving combinatorial optimization problems. In particular, topics related to modeling / solving these problems via integer linear programming (column generation methods, duality and Lagrangian methods) are explored. Moreover, the theory of network flows, dynamic programming, matroid optimisation and solution algorithms for some fundamental polynomial problems on graphs are presented.
Texts
– Paolo Serafini, “Ottimizzazione”, Zanichelli, Bologna 2000.

– Lecture notes.