Implicit enumeration strategies for the hypervolume subset selection problem

Abstract The hypervolume subset selection problem arises within selection procedures of multiobjective evolutionary algorithms as well as for extracting a succinct subset of optimal solutions of a multiobjective optimization problem. Although efficient algorithms are known for two dimensions, this problem becomes NP-hard for more dimensions. In this article, we introduce an integer linear programming formulation for this problem for more than two dimensions that is based on the decomposition of the dominated region of the set of nondominated points. Moreover, we propose a branch and bound algorithm that uses combinatorial arguments and discuss bounding strategies based on the application of three upper bounds. We analyze the performance of the two solution approaches on a wide range of instances. The results indicate that the branch and bound algorithm has better performance for several orders of magnitude.