Programação Inteira
Código: PINF7027
Curso: Doutorado em Ciência da Computação
Créditos: 4
Carga horária: 60
Ementa: * Caracterização de Problemas de Programação Inteira.
* Modelos e Aplicações.
* Branch-and-bound para resolver programas inteiros.
* Pré-processamento e probing em programas inteiros.
* Heurística primais para programas inteiros.
* Regras avançadas de ramificação e seleção de nós para programas inteiros.
* Teoria Poliédrica: Conceitos de dimensão, faces, facetas, representações poliédricas e polaridade;
equivalência de separação e otimização.
* Técnicas para obter desigualdades válidas, os planos de corte de Gomory, "mixed-integer rounding", "lifting", "cover inequalities".
* Algoritmos Branch-and-cut
* Introdução a software para resolver programas inteiros.
* Relaxação Lagrangiana, determinação de Multiplicadores de Lagrange: Otimização Subgradiente e Ajustamento de Multiplicadores.
* Decomposição de Benders, Branch-and-Price, Branch-and-Cut-and-Price.
Bibliografia: * NEMHAUSER, George L.; WOLSEY, Laurence A. Integer and combinatorial optimization. New York, N.Y.: John Wiley & Sons, 1999. xiv, 763 p. (Wiley-Interscience series in discrete mathematics and optimization). ISBN 9780471359432.
* SCHRIJVER, A. Theory of linear and integer programming. Chichester, England: J. Wiley & Sons, 1998. xi, 471 p. (Wiley-Intersciense series in discrete mathematics and optimization) ISBN 9780471982326.
* CONFORTI, Michele, CORNUEJOLS, Gerard, ZAMBELLI, Giacomo. Integer Programming. Springer International Publishing, 2014.XII, 456 p. (Graduate Texts in Mathematics, Volume 271) ISBN 9783319110073.