• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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
2017
Journal name
European Journal of Operational Research
Volume
260
Number
3
Pages
814-827
Publication identifier
10.1016/j.ejor.2016.11.020
Metadata
Show full item record
Author(s)
Bazgan, Cristina
Laboratoire 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; kernel
JEL
C44 - Operations Research; Statistical Decision Theory

Related items

Showing items related by title and author.

  • Thumbnail
    Représentations discrètes de l'ensemble des points non dominés pour des problèmes d'optimisation multi-objectifs 
    Jamain, Florian (2014-06) Thèse
  • Thumbnail
    Approximate Pareto sets of minimal size for multi-objective optimization problems 
    Bazgan, Cristina; Jamain, Florian; Vanderpooten, Daniel (2015) Article accepté pour publication ou publié
  • Thumbnail
    On the number of non-dominated points of a multicriteria optimization problem 
    Bazgan, Cristina; Jamain, Florian; Vanderpooten, Daniel (2013) Article accepté pour publication ou publié
  • Thumbnail
    Approximation in multiobjective optimization using e-kernels 
    Jamain, Florian; Bazgan, Cristina; Vanderpooten, Daniel (2014) Communication / Conférence
  • Thumbnail
    On Approximate Kernels of Minimal Size for Bicriteria Problems 
    Jamain, Florian; Bazgan, Cristina; Vanderpooten, Daniel (2013) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo