====== Trabalhos ======
===== Considerações gerais =====
* O trabalho é em grupos até dois.
* 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**
* O trabalho é estruturado em quatro etapas
^ Etapa ^ Prazo ^ Entregáveis ^
| 1 | 25 de abril | Descrição e implementação do modelo matemático com resultados (20%) |
| 2 | 02 de maio | Proposta concreta com descrição de heurística e de todos componentes heurístcas aplicados ao problema (25%) |
| 3 | 13 de maio | Trabalho escrito final (parte do modelo e da heurística) (35%) |
| 4 | 13 e 18 de maio | Apresentação do trabalho (20%) |
* Conteúdo da proposta: 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.
* Trabalho: {{tp20171.pdf|Como perder pontos?}}
===== Problemas =====
{{t20202.pdf|Definição dos problemas}} :!: Atualizado: 25 de março!
===== 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)]]**
===== Trabalhos selecionados =====
^ No. ^ Trabalho ^ Nome ^ E1 ^ E2 ^ E3 ^ E4 ^
| 1 | RMV+SA | Jéssica & Roberta | | - | ✓ | ✓ |
| 2 | RMV+AG | Tiago & Alexandre | ✓ | ✓ | ✓ | ✓ |
| 3 | RMV+GRASP | Gabriel | - | | | |
| 4 | PMD+SA | Luiza & Francielle | ✓ | ✓ | ✓ | ✓ |
| 5 | RMV+ILS | Argel & Matheus | ✓ | ✓ | ✓ | ✓ |
| 6 | RMV+VNS | Lucas & Renan | ✓ | ✓ | ✓ | ✓ |
| 7 | RMV+BT | Andrei & Rafael | ✓ | ✓ | ✓ | ✓ |
| 8 | CMB+GRASP | Andrei & Augusto | ✓ | ✓ | ✓ | ✓ |
| 9 | PMD+BT | Felipe & Isis | ✓ | ✓ | | |
| 10 | PMD+VNS | Vagner | ✓ | - | | |
| 11 | CMB+GA | Gabriel RP & Arthur | ✓ | ✓ | ✓ | ✓ |
| 12 | CMB+SA | Bruna & Gessica | ✓ | ✓ | ✓ | ✓ |
| 13 | CMB+BT | Fernando | ✓ | ✓ | ✓ | |
| 14 | CMB+ILS | Renan | - | - | | |
| 15 | CMB+VNS | Aline & Mayra | ✓ | ✓ | ✓ | ✓ |
Status: 17 de maio.\\
#Trabalhos definidos: 26/30.
A=Apresentação, R=Relatorio, C=Codigo. (+x): entregue (com atraso de x dias).
==== Seleções ====
^ ^ CMB ^ RMV ^ PMD ^
| SA | X | X | X |
| ILS | X | X | |
| IGA | | | |
| BT | X | X | X |
| AG | X | X | |
| GRASP | X | X | |
| VNS | X | X | X |
CMB = Coloração mais balanceada\\
RMV = Rota mais valiosa\\
PMD = Partição mais distante
===== Agenda =====
^ Data ^ Hora ^ Apresentação ^
| 13/05 | 13.30 | [Transferido] |
| ::: | 13.44 | RMV+AG |
| ::: | 13.58 | RMV+ILS |
| ::: | 14.12 | PMD+VNS |
| ::: | 14.26 | RMV+BT |
| ::: | 14.40 | CMB+BT |
| ::: | 14.54 | CMB+VNS |
| 18/05 | 13.30 | PMD+BT |
| ::: | 13.44 | CMB+GRASP |
| ::: | 13.58 | CMB+GA |
| ::: | 14.12 | PMD+SA |
| ::: | 14.26 | RMV+VNS |
| ::: | 14.40 | CMB+SA |
| ::: | 14.54 | RMV+SA |