Pre-requisito:  MC448 / MC458

Ementa:

Programação Linear: formulando problemas, algoritmo Primal-Simplex, Dualidade em PL, algoritmo Dual-Simplex e a complexidade de resolução de um programa linear. Programação Linear Inteira: formulações e complexidade. Otimali-dade: relaxações e limitantes. Relaxação Lagrangeana: método do subgradiente e heurísticas lagrangeanas. Proble-mas de PLI bem resolvidos e Unimodularidade Total. Algoritmos de Branch-and-Bound para PLI. O método de geração de colunas. Algoritmos de Planos-de-Corte para PLI. Desigualdades Válidas Fortes e técnicas de lifting, Combinatória Poliédrica, O problema da separação.

Programa: 

  - Programação Linear (PL):
  - Formulando problemas em PL
  - Algoritmo Primal-Simplex
  - Dualidade em PL
  - O algoritmo-Dual Simplex
  - A complexidade de resolução de um programa linear
  - Programação Linear Inteira (PLI):
  - Formulações e complexidade
  - Otimalidade: relaxações e limitantes
  - Problemas de PLI bem resolvidos e Unimodularidade Total
  - Relaxação Lagrangeana: método do subgradiente e heurísticas lagrangeanas
  - Algoritmos de Branch-and-Bound para PLI
  - O método de geração de colunas
  - Algoritmos de Planos-de-Corte para PLI
  - Desigualdades Válidas Fortes
  - Teoria Poliédrica básica
  - Combinatória Poliédrica aplicada ao problema da mochila binária
  - Combinatória Poliédrica aplicada ao problema do caixeiro viajante
  - O problema da separação

  - A questão da complexidade de otimização versus a complexidade de separação 

Bibliografia:

1 - L. Wolsey. Integer Programming, Wiley-Interscience (1998).
2 - G. Nemhauser e L. Wolsey. Integer and Combinatorial Optimization, Wiley-Interscience (1988).
3 - D. Bertsimas e J. Tsitsiklis. Introduction to Linear Optimization, Athena Scientific (1997).
4 - M. Bazaraa, J. Jarvis e H. Sherali. Linear Programming and Network Flows, John Wiley and Sons (1990).