• 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 2(DOIS). 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. 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 associadas às arestas (i,j) em E, demandas q(v) associados 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 03.1.
  
  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 obritdos. Este relatório deverá conter 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.
  
  Os códigos (comentados) devem ser entregues eletronicamente apenas.

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