Pós Graduação em Ciência da Computação
Linha de Pesquisa: Otimização
Programação Linear

Alexandre Salles da Cunha
Professor Titular
Departamento de Ciência da Computação
Universidade Federal de Minas Gerais
acunha@dcc.ufmg.br

Março 2025

1 Objetivos do curso

Apresentar os fundamentos de Programação Linear, visando capacitar o aluno de Pós-Graduação em Ciência da Computação a desenvolver pesquisa em Programação Matemática, com ênfase em Otimização Linear de grande porte.

2 Plano de Curso

  1. Fundamentos matemáticos (4 aulas)
    1. Conceitos de Análise Convexa (2 aulas)
    2. Revisão de Álgebra Linear (2 aulas)
  2. Fundamentos de Programação Linear (aprox. 13 aulas)
    1. Definição do Problema, formas canônicas e padrão (1 aula).
    2. Projeção e Eliminação de Fourier-Motzkin (2 aulas)
    3. Dualidade via Projeção, Teoremas das Alternativas (1 aula)
    4. Geometria da Programação Linear (3 aulas)
    5. Método Simplex (2 aulas)
    6. Dualidade em Programação Matemática e Dualidade em Programação Linear (2 aulas)
    7. Análise de Sensibilidade (1 aula)
    8. Dual Simplex (1 aula)
  3. Métodos de Decomposição (6 aulas)
    1. Decomposição de Dantzig-Wolfe em Programação Linear (2 aulas)
    2. Geração de Colunas em Programação Inteira (2 aulas)
    3. Decomposição de Benders (2 aulas)
  4. Problemas de Fluxo em Redes e Formulações Integrais (4 aulas)
    1. Total Unimoduralidade
    2. Fluxo de Custo Mínimo
    3. Emparelhamentos em Grafos Bipartidos
    4. Emparelhamentos em Grafos Gerais
    5. Árvores Geradoras Mínimas
  5. Conceitos básicos de Algoritmos de Pontos Interiores (2 aulas)

3 Referências Bibliográficas

As referências principais são os livros textos de Bertsimas e Tsitsiklis [5], Vanderbei [17], Chvátal [6] e Martin [13]. Além delas, alguns clássicos merecem ser citados como fontes auxiliares: Lasdon [12], Dantzig [8, 9, 10], Ziegler [18] e Grünbaum [11]. Para a parte de Fluxo em Redes, as referências principais são as seguintes, além das já citadas para Programação Linear: [1, 3, 2]. Uma boa introdução à Análise Convexa é apresentada no Capítulo 1 de [4] e no livro texto de Çinlar e Vanderbei [7]. Duas boas referências para Álgebra Linear são Axler [16] e Trefethen e Bau [16]. As notas de aula do curso de Álgebra Linear Computacional (revisão de fundamentos de Álgebra Linear e Fatorações Básicas) que ministro na graduação, disponíveis aqui também podem ser úteis.

4 Avaliação - Semestre 2025/1

  1. 2 avaliações individuais, 30 pontos cada. A primeira ocorrerá após a apresentação do Método Dual Simplex. A segunda avaliação ocorrerá ao final do curso.
  2. 1 Trabalho de Implementação de um Algoritmo de Geração de Colunas ou Benders a ser discutido/definido com o professor. 20 pontos.
  3. Resumo do Artigo 1 [14] e do Artigo 2 [15], no início e ao final do curso. Total das duas atividades: 5 pontos. No primeiro resumo de cada artigo (1 folha A4, frente e verso, no máximo), o aluno deve apresentar o que entendeu e, eventualmente, o que não entendeu do trabalho. Ao final do semestre, deverá fazer uma segunda leitura, produzindo a atualização do primeiro resumo de cada um dos dois artigos.
  4. Listas de Exercícios: 15 pontos.

Referências

[1]   Ahuja, R. K., Orlin, J. B., e Magnanti, T. Network Flows: Theory, Algorithms and Applications. Prentice Hall, 1993.

[2]   Bazaraa, M. S., Jarvis, J. J., e Sherali, H. D. Linear Programming and Network Flows. John Wiley and Sons, 1990.

[3]   Bertsekas, D. P. Network Optimization: Continuous and Discrete Models. Athena Scientific, 1998.

[4]   Bertsekas, D. P. Convex Optimization Theory. Athena Scientific, 2009.

[5]   Bertsimas, D., e Tsitsiklis, J. N. Introduction to Linear Optimization. Athena Scientific, 1997.

[6]   Chvátal, V. Linear Programming. Freeman, 1983.

[7]   cinlar, E. C., e Vanderbei, R. J. Real and Convex Analysis. Springer, 2013.

[8]   Dantzig, G. Linear Programming and Extensions. Princeton, 1963.

[9]   Dantzig, G., e Thapa, M. Linear Programming I: Introduction. Springer, 1997.

[10]   Dantzig, G., e Thapa, M. Linear Programming II: Theory and Extensions. Springer, 1997.

[11]   Grunbaum, B. Convex Polytopes, 2nd ed. Springer, 2003.

[12]   Lasdon, L. Optimization Theory for Large Systems. Macmillan Company, New York, 1970.

[13]   Martin, R. Large Scale Linear and Integer Programming. Springer, 1998.

[14]   Morais, V., da Cunha, A. S., e Mahey, P. A branch-and-cut-and-price algorithm for the stackelberg minimum spanning tree game. Electronic Notes in Discrete Mathematics 52 (2016), 309–316.

[15]   Pereira, D. L., e Salles da Cunha, A. Dynamic intersection of multiple implicit dantzig–wolfe decompositions applied to the adjacent only quadratic minimum spanning tree problem. European Journal of Operational Research 284, 2 (2020), 413–426.

[16]   Trefethen, L. N., e III, D. B. Numerical Linear Algebra. SIAM, 1997.

[17]   Vanderbei, R. Linear Programming: Foundations and Extensions. Springer, 1997.

[18]   Ziegler, G. M. Lectures on Polytopes. Springer, 1995.