Algoritmos Paralelos em Otimização

horário: segundas e quartas de 11 às 13:00h na sala 230B

Ementa da disciplina

• MPI;
• CUDA;
• Estratégias de paralelização de métodos aproximados:
• algoritmos de construção de soluções;
• métodos de busca local;
• algoritmos evolutivos;
• busca tabu;
• GRASP;
• simulated annealing;
• VND;
• VNS; e
• ILS.
• Estratégias de paralelização de métodos exatos;
• Estratégias de balanceamento de carga em algoritmos paralelos;
• Aplicações de algoritmos paralelos em problemas de otimização.

Critério de avaliação

Literatura básica

• Livros texto:
• Enrique Alba (editor), Parallel Metaheuristics: A New Class of Algorithms, Wiley, 2005.
• El-Ghazali Talbi (editor), Parallel Combinatorial Optimization, Wiley, 2006.
• MPI: A Message-Passing Interface Standard, 1994.
• nVidia CUDA C: Programming Guide, Version 3.2, 2010.

Aulas ministradas

• 08/08

  • Apresentação do curso: objetivos, tópicos abordados, literatura básica e critério de avaliação.
  
  

• 10/08

  • Noções de programação paralela.
  
  

• 22/08

  • Introdução a MPI.
  
  

• 24/08

  • Introdução a CUDA.
  
  

• 29/09

  • ILS paralelo para o problema de reoteamento de veículos com janelas de tempo e a instrução MAP_REDUCE.
  
  

• 12/09

  • Nomemclatura usada para classificar programas paralelos;
  • GRASP paralelo; e
  • Exemplo de GRASP paralelo.
  
  

• 14/09

  • Busca tabu paralela.
  
  

• 19/09

  • Simulated Annealing paralelo.
  
  

• 28/09

  • Algoritmo genético paralelo.
  
  

• 03/10

  • VNS paralelo.
  
  

• 05/10

  • Colônias de formigas.
  
  

• 10/10

  • Heurísticas híbridas paralelas.
  
  

• 26/10

  • Branch and bound paralelo.
  
  

• 31/10

  • Programação dinâmica paralela.
  
  

• 23/11

  • Branch and cut paralelo.
  
  

• 28/11

  • Resolução de problemas multicritério em ambientes paralelos.
  
  

• 07/12

  • Apresentação de trabalho computacional.