Algoritmos Polinomiais para Problemas de Otimização Combinatória com Multi-Objetivos em Grafos
Autores
|
4545 |
44,1963
|
|
|
4546 |
44,1963
|
Informações:
Publicações do PESC
O foco deste trabalho são problemas de otimização combinatória multi-objetivo em grafos considerando, no máximo, uma função totalizadora (por exemplo, MinSum ou MaxProd). As demais funções objetivo consideradas são do tipo gargalo (MinMax ou MaxMin). Algoritmos polinomiais para a obtenção de um conjunto mínimo completo de soluções Pareto-ótimas serão apresentados, juntamente com demonstrações de otimalidade, experimentos computacionais e aplicações para o caso tri-objetivo. Em particular, árvore geradora, árvore de Steiner e caminho são os problemas considerados nesta tese.
The focus of this work are multi-objective combinatorial optimization problems in graphs with at most one totalizing objective function (for example, MinSum or MaxProd). The other objectives are of the bottleneck type (MinMax or MaxMin). Polynomial algorithms are developed which generate a minimal complete set of Pareto-optimal solutions. Optimality proofs, computational experiments and applications for tri-objective cases are given. In particular, spanning tree, Steiner tree and optimal paths problems are considered.