Please use this identifier to cite or link to this item: https://hdl.handle.net/10316/83275
Title: Branch-and-bound for the hypervolume subset selection problem
Other Titles: Branch-and-bound for the hypervolume subset selection problem
Authors: Gomes, Ricardo Jorge Pires 
Orientador: Paquete, Luís Filipe dos Santos Coelho
Keywords: Algoritmo de Branch-and-Bound; Problema de Seleção do Subconjunto que maximiza o Indicador de Hipervolume; Otimização Multiobjectivo; Programação Inteira; Branch-and-Bound Algorithm; Hypervolume Subset Selection Problem; Multiobjective Optimisation; Integer Programming
Issue Date: 11-Jul-2017
Serial title, monograph or event: Branch-and-bound for the hypervolume subset selection problem
Place of publication or event: DEI-FCTUC
Abstract: O foco principal desta tese é a análise e síntese de um algoritmo de branch-and-bound para o problema de seleção do subconjunto que maximiza o indicador de hipervolume para um número arbitrário de objetivos. Este problema surge nos procedimentos de seleção em heurísticas para otimização multiobjetivo, no qual se pretende selecionar um pequeno subconjunto de soluções de compromisso. A abordagem de branch-and-bound discutida nesta tese combina várias noções de limites e uma estratégia de branching. Em particular, quatro funções de limite e um ordenamento dinâmico de variáveis para a estratégia de branching são propostos. Uma versão paralela do algoritmo de branch-and-bound é também apresentada para tirar partido de sistemas com múltiplas unidades de processamento. A versão paralela do algoritmo de branch-and-bound integra uma pool de threads que explora os nós da árvore de procura de forma concorrentemente. O algoritmo de branch-and-bound é comparado com uma abordagem baseada na formulação de programação inteira. Ambas as versões do algoritmo de branch-and-bound e seus diferentes componentes são avaliadas em termos de tempo de execução e complexidade respetivamente. A versão paralela do algoritmo de branch-and-bound é adicionalmente avaliada em termos de speedup. Os resultados experimentais obtidos numa grande quantidade de instâncias deste problema indicam que a nossa abordagem tem melhor desempenho e a versão paralela é capaz de obter speedups impressionantes em comparação com a versão sequencial.
The main focus of this thesis is the design and analysis of a branch-and-bound algorithm for the hypervolume subset selection problem for an arbitrary number of objectives. This problem arises in selection procedures of heuristic algorithms for multiobjective optimisation, in which the goal is to select a small subset of good compromise solutions. The branch-and-bound approach discussed in this thesis combines several notions of bounds and a branching strategy. In particular, four bounding functions and a dynamic variable ordering for the branching strategy are proposed. Moreover, a parallel version of the branch-and-bound algorithm is presented in order to take advantage of systems with multiple processing units. The parallel version of the branch-and-bound algorithm integrates a thread pool to explore, concurrently, the nodes of the search tree. The branch-and-bound algorithm is compared with a state-of-the-art solution approach based on an integer programming formulation. Both versions of branch-and-bound algorithm and their different components are assessed in terms of running time and time complexity respectively. The parallel version of the branch-and-bound algorithm is additionally assessed in terms of speedup. The experimental results indicate that the proposed branch-and-bound approach performs faster for a wide range of instances of the problem and the parallel version of the branch-and-bound algorithm is able to achieve impressive speedups as compared to the sequential version.
Description: Dissertação de Mestrado em Engenharia Informática apresentada à Faculdade de Ciências e Tecnologia
URI: https://hdl.handle.net/10316/83275
Rights: openAccess
Appears in Collections:UC - Dissertações de Mestrado

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

Page view(s) 50

467
checked on Mar 26, 2024

Download(s) 50

441
checked on Mar 26, 2024

Google ScholarTM

Check


This item is licensed under a Creative Commons License Creative Commons