Programa

• Introdução a Problemas de Otimização

• Problemas Computacionais e Algoritmos

  • Definições e terminologia: espaço de soluções, função objetivo, soluções viáveis etc
  • Máximos/mínimos locais
  • Busca no espaço de soluções
  • Discreta X contínua
  • Combinatória X não combinatória

• Programação Linear

• Técnicas combinatórias de algoritmos

  • Enumeração;
  • Backtracking;
  • Algoritmos gulosos;
  • Programação dinâmica;
  • Branch-and-bound;
  • Algoritmos de Aproximação

Objetivo

Tratar de assuntos referentes a algoritmos para problemas de otimização com ênfase em algoritmos exatos.

Avaliação

A definir

Calendário

02/03 Primeira aula

25/05 Semana acadêmica BCC

27/05 Semana acadêmica BCC

Material de Apoio

• Repositórios com Instâncias de Programas Lineares
  • MP-Testdata
  • MIPLIB
    • MIPLIB 3.0 Problem Set
    • MIPLIB 2010 Complete problem set
  • NetLib
  • GAMS Model Library
  • Hans D. Mittelmann instances
  • Csaba Mészáros instances
• Enumerações
  • Random Generation and Enumeration of Proper Interval Graphs (Toshiki Saitoh, Katsuhisa Yamanaka, Masashi Kiyomi, Ryuhei Uehara)
  • Random Generation and Enumeration of Bipartite Permutation Graphs (Toshiki Saitoh, Yota Otachi, Katsuhisa Yamanaka, Ryuhei Uehara)
  • Wikipedia: Heap's Algorithm - Para gerar permutações
  • Algorithms for Generating Permutations and Combinations (Nathan Wodarz)

Bibliografia

Understanding and Using Linear Programming (Jiří Matoušek, Bernd Gärtner)

Algoritmos de Programação Linear: Programação Linear Concreta (Paulo Feofiloff)

Applied Mathematical Programming (Stephen Bradley, Arnoldo Hax e Thomas Magnanti): é um livro antigo, porém muito aprofundado, sobre o tema.

Algorithm Design (Jon Kleinberg e Éva Tardos, 2005)

Introduction to Algorithms (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, e Clifford Stein, 2009)

The Algorithm Design Manual. Skiena. Springer, 1998.

Combinatorial Optimization - Algorithms and Complexity. Papadimitriou, Steiglitz. Dover Publications. 1998.

Combinatorial Algorithms - Generation, Enumeration and Search. Kreher, Stinson. CRC Press. 1999.

Algorithms. R. Sedgewick. Addison-Wesley, Reading, Massachusetts, 1983.

Data Structures and Algorithms. A.V. Aho, J.E. Hopcroft, J.D. Ullman. Addison-Wesley, Reading, Massachusetts, 1983.

Algorithms and Data Structures. N. Wirth. Prentice-Hall, 1986 (Tradução: Algoritmos e Estruturas de Dados. Prentice-Hall do Brasil Ltda, 1989).

The Art of Computer Programming vol. 1, D.E. Knuth.

The Art of Computer Programming vol. 3, D.E. Knuth.