Disciplina: Tópicos especiais em computação:
Programação linear inteira: formulações, técnicas e aplicações.
Professor responsável: Santiago Valdés Ravelo.
Pré-requisitos: Não há
Carga horária: 60 horas.
Créditos: 4.
Semestre oferecido: 2020/1.
Súmula
Abordagem de problemas combinatórios sob a ótica de programação linear inteira. Estudo de diferentes técnicas de otimização baseadas em formulações matemáticas dos problemas.
Objetivos
Ao final da disciplina se espera que o aluno seja capaz de:
Programa
Semana 1 Introdução e apresentação da disciplina.
Semana 2 – 3 Programação linear.
Semana 4- Programação linear inteira.
Semana 5 – 6 Relaxações
Semana 7 – 8 Métodos exatos e pacotes.
Semana 9 – 12 Matheurísticas: hibridização de heurísticas e metaheurísticas com modelos matemáticos.
Semana 13 – 16 Algoritmos de aproximação baseados em formulações matemáticas.
Semana 17 – 18 Apresentação de seminários e entrega dos trabalhos finais.
Critérios de avaliação
Os estudantes serão avaliados a partir da entrega de listas de exercícios sobre os diferentes tópicos e de um trabalho a ser desenvolvido ao longo da disciplina. Considerando que alunos de diferentes áreas se inscrevam, a disciplina propõe que cada um desenvolva um trabalho que una os conteúdos da disciplina e de sua área de pesquisa. Desta forma, cada estudante selecionará um problema de otimização combinatória relacionado à sua área de pesquisa e sobre ele deverá:
A média final será calculada como segue, ponderando os itens acima relacionados, além da entrega de listas de exercícios sobre os diferentes tópicos: o item a) com peso 3, o b) com peso 3, o c) com peso 2 e as listas de exercícios com peso 2.
Bibliografia
[1 ] Vanderbei, Robert J. “LInear Programming: foundations and extensions”. Springer.
[2 ] Papadimitriou, Christos and Steiglitz, Kenneth. “Combinatorial Optimizaton: Algorithms and Complexity”. Prentice Hall.
[3 ] Nemhauser, George L. and Wolsey, Laurence A.. “Integer and combinatorial optimization”. John Wiley & Sons.
[4 ] Garfinkel, Robert and Nemhauser, George L.. “Integer Programming”. John Wiley & Sons.
[5 ] Fischetti, Martina and Fischetti, Matteo. “Matheuristics”. Springer.
[6 ] Maniezzo, Vittorio, Stu¨tzle, Thomas and Voss, Stefan. “Matheuristics Hybridizing Metaheuristics and Mathematical Programming”. Springer.
[7 ] Williamson, David P. and Shmoys, David B.. “The Design of Approximation Algorithms”. Cambridge University Press.