====== 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 {{t20252.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-2-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é **3 de setembro 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é **20 de outubro 2025**.\\
  - Entregar o trabalho completo até **8 de dezembro 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.
    * Normas para o relatórios:
      * O formato segue as [[https://proceedings.science/cfp/sbpo-2024|normas da SOBRAPO]].
      * Em particular: não mais que 12 páginas, fonte 11 pontos.
      * Restrições adicionais: sem uso excessivo de listas numeradas ou com marcados.
  * 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  ^  E  ^
|   1 | DLN+AG    | <del>João, Gilmar</del>  |  ✅.  |        |      |      |     |  |
|   2 | DLN+SimAnn  | Eduardo L            |   ✅.   |  ✅    |  ✅  |  ✅  |  ✅  |  |
|   3 | DLN+IGA    | <del>Joao Pedro,</del> Pedro S  |  ✅.  |  ✅  |  ✅  |  ✅  |     |  |
|  4a | DR+AG       | Guilherme            |   ✅.   |        |  ✅  |  ✅  |  ✅  |  |
|  4b | DR+AG       | Taylor               |   ✅.   |        |      |       |      |  |
|   5 | DLNB+AG     | Gabriel WW           |   ✅.   |   ✅   |      |  ✅   |  ✅  |  |
|   6 | DLN+GRASP   | Breno, <del>Cassio</del>  |    |        |      |  ✅   |  ✅  |  |
|   7 | DLN+ILS     | Bibiana, Gabriel CW  |         |        |      |  ✅   |  ✅  |  ✅  |
|   8 | DLN+VNS     | Leonardo             |   ✅.   |   ✅   |      |  ✅  |  ✅  |  ✅  |
|   9 | DLN+BT      | Clara, Vitor         |   ✅.   |   ✅   |      |  ✅  |  ✅  |  |
|  10 | DLNB+BT     | Eduardo F, Pedro B   |   ✅.   |   ✅   |  ✅  |  ✅    |  ✅  |  ✅  |
|  11 | DR+GRASP    | Mario                |   ✅.   |   ✅   |      |  ✅  |  ✅  |  |
|  12 | DR+VNS      | Lucas, Eraldo        |         |   ✅   |      |      |     |  |
|  13 | NN          | <del>Bernardo</del>  |         |        |      |      |     |  |
Status: 4 de dezembro 2025.\\
#Trabalhos definidos: 21/24.

P: Proposta, F: Formulação, A: Apresentação, R: Relatório, C: Código, E: Dados experimentais.   (+x): entregue (com atraso de x dias).

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

^                                     ^  DLN   ^   DLNB  ^   DR  ^
| Simulated Annealing (SimAnn)        |   ✅   |        |        |
| Iterated Local Search (ILS)         |   ✅   |        |        |
| Iterated Greedy Algorithm (IGA)     |   ✅   |        |        |
| Busca Tabu (BT)                     |   ✅   |   ✅   |   ✅   |
| Algoritmo Genetico (AG)             |   ✅   |   ✅   |   ✅   |
| GRASP                               |   ✅   |        |        |
| Variable Neighborhood Search (VNS)  |   ✅   |        |   ✅   |

DLN = Depositar lixo nuclear\\
DLNB = Depositar lixo nuclear de forma balanceada\\
DR = Depósitos representativos

===== Agenda =====

^ Data  ^ Hora   ^ Apresentação ^
| 08/12 |  10.30 | DLN+GRASP         |
| :::   |  10.45 | DLN+BT            |
| :::   |  11.00 | DLN+VNS           |
| :::   |  11.15 | <del>DLN+AG</del>  |
| :::   |  11.15 | DLN+SimAnn        |
| :::   |  11.30 | DLN+IGA           |
| :::   |  11.45 | <del>NN</del>     |
| 10/12 |  10.30 | DLN+ILS           |
| :::   |  10.45 | DR+AG (4a)        |
| :::   |  11.00 | DR+VNS            |
| :::   |  11.15 | <del>DR+GRASP</del>  |
| :::   |  11.15 | DLNB+BT           |
| :::   |  11.30 | DLNB+AG           |
| :::   |  11.45 | DR+AG (4b)        |