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

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

  * O trabalho é em grupos de três.
  * Cada grupo escolhe **um problema** e **uma meta-heurística**.
  * Tarefa da cada grupo:
      * Formular o problema como programa linear
      * Resolver as instâncias definidos (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 11/12/2009**.
    * Contéudo: Definição dos principais elementos da abordagem (vizinhanças, etc.)
  * **Prazos** Entrega do trabalho escrito: 23/12/2009.

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

  * [[http://mat.gsia.cmu.edu/COLOR/instances.html|Coloração de grafos]]
    * Instâncias, melhores valores conhecidos e limite superior da solução ótima:

^ Nome ^ Chi((Número chromático: Menor número de cores necessárias para colorir o grafo)) ^
| dsjc125.1   |   5 |
| dsjc500.1   |  12 |
| dsjc1000.5  |   ? |
| queen13_13  |  13 |
| le450_25a   |  25 |
| school1     |  14 |
| school1_nsh |  14 |
| latin_square_10 |  ? |
| myciel6     |  7 |
| myciel7     |  8 |



  * [[http://heur.uv.es/optsicom/maxcut.html|Corte máximo]] (baixar set1)
    * Instâncias e melhores valores conhecidos:

^Nome ^ Maxcut ^ Limite ^
| g01 |  11624 |  12078 |
| g02 |  11620 |  12084 |
| g14 |   3060 |   3187 |
| g21 |    931 |      ? |
| g22 |  13346 |  14123 |
| g23 |  13317 |  14129 |
| g34 |   1372 |   1541 |
| g35 |   7670 |   8000 |
| g49 |   6000 |      ? |
| g50 |   5880 |      ? |


  * [[http://math.nist.gov/MatrixMarket/collections/hb.html|Minimização da largura de banda de matrizes]]
    * Instâncias e melhores valores conhecidos:

^ Nome ^ Largura ^
| bcsstk01 |   5 |
| bcsstk22 |   9 |
| bcsstk04 |  36 |
| bcsstk05 |  19 |
| bcsstk19 |  13 |
| west0167 |  31 |
| mcca     |  32 |
| fs_183_1 |  52 |
| nos3     |  43 |
| jagmesh1 |  24 |

**Obs**: As instâncias west0167, mcca e fs_183_1 são assimétricos, mas devem ser considerados simétricos na solução do problema, i.e. caso a_ij ou a_ji é diferente de 0, consideramos a_ij=a_ji=1.

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

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


===== Convenções =====

  * 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âmtero 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}}).
  * 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 ^ R ^ C ^
| 1    |  BW+VNS  |  Vinícius,Rafael,Rafael  | X | X | X |
| 2    |  MC+AG   |  Germano,Vítor,Hugo  | X | X | X |
| 3    |  CG+VNS  |  Eduardo,Gabriel,Vanius  | X | X | X |
| 4    |  CG+GRASP  | Cristofer Kremer, Elias Ricken de Medeiros, Vinicius Rigon  | | X | X |
| 5    |  CG+AG  |  Tiago dal Pai, Tiago Santos, Vinícius Schmitt  | X | X | X |
| 6    |  MC+GRASP  |  Leonardo,Kassius,Henrique  | X | X | X |
| 7    |  MC+VNS  |  Matheus Bertram, Germano Carniel, Guilherme  | X | X | X |
| 8    |  BW+AG  |  André Ferreira, Diego, Thomas Rodrigues  | | X | X |
| 9    |  BW+GRASP  |  Alan Delgado, Rodrigo Zembrzuski, Tiago Rosa  | | X | |
| 10   |  CG+BT  |  Marcelo Schmidt, Fábio Prochnow, Aline Lermen  | X | X | X |
| 11   |  CG+SA  |  Priscila, Daniela  | | | |
| 12   |  MC+BT  |  Tomaz Rocha,Wagner Schmitt e Júlia Kikuye  | X | X | X |
| 13   |  ?  |  Matheus Berlesi  | | | |
| 14   |  MC+SA  |  André Siqueira  | X | X | X |
#Escolhas: 37/41. A=Apresentação, R=Relatório, C=Código.

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

^       ^ CG  ^ MC  ^ BW ^
| SA    |  X  |  X  |     |
| VNS   |  X  |  X  |  X  |
| BT    |  X  |  X  |     |
| AG    |  X  |  X  |  X  |
| GRASP |  X  |  X  |     |

===== Agenda =====
^ Data ^ Hora ^ Apresentação ^
| 16/12 |  10.30 |  Grupo 4  |
| 16/12 |  10.50 |  Grupo 11  |
| 16/12 |  11.10 |  Grupo 6  |
| 16/12 |  11.30 |  Grupo 8  |
| 16/12 |  11.50 |  Grupo 1  |
| 21/12 |  10.30 |  Grupo 7  |
| 21/12 |  10.50 |  Grupo 5  |
| 21/12 |  11.10 |  Grupo 9  |
| 23/12 |  10.30 |  Grupo 3  |
| 23/12 |  10.50 |  Grupo 12  |
| 23/12 |  11.10 |  Grupo 13  |
| 23/12 |  11.30 |  Grupo 14  |
| 23/12 |  11.50 |  Grupo 10  |
| 23/12 |  12.10 |  Grupo 2   |