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

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

  * O trabalho é em grupos de três.
  * Cada grupo escolhe **um problema** e **uma meta-heurística**.
  * Tarefa de cada grupo:
      - 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.ufrgs.br/propesq/seminarios/apresentacaooral.ppt|Como apresentar]]
  * :!: **Apresentar uma proposta ate 5/12/2010**.
    * Contéudo: Definição dos principais elementos da abordagem (vizinhanças, etc.)
  * **Prazos** Entrega do trabalho escrito: 12/12/2010.

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

  - [[http://www.or.deis.unibo.it/research_pages/ORinstances/BPPC.html|Bin Packing Problem with Conflicts]]
    - Obs: Substituir instâncias NU_<x>_9.txt por U_<x>_8.txt.
  - [[http://www.fceia.unr.edu.ar/~daniel/ecopt|Equitable Coloring Problem]]
  - [[http://www.or.deis.unibo.it/research_pages/ORinstances/PCmax.htm|Sequenciamento em máquinas paralelas]]

===== 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 parametros 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    | BT+MP     | Alessandro, Daniel, Maurício                                     | X | X | X | X |
| 2    | GRASP+MP  | César, Jefferson, João                                           | X | X | X | X |
| 3    | GA+MP     | Anderson, Alexandre, Guilherme Dias                              | X |   | X |   |
| 4    | BP+GA     | Diogo, <del> Guilherme Teixeira </del>, Guilherme Severo, Paula  | X | X | X | X |
| 5    | BP+GRASP  | Guilherme Schievelbein, Fernando, José                           | X | X | X | X |
| 6    | SA+MP     | <del> Guilherme Severo, Karina, Ricardo </del>                   |   |   |   |   |
| 7    | EC+GA     | Éderson, Leandro, Maitê                                          | X |   | X | X |
| 8    | EC+VNS    | Diogo Cravo, Lucas Freire, <del>Lucas Tomasi </del>              | X |   | X | X |
| 9    | EC+SA     | Luca Barreto, Felipe                                             | X | X | X | X |
#Escolhas: 26/32. P=Proposta, A=Apresentação, R=Relatório, C=Código.

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

^       ^ BP  ^ EC  ^ MP ^
| SA    |    |  X  |  X  |
| VNS   |    |  X  |     |
| BT    |    |     |  X  |
| AG    | X  |  X  |  X  |
| GRASP | X  |     |  X  |

===== Agenda =====
^ Data ^ Hora ^ Apresentação ^
| 12/12 |  10.30 |  EC+SA               |
| 12/12 |  10.50 |  EC+GA               |
| 12/12 |  11.10 |  EC+VNS              |
| 12/12 |  11.30 |  BP+GA               |
| 12/12 |  11.50 |  BP+GRASP            |
| 14/12 |  10.30 |  MP+GA               |
| 14/12 |  10.50 |  MP+BT               |
| 14/12 |  11.10 |  <del> MP+SA </del>  |
| 14/12 |  11.30 |  MP+GRASP            |