Trabalhos

• O trabalho é em grupos de três.
• Cada grupo escolhe um problema e uma meta-heurística.
• Tarefa da cada grupo:
  • Formular o problema como programa linear
  • Resolver as instâncias definidos (abaixo) com um solver genérico (p.ex. GLPK,SCIP)
  • Definir e implementar e meta-heurística escolhida para o problema
  • Resolver as instâncias definidas com a meta-heurística
  • Documentar e analisar os experimentos: relatório
  • Apresentar os resultados: apresentação em aula

• Como apresentar
• Apresentar uma proposta ate 11/12/2009.
  • Contéudo: Definição dos principais elementos da abordagem (vizinhanças, etc.)
• Prazos Entrega do trabalho escrito: 23/12/2009.

Definição dos problemas

• Coloração de grafos
  • Instâncias, melhores valores conhecidos e limite superior da solução ótima:

• Corte máximo (baixar set1)
  • Instâncias e melhores valores conhecidos:

• Minimização da largura de banda de matrizes
  • Instâncias e melhores valores conhecidos:

Obs: As instâncias west0167, mcca e fs_183_1 são assimétricos, mas devem ser considerados simétricos na solução do problema, i.e. caso a_ij ou a_ji é diferente de 0, consideramos a_ij=a_ji=1.

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

• Todas implementações devem aceitar uma instância no formato do problema na entrada padrão (stdin) e imprimir a melhor solução encontrada na saida padrão (stdout).
• Os principais parametros do método devem ser definíveis pela linha de comando.
• O primeiro parâmtero da linha de comando é o nome de um arquivo para gravar a melhor solução encontrada.

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. Todas escolhas feitas para aplicar a meta-heuristica para o problema em questão devem ser claramente relatadas. Isso inclui a representação do problema, a função objetivo, a geração da solução inicial, a vizinhança e a estratégia de escolha em caso de buscas locais, os operadores (crossover,mutação) em caso de algoritmos genéticos, outros parameteros do métodos (temperature,lista tabu e tenure,…), critério de terminação. (Essa lista não é exhaustiva.)

• Avaliação experimental
  

Reprodutibilidade: Documentação das instâncias, tempo de execução, parametros, número de experimentos, semente do gerador randômico, etc. Método de escolha de parâmetros. 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: 37/41. A=Apresentação, R=Relatório, C=Código.