Topics of Combinatorial Optimization

Objectives

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

General characterization

Code

11643

Credits

6.0

Responsible teacher

Isabel Cristina Silva Correia

Hours

Weekly - Available soon

Total - 56

Teaching language

Português

Prerequisites

Knowledge of Linear Programming  and  of basics of Graph Theory.

Bibliography

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 http://homepages.cwi.nl/~lex/files/dict.pdf

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

Programs where the course is taught: