Pesquisa Operacional 2

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.

• 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.
  • Instruções para download (atualizado em agosto de 2026)

• 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 instalá-lo na sua máquina antes; siga as instruções para download. 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.

1. O modelo de programação linear inteira mista
2. Exemplos de aplicações
   Referência: Goldbarg, M. C.; Luna, H. P. L. Otimização combinatória e programação linear: modelos e algoritmos. Elsevier, 2ed, 2005
3. Exemplos de problemas e respectivos pacotes/códigos para uso no Julia, veja este link

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

2. 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

   2. Inserção de restrições/cortes no quadro simplex ótimo e o método dual simplex (conteúdo de PO I, revisão)
      Referência: Bazaraa, M. S.; Jarvis, J. J.; Sherali, H. D. Linear Programming and Network Flows. Wiley, 4ed, 2010

   3. Método de enumeração e poda (Branch-and-bound) baseado em relaxação linear
      Referências:
      1) Goldbarg, M. C.; Luna, H. P. L. Otimização combinatória e programação linear: modelos e algoritmos. Elsevier, 2ed, 2005
      2) Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021

   4. Exemplo completo de aplicação do Branch-and-Bound (contém resumo sobre inserção de restrições no quadro simplex ótimo)

   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
   6. EXERCÍCIOS: Veja Lista 1
3. Método de planos de corte
   Referência: Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021
   1. Desigualdades válidas
   2. Cortes fracionários de Gomory via quadro simplex
      Referência: Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021
   3. Esquema geral do método

4. Método de enumeração e poda com adição de cortes (Branch-and-cut)
   Referências:
   1) Goldbarg, M. C.; Luna, H. P. L. Otimização combinatória e programação linear: modelos e algoritmos. Elsevier, 2ed, 2005
   2) Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021

5. Comentários sobre o 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
6. Comentários sobre os métodos Branch-and-price e Branch-cut-and-price
   Referência: Wolsey, L. A. Integer Programming. 2ed, Wiley, 2021

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

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