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.

Volltext Dateien herunterladen

  • Es existiert eine neuere Version dieses Dokumentes. Bitte verwenden Sie den unten in den Metadaten aufgeführten Link zur aktuellen Version.

Metadaten exportieren

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

$Rev: 13581 $