Enumeração de soluções em problemas de optimização em redes

Abstract

A enumeração de K soluções de um dado problema combinatório é uma generalização, natural, desse problema combinatório, em que, em vez de se procurar uma única solução óptima, se pretende listar, por ordem não decrescente de um determinado custo, as K melhores soluções do problema. Este trabalho debruça-se sobre alguns problemas de determinação ordenada de soluções em Optimização em Redes, começando por analisar dois dos problemas clássicos, a enumeração de trajectos e a enumeração de caminhos, do ponto de vista mais habitual em que a função objectivo é aditiva, e para uma função objectivo genérica. Desenvolvem-se vários algoritmos para enumeração de trajectos e de caminhos que melhoram outros já conhecidos, incluindo processos para listar trajectos e caminhos relativamente a problemas que não verificam o Princípio de Optimalidade. Na sequência do estudo daqueles problemas analisa-se a enumeração de trajectos e caminhos óptimos segundo uma função objectivo concreta, conhecida como tempo total de transmissão e com aplicação nas áreas de redes de transportes e redes de telecomunicações. Introduzem-se dois algoritmos para enumerar caminhos segundo essa função objectivo e adaptam-se algoritmos de enumeração de caminhos e trajectos óptimos a esta função objectivo concreta. Aborda-se a determinação ordenada de soluções de problemas combinatórios na generalidade, com especial ênfase para a enumeração de afectações. Propõe-se um algoritmo para este último problema, donde resulta também uma rotina para determinar a segunda melhor afectação. Por fim, apresentam-se duas aplicações de algoritmos de enumeração a problemas de telecomunicações, nomeadamente um problema de encaminhamento de video-tráfego e um problema de encaminhamento de informação na internet.