COMBINATORIAL OPTIMIZATION

Academic Year 2021-2022

Teachers

Franca Rinaldi

Unit Credits

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 designed 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 development, the resolution of some exercises may be proposed in order to verify the student’s ability to apply his/her theoretical and methodological knowledge to the formulation of models, the resolution of numerical issues and the proof of easy statements.

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.

The course presents some classes of problems and methodologies of particular relevance in combinatorial optimization. The main topics of the course are the theory of duality and Lagrangian methods, the column generation method, network flows, dynamic programming, matroid optimization and matching problems on graphs.

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 / resolution via integer linear programming (column generation methods, duality and Lagrangian methods) are explored and the theory of flow networks, dynamic programming, optimization on matroids and solution algorithms for some fundamental problems on graphs are presented.

Texts

– Paolo Serafini, “Ottimizzazione”, Zanichelli, Bologna 2000.

– Lecture notes.

Academic Year 2021-2022