====== Trabalhos ====== ===== Considerações gerais ===== * O trabalho é em grupos de dois. * 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** * Aprende as [[:regras para escrever bem]] e [[http://www.ufrgs.br/propesq/seminarios/apresentacaooral.ppt|como apresentar]] * :!: **Apresentar uma proposta ate 24/06/2011**. * Contéudo: Definição dos principais elementos da abordagem (vizinhanças, etc.) * **Prazos** Entrega do trabalho escrito: 04/07/2011. ===== Problemas ===== {{:inf05010:t-2011-1d.pdf|Definição dos problemas}} * [[http://people.brunel.ac.uk/~mastjjb/jeb/orlib/tableinfo.html|Timetabling (TT)]] * Instâncias, melhores valores conhecidos e limite superior da solução ótima: ^ Instância ^ c ((Número de colisões)) ^ | hdttp4 | 0 | | hdttp5 | 0 | | hdttp6 | 0 | | hdttp7 | 0 | | hdttp8 | 0 | //Observação//: A função objetivo é a soma do número de colisões por período. O número de colisões num período é a soma do número de colisões por curso, professor ou sala. Para cada elemento (curso, professor, sala) o número de colisões é igual ao número de ocorrências do elemento no período menos um, mas não menos que 0. * [[http://people.brunel.ac.uk/~mastjjb/jeb/orlib/cspinfo.html|Alocação de tripulações (AT)]] * Instâncias e valores ótimos: ^ Instância ^ Número de tarefas ^ Número de tripulações ^ Valor ótimo ^ | csp50 | 50 | 31 | 1872 | | csp100 | 100 | 48 | 3905 | | csp150 | 150 | 73 | 5347 | | csp200 | 200 | 97 | 6288 | | csp250 | 250 | 112 | 7707 | | csp300 | 300 | 133 | 9026 | | csp350 | 350 | 148 | 10378 | | csp400 | 400 | 163 | 11696 | | csp450 | 450 | 186 | 12232 | | csp500 | 500 | 208 | 12772 | * [[http://www.mech.kuleuven.be/en/cib/op|Orientação (O)]] * Instâncias e melhores valores conhecidos: ^ Instância ^ Tempo D ^Pontuação ^ c ((Melhor valor conhecido)) ^ | brazil58 | 12698 | Tipo 1 | 46 | | eil101 | 315 | Tipo 1 | 64 | | gi1262 | 1189 | Tipo 1 | 158 | | brazil58 | 12698 | Tipo 2 | 2220 | | eil101 | 315 | Tipo 2 | 3655 | | gi1262 | 1189 | Tipo 2 | 8321 | | brazil58 | 12698 | Tipo 3 | 1702 | | eil101 | 315 | Tipo 3 | 3345 | | gi1262 | 1189 | Tipo 3 | 9246 | | Chao64 | 15 | - | TBD | | Chao64 | 80 | - | TBD | | Chao66 | 5 | - | TBD | | Chao66 | 130 | - | TBD | As instâncias brazil58, eil101 e gi1262 encontram-se na [[http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95|TSPLIB]]. O tipo de pontuação é explicado na {{:inf05010:t-2011-1c.pdf|definição dos problemas}} Observações: * Para as instâncias Chao, o ponto inicial é o primeiro ponto do arquivo e o ponto final o segundo ponto do arquivo. Ver a {{http://www.mech.kuleuven.be/en/cib/op/instances/OP_format/view|descrição do formato}}. * Para as instâncias do TSPLIB, o ponto inicial e final é o primeiro ponto (o depot). ===== 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). //Observação//: No caso do problema de Timetabling a entrada padrão consiste do conteúdo do arquivo "note" seguido do conteúdo do arqivo "req". * Os principais parâmetros do método devem ser definíveis pela linha de comando. ===== 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 ^ CP ^ A ^ R ^ C ^ | 1 | O+GRASP | Gabriel Visconti, Oendel Merlo | ✓ | - | - | - | | 2 | O+SA | Marcelo Rebeldo Benites, Gabriel Roleto | ✓ (+5) | ✓L | ✓ | ✓ | | 3 | O+BT | Gustavo Schmid de Jesus, Guilherme Martini | ✓ | ✓L | ✓ | ✓ | | 4 | O+VNS | Dennis Giovani Balreira, Hugo Schroter Lazzari | ✓ | ✓L | ✓ | ✓ | | 5 | TT+AG | Lisardo Sallaberry Kist, Vítor Fortes Rey | ✓ (+6) | ✓ | ✓ | | | 6 | O+GA | Ricardo Rapacki, Anderson Foscarini | ✓ | ✓L | ✓X | ✓ | | 7 | TT+GRASP | John Gamboa, José Luis Damaren Junior | ✓ | ✓ | ✓ | | | 8 | AT+AG | Gustavo Cabral, Frederico Betting | ✓ | ✓ | ✓ | ✓ | | 9 | TT+VNS | Tiago Gomes, Carlos Junges | | - | - | - | | 10 | AT+GRASP | Bernardo, Vinícius | ✓ | - | - | - | | 11 | TT+SA | Diego Toralles Avila, Lucas | ✓ | ✓L | ✓ | ✓ | #Escolhas: 22/26. CP=Checkpoint, A=Apresentação, R=Relatório, C=Código. ✓: Tarefa concluída.\\ (+x): com atraso de x dias.\\ L: Lâminas entregues.\\ ==== Seleções ==== ^ ^ TT ^ AT ^ O ^ | SA | X | | X | | VNS | X | | X | | BT | | | X | | AG | X | X | X | | GRASP | X | X | X | ===== Agenda ===== ^ Data ^ Hora ^ Apresentação ^ | 04/07 | 8.30 | O+GRASP | | 04/07 | 8.50 | O+SA | | 04/07 | 9.10 | O+BT | | 04/07 | 9.30 | O+VNS | | 04/07 | 9.50 | O+GA | | 06/07 | 8.30 | TT+GRASP | | 06/07 | 8.50 | TT+AG | | 06/07 | 9.10 | TT+VNS | | 06/07 | 9.30 | TT+SA | | 06/07 | 9.50 | AT+AG | | 06/07 | 10.10 | AT+GRASP |