• 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.
  
  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.
    
    
  • 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, utiliza uma metaeurística GRASP, trabalho 1e).
    
    
  • 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 do Corte Máximo (MAX-CUT): Dado um grafo G=(V,E) e os pesos w_e ³ 0 associados às arestas em E, encontrar um conjunto X Ì V, tal que o valor do corte definido por X: å_{(i,j)| i Î X, j Î V-X}w_(i,j), seja máximo.
    
    Utilize como instâncias os grafos no link "Dados Max-Cut" na URL http://www-di.inf.puc-rio.br/~poggi//aalg022.html . (Estes grafos podem ser transformados numa matriz |V| × |V| simétrica.) Obs.: A instância com |V|=50 já deve ser difícil de ser resolvida exatamente.
  
  Caso o tempo de CPU ultrapasse 1 hora, faça com que seu algoritmo imprima a melhor solução encontrada até então.

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