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

  * O trabalho é em grupos de no máximo dois.
  * 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 16/06/2010**.
    * Contéudo: Definição dos principais elementos da abordagem (vizinhanças, etc.)
  * **Prazos** Entrega do trabalho escrito: 23/06/2010.
===== Problemas =====
{{t2010-1.pdf|Definição dos problemas}}

  * [[http://iridia.ulb.ac.be/~cblum/kctlib|Menor árvore de cardinalidade k]]
    * Instâncias, melhores valores conhecidos e limite superior da solução ótima:

^ Nome ^ k ^ Valor ^
| g1000-4-01.dat | 20 | 263 |
| g1000-4-01.dat | 200 | 3308 |
| g1000-4-02.dat | 20 | 281 |
| g1000-4-05.dat | 20 | 268 |
| g1000-4-05.dat | 200 | 3620 |
| g400-4-02.dat	| 20 | 328 |
| g400-4-03.dat	| 20 | 302 |
| g400-4-05.dat	| 20 | 320 |
| bb33x33_2.dat | 100 | 1524 |
| bb33x33_2.dat | 500 | 9465 |
| bb33x33_2.dat | 900 | 20993 |
| bb100x10_1.dat | 100 | 1601 |
| bb100x10_1.dat | 500 | 9961 |
| bb100x10_1.dat | 900 | 22732 |
| le450_15a.dat | 90 | 135 |
| le450_15a.dat | 360 | 1060 |

  * [[http://people.brunel.ac.uk/~mastjjb/jeb/orlib/pmedcapinfo.html|P-Medianas capacitado]] (baixar set1)
    * [[http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/pmedcap1.txt|Instâncias]] e melhores valores conhecidos:

^ Nome ^ Valor ^
|   1 |   713 |
|   2 |   740 |
|   3 |   751 |
|   4 |   651 |
|   5 |   664 |
|   6 |   778 |
|   7 |   787 |
|   8 |   820 |
|   9 |   715 |
|  10 |   829 |
|  11 |  1006 |
|  12 |   966 |
|  13 |  1026 |
|  14 |   982 |
|  15 |  1091 |
|  16 |   954 |
|  17 |  1034 |
|  18 |  1043 |
|  19 |  1031 |
|  20 |  1005 | 

  * [[http://people.brunel.ac.uk/~mastjjb/jeb/orlib/airlandinfo.html|Atterisagem de aviões]]
    * Instâncias e valor da solução ótima conhecidos:

^ Nome ^ Valor ^
| airland1 |    700 |
| airland2 |   1480 |
| airland3 |    820 |
| airland4 |   2520 |
| airland5 |   3100 |
| airland6 |  24442 |
| airland7 |   1550 |
| airland8 |   1950 |

===== 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    |  AA+GRASP |  Bruno Fiss, Kauê  |  |  |  |
| 2    |  MACk+SA  |  Tadeu, Federico  |  |  |  |
| 3    |  MACk+AG  |  Thais, Renato  |  |  |  |
| 4    |  MACk+GRASP  |  Bruno Jurkovski, Marcos  |  |  |  |
| 5    |  AA+AG  |  Christian, Márcio  |  |  |  |
| 6    |  MACk+BT  |  André, Octavio   |  |  |  |
| 7    |  AA+VNS  |  Luiza, Nellison  |  |  |  |
| 8    |  PMC+AG  |  Gustavo, Juliano  |  |  |  |
| 9    |  AA+SA  |  Bruno Marques, Matheus Lehmann  |  |  |  |
| 10   |  AA+BT  |  Angelo Ghezzi, Matheus Jullien  |  |  |  |
| 11   |    |    |  |  |  |
| 12   |    |    |  |  |  |
| 13   |    |    |  |  |  |
#Escolhas: 20/26. A=Apresentação, R=Relatório, C=Código.

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

^       ^ MACk  ^ PMC  ^ AA ^
| SA    |  X  |    |  X  |
| VNS   |    |    |  X  |
| BT    |  X  |    |  X  |
| AG    |  X  |  X  |  X  |
| GRASP |  X  |    |  X  |
===== Agenda =====
^ Data ^ Hora ^ Apresentação ^
| 23/06 |  8.30 |  Grupo 7  |
| 23/06 |  8.50 |  Grupo 10  |
| 23/06 |  9.10 |  Grupo 9  |
| 23/06 |  9.30 |  Grupo 1  |
| 23/06 |  9.50 |  Grupo 5  |
| 28/06 |  8.30 |  Grupo 3  |
| 28/06 |  8.50 |  Grupo 8  |
| 28/06 |  9.10 |  Grupo 2  |
| 28/06 |  9.30 |  Grupo 6  |
| 28/06 |  9.50 |  Grupo 4  |