• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Exact Methods for Computing All Lorenz Optimal Solutions to Biobjective Problems

Thumbnail
Date
2015
Notes
LNCS n°9346
Dewey
Recherche opérationnelle
Sujet
Multiobjective Combinatorial Optimization; Fairness; Lorenz dominance; Two-phase method
DOI
http://dx.doi.org/10.1007/978-3-319-23114-3_19
Conference name
4th International Conference on Algorithmic Decision Theory, ADT 2015
Conference date
09-2015
Conference city
Lexington, KY
Conference country
United States
Book title
Algorithmic Decision Theory 4th International Conference, ADT 2015, Lexington, KY, USA, September 27-30, 2015, Proceedings
Author
Walsh, Toby
Publisher
Springer
Publisher city
Berlin Heidelberg
Year
2015
ISBN
978-3-319-23113-6
Book URL
10.1007/978-3-319-23114-3
URI
https://basepub.dauphine.fr/handle/123456789/15811
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Galand, Lucie
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lust, Thibaut
233 Laboratoire d'Informatique de Paris 6 [LIP6]
Type
Communication / Conférence
Item number of pages
305-321
Abstract (EN)
This paper deals with biobjective combinatorial optimization problems where both objectives are required to be well-balanced. Lorenz dominance is a refinement of the Pareto dominance that has been proposed in economics to measure the inequalities in income distributions. We consider in this work the problem of computing the Lorenz optimal solutions to combinatorial optimization problems where solutions are evaluated by a two-component vector. This setting can encompass fair optimization or robust optimization. The computation of Lorenz optimal solutions in biobjective combinatorial optimization is however challenging (it has been shown intractable and NP-hard on certain problems). Nevertheless, to our knowledge, very few works address this problem. We propose thus in this work new methods to generate Lorenz optimal solutions. More precisely, we consider the adaptation of the well-known two-phase method proposed in biobjective optimization for computing Pareto optimal solutions to the direct computing of Lorenz optimal solutions. We show that some properties of the Lorenz dominance can provide a more efficient variant of the two-phase method. The results of the new method are compared to state-of-the-art methods on various biobjective combinatorial optimization problems and we show that the new method is more efficient in a majority of cases.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.