Hypervolume Subset Selection in Two Dimensions: Formulations and Algorithms
- The hypervolume subset selection problem consists of finding a subset, with a given cardinality, of a nondominated set of points that maximizes the hypervolume indicator. This problem arises in selection procedures of population-based heuristics for multiobjective optimization, and for which practically efficient algorithms are strongly required. In this article, we provide two new formulations for the two-dimensional variant of this problem. The first is an integer programming formulation that can be solved by solving its linear relaxation. The second formulation is a \(k\)-link shortest path formulation on a special digraph with Monge property that can be solved by dynamic programming in \(\mathcal{O}(n^2)\) time complexity. This improves upon the existing result of \(O(n^3)\) in Bader.
Author: | Tobias Kuhn, Carlos M. Fonseca, Luís Paquete, Stefan Ruzika, José Rui Figueira |
---|---|
URN: | urn:nbn:de:hbz:386-kluedo-37700 |
Document Type: | Preprint |
Language of publication: | English |
Date of Publication (online): | 2014/03/30 |
Year of first Publication: | 2014 |
Publishing Institution: | Technische Universität Kaiserslautern |
Date of the Publication (Server): | 2014/03/31 |
Newer document version: | urn:nbn:de:hbz:386-kluedo-37983 |
Tag: | Hypervolume; Multiobjective optimization; Subset selection; k-link shortest path |
Page Number: | 14 |
Faculties / Organisational entities: | Kaiserslautern - Fachbereich Mathematik |
DDC-Cassification: | 5 Naturwissenschaften und Mathematik / 510 Mathematik |
Licence (German): | Standard gemäß KLUEDO-Leitlinien vom 10.09.2012 |