Optimização Discreta

Licenciatura: Matemática

Ano Lectivo: 2003/04

Programa:

a) Formulações algébricas de problemas de Optimização Discreta.

b) Relaxações (lineares, combinatórias e Lagrangeanas; dualidade em Optimização Discreta).

c) Conjuntos Poliédricos Inteiros (integralidade dual total e unimodularidade total).

d) Submodularidade (algoritmo Guloso e matroides).

e) Emparelhamentos e Afectação (algoritmos para os emparelhamentos de cardinalidade máxima e de peso máximo e para o problema da afectação).

f) Introdução à Programação Dinâmica (aplicação aos problemas de loteamento e da mochila).

g) Algoritmos Branch and Bound e de Planos Cortantes.