Optimização Combinatória

Conhecimentos de Base Recomendados

Programação Linear e Matemática Discreta.

Resultados de Aprendizagem

Em Otimização Combinatória estudamos técnicas combinadas de combinatória, programação linear e algoritmos para resolver problemas de otimização em estruturas discretas ou mistas. Exemplos de problemas reais são a calendarização de exames e aulas numa escola, o sequenciamento de tarefas num processo industrial, o dimensionamento de pessoal num centro de atendimento e o dimensionamento de redes de telecomunicações. Grande parte dos problemas provém de áreas como a Investigação Operacional e as Ciências de Computação.

Estágio(s)

Não

Programa

Árvore geradora mínima (Prim e Kruskal).

Caminhos mais curtos (Ford-Bellman e Dijkstra).

Fluxo Máximo e Corte Mínimo (Ford-Fulkerson).

Emparelhamentos em grafos bipartidos (Kuhn) e não bipartidos (Edmonds).

Unimodularidade Total (Hoffman-Kruskal e Ghouila-Houri).

Estrutura facial de poliedros (polar, pontos extremos, faces, facetas).

Planos cortantes (Gomory, lift-and-project, split, mir).

Um estudo computacional (e.g., o problema do caixeiro viajante).

Docente(s) responsável(eis)

João Luís Cardoso Soares

Métodos de Avaliação

Final
Apresentação de um trabalho : 10.0%
Exame: 90.0%

Contínua
Trabalhos para casa : 10.0%
Apresentação de um trabalho : 10.0%
Duas frequências : 80.0%

Bibliografia

COOK, W.; CUNNINGHAM, W.; PULLEYBLANK W. [et.al.] (1998). Combinatorial Optimization, Wiley-Interscience. (Cota na Biblioteca: 90C/Com.Coo)