====== Trabalhos ======
===== Considerações gerais =====
* O trabalho é em grupos até 2. Cada grupo escolhe **um problema** e **uma meta-heurística**.
* Tarefas:
- Formular o problema como programa linear ou inteiro.
- Resolver as instâncias definidas (ver abaixo) com um solver genérico (p.ex. CPLEX, GLPK, SCIP).
- Definir e implementar a meta-heurística escolhida para o problema.
- Resolver as instâncias definidas com a meta-heurística.
- Documentar e analisar os experimentos num **relatório**.
- **Apresentar** os resultados em aula.
===== Passo a passo =====
- Ler a {{t20251.pdf|definição dos problemas}}, selecionar um problema.\\
- Selecionar uma heurística ([[https://www.inf.ufrgs.br/~MRPRITT/doku.php?id=inf05010:2025-1-trabalhos#meta-heuristicas|lista abaixo]], Aulas 1-3).\\
- Informar sobre a seleção por email: integrantes, [[2025-1-trabalhos#selecoes|problema e heurística selecionada]]. (Cada combinação problema+heurística é disponível somente uma vez.)\\
- Submeter uma proposta para implementação da heurística até **2 de abril 2025**.\\
* Conteúdo: Definição dos principais elementos da abordagem (representação de uma solução, solução inicial, vizinhanças, critério de parada, etc.).
- Apresenter uma formulação matemática até **31 de maio 2025**.\\
- Entregar o trabalho completo até **25 de junho 2025**.\\
- Apresentar o trabalho numa das aulas previstas no cronograma (a [[2025-1-trabalhos#agenda|agenda]] vai ser definida mais próximo das datas de apresentação).
===== Meta-heurísticas =====
* Simulated annealing (SimAnn)
* Busca local iterada / Busca gulosa iterada (ILS)
* Busca Tabu (BT)
* Algorítmo genético/memético (GA)
* GRASP
* Variable neighborhood search (VNS)
===== 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 parâmetros do métodos (temperatura,lista tabu e tenure,...), critério de terminação. (Essa lista não é exaustiva.)
==== Avaliação experimental ====
Reprodutibilidade: Documentação das instâncias, tempo de execução, parâmetros, número de experimentos, semente do gerador randômico, dados experimentais, etc. Método de escolha de parâmetros. Discussão e conclusões. Em particular: para métodos estocásticos os valores apresentados devem ser médias de pelo menos 5 replicações de cada experimento com sementes diferentes.
==== Implementação ====
Critérios básicas da eng. de SW: documentação, legibilidade, etc.
=== 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 saída padrão (stdout).
* Os principais parâmetros 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.
===== Entregáveis =====
O trabalho consiste em:
* Um [[:relatorio|relatório]] com a documentação da solução com resultados e discussão (veja um {{ga-r.pdf|exemplo}}).
* Elementos obrigatórios: Introdução, Formulação, Descrição da solução, Resultados obtidos com análise, Conclusão e Bibliografia.
* Uma implementação do modelo matemática e da heurística (linguagem arbitrária desde seja padrão sem uso de bibliotecas proprietárias e pode ser compilado e executado usando somente software livre).
* 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.
* Protocolos das execuções do solver e da meta-heuristica e outros dados experimentais detalhados;
* Uma apresentação em aula.
===== Outras informações úteis ====
* [[trabalho-faq|Perguntas frequentes (FAQ)]]
* Como apresentar? [[http://lmgtfy.com/?q=como+apresentar+bem+um+artigo+cientifico|Mais informações.]]
* Trabalho: {{tp20171.pdf|Como perder pontos?}}
===== Trabalhos selecionados =====
^ No. ^ Trabalho ^ Nome ^ P ^ F ^ A ^ R ^ C ^
| 1 | TB+SimAnn | Gabriel VP, Arthur OR | ✅. | ✅. | | ✅ | ✅ |
| 2 | TB+BT | Gabriel CA, Mário | ✅. | ✅. | | ✅ | ✅ |
| 3 | TB+VNS | Gleydson, Giovanni | ✅. | ✅. | ✅ | ✅ | ✅ |
| 4 | TB+AG | João Pedro | | | | | |
| 5 | MNM+GRASP | Mateus, Arthur CC | ✅ | ✅. | | ✅ | ✅ |
| 6 | TB+GRASP | Leonardo DD | ✅. | | | | |
| 7 | TB+ILS | Leonardo NR | ✅. | ✅. | | ✅ | ✅ |
| 8 | VSE+GA | Nicolas | ✅. | | | ✅ | ✅ |
| 9 | VSE+GRASP | Julianna, Léo | ✅. | ✅. | | ✅ | ✅ |
| 10 | TB+IGA | Fernando | | | ✅ | ✅ | ✅ |
| 11 | VSE+SimAnn | Luís | | | | ✅ | ✅ |
Status: 1 de julho 2025.\\
#Trabalhos definidos: 16.
P: Proposta, F: Formulação, A: Apresentação, R: Relatório, C: Código. (+x): entregue (com atraso de x dias).
==== Seleções ====
^ ^ VSE ^ MNM ^ TB ^
| Simulated Annealing (SimAnn) | X | | X |
| Iterated Local Search (ILS) | | | X |
| Iterated Greedy Algorithm (IGA) | | | X |
| Busca Tabu (BT) | | | X |
| Algoritmo Genetico (AG) | X | | X |
| GRASP | X | X | X |
| Variable Neighborhood Search (VNS) | | | X |
VSE = Viajar Sem Estresse\\
MNM = Menor Número de Mentores\\
TB = Trabalho Balanceado
===== Agenda =====
^ Data ^ Hora ^ Apresentação ^
| 25/06 | 10.30 | ✅ TB+VNS |
| ::: | 10.50 | TB+GRASP |
| ::: | 11.30 | TB+AG |
| 30/06 | 10.30 | ✅ VSE+GA |
| ::: | 10.50 | ✅ TB+SimAnn |
| ::: | 11.10 | ✅ MNM+GRASP |
| ::: | 11.30 | ✅ TB+ILS |
| ::: | 11.50 | ✅ TB+IGA |
| 02/07 | 10.30 | ✅ TB+BT |
| ::: | 10.50 | VSE+SimAnn |
| ::: | 11.10 | ✅ VSE+GRASP |