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








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

  * O trabalho pode ser feito em grupos de dois ou três.
  * Cada grupo escolhe **um problema** e ** uma meta-heurística**.
  * Cada grupo implementa o problema, conduz testes com instâncias definidas (listadas abaixo), documenta os resultados e apresenta-los.
  * [[http://www.ufrgs.br/propesq/seminarios/apresentacaooral.ppt|Como apresentar]]
  * :!: **Apresentar uma proposta ate 28/11/2008**.








===== Problemas =====
{{t.pdf|Definição dos problemas}}

  * [[http://staffweb.cms.gre.ac.uk/~wc06/partition|Bi-particionamento de grafos]]
    * Instâncias: add20,data,3elt,uk,add32,bcsstk33,whitaker3,crack,wing_nodal,fe_4elt2,vibrobox,bcsstk29,4elt,fe_sphere,cti,memplus
  * [[http://www.satlib.org|Satisfatibilidade máxima (MAX-SAT)]]
    * Instâncias ((Obs: Todas instâncias são satisfatíveis, tal que o valor da solução ótima é o número de claúsulas.)): uf75-325(31,41),uf125-538(52,96),uf175-753(53,58),uf250-1065(97,93),logistics.a,logistics.b,qg4-08,qg4-09,qg6-09,qg7-09

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

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



===== 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, por exemplo representação do problema e a seleção das operações.
  * Avaliação experimental\\
    Reprodutibilidade: Documentação das instâncias, tempo de execução, parametros, número de experimentos, semente do gerador randômico, etc. Discussão e conclusões.
  * Implementação\\
    Critérios básicas da eng. de SW: documentação, legibilidade, etc.

O trabalho consiste em:
  * Um relatório com a documentação da solução com resultados e discussão (veja um {{sa-r.pdf|exemplo}}).
  * 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 ^ A ^
| 1    | MAXSAT+VNS  | Rodrigo Santos, Henrique Valer |  |
| 2    | GBP+GA      | Guilherme Lima, Giovanni Rinaldi, Roger Gouveia |  |
| 3    | MAXSAT+SA   | Leandro Vasconcelos, Francisco Rodrigues |  |
| 4    | GBP+SA      | Leonardo, Júlio, Wagner | {{gbp-sa.pdf|A}} |
| 5    | MAXSAT+GRASP | Daniel, Soares, Gabriel Pereira, Vanius Zapalowski |  |
| 6    | MAXSAT+BT    | Marcius Vieira, Rosele Schmidt, Soraya Hossain |  |
| 7    | GBP+BT       | Cezar Rosa, Bruno | {{gbp-bt.pdf|A}} |
| 8    | MAXSAT+GA    | Felipe, Adrian, Thiago |  |
| 9    | GBP+GRASP    | Carlos | {{gbp-grasp.pdf|A}} |
#Escolhas: 20/27.






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

^       ^ BPG  ^ MAXSAT  ^
| SA    |  X  |  X  |
| VNS   |     |  X  |
| BT    |  X  |  X  |
| GA    |  X  |  X  |
| GRASP |  X  |  X  |




===== Agenda =====
^ Data ^ Hora ^ Apresentação ^
| 01/12 | 10.30 |  4 |
| 01/12 | 10.50 |  2 |
| 01/12 | 11.10 |  9 |
| 01/12 | 11.30 |  7 |
| 01/12 | 11.50 |   |
| 03/12 | 10.30 |  3 |
| 03/12 | 10.50 |  6 |
| 03/12 | 11.10 |  8 |
| 03/12 | 11.30 |  5 |
| 03/12 | 11.50 |  1 |