Trabalhos

• O trabalho é em grupos de dois.
• Cada grupo escolhe um problema e uma meta-heurística.
• Tarefa de cada grupo:
  • Formular o problema como programa linear ou inteiro
  • Resolver as instâncias definidas (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

• Aprende as regras para escrever bem e como apresentar
• Apresentar uma proposta ate 24/06/2011.
  • Contéudo: Definição dos principais elementos da abordagem (vizinhanças, etc.)
• Prazos Entrega do trabalho escrito: 04/07/2011.

Definição dos problemas

• Timetabling (TT)
  • Instâncias, melhores valores conhecidos e limite superior da solução ótima:

Observação: A função objetivo é a soma do número de colisões por período. O número de colisões num período é a soma do número de colisões por curso, professor ou sala. Para cada elemento (curso, professor, sala) o número de colisões é igual ao número de ocorrências do elemento no período menos um, mas não menos que 0.

• Alocação de tripulações (AT)
  • Instâncias e valores ótimos:

• Orientação (O)
  • Instâncias e melhores valores conhecidos:

As instâncias brazil58, eil101 e gi1262 encontram-se na TSPLIB. O tipo de pontuação é explicado na definição dos problemas

Observações:

• Para as instâncias Chao, o ponto inicial é o primeiro ponto do arquivo e o ponto final o segundo ponto do arquivo. Ver a descrição do formato.
• Para as instâncias do TSPLIB, o ponto inicial e final é o primeiro ponto (o depot).

• 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).

Observação: No caso do problema de Timetabling a entrada padrão consiste do conteúdo do arquivo “note” seguido do conteúdo do arqivo “req”.

• Os principais parâmetros do método devem ser definíveis pela linha de comando.

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: 22/26. CP=Checkpoint, A=Apresentação, R=Relatório, C=Código.

✓: Tarefa concluída.
(+x): com atraso de x dias.
L: Lâminas entregues.