Exact Methods for Computing All Lorenz Optimal Solutions to Biobjective Problems
Galand, Lucie; Lust, Thibaut (2015), Exact Methods for Computing All Lorenz Optimal Solutions to Biobjective Problems, in Walsh, Toby, Algorithmic Decision Theory 4th International Conference, ADT 2015, Lexington, KY, USA, September 27-30, 2015, Proceedings, Springer : Berlin Heidelberg, p. 305-321. 10.1007/978-3-319-23114-3_19
Type
Communication / ConférenceDate
2015Conference title
4th International Conference on Algorithmic Decision Theory, ADT 2015Conference date
2015-09Conference city
Lexington, KYConference country
United StatesBook title
Algorithmic Decision Theory 4th International Conference, ADT 2015, Lexington, KY, USA, September 27-30, 2015, ProceedingsBook author
Walsh, TobyPublisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-319-23113-6
Pages
305-321
Publication identifier
Metadata
Show full item recordAuthor(s)
Galand, LucieLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lust, Thibaut

Laboratoire d'Informatique de Paris 6 [LIP6]
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.Subjects / Keywords
Multiobjective Combinatorial Optimization; Fairness; Lorenz dominance; Two-phase methodRelated items
Showing items related by title and author.
-
Galand, Lucie; Lust, Thibaut (2011) Communication / Conférence
-
Galand, Lucie; Lust, Thibaut (2013) Communication / Conférence
-
Belhoul, Lyes; Galand, Lucie; Vanderpooten, Daniel (2014) Article accepté pour publication ou publié
-
Galand, Lucie; Lust, Thibaut (2015) Communication / Conférence
-
Artigues, Christian; Jozefowiez, Nicolas; Aloulou, Mohamed Ali (2010) Communication / Conférence