ALGO Talk - Exploiting an integer linear programming formulation for the hypervolume subset selection problem

Talk by Andreia Guerreiro, INESC-ID, 2 July 2021

Abstract:

Set-quality indicators, which map a set of points into a scalar value, are a convenient way of assessing the quality of a set of solutions in multiobjective optimization. The hypervolume indicator is one of the most commonly used quality indicators. Due to its theoretical properties, it is frequently used within the (environmental) selection step in Evolutionary Multiobjective Optimization Algorithms (EMOAs). In such a case, selection may be viewed as a Hypervolume Subset Selection Problem (HSSP) that consists of selecting a subset of $k$ points out of a set of n points that maximizes the hypervolume indicator. However, already with 3 objectives, HSSP-based selection in EMOAs is usually solved either for particular cases such as $k=n-1$, or with greedy algorithms. Although a few exact algorithms exist to compute the HSSP for $k<n-1$, faster algorithms are required to make its integration in EMOAs 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 of the HSSP. Such algorithm makes HSSP-based selection in EMOAs more practical, at least for 3 objectives.