Ensinar técnicas para o tratamento de problemas de otimização combinatória, em especial aqueles que podem ser formulados como problemas em grafos.
O escopo da otimização combinatória e programação inteira. Modelagem de vários problemas usando variáveis 0/1. O problema do transporte. Especialização do método simplex para redes. Aplicações: teorema de Hall, teorema de König, teorema de Dilworth. O problema do transporte capacitado: o método primal-dual. Algoritmos para fluxos máximos em redes. Fluxos de custo mínimo e circulações viáveis: o método "out-of-kilter". Estudo aprofundado de poliedros de alguns problemas não-unimodulares bem resolvidos (emparelhamentos, branchings, etc.).
W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver, Combinatorial Optimization, John Wiley, 1998.R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993.C.H. Papadimitrou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice Hall, 1982.E. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart & Winston, 1976.V. Chvátal, Linear Programming, Freeman, New York, 1983.
