Pesquisa Operacional 2

Horários das aulas

• —
• —

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. A seguir você encontra instruções de instalação, bem como exemplos simples que ajudarão você a dar os primeiros passos nas ferramentas de otimização disponíveis no Julia.

• Tutorial para instalação e uso da linguagem de programação Julia
• Julia para Otimização - primeiros passos

Para auxiliá-lo na instalação do Julia pré-compilado + pré-requisitos + pacotes utilizados nas disciplinas de otimização, baixe ESTE SCRIPT e siga as instruções contidas nele (testado no Ubuntu 22.04)

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

• 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