Hypervolume scalarizations for multiobjective graph optimization problems

Abstract

Muitas situações da vida real resultam em problemas de optimização com objectivos múltiplos que muitas vezes estão em conflito. Por exemplo, em finanças, queremos escolher um portfolio em que o retorno esperado é tão alto como possível e o risco é tão baixo como possível. Uma forma de resolver estes problemas é escalarizar os vários objectivos para obter um problema de optimização com um único objectivo. Nesta tese, usamos a notação de escalarização de hipervolume para resolver problemas de optimização em grafos, com um ênfase particular no Problema do Caminho Mais Curto e no Problema da Árvore de Abrangência Mínima. Para o primeiro problema, introduzimos escalarizações de hipervolume para o Problema do Caminho Mais Curto Biobjectivo e a sua formulação de programação linear inteira mista. Além do mais, propomos um algoritmo de "label setting" para resolver o Problema do Caminho Mais Curto Biobjectivo e condições de corte para melhorar a performance do algoritmo. Para além disso, demonstramos a complexidade computacional da resolução deste problema e apresentamos resultados numéricos numa ampla gama de instâncias de problemas de grafos. Para o Problema da Árvore de Abrangência Mínima, introduzimos a escalarização de hipervolume para o Problema da Árvore de Abrangência Mínima Biobjectivo e a sua formulação de programação linear inteira mista. Também propomos um algoritmo de "branch-and-bound" para resolver a escalarização de hipervolume, com condições de corte para melhorar a performance, e demonstramos a complexidade computacional.

Many real-life situations result in optimization problems with multiple objectives that are very often conflicting. For example, in finance, we want to choose a portfolio where the expected value is as high as possible and the risk is as low as possible. One way of solving these problems is to scalarize the several objectives in order to obtain a single objective optimization problem. In this thesis we use the notion of hypervolume scalarization to solve graph optimization problems, with particular emphasis for the Shortest Path Problem and Minimum Spanning Tree Problem. For the first problem, we introduce the hypervolume scalarization for the Biobjective Shortest Path Problem and the corresponding mixed integer linear programming formulation. In addition, we propose a label setting algorithm to solve the hypervolume scalarized version of the problem and pruning conditions to improve the performance of the algorithm. Moreover, we prove the computational complexity of solving the hypervolume scalarization and present numerical results for a wide range of graph problem instances. For the Spanning Tree Problem, we introduce the hypervolume scalarization for the Biobjective Minimum Spanning Tree Problem and the corresponding mixed integer linear programming formulation. We also propose a branch-and-bound algorithm to solve the hypervolume scalarization for the Biobjective Minimum Spanning Tree Problem with pruning conditions to improve its performance and we analyze the computation complexity of this problem.