Topics of Combinatorial Optimization


Development of knowledge, skills and competences to address a wide variety of combinatorial optimization problems.

General characterization





Responsible teacher

Isabel Cristina Silva Correia


Weekly - Available soon

Total - 56

Teaching language



Knowledge of Linear Programming  and  of basics of Graph Theory.


B. Korte, J. Vygen, Combinatorial Optimization: Theory and Algorithms, Springer, 2012.

L. Lovász and M.D. Plummer, Matching Theory, North-Holland Mathematics Studies, 1986.

A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics, Springer, 2003.

A. Schrijver, A Course in Combinatorial Optimization, 2013 available from

D.B. West, Introduction to Graph Theory, Prentice Hall, 2001

Teaching method

The course consist of lectures where presentations of theoretical concepts, proofs, and resolution and discussion of proposed exercises are conducted; and study outside the classroom, where the student, individually and in groups, using the available material and the support of teachers, in classes and in pre-established office hours, assimilates the theoretical material and seeks to solve the suggested exercises.

Evaluation method

During the semester there will be  two tests and one work on a specific topic.

Subject matter

1. Graphs

2. Polytopes

3. Matchings and covers in bipartite graphs

4. Flows

5. Matroids

6. Computational complexity

7. Integer linear programming and totally unimodular matrices


Programs where the course is taught: