Skip to main content

Exploiting an Integer Linear Programming Formulation for the Hypervolume Subset Selection Problem

Online Event |

As part of CEGIST's seminar cycle, we are proud to announce that Andreia P. Guerreiro (INESC-ID, Automated Reasoning and Software Reliability group) will present the work "Exploiting an Integer Linear Programming Formulation for the Hypervolume Subset Selection Problem".

This seminar will take place on September 27 at 15h30, online, via Zoom (link below).

Our seminars are free to attend and open to everyone. Please share with whomever may be interested.

Andreia P. Guerreiro
Andreia P. Guerreiro


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.


CEGIST - Centro de Estudos de Gestão
Instituto Superior Técnico

Av. Rovisco Pais, 1049 - 001 Lisboa
Tel: +351 21 841 77 29 (ext. 1729)
Fax: +351 21 841 79 79

Sponsored by


Host Institution

IST Lisboa