Discrete representation of the non-dominated set for multi-objective optimization problems using kernels
Bazgan, Cristina; Jamain, Florian; Vanderpooten, Daniel (2017), Discrete representation of the non-dominated set for multi-objective optimization problems using kernels, European Journal of Operational Research, 260, 3, p. 814-827. 10.1016/j.ejor.2016.11.020
Type
Article accepté pour publication ou publiéDate
2017Journal name
European Journal of Operational ResearchVolume
260Number
3Pages
814-827
Publication identifier
Metadata
Show full item recordAuthor(s)
Bazgan, CristinaLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Jamain, Florian
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Vanderpooten, Daniel
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
In this paper, we are interested in producing discrete and tractable representations of the set of non-dominated points for multi-objective optimization problems, both in the continuous and discrete cases. These representations must satisfy some conditions of coverage, i.e. providing a good approximation of the non-dominated set, spacing, i.e. without redundancies, and cardinality, i.e. with the smallest possible number of points. This leads us to introduce the new concept of (ε, ε′)-kernels, or ε-kernels when ɛ′=ɛ is possible, which correspond to ε-Pareto sets satisfying an additional condition of ε′-stability. Among these, the kernels of small, or possibly optimal, cardinality are claimed to be good representations of the non-dominated set. We first establish some general properties on ε-kernels. Then, for the bi-objective case, we propose some generic algorithms computing in polynomial time either an ε-kernel of small size or, for a fixed size k , an ε-kernel with a nearly optimal approximation ratio 1+ɛ. For more than two objectives, we show that ε-kernels do not necessarily exist but that (ε, ε′)-kernels always exist. Nevertheless, we show that the size of a smallest (ε, ε′)-kernel can be very far from the size of a smallest ε-Pareto set.Subjects / Keywords
Multiple objective programming; Pareto set; Non-dominated points; Discrete representation; Exact and approximation algorithms; kernelRelated items
Showing items related by title and author.
-
Jamain, Florian (2014-06) Thèse
-
Bazgan, Cristina; Jamain, Florian; Vanderpooten, Daniel (2015) Article accepté pour publication ou publié
-
Bazgan, Cristina; Jamain, Florian; Vanderpooten, Daniel (2013) Article accepté pour publication ou publié
-
Jamain, Florian; Bazgan, Cristina; Vanderpooten, Daniel (2014) Communication / Conférence
-
Jamain, Florian; Bazgan, Cristina; Vanderpooten, Daniel (2013) Communication / Conférence