Título:
  Algoritmos para Problemas de Planejamento de Redes

Autor:
  Frederico Rodrigues Borges da Cruz

Resumo:
  Nessa tese, estudamos alguns problemas de planejamento de redes (network 
design problems), uma denominação genérica que agrupa muitos problemas 
importantes. São problemas definidos em grafos, onde é procurado um 
sub-conjunto de arcos e de nós, cumprindo certos requisitos. Apresentamos 
o problema não-capacitado de fluxos com custos fixos (NCFCF), com uma 
revisão bibliográfica atualizada sobre os avanços no estudo do problema, 
e desenvolvemos um método de solução original. Mostramos resultados 
computacionais, onde são resolvidos problemas conhecidos na literatura. 
Introduzimos um novo modelo, o problema de planejamento de redes em 
multi-níveis (PRMN), apresentando uma revisão bibliográfica sobre problemas 
correlatos e mostrando o crescente interesse nesse tipo de modelo. Os 
métodos desenvolvidos para o problema NCFCF foram então estendidos a esse 
novo modelo, o problema PRMN, com resultados promissores, conforme atestam 
os resultados computacionais que apresentamos. Elaboramos um estudo 
comparativo entre diversas implementações paralelas para os algoritmos 
desenvolvidos, com resultados práticos encorajadores, em termos de speedup. 
Fazemos uma revisão bibliográfica e discutimos possíveis extensões para a 
nossa pesquisa. Finalmente, é importante reforçar que os principais 
resultados dessa tese podem ser estendidos a muitos outros problemas de 
planejamento de redes.

Palavras-chaves:
  Planejamento de redes; programação inteira-mista; localização; 
fluxos em redes.