Português English
Contato

Lista de Disciplinas | CMP608

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:

  • Modelar/formular problemas de otimização como de programação linear inteira.
  • Solucionar de forma exata esses problemas usando as formulações propostas e pacotes prontos (ex. CEPLEX, Gurobi).
  • Projetar matheurísticas e/ou algoritmos de aproximação que explorem os modelos propostos para os problemas.

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á:

  1. a) Entregar relatórios descrevendo resultados parciais obtidos para o problema após o estudo dos diferentes tópicos.
  2. b) Entregar um trabalho final (em formato de artigo científico) compilando os resultados produzidos para o problema ao longo da disciplina.
  3. c) Apresentar os resultados de forma oral.

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.