Programa

Programação Inteira

Mestrado Bolonha em Estatística e Investigação Operacional

Programa

1. Introdução: definição, soluções ótimas, limites, variáveis binárias; PI vs. PL. 2. Formulação: modelos em PI/PLIM; técnicas de modelação; linguagens e softwares; formulações alternativas. 3. Problemas fáceis/difíceis e noções de complexidade. 4. Relaxações lineares: revisão de PL; matrizes unimodulares e totalmente unimodulares; casos notáveis; modelos com TU. 5. Algoritmos de enumeração: relaxações; decomposição e enumeração implícita; branch & bound; fatores de desempenho. 6. Poliedros: definições; teoremas; invólucro convexo. 7. Desigualdades válidas: definições; Chvátal-Gomory; problemas estruturados; desigualdades fortes. 8. Planos de corte: Gomory; algoritmo genérico e separação; branch & cut. 9. Formulações com variáveis adicionais: projeção; formulações estendidas; fortes; exponenciais. 10. Relaxação lagrangeana: definições; dual; força; relação com outras reformulações. 11. Heurísticas: propósito; classificação; heurísticas estruturais e em PI.