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.

Download full text files

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

Export metadata

Metadaten
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