Hypervolume Subset Selection in Two Dimensions: Formulations and Algorithms

  • The hypervolume subset selection problem consists of finding a subset, with a given cardinality \(k\), of a set of nondominated points that maximizes the hypervolume indicator. This problem arises in selection procedures of evolutionary algorithms for multiobjective optimization, for which practically efficient algorithms are required. In this article, two new formulations are provided for the two-dimensional variant of this problem. The first is a (linear) integer programming formulation that can be solved by solving its linear programming relaxation. The second formulation is a \(k\)-link shortest path formulation on a special digraph with the Monge property that can be solved by dynamic programming in \(\mathcal{O}(n(k + \log n))\) time. This improves upon the \(\mathcal{O}(n^2k)\) result of Bader (2009), and matches the recent result of Bringmann et al. (2014), which was developed independently from this work using different techniques. Moreover, it is shown that these bounds may be further improved under mild conditions on \(k\).

Download full text files

Export metadata

Metadaten
Author:Tobias Kuhn, Carlos M. Fonseca, Luís Paquete, Stefan Ruzika, José Rui Figueira
URN:urn:nbn:de:hbz:386-kluedo-37983
Document Type:Preprint
Language of publication:English
Date of Publication (online):2014/05/14
Year of first Publication:2014
Publishing Institution:Technische Universität Kaiserslautern
Date of the Publication (Server):2014/05/14
Older document version:urn:nbn:de:hbz:386-kluedo-37700
Tag:Hypervolume; Multiobjective optimization; Subset selection; k-link shortest path
Page Number:17
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
Licence (German):Standard gemäß KLUEDO-Leitlinien vom 10.09.2012