• O objetivo do 2^o Trabalho é a implementação de um algoritmo de branch-and-bound para um problema NP-difícil. Isto é, um problema de otimização cuja versão de decisão é um problema NP-completo.
  
  Este trabalho deve ser feito em grupos de no MÁXIMO 3(TRÊS). Caso contrário não será considerado.
  
  A apresentação do seu algoritmo deve conter uma descrição de cada um dos elementos em um branch-and-bound, são eles:
  • Critério de particionamento do espaço de soluções;
    
    
  • Uma relaxação do problema (um majorante se o problema é de maximização, minorante caso contrário). Neste item, mostre como a sua relaxação é modificada quando se considera apenas um subconjunto do espaço de soluções (ou seja, quando um elemento tem seu valor fixado ou passa a não poder receber alguns valores).
    
    
  • Um método para obter uma ``boa'' solução viável (um minorante se o problema é de maximização, majorante caso contrário). Esta solução pode ser obtida por um método guloso e refinada por uma busca local. (Para obter uma solução ainda melhor, utilize uma metaeurística, como GRASP, Busca Tabu, Algoritmo Genético, etc. Este item NÃO É OBRIGATóRIO).
    
    
  • Critério de seleção do particionamento a ser feito em cada nó da árvore de busca.
    
    
  • Critério de percorrimento da árvore de busca (sugere-se que seja busca em profundidade, permitindo uma implementação recursiva e mais simples de ser feita).
  
  
• O problema sobre o qual deve-se aplicar o algoritmo de branch-and-bound segue:
  
  
  • Problema da Árvore Geradora com Restrições de Capacidade (CAP-MST): Dado um grafo G=(V È { r }, E), custos c(i,j) ³ 0 associados às arestas (i,j) em E, demandas q(v) associadas aos vértices v em V, e uma capacidade Q. Deseja-se encontrar uma árvore geradora de G, cujas sub-árvores enraizadas no vértice r possuam a soma das demandas dos seus vértices inferiores ou iguais à Q, cujo custo total de suas arestas seja mínimo.
    
    As instâncias estão no link CAP-MST da página de Análise de Algoritmos 05.2.
  
  Apresente sempre a sua melhor solução (lista das arestas com seus respectivos valores) e o seu valor total. Caso o tempo de CPU ultrapasse 1 hora, faça com que seu algoritmo termine imprima a melhor solução encontrada até então.
  
  Deverá ser apresentado um relatório sobre as experiências computacionais comentando os resultados obtidos. Este relatório deverá conter:
  • Complexidade do Problema CAP-MST (prova de que é NP-difícil);
  • Uma tabela com o valor da melhor solução obtida, indicando se é ótima (provado pelo seu algoritmo) ou não, o tempo de cpu total utilizado na resolução, o valor do limite inferior obtido no nó raiz, e o valor da solução ótima (ou melhor conhecida) que serão fornecidos. A tabela deverá ter uma linha para cada uma das 39 instâncias contidas no arquivo no link;
  • Uma análise dos resultados com relação à complexidade assintótica do algoritmo implementado. Mostrar o crescimento do tempo é exponencial em função do tamanho da instância;
  • Uma análise separada das diferentes etapas do algoritmo.
  
  Os códigos (comentados) devem ser entregues eletronicamente apenas. Um roteiro para o documento a ser entregue segue:
  
  
  • Descrever os algoritmos informalmente.
  • Demonstrar o entendimento do algoritmo explicando, em detalhe, o resultado que o algoritmo deve obter e justificá-lo.
  • Explicar a fundamentação do algoritmo e justificar a sua corretude. Apresentar e explicar a complexidade teórica esperada para cada algoritmo.
  • Documente o arquivo contendo o código fonte de modo que cada passo do algoritmo esteja devidamente identificado e deixe claro como este passo é executado.
  A corretude código será testada sobre um conjunto de instâncias que será distribuido. O trabalho entregue deve conter:
  • Um documento contendo o roteiro de desenvolvimento dos algoritmos (e dos códigos), os itens pedidos acima, comentários e análises sobre a implementação e os testes realizados (papel).
  • Um e-mail contendo um arquivo . zip com os códigos fonte e os executáveis correspondentes (mudar a extenção de .zip para .zxx) deve ser enviado para marcus.poggi@gmail.com com o assunto (ou subject) AA052T2.

This document was translated from L^AT_EX by H^EV^EA.