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

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

  * O trabalho é em grupos até 2.
  * Cada um pode escolher **um problema** e **uma meta-heurística**.
  * Tarefas:
      - Formular o problema como programa linear ou inteiro.
      - Resolver as instâncias definidas (mais informações abaixo) com um solver genérico (p.ex. CPLEX,GLPK,SCIP).
      - Definir e implementar a meta-heurística escolhida para o problema.
      - Resolver as instâncias definidas com a meta-heurística.
      - Documentar e analisar os experimentos num **relatório**.
      - **Apresentar** os resultados em aula.

  * :!: **Submeter uma proposta ate 25 de janeiro 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.) e a formulação matemática do problema.
    * Encaminhar a proposta para marcus.ritt@inf.ufrgs.br
    * Cada proposta vai ter um feedback, mas não é avaliada.
  * :!: **Entrega do trabalho escrito: 15 de fevereiro 2024**
  * Trabalho: {{tp20171.pdf|Como perder pontos?}}

===== Passo a passo =====

  - Ler a {{t20232.pdf|definição dos problemas}}, selecionar um problema.\\
  - Selecionar uma heurística (Aulas 18-20).\\
  - Informar sobre a seleção por email: integrantes, [[2023-2-trabalhos#selecoes|problema e heurística selecionada]]. (Cada combinação problema+heurística é disponível somente uma vez.)\\
  - Submeter uma proposta até 25 de janeiro 2024.\\
  - Entregar o trabalho completo até 15 de fevereiro 2024.\\
  - Apresentar o trabalho numa das aulas previstas no cronograma (a [[2023-2-trabalhos#agenda|agenda]] vai ser definida mais próximo das datas de apresentação).

===== Problemas =====

{{t20232.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, 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.
  * 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)]]**
===== Trabalhos selecionados =====

^ No. ^ Trabalho         ^ Nome                    ^  P     ^  A  ^  R  ^  C  ^
|   1  |  AF+SimAnn  |  Felipe, Henrique      |  ❌  |    ✓      |    ✓     |   ✓      |
|   2  |  VF+SimAnn  |  Bibiana, Luis         |  ✓.  |          |    ✓     |   ✓      |
|   3  |  CATC+BT    |  Flávio, Rafael        |  ✓.  |          |    ✓     |   ✓      |
|   4  |  VF+AG      |  Caetano, Santiago     |  ✓.  |          |    ✓     |   ✓      |

Status: 18 de fevereiro 2024.\\
#Trabalhos definidos: 8.

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

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

^       ^  AF  ^  CATC  ^  VF  ^
| SimAnn  |   X    |        |  X   |
| ILS     |        |        |      |
| IGA     |        |        |      |
| BT      |        |   X    |      |
| AG      |        |        |  X   |
| GRASP   |        |        |      |
| VNS     |        |        |      |

AF = Atrapalhando fugitivos\\
CATC = O caminhante que adorava trilhas curtas\\
VF  = Viagens felizes

===== Agenda =====

^ Data ^ Hora ^ Apresentação ^
| 15/02 |  13.30 |  CATC+BT      |
| :::   |  13.55 |  AF+SimAnn    |
| :::   |  14.20 |  VF+AG        |
| :::   |  14.45 |  VF+SimAnn    |
| 20/02 |  13.30 |        |	    
| :::   |  13.55 |        |	    
| :::   |  14.20 |        |	    
| :::   |  14.45 |        |