====== Trabalhos ======

===== Considerações gerais =====

  * O trabalho é em grupos de 2.
  * Cada grupo escolhe **um problema** e **uma meta-heurística**.
  * Tarefa de todos:
      - Formular o problema como programa linear ou inteiro
      - Resolver as instâncias definidas (abaixo) com um solver genérico (p.ex. CPLEX,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**

  * :!: **Apresentar uma proposta ate 5 de junho**.
    * 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.) e a formulação matemática do problema.
  * :!: **Entrega do trabalho escrito: 19 de junho**.
  * Trabalho: {{tp20171.pdf|Como perder pontos?}}

===== Problemas =====

{{T20191.pdf|Definição dos problemas}}

===== Meta-heurísticas =====

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

===== Convenções da implementação =====

  * 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.

===== Documentação e critérios de avaliação =====

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 parâmetros do métodos (temperatura,lista tabu e tenure,...), critério de terminação. (Essa lista não é exaustiva.)
  * Avaliação experimental\\
    Reprodutibilidade: Documentação das instâncias, tempo de execução, parâmetros, número de experimentos, semente do gerador randômico, 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. 
  * Implementação\\
    Critérios básicas da eng. de SW: documentação, legibilidade, etc.

O trabalho consiste em:
  * Um [[:relatorio|relatório]] com a documentação da solução com resultados e discussão (veja um {{ga-r.pdf|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 bibliotecas proprietárias e pode ser compilado e executado usando somente software livre).
  * Uma apresentação em aula. Como apresentar? [[http://lmgtfy.com/?q=como+apresentar+bem+um+artigo+cientifico|Mais informações.]]


**[[trabalho-faq|Perguntas frequentes (FAQ)]]**
===== Grupos e trabalhos selecionados =====

^ No. ^ Trabalho ^ Nome   ^  P  ^  A  ^  R  ^  C  ^
|   1 | ACDM+SA.     |  Catarina, Eduardo        |  o.  |  o  |  o  |  o  |
|   2 | DMTE+SA.     |  Ivan, Bernardo           |  o.  |  o  |  o  |  o  |
|   3 | MAED+SA.     |  Leonardo                 |  o.  |  o  |  o  |  o  |
|   4 | DMTE+BT.     |  Felipe Girardi, Lucca    |  o.  |  o  |  o  |  o  |
|   5 | MAED+BT.     |  Mateus, Ricardo          |  o.  |  o  |  o  |  o  |
|   6 | ACDM+BT.     |  Liliane, Jordano         |  o.  |  o  |  o  |  o  |
|   7 | MAED+ILS.    |  Guilherme, Marlize       |  o.  |  o  |  o  |  o  |
|   8 | ACDM+VNS.    |  Jéferson                 |  o.  |  o  |  o  |  o  |
|   9 | MAED+AG.     |  Lucas, Arthur            |  o.  |  o  |  o  |  o  |
|  10 | ACDM+AG.     |  Iron, Matheus            |  o.  |  o  |  o  |  o  |
|  11 | DMTE+ILS.    |  <del>Lucas Corssac</del>, Mauricio  |  o.  |  o  |  o  |  o  |
|  12 | MAED+GRASP  |  Giovana, Yuri            |  o.  |  o  |  o  |  o  |

Status: 27 de junho.\\
#Trabalhos definidos: 21/31.

A=Apresentação, R=Relatorio, C=Codigo. <html>&#x2713;</html> (+x): entregue (com atraso de x dias).

==== Seleções ====

^       ^  MAED  ^  ACDM  ^  DMTE  ^
| SA    |   X    |    X   |    X   |
| ILS   |   X    |        |    X   |
| IGA   |        |        |        |
| BT    |   X    |    X   |    X   |
| AG    |   X    |    X   |        |
| GRASP |   X    |        |        |
| VNS   |        |    X   |        |

MAED = Menor árvore enraizada direcionado

ACDM = Agendamento com distâncias mínimas

DMTE = Distribuição de menor tempo de espera


===== Agenda =====


^ Data ^ Hora ^ Apresentação ^
| 24/06 |  10.30 |  DMTE+BT     |  
| 24/06 |  10.46 |  ACDM+SA     |  
| 24/06 |  11.02 |  ACDM+AG     |  
| 24/06 |  11.18 |  MAED+BT     |  
| 24/06 |  11.34 |  MAED+AG     |
| 24/06 |  11.50 |  <del>DMTE+ILS</del>    |  
| 26/06 |  10.30 |  MAED+ILS    |
| 26/06 |  10.46 |  MAED+SA     |  
| 26/06 |  11.02 |  ACDM+BT     |  
| 26/06 |  11.18 |  DMTE+SA     |  
| 26/06 |  11.34 |  ACDM+VNS    |
| 26/06 |  11.50 |  MAED+GRASP  |
| 26/06 |  12.05 |  DMTE+ILS    |