====== Trabalhos ======
===== Considerações gerais =====
* O trabalho é em grupos de dois.
* Cada um 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 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.
===== Problemas =====
{{T20142.pdf|Definição dos problemas}}
===== Meta-heurísticas =====
* Simulated annealing (SA)
* Variable neighborhood search (VNS)
* Busca Tabu (BT)
* Algorítmo genético/memético (GA)
* GRASP
===== 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 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.
===== 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 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 [[:relatorio|relatório]] com a documentação da solução com resultados e discussão (veja um {{sa-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 bibliotécas 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 | GRASP+CVH | Gabriel Paula, Alexander | ✓. | | | |
| 2 | BT+VRP | Ana, Tais | ✓. | ✓ | ✓ | ✓ |
| 3 | BT+TTP | Guilherme, Leonardo | ✓ | ✓ | ✓ | ✓ |
| 4 | AG+TTP | Pedro, Lucas | ✓. | ✓ | ✓ | ✓ |
| 5 | BT+CVH | Deividi, Julio | ✓. | ✓ | ✓ | ✓ |
| 6 | SA+TTP | Andre, Mateus | ✓ | ✓ | ✓ | ✓ |
| 7 | SA+VRP | Alan, Wladimir | ✓. | ✓ | ✓ | ✓ |
| 8 | GA+VRP | Iuri | ✓. | | | |
| 9 | SA+CVH | Bruno, Marcos | | | | |
Status: 28 de novembro.\\
#Trabalhos definidos: 17/19.
P=Proposta, A=Apresentação, R=Relatorio, C=Codigo. ✓ (+x): entregue (com atraso de x dias).
==== Seleções ====
^ ^ CVH ^ TTP ^ VRP ^
| SA | X | X | X |
| VNS | | | |
| BT | X | X | X |
| AG | | X | X |
| GRASP | X | | |
CVH = Caixeiro viajante com seleção de hotéis
TTP = Traveling tournament problem
VRP = Roteamento de veículos
===== Agenda =====
^ Data ^ Hora ^ Apresentação ^
| 17/11 | 10.30 | BT+CVH (Deividi,Julio) |
| 17/11 | 10.50 | BT+TTP (Guilherme, Leonardo) |
| 17/11 | 11.10 | SA+TTP (Andre,Mateus) |
| 17/11 | 11.30 | GA+VRP (Iuri) |
| 17/11 | 11.50 | |
| 19/11 | 10.30 | GRASP+CVH (Gabriel Paula, Alexander) |
| 19/11 | 10.50 | AG+TTP (Pedro, Lucas) |
| 19/11 | 11.10 | SA+VRP (Alan, Wladimir) |
| 19/11 | 11.30 | BT+VRP (Ana, Tais) |
| 19/11 | 11.50 | SA+CHV (Bruno, Marcos) |