Tópicos em Pesquisa Operacional

Ementa

Ementa variável.

TÓPICO 1: Métodos de pontos interiores para programação linear

Conteúdo:

1. Preliminares e o método primal afim escala (Dikin)
   • Leitura introdutória: capítulo 1 do livro de Wright (páginas 1 a 6)
2. Método dual afim escala
3. Método primal dual afim escala
   • Sobre a heurística Approximate Minimum Degree (AMD)
     • Artigo que propôs a heurística
     • Muita pesquisa foi feita sobre métodos para reordenamento. Julia e Matlab usam a eficiente rotina CHOLMOD.
   • Exemplo da diferença entre usar ou não AMD antes de Cholesky (código Julia)
4. Tragetória central e o método seguidor de caminhos
5. Método preditor-corretor de Mehrotra
   • Veja a descrição do método preditor-corretor do CPLEX (CPLEX Barrier)

EXERCÍCIOS DO TÓPICO

• Código base para o exercício 6 (primal-dual afim escala em Julia)
• Estrutura de esparsidade dos problemas-teste selecionados
• Resultados numéricos esperados nos problemas-teste selecionados
• “Código extra”: interface Julia para o método preditor-corretor do CPLEX
• Tulip.jl, uma boa implementação do método preditor-corretor com múltiplas correções em Julia

Referências:

• Vanderbei, R. J. Linear programming. Foundations and extensions. 3 ed, Springer, 2008.
• (capítulo 14) Nocedal, J.; Wright, S. J. Numerical optimization. Springer, 2006.
• (capítulo 9) Maculan, N.; Fampa, M. H. C. Otimização linear. Editora UnB, 2006.

Outras:

• (uma referência super completa para métodos primais-duais) Wright, S. J. Primal-Dual Interior-Point Methods. SIAM, 1997.

TÓPICO 2: A linguagem de programação Julia

Conteúdo:

1. Apresentação
2. Julia para otimização

EXERCÍCIOS DO TÓPICO:

1. Instalar o Julia em sua máquina, de acordo com este link
2. Estudar os exemplos 1, 2, 3, 4, 5, 6, 8, 12 e 14 deste link

Referências:

• Pequeno tutorial sobre Julia e links internos

TÓPICO 3: Comparação de desempenho entre algoritmos

Conteúdo:

1. Introdução
2. Perfis de desempenho de Dolan e Moré
3. O pacote Julia BenchmarkProfiles
4. Análise de perfis através de exemplos
5. Dicas para contagem do tempo de execução

SLIDES

EXERCÍCIOS DO TÓPICO

Referências:

• (artigo que propôs os perfis) Dolan, Elizabeth D.; Moré, Jorge J. Benchmarking optimization software with performance profiles. Math. Program., Ser. A 91: 201-213 (2002). artigo revista; PDF acesso aberto
• (curta explicação – seção 6.3) Ribeiro, A. A; Karas, E. W. Otimização contínua. Cengage, 2014
• (pacote para geração de perfis) Pacote Julia BenchmarkProfiles

TÓPICO 4: Relaxação lagrangiana para programação linear inteira

Conteúdo:

1. Função lagrangiano e a relaxação lagrangiana de um problema linear
   • Explicação do exemplo GAP (Generalized Assignment Problem)
2. Propriedades da função lagrangiano; subgradiente/subdiferencial
3. Método do subgradiente para funções convexas e sua convergência
4. Resolução do problema lagrangiano via método do subgradiente

EXERCÍCIOS DO TÓPICO

• Código base para uso do CPLEX ou GLPK no Julia (problema de localização de facilidades não capacitado)

Referências:

• (artigo guia) Fisher, M. L. The Lagrangian Relaxation Method for Solving Integer Programming Problems. Management Science 27(1), 1-18 (1981) artigo revista (2004); PDF aberto (1981)
• (método do subgradiente e sua convergência – seções 3.1 e 3.2) Bertsekas, D. P. Convex Optimization Algorithms. Athena Scientific, 2015.
• (um panorama geral – capítulo 10) Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021.

Outras:

• (aplicação em branch-and-bound) Florentino, H. O. Relaxação lagrangeana em programação inteira. Dissertação de Mestrado (ICMC/USP), São Carlos, 1990.
• (capítulo 11) Maculan, N.; Fampa, M. H. C. Otimização linear. Editora UnB, 2006.

TÓPICO 5: Algoritmos de otimização em aprendizado de máquina

Conteúdo:

1. Introdução
2. Método do gradiente incremental
3. Um pouco de probabilidade
4. Método do gradiente estocástico (SG) e variantes
5. Convergência do método do gradiente estocástico para funções convexas
6. Treinamento de redes neurais multicamadas tipo feedfoward, backpropagation
7. Experimentos numéricos
   • Diferença entre gradiente incremental e estocástico
   • Pacote com datasets prontos para Julia: MLDatasets.jl
   • Exemplo de uso do Flux no dataset MNIST (código)
   • Sobre o dataset MNIST: wikipedia; página do autor; estatísticas dos dados
   • Exemplos prontos de uso do Flux: model-zoo

Conjunto de dados (datasets) disponíveis para uso:

• UC Irvine Machine Learning Repository
• Datasets no TensorFlow
• Informações variadas sobre vários datasets

Alguns pacotes Julia para aprendizado de máquina:

• Flux.jl (implementado em Julia puro)
• Merlin.jl (implementado em Julia puro)
• ScikitLearn.jl (interface para scikit-learn, implementado em Python)
• TensorFlow.jl (interface para ambiente TensorFlow)

EXERCÍCIOS DO TÓPICO

Referências:

• (introdução aprendizado de máquina) Bottou, L; Curtis, F. E.; Nocedal, J. Optimization Methods for Large-Scale Machine Learning. SIAM Rev., 60(2), 223-311 (2018). artigo revista; PDF acesso livre
• (introdução gradiente incremental – seção 2.1.5) Bertsekas, D. P. Convex Optimization Algorithms. Athena Scientific, 2015.
• (texto sobre probabilidade) Curso “Teoria da Probabilidade” de A. Morgado e R. Teixeira (FGV) (link para notas de aula)
• ((sub)gradiente incremental/estocástico e convergência – seções 8.3, 8.4) Beck, A. First-Order Methods in Optimization. MOS-SIAM Series on Optimization, SIAM, 2017.

Outras:

• (curso básico) Livro on-line “Neural Networks and Deep Learning”
• (resumo de vários métodos) paperswithcode.com

TÓPICO 6: Geração de colunas

Conteúdo:

1. Elementos de Programação Linear (revisão): representação de poliedros e método Simplex
   • Revisão completa e exemplos no livro de Maculan e Fampa e nas notas de aula de PL disponibilizadas via AVA
2. Método de geração de colunas para problemas lineares (PLs) contínuos
3. Decomposição de Dantzig-Wolfe, PLs com variáveis inteiras, comentários sobre branch-and-price
4. Exemplo: geração de colunas aplicado ao problema cutting stock
   • Referência: Seções 6.1 e 6.2 de Bertsimas, Tsitsiklis - Introduction to Linear Optimization (1997)
   • Código Julia + instâncias
   • URL para instâncias utilizadas

EXERCÍCIOS DO TÓPICO

Leituras interessantes:

• Geralmente o método de geração de colunas vem associado ao método Simplex, ou seja, o problema auxiliar, que fornece a nova coluna a entrar no problema mestre, é resolvido via Simplex. Mas isso não é obrigatório! É possível usar métodos de pontos interiores (tópico 1) no lugar do Simplex com sucesso. O mesmo vale para geração de colunas dentro de um esquema enumerativo ao resolver problemas com variáveis inteiras. Veja por exemplo este artigo e suas referências.

• Em alguns casos interessantes é possível usar relaxação lagrangiana (tópico 4) nos problemas do método de geração de colunas. Veja por exemplo o capítulo 9 deste livro.

Referências:

• (capítulo 7) Maculan, N.; Fampa, M. H. C. Otimização linear. Editora UnB, 2006.
• (um panorama geral – Capítulo 11) Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021.
• (cutiing stock – seções 6.1 e 6.2) Bertsimas, Tsitsiklis - Introduction to Linear Optimization (1997).

Outra:

• Munari, P.; Morabito, R. A branch-price-and-cut algorithm for the vehicle routing problem with time windows and multiple deliverymen. TOP 26, 437-464 (2018). artigo revista; PDF acesso livre