Please use this identifier to cite or link to this item: https://hdl.handle.net/10316/96099
Title: Hypervolume scalarizations for multiobjective graph optimization problems
Other Titles: Escalarizações de hipervolume para problemas de optimização multiobjectivo em grafos
Authors: Lourenço, Ana Catarina Quitério
Orientador: Paquete, Luís Filipe dos Santos Coelho
Keywords: Escalarizações de hipervolume; Optimização combinatória multiobjectivo; Programação linear inteira; Problema do Caminho Mais Curto; Problema da Árvore de Abrangência Mínima; Hypervolume scalarizations; Multiobjective combinatorial optimization; Integer linear programming; Shortest Path Problem; Minimum Spanning Tree Problem
Issue Date: 13-Jul-2021
Serial title, monograph or event: Hypervolume scalarizations for multiobjective graph optimization problems
Place of publication or event: DEI- FCTUC
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.
Description: Dissertação de Mestrado em Engenharia Informática apresentada à Faculdade de Ciências e Tecnologia
URI: https://hdl.handle.net/10316/96099
Rights: openAccess
Appears in Collections:UC - Dissertações de Mestrado

Files in This Item:
File Description SizeFormat
teseMEI_AnaCatarinaQuiterioLourenco.pdf1.42 MBAdobe PDFView/Open
Show full item record

Page view(s)

41
checked on Mar 26, 2024

Download(s)

38
checked on Mar 26, 2024

Google ScholarTM

Check


This item is licensed under a Creative Commons License Creative Commons