Trabalhos

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

1. Ler a definição dos problemas, selecionar um problema.
   
2. Selecionar uma heurística (lista abaixo, Aulas 1-3).
   
3. Informar sobre a seleção por email: integrantes, problema e heurística selecionada. (Cada combinação problema+heurística é disponível somente uma vez.)
   
4. Submeter uma proposta para implementação da heurística até 17 de outubro 2024.
   
   • Conteúdo: Definição dos principais elementos da abordagem (representação de uma solução, solução inicial, vizinhanças, critério de parada, etc.).
5. Apresenter uma formulação matemática até 30 de novembro 2024.
   
6. Entregar o trabalho completo até 7 de janeiro 2025.
   
7. Apresentar o trabalho numa das aulas previstas no cronograma (a agenda vai ser definida mais próximo das datas de apresentação).

• Simulated annealing (SimAnn)
• Busca local iterada / Busca gulosa iterada (ILS)
• Busca Tabu (BT)
• Algorítmo genético/memético (GA)
• GRASP
• Variable neighborhood search (VNS)

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.

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 parâmetros do métodos (temperatura,lista tabu e tenure,…), critério de terminação. (Essa lista não é exaustiva.)

Reprodutibilidade: Documentação das instâncias, tempo de execução, parâmetros, número de experimentos, semente do gerador randômico, dados experimentais, etc. Método de escolha de parâmetros. Discussão e conclusões. Em particular: para métodos estocásticos os valores apresentados devem ser médias de pelo menos 5 replicações de cada experimento com sementes diferentes.

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

• 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 saída 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 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.
  • Uma implementação do modelo matemática e da heurística (linguagem arbitrária desde seja padrão sem uso de bibliotecas proprietárias e pode ser compilado e executado usando somente software livre).
  • 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.
  • Protocolos das execuções do solver e da meta-heuristica e outros dados experimentais detalhados;
• Uma apresentação em aula.

• Perguntas frequentes (FAQ)
• Como apresentar? Mais informações.
• Trabalho: Como perder pontos?

Status: 10 de janeiro 2025.
#Trabalhos definidos: 17.

P: Proposta, F: Formulação, A: Apresentação, R: Relatório, C: Código. (+x): entregue (com atraso de x dias).

DOG = Distribuição ótima em GPUs
OCS = O carrossel seguro