Detalhes

Nome da Disciplina: TÓPICOS ESPECIAIS II - PROGRAMAÇÃO INTEIRA E OTIMIZAÇÃO COMBINATÓRIA

Carga Horária: 60

Créditos: 3

Obrigatória: Não

Revisão de programação linear. Programação inteira: formulação de problemas, complexidade, otimalidade: relaxações e limitantes, problemas bem resolvidos, unimodularidade total. Relaxação lagrangeana: dualidade lagrangeana, método do subgradiente, heurísticas lagrangeanas. Métodos exatos básicos: branch-and-bound, geração de colunas, algoritmos de planos de corte, enumeração implícita. Teoria poliédrica: desigualdades válidas fortes, problema da separação, complexidade de otimização vs. complexidade de separação. Problemas clássicos: caixeiro viajante, mochila, localização, recobrimento, particionamento, empacotamento, problema de Steiner, roteamento. Combinatória poliédrica aplicada aos problemas da mochila binária e do caixeiro viajante.

L.A. Wolsey, Integer Programming, Wiley, 1998. G.L. Nemhauser e L.A. Wolsey, Integer and Combinatorial Optimization , Wiley, 1988. M.S. Bazaraa, J.J. Jarvis e H.D. Sherali, Linear Programming and Network Flows, Wiley, 1990. L. Applegate, R.E. Bixby, V. Chvátal e W.J. Cook, The Traveling Salesman Problem, Princeton University Press, 2006. R.K. Martin, Large Scale Linear and Integer Optimization: A Unified Approach, Kluwer,1999.