Trabalhos

• O trabalho é em grupos de dois.
• Cada um escolhe um problema e uma meta-heurística.
• Tarefa de todos:
  1. Formular o problema como programa linear ou inteiro
  2. Resolver as instâncias definidas (abaixo) com um solver genérico (p.ex. CPLEX,GLPK,SCIP)
  3. Definir e implementar e meta-heurística escolhida para o problema
  4. Resolver as instâncias definidas com a meta-heurística
  5. Documentar e analisar os experimentos: relatório
  6. Apresentar os resultados: apresentação em aula

• Apresentar uma proposta ate 29 de outubro.
  • Contéudo: Definição dos principais elementos da abordagem (representação de uma solução, solução inicial, vizinhanças, critério de parada, etc.) e a formulação matemática do problema.
• Nova data limite para propostas: 6 de novembro. Entregas depois dessa data perdem 0.5 pontos por dia na avaliação.
• Prazos Entrega do trabalho escrito: 24 de novembro.

Definição dos problemas

• 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 parâmetros do método devem ser definíveis pela linha de comando.
• O primeiro parâmetro 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).
  • Elementos obrigatórios: Introdução, Formulação, Descrição da solução, Resultados obtidos com análise, Conclusão e Bibliografia.
  • Nos resultados computacionais, uma tabela informando, para cada instância: valor da solução inicial (SI), valor da solução final (SF), desvio percentual da solução final em relação à inicial calculado como 100*(SI-SF)/SI, desvio percentual da SF em relação à solução ótima, tempo computacional da metaheurística, tempo computacional da resolução via solver.
• 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. Como apresentar? Mais informações.

Perguntas frequentes (FAQ)

Status: 28 de novembro.
#Trabalhos definidos: 17/19.

P=Proposta, A=Apresentação, R=Relatorio, C=Codigo. ✓ (+x): entregue (com atraso de x dias).

CVH = Caixeiro viajante com seleção de hotéis

TTP = Traveling tournament problem

VRP = Roteamento de veículos