Branch-and-bound for the hypervolume subset selection problem

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.