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.
Verfasser*innenangaben: | Tobias Kuhn, Carlos M. Fonseca, Luís Paquete, Stefan Ruzika, José Rui Figueira |
---|---|
URN: | urn:nbn:de:hbz:386-kluedo-37700 |
Dokumentart: | Preprint |
Sprache der Veröffentlichung: | Englisch |
Datum der Veröffentlichung (online): | 30.03.2014 |
Jahr der Erstveröffentlichung: | 2014 |
Veröffentlichende Institution: | Technische Universität Kaiserslautern |
Datum der Publikation (Server): | 31.03.2014 |
Neuere Dokument-Version: | urn:nbn:de:hbz:386-kluedo-37983 |
Freies Schlagwort / Tag: | Hypervolume; Multiobjective optimization; Subset selection; k-link shortest path |
Seitenzahl: | 14 |
Fachbereiche / Organisatorische Einheiten: | Kaiserslautern - Fachbereich Mathematik |
DDC-Sachgruppen: | 5 Naturwissenschaften und Mathematik / 510 Mathematik |
Lizenz (Deutsch): | Standard gemäß KLUEDO-Leitlinien vom 10.09.2012 |