Nível:
Graduação
Nome da disciplina:
Programação Combinatória
Número de Créditos:
4
Oferecimento:
A Critério da Unidade
Pré-requisito:
MS428
Ementa:
Formulação e problemas combinatórios: mochila, emparelhamento, carteiro chinês, caixeiro viajante, representação, cobertura e particionamento de conjuntos, etc. Métodos de otimização: branch and bound, branch and cut, planos de corte e método de Benders.
Conteúdo / Programa:
Objetivo: Identificação de problemas de otimização que podem ser modelados como problemas de otimização combinatorial. Técnicas de modelagem. Estudo da complexidade dos problemas. Apresentação de algoritmos para sua solução. Conteúdo: Formulação de problemas combinatórios: mochila, emparelhamento, carteiro chinês, caixeiro viajante, representação, cobertura e particionamento de conjuntos. Utilização de variáveis inteiras em modelagem. Introdução à teoria de complexidade. Métodos de otimização: branch and bound, branch and cut, planos de corte e método de Benders. Características do problema, teoria das desigualdades válidas.
Objetivo:
Identificação de problemas de otimização que podem ser modelados como problemas de otimização combinatorial. Técnicas de modelagem. Estudo da complexidade dos problemas. Apresentação de algoritmos para sua solução.
Forma de Avaliação:
Por nota e frequência
Referência Bibliográfica:
[1] Laurence A. Wolsey. Integer Programming. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley Sons, 1998.[2] Marcos Arenales, Vinı́cius Armentano, Reinaldo Morabito, e Horacio Yanasse. Pesquisa Operacional. Campus, 2 ª ed., 2015.[3] George Nemhauser e Laurence Wolsey. Integer and Combinatorial Optimization. John Wiley Sons, 1999.[4] Marco Cesar Goldbarg e Henrique Pacca Loureiro Luna. Otimização Combinatória e Programação Linear: Modelos e Algoritmos. Campus, 2 ª ed., 2005.