====== Trabalhos ====== ===== Considerações gerais ===== * O trabalho é individual. * 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. 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** * [[http://www.propesq.ufrgs.br/eventos/2012/seminarios2012.php|Como apresentar]] * :!: **Apresentar uma proposta ate 5/6/2013**. * Contéudo: Definição dos principais elementos da abordagem (vizinhanças, etc.) * **Prazos** Entrega do trabalho escrito: 26/6/2013. ===== Problemas ===== {{t-2013-1.pdf|Definição dos problemas}} - [[http://staffweb.cms.gre.ac.uk/~wc06/partition|Biparticionamento de grafos]] - [[http://www.satlib.org|MAX-SAT]] - [[http://www.inf.ufrgs.br/~mrpritt/Instances.zip|Sudoku]] ===== 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. **[[trabalho-faq|Perguntas frequentes (FAQ)]]** ===== Grupos e trabalhos selecionados ===== ^ No. ^ Trabalho ^ Grupo ^ P ^ A ^ R ^ C ^ | 1 | SAT+GRASP | Vinicius Rigon | x | x | | | | 2 | SAT+VNS | Lucas Lazzari Tomasi | ✓ | | ✓ | ✓ | | 3 | SAT+BT | Luan Fonseca Garcia | ✓ | ✓ | ✓ | ✓ | | 4 | SD+SA | Ricardo Godoy | ✓ | ✓ | ✓ | ✓ | | 5 | SD+AG | Lucas Cardoso | ✓ | ✓ | | | | 6 | SD+BT | Ramon Zimmermann Schultz | ✓ | ✓ | ✓ | ✓ | | 7 | SAT+SA | Charles Arnoud | ✓ (+6) | ✓ | ✓ | ✓ | | 8 | GBP+VNS | Neimar Braga | ✓ (+12) | ✓ | ✓ | ✓ | | 9 | SD+VNS | Matheus Marchini | ✓ | ✓ | ✓ | ✓ | | 10 | GBP+BT | Felipe Fogazzi | ✓ (+7) | | | | | 11 | GBP+GA | Guilherme Longoni | x | (✓) | | | | 12 | SD+GRASP | Eduardo Graebin | ✓ (+12) | x | | | Status: 2 de julho.\\ #Escolhas: 12/15. P=Proposta, A=Apresentação, R=Relatório, C=Código. ✓ (+x): tarefa feita (com atraso de x dias). ==== Seleções ==== ^ ^ GBP ^ SAT ^ SD ^ | SA | X | X | X | | VNS | X | X | X | | BT | X | X | X | | AG | | | X | | GRASP | | X | X | ===== Agenda ===== ^ Data ^ Hora ^ Apresentação ^ | 26/06 | 8.30 | Lucas Cardoso | | 26/06 | 8.50 | Ramon | | 26/06 | 9.10 | Ricardo | | 26/06 | 9.30 | Matheus | | 26/06 | 9.50 | Eduardo | | 01/07 | 8.30 | Vinícius | | 01/07 | 8.50 | Luan | | 01/07 | 9.10 | Lucas Cardoso | | 01/07 | 9.30 | Charles | | 01/07 | 9.50 | Guilherme | | 03/07 | 8.30 | Felipe | | 03/07 | 8.50 | Neimar | | 03/07 | 9.10 | Lucas Tomasi | | 03/07 | 9.30 | | | 03/07 | 9.50 | |