• Este curso aborda técnicas que, hoje, correspondem à forma mais eficiente para a obtenção de soluções ótimas para um amplo conjunto de problemas de alta complexidade presentes na tomada de decisão em inúmeros contextos(econômico, logístico, etc). Discute-se também o impacto destas técnicas na obtenção de soluções aproximadas de boa qualidade.
  
  
• Discute a qualidade dos algoritmos. Estes, que tem o objetivo de encontrar soluções ótimas para tais problemas, baseiam-se em busca em árvores e enumeração, sendo tão eficientes quanto sua capacidade de avaliar as expectativas otimistas para a solução e sua capacidade de decidir sobre escolhas possíveis ao longo da busca.
  
  
• Apresenta as bases para a proposta de métodos para cálculo das expectativas para o valor da solução ótima do problema. Estas são feitas a partir da modelagem do problema em questão como os problemas clássicos sobre os quais modificações podem ser necessárias. Entre os problemas clássicos mais utilizados nesta etapa estão os problemas de Fluxo em Redes (Fluxo Máximo, Fluxo a Custo Mínimo, Fluxos com Ganhos, Fluxos Não-Lineares, Multi-Fluxos); problemas em Grafos (Emparelhamento Máximo (Ponderado), Caminho mais curto, Árvore Geradora Mínima, Caminhamento Mínimo/Máximo, etc), problemas Numéricos (Mochila, Empacotamento, etc) e problemas de programação Linear (Inteira) que permite unificar os algoritmos para resolução da maioria dos problemas acima citados.
  
  
• Descreve e avalia os uso de técnicas como Relação Lagrangeana e Programação Dinâmica em conjunto com os algoritmos conhecidos para a resolução dos problemas clássicos (citados acima) para a obtenção da expectativas e seu impacto na qualidade do algoritmo final.

• Desenvolver a capacidade de avaliar a complexidade e a qualidade dos algoritmos propostos para um determinado problema.
• Estudar os algoritmos básicos para as classes mais importantes de problemas neste contexto.
• Prover conhecimento para o desenvolvimento de algoritmos eficientes para novos problemas de otimização.
• Compreender a importância da implementação e a sensibilidade do comportamento dos algoritmos à ela.
• Conhecer as potencialidades e as limitações do conhecimento algorítmico atual.
• Discutir as tendências da pesquisa na área.

• Parte I Modelos
  
  · Problemas de Fluxo: Fluxo Máximo, Caminho mais curto, Fluxo a Custo Mínimo, Fluxos com Ganhos, Fluxos Não-Lineares, e Multi-Fluxos.
  
  · Problemas em Grafos: Árvores geradoras mínimas, caminho mais curto, emparelhamento máximo não-ponderado e ponderado, assignment, cortes mínimo e máximo, coloração de vértices e arestas, problema de Steiner, caixeiro viajante e roteamentos.
  
  · Problemas Numéricos: Mochila, Empacotamento uni e multi-dimensional, Lot Sizing.
  
  · Aplicações: Problemas de confecção de horários, problemas de atribuição de recursos, problemas de planejamento de redes de comunicação e de redes elétricas, planejamento multi-periódico, problemas em logística.
  
  
• Parte II Algoritmos
  
  · Métodos básicos: programação dinâmica, algoritmos para programação linear e inteira, decomposição, relaxação Lagrangeana, branch-and-bound.
  
  · Desenvolvendo e evoluindo os algoritmos: trabalhando com um número exponencial de variáveis e restrições, branch-and-cut, branch-and-price e branch-cut-and-price, noções de cortes poliédricos.

1. R.K. Ahuja, T.L. Magnanti e J.B.Orlin, Network Flows, Prentice Hall, 1993.
   
   
2. G.L. Nemhauser e J. L.A. Wolsey, Integer and Combinatorial Optimization, John Wiley & Sons, 1988.
   
   
3. W.J. Cook, W.H. Cunningham, W.R. Pulleyblank e A. Schrijver,Combinatorial Optimization, John Wiley and Sons, New York, 1998.
   
   
4. J. L.A. Wolsey, Integer Programming, Wiley Interscience, 1998.
   
   
5. C. Papadimitriou e K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice Hall, 1982.
   
   
6. N. Christofides, Graph Theory: An Algorithmic Approach, Academic Press, 1975.
   
   
7. E. Horowitz e S. Sahni, Fundamentals of Computer Algorithms, Computer Science Press, 1978-89.
   
   
8. M. Garey e D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness W.H.Freeman and Company, 1979.
   
   
9. U. Manber, Algorithms: A Creative Approach, Addison-Wesley, 1989.
   
   
10. R.E. Tarjan, Data Structures and Network Algorithms, SIAM, 1983.
    
    
11. P.A. Jensen e W. Barnes, Network Flow Programming, Wiley, 1980.
    
    
12. M. Gondran e M. Minoux, Graphs and Algorithms, Wiley-Interscience, 1984.
    
    
13. T.H. Cormen, C.E. Leiserson e R.L. Rivest, Introduction to Algorithms, McGraw-Hill, New York, 1990.
    
    
14. G. Brassard e P. Bratley, Algorithmics: Theory and Practice, Prentice-Hall, 1988.

This document was translated from L^AT_EX by H^EV^EA.