Titulo Estágio
Branch-and-bound for the hypervolume subset selection problem
Áreas de especialidade
Sistemas Inteligentes
Local do Estágio
ECOS/DEI
Enquadramento
Typically, multiobjective optimization (MO) problems are solved according to the principle of Pareto-optimality: A solution is called Pareto-optimal if there is no other feasible solution that is at least as good with respect to all objectives and strictly better with respect to at least one objective [1]. In other words, the image of such solution in the objective space is not dominated by the image of any other feasible solution. Under conflicting objectives, there is more than one solution that is Pareto-optimal. Each of these Pareto-optimal solutions corresponds to a different compromise among the objective functions and each of them is potentially relevant for a decision maker. Therefore, the goal of MO is to compute the complete set of Pareto-optimal solutions, but since this is very often a hard computational task, heuristic methods have been proposed to find an approximation in a reasonable amount of time.
Objetivo
Heuristic methods for MO problems iteratively select a set of candidate solutions from a larger pool, based on a certain measure of solution quality. This is known as the subset selection problem and can be formalized in several different manners, depending of the measure that is chosen. One of the most used measures is the hypervolume indicator. Given a set of points (as images of candidate solutions that are mutually nondominated), the hypervolume indicator measures the size of the region of the objective space that is dominated by those points and bounded by some reference point [2]. The hypervolume subset selection problem (HSSP) consists of finding a subset of k elements from a set of n nondominated points that maximizes the hypervolume indicator [3]. There have been recent algorithmic contributions to solve this problem for 2 and 3 objectives. In the latter case, a greedy algorithm with performance guarantee has shown to perform quite well on several benchmark instances [4]. An integer linear programming (ILP) formulation of the HSSP has also been devised, but the solver's run-time makes it infeasible for reasonably sized problems.
In this project, the goal is to implement a branch-and-bound approach to solve the HSSP for an arbitrary number of objectives. The impact of several notions of bounds and variable ordering, in particular that provided by the greedy approach, is to be analysed in several test cases that are currently available.
Plano de Trabalhos - Semestre 1
1) Literature review
2) Definition of upper and lower bounds on the optimal value of the HSSP
3) Implementation of the greedy heuristic, reusing code described in [4]
4) Branch-and-bound implementation for 2 and 3 objectives
5) Writing of the intermediate report
Plano de Trabalhos - Semestre 2
1) Branch-and-bound implementation for an arbitrary number of objectives
2) Experimental analysis and comparison with the ILP model
3) Writing of the final report
Condições
This MSc project is for students that would like to deepen his knowledge on algorithms. The MSc student can use the computational resources from ECOS group for performing experiments. This project has no funding available.
Observações
References
[1] M. Ehrgott: Multicriteria Optimization (2. ed.). Springer, 2005.
[2] E. Zitzler and L. Thiele: Multiobjective Optimization Using Evolutionary Algorithms - A Comparative Case Study. PPSN 1998: 292-304, 1998.
[3] J. Bader and E. Zitzler, . Hype: An algorithm for fast hypervolume-based many-objective optimization. Evolutionary Computation, 19(1):45–76., 2011.
[4] A.P. Guerreiro, C.M. Fonseca, L.Paquete: Greedy Hypervolume Subset Selection in the Three-Objective Case. GECCO 2015: 671-678, 2015.
- T. Kuhn, Representative Systems and Decision Support for Multicriteria Optimization Problems, PhD Thesis, University of Kaiserslautern, 2015.
Orientador
Luís Paquete
paquete@dei.uc.pt 📩