Ementa de Disciplina

×

INF2912

OTIMIZACAO COMBINATORIA

3 créditos

Ementa

Parte I: fluxo em redes, programação linear, inteira e mista. Problemas clássicos (modelos): transportes, atribuição, fluxo máximo, caminho mais curto, fluxo a custo mínimo, fluxos com ganhos, fluxos não-lineares e multi-fluxos. Modelagem: problemas de confecção de horários, problemas de atribuição de recursos, problemas de planejamento de redes de comunicação e de redes elétricas, problemas multi-periodos. Algoritmos: algoritmos de complexidade polinomial, algoritmos para programacao linear, algoritmos paralelizáveis, algoritmos aproximados. Parti II: multi-fluxos inteiros em redes problema e modelos: o problema clássico e suas aplicações em otimização combinatória. Dificuldades na sua resolução e importância do modelo. Algoritmos de geração de colunas e de geração de planos de corte. Métodos de resolução: decomposição, relaxação lagrangeana, branch-and-bound, branch-and-price, branch-and-cut e branch-and-cut-and-price.

Pré-requisitos

Nenhum pre-requisito encontrado para INF2912

Última atualização da ementa: 13/05/2014