An hypervolume dichotomic scheme for multiobjective optimization

Abstract

Problemas de otimização multiobjectivo podem facilmente ser encontrados na nossa via diária. Em múltiplas situações nos conseguimos encontrar, sem reparar, a tentar otimizar vários objetivos. Nesta dissertação propomos métodos para resolver problemas de otimização multiobjectivo. Em particular, estes métodos são baseados no conceito de escalarização de hypervolume e estendem o trabalho anterior na seguinte forma: i) descrevemos uma software framework que implementa a procura dicotómica para resolver qualquer problema de otimização biobjetivo que pode ser formulado em termos de escalarização de hypervolume; esta ferramenta é capaz de encontrar o conjunto completo de soluções ótimas, assim como um deste que tem uma garantia de proximidade; também providenciamos a documentação necessária para ajudar o utilizador a implementar a framework, juntamente com um exemplo prático do problema da mochila biobjectivo implementado com scip ii) apresentamos uma versão do esquema dicotómico com paralelização para encontrar o conjunto completo de soluções ótimas; iii) estendemos a abordagem dicotómica para qualquer número de objetivos que funciona sob alguns pressupostos. Para além disso, apresentamos resultados numéricos numa ampla gama de instâncias. Com estes resultados pudemos concluir que a versão com paralelização é significativamente mais rápida, especialmente para números de valores de entrada maiores. Também pudemos concluir que, para a abordagem para qualquer número de objetivos, uma seleção aleatória do próximo subproblema a resolve permite encontrar o conjunto de pontos não dominados resolvendo e gerando um menor número de subproblemas.

Multiobjective optimization problems can easily be found in our daily life. In multiple cases we inadvertently find ourselves trying to optimize several objectives. In this dissertation, we propose methods to solve multiobjective optimization problems. In particular, these methods are based on the concept of hypervolume scalarization and extend previous work on the following manner: i) we describe a software framework that implements a dichotomic search to solve any biobjective optimization problem that can be formulated in terms of hypervolume scalarization; this framework can provide the complete set of optimal solution as well as a subset of it that has an approximation guarantee; we also provide the required documentation to help the user to implement it, with an application example for a biobjective knapsack problem implemented with scip; ii) we present a parallel version of the dichotomic scheme to find the complete set of optimal solutions; iii) we extend the dichotomic approach for any number of objectives that works under some assumptions. In addition, we present numerical results on a wide range of instances. From these results we were able to conclude that the parallel version presented is significantly faster, specially for larger input sizes. We also concluded that, for the approach for any number of objectives, a random selection method of the next subproblem to solve allows to find the complete nondominated set while generating and solving less number of subproblems.