Combinatorial Optimization


(i) Comprehension of the main concepts from graphs, polyhedra; and matroids

(ii) Development of algorithm designing skills;

(iii) Improving modeling skills;

(iv) Improving mathematical maturity;

General characterization





Responsible teacher

Manuel Valdemar Cabral Vieira


Weekly - 4

Total - 70

Teaching language



Students are supposed to have knowledge in Linear Programming, and some skills in algorithms.


L.A. Wolsey, Integer Programming, Wiley, 1998.

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

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

A. Schrijver, A Course in Combinatorial Optimization, 2013

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



Teaching method

In this course classes are theoretical-practical.

Lectures consist of expose of theoretical concepts and carry up some proffs, using the framework and the projector, and resolution of exercises and problems.

Part of the study is done independently by the student, individually and in groups, using bibliographic brackets, and the support of the teacher in the classroom, and in pre-established schedules reserved for the students'''' attendence.

Evaluation method

The student will be excluded of the evaluation if his presences in classes is less than 2/3 of the total number of classes.

Rules of evaluation

The student will be excluded of the evaluation if  her/his number of presences in the classes  is less than 2/3.

The student may be evaluated by three tests and will be approved if  the three tests sum up (rounded) at least 10. The grade will be the rounded sum of the tests.

The student may also be approved by a final exam if the exam''''s grade is at least 10. The grade will be the one attained in the exam (rounded) and any grade in any test will be discarded.

Any grade improvement may be done in the final exam and will be subject to the same demands as the exam.

An additional project and/or oral exam is required for grades above 17.

Subject matter

1. Graphs
2. Modeling with binary variables

3. Integer programming

4. Trees

5. Shortest paths

6. Matchings

7. Flows
8. Matroids

9. Computational complexity

10. Approximation algorithms


Programs where the course is taught: