This seminar will take place on September 27 at 15h30, online, via Zoom (link below).
https://videoconf-colibri.zoom.us/j/86970689592?pwd=bkpMK1lSQllqWlQxenEwczlYNjZrUT09
Our seminars are free to attend and open to everyone. Please share with whomever may be interested.
Summary
Multiobjective optimization problems consist of the simultaneous minimization (or maximization) of multiple objective functions. Due to the usually conflicting nature of objectives, typically no single optimal solution exist, but instead there is a (possibly large) set of Pareto-optimal solutions. Often the aim in multiobjective optimization is to find a diverse subset of the Pareto-optimal solutions, for example, to present to the Decision Maker only a small number of Pareto-optimal solutions. This may be interpreted as a subset selection problem where the goal is to find a bounded-size subset of solutions that maximize a given set-quality indicator. Such indicators are used to evaluate solution sets by mapping (the image of) a solution set into a single scalar value. The hypervolume indicator is one of the most commonly used quality indicators due to its theoretical properties. The Hypervolume Subset Selection Problem (HSSP) consists of selecting a subset of k points out of a set of n points that maximizes the hypervolume indicator. This problem may arise not only when selecting which solutions to present to the Decision Maker but also within the search process, for example, in the selection step of evolutionary multiobjective optimization algorithms. Hence, it is important that the HSSP can be computed in a reasonable amount of time. Although polynomial-time algorithms exist for solving the HSSP with 2 objectives, already with 3 objectives the HSSP is solved efficiently only for particular cases, such as k=n-1, or by computing an approximation with greedy algorithms. Even though a few exact algorithms exist to compute the HSSP for 3 or more objectives and k<n-1, faster algorithms are required to make its use more practical. In this talk, a new integer linear programming formulation for the HSSP is presented, as well as an algorithm that exploits such formulation to considerably speed up the computation time of the HSSP.
Speaker's bio
Andreia P. Guerreiro is currently a junior researcher and a member of the Automated Reasoning and Software Reliability group at INESC-ID in Lisbon. She obtained her Masters degree in Information Systems and Computer Engineering from Instituto Superior Técnico, and her PhD degree in Information Science and Technology from the University of Coimbra. Her research work is concerned with approximation algorithms for multiobjective combinatorial optimization, the development and analysis of efficient indicator-based selection algorithms, as well as algorithms for performance assessment in multiobjective optimization.