• O trabalho pode ser feito em grupos de dois ou três.
• Cada grupo escolhe um problema e uma meta-heurística.
• Cada grupo implementa o problema, conduz testes com instâncias definidas (listadas abaixo), documenta os resultados e apresenta-los.
• Como apresentar
• Apresentar uma proposta ate 28/11/2008.

Definição dos problemas

• Bi-particionamento de grafos
  • Instâncias: add20,data,3elt,uk,add32,bcsstk33,whitaker3,crack,wing_nodal,fe_4elt2,vibrobox,bcsstk29,4elt,fe_sphere,cti,memplus
• Satisfatibilidade máxima (MAX-SAT)
  • Instâncias ¹⁾: uf75-325(31,41),uf125-538(52,96),uf175-753(53,58),uf250-1065(97,93),logistics.a,logistics.b,qg4-08,qg4-09,qg6-09,qg7-09

• Simulated annealing (SA)
• Variable neighborhood search (VNS)
• Busca Tabu (BT)
• Algorítmo genético/memético (GA)
• GRASP

O objetivo do trabalho é conhecer uma meta-heurística profundamente e ganhar experiência prática para aplicar-la em novos problemas. A avaliação reflete esse objetivo.

• Entendimento do método
  

Definição e justificativa da abordagem ao problema, por exemplo representação do problema e a seleção das operações.

• Avaliação experimental
  

Reprodutibilidade: Documentação das instâncias, tempo de execução, parametros, número de experimentos, semente do gerador randômico, etc. Discussão e conclusões.

• Implementação
  

Critérios básicas da eng. de SW: documentação, legibilidade, etc.

O trabalho consiste em:

• Um relatório com a documentação da solução com resultados e discussão (veja um exemplo).
• Uma implementação (linguagem arbitrário desde seja padrão sem uso de bibliotécas proprietárias e pode ser compilado e executado usando somente software livre).
• Uma apresentação em aula.

Perguntas frequentes (FAQ)

#Escolhas: 20/27.