• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • 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

Représentations discrètes de l'ensemble des points non dominés pour des problèmes d'optimisation multi-objectifs

Discrete representations of the nondominated set for multi-objective optimization problems

Jamain, Florian (2014), Représentations discrètes de l'ensemble des points non dominés pour des problèmes d'optimisation multi-objectifs, doctoral thesis prepared under the supervision of Bazgan, Cristina, Université Paris Dauphine, 83 p.

View/Open
2014PA090023.pdf (604.6Kb)
Type
Thèse
Date
2014-06
Pages
83
Metadata
Show full item record
Author(s)
Jamain, Florian
Under the direction of
Bazgan, Cristina
Abstract (FR)
Le but de cette thèse est de proposer des méthodes générales afin de contourner l’intractabilité de problèmes d’optimisation multi-objectifs.Dans un premier temps, nous essayons d’apprécier la portée de cette intractabilité en déterminant une borne supérieure, facilement calculable, sur le nombre de points non dominés, connaissant le nombre de valeurs prises par chaque critère.Nous nous attachons ensuite à produire des représentations discrètes et tractables de l’ensemble des points non dominés de toute instance de problèmes d’optimisation multi-objectifs. Ces représentations doivent satisfaire des conditions de couverture, i.e. fournir une bonne approximation, de cardinalité, i.e. ne pas contenir trop de points, et si possible de stabilité, i.e. ne pas contenir de redondances. En s’inspirant de travaux visant à produire des ensembles ε-Pareto de petite taille, nous proposons tout d’abord une extension directe de ces travaux, puis nous axons notre recherche sur des ensembles ε-Pareto satisfaisant une condition supplémentaire de stabilité. Formellement, nous considérons des ensembles ε-Pareto particuliers, appelés (ε, ε′)-noyaux, qui satisfont une propriété de stabilité liée à ε′. Nous établissons des résultats généraux sur les (ε, ε′)-noyaux puis nous proposons des algorithmes polynomiaux qui produisent des (ε, ε′)-noyaux de petite taille pour le cas bi-objectif et nous donnons des résultats négatifs pour plus de deux objectifs.
Abstract (EN)
The goal of this thesis is to propose new general methods to get around the intractability of multi-objective optimization problems.First, we try to give some insight on this intractability by determining an, easily computable, upper bound on the number of nondominated points, knowing the number of values taken on each criterion. Then, we are interested in producingsome discrete and tractable representations of the set of nondominated points for each instance of multi-objective optimization problems. These representations must satisfy some conditions of coverage, i.e. providing a good approximation, cardinality, i.e. it does not contain too many points, and if possible spacing, i.e. it does not include any redundancies. Starting from works aiming to produce ε-Pareto sets of small size, we first propose a direct extension of these works then we focus our research on ε-Pareto sets satisfying an additional condition of stability. Formally, we consider special ε-Pareto sets, called (ε, ε′)-kernels, which satisfy a property of stability related to ε′. We give some general results on (ε, ε′)-kernels and propose some polynomial time algorithms that produce small (ε, ε′)-kernels for the bicriteria case and we give some negative results for the tricriteria case and beyond.
Subjects / Keywords
Représentations discrètes; Ensemble de Pareto; Approximation; Points non dominés; Noyaux; Problèmes d’optimisation multi-objectifs; Discrete representations; Pareto set; Approximation; Nondominated points; Kernels; Multi-objective optimization problems
JEL
C44 - Operations Research; Statistical Decision Theory

Related items

Showing items related by title and author.

  • Thumbnail
    Discrete representation of the non-dominated set for multi-objective optimization problems using kernels 
    Bazgan, Cristina; Jamain, Florian; Vanderpooten, Daniel (2017) Article accepté pour publication ou publié
  • 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
    Local Search, data structures and Monte Carlo Search for Multi-Objective Combinatorial Optimization Problems 
    Cornu, Marek (2017-12-18) Thèse
  • Thumbnail
    Résolution de problèmes d'optimisation combinatoire mono et multi-objectifs par énumération ordonnée 
    Belhoul, Lyes (2014-12) Thèse
  • 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é
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