Pesquisa Operacional 2

Horários das aulas

• Segundas-feiras de 12:00 as 14:00 (Sala 5 Eixo 1, LABMAT)
• Terças-feiras de 16:00 as 18:00 (Sala 11 Eixo 1, LABMAT)

Ementa e programa

Objetivos da disciplina

• Estudar modelos de problemas variados usando as técnicas de programação linear inteira e programação dinâmica
• Promover o uso de pacotes computacionais de resolução de problemas de programação linear Inteira
• Estudar teoria, algoritmos e aplicações de Otimização em Redes

Textos de referência

• Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021
• Bazaraa, M. S.; Jarvis, J. J.; Sherali, H. D. Linear Programming and Network Flows. Wiley, 4ed, 2010
• Hillier, F. S.; Lieberman, G. J. Introdução à Pesquisa Operacional. McGraw-Hill, 8ed, 2006

Textos complementares

• Maculan, N.; Fampa, M. H. C. Otimização linear. Editora UnB, 2006
• Luenberguer; Ye. Linear and Nonlinear Programming. Springer, 2008

Canais de acesso

• E-mail do professor: leonardo.secchin@ufes.br
• Sala do professor: prédio do Departamento de Matemática Aplicada, sala 08

Formas de avaliação

• provas escritas, listas de exercícios, trabalhos computacionais ou apresentações orais.

Conteúdo

A linguagem de programação Julia

Julia é uma linguagem de programação de alto nível surgida em 2012, que implementa várias ferramentas para uso geral em matemática aplicada. Em particular, Julia possui várias ferramentas para otimização. É muito parecida com o Matlab, portanto os códigos são fáceis de entender. Os trabalhos computacionais desta disciplina serão feitos em Julia.

Para uma introdução ao Julia e seu uso em otimização, acesse este link.

Softwares / Interfaces para Julia

• CPLEX
  O CPLEX é um pacote mantido pela IBM e muito utilizado na academia e indústria. Nele há vários métodos para programação linear inteira mista. É um software proprietário, mas estudantes das universidades podem obter licença de uso mediante preencimento de um cadastro. Recomendo familiarizar-se com o pacote desde o início da disciplina.
  • Instruções para download (testado em abril de 2024)

• GLPK
  GLPK é um pacote que implementa vários métodos para programação linear inteira mista. Ao contrário do CPLEX, é software livre, ou seja, você pode instalar e usar sem a necessidade de obter licenças. É uma opção de fácil instalação caso você tenha problemas com o CPLEX.

• Uso dos pacotes no Julia
  Tanto o CPLEX quando o GLPK podem ser utilizados dentro do Julia. Para tanto, basta instalar os pacotes CPLEX.jl e GLPK.jl no seu Julia.
  • Obs: CPLEX.jl não instala o CPLEX automaticamente, você precisa obter a licença e instalar na sua máquina. Já GLPK.jl baixa e instala o GLPK automaticamente.
  • Teste executando o código exemplo para o problema de localização de facilidades não capacitado

Programação inteira e inteira mista

1. Modelagem de problemas
   Referências:
   1) Hillier, F. S.; Lieberman, G. J. Introdução à Pesquisa Operacional. McGraw-Hill, 8ed, 2006
   2) Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021

2. Relaxação Linear e relaxação Lagrangeana
   Referência: Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021

Exemplos de problemas e respectivos pacotes/códigos para uso no Julia

• Vários exemplos neste link

Métodos em programação inteira mista

1. Método de enumeração e poda (Branch-and-bound)
   1. Pré-processamento
      Referências:
      1) Hillier, F. S.; Lieberman, G. J. Introdução à Pesquisa Operacional. McGraw-Hill, 8ed, 2006
      2) Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021
      • Pré-processamento de PL’s: fixação de variáveis, aperto de limitantes das variáveis e identificação de restrições redundantes
      • Identificação de PL’s inviáveis ou ilimitados
      • Estratégias adicionais de pré-processamento para problemas com variáveis inteiras e binárias: aperto de restrições

   2. Inserção de restrições no quadro simplex e o método dual simplex (revisão)
      Referências:
      1) Hillier, F. S.; Lieberman, G. J. Introdução à Pesquisa Operacional. McGraw-Hill, 8ed, 2006
      2) Bazaraa, M. S.; Jarvis, J. J.; Sherali, H. D. Linear Programming and Network Flows. Wiley, 4ed, 2010

   3. Branch-and-bound baseado em relaxação linear
      Referência: Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021

   4. Branch-and-bound - exemplos com variáveis inteiras e binárias
      Referência: Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021

   5. Exemplo de problema inviável em que branch-and-bound fracassa
      Referência: Jeroslow. Trivial integer programs unsolvable by branch-and-bound. Mathematical Programming 6, 105-109 (1974)
      • Código Julia
2. Método de planos de corte
   Referência: Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021
   1. Desigualdades válidas
   2. Esquema geral do método
3. Método Branch-and-cut
   Referência: Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021
   1. Cortes de Chvatal-Gomory
   2. Cortes fracionários de Gomory via quadro simplex
4. Método de geração de colunas
   Referências:
   1) Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021
   2) Maculan, N.; Fampa, M. H. C. Otimização linear. Editora UnB, 2006
   3) Tópico 6 deste link
   1. Geração de colunas aplicado ao problema de corte de estoque (cutting stock)
      • Código Julia com instâncias do problema
   2. Decomposição de Dantzig-Wolfe

5. Comentários sobre os métodos Branch-and-price e Branch-cut-and-price
   Referência: Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021

6. Comentários sobre o uso de heurísticas/metaheurísticas no contexto de métodos enumerativos
   Referência: Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021

Otimização em redes

Referência: Bazaraa, M. S.; Jarvis, J. J.; Sherali, H. D. Linear Programming and Network Flows. Wiley, 4ed, 2010

1. Conceitos básicos (grafos, árvore etc)
2. Exemplos: caminho mínimo, fluxo máximo, fluxo de custo mínimo, problemas do transporte e atribuição
3. Problema do transporte: resolução via simplex
   1. Matriz totalmente unimodular
   2. Obtendo uma base inicial viável
   3. Quadro simplex
   4. Caso particular: problema de atribuição
      • Relaxação linear, matriz totalmente unimodular e integralidade das soluções
4. Problema de fluxo de custo mínimo
   1. Método simplex de rede
5. Problema do menor caminho
   1. Algoritmo de Dijkstra para custos não negativos

Programação dinâmica

Referência: Hillier, F. S.; Lieberman, G. J. Introdução à Pesquisa Operacional. McGraw-Hill, 8ed, 2006

1. Princípios da programação dinâmica
2. Exemplo simples: sequência de Fibonacci
3. Problema da mochila 0-1
4. Exemplo protótipo, seção 10.1 do livro de Hillier e Lieberman
5. Exemplos da seção 10.3 do livro de Hillier e Lieberman
6. Outros exemplos
   1. Subset sum
   2. O algoritmo de Dijkstra (tópico anterior) usa conceitos de programação dinâmica