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
TypeCommunication / Conférence
Conference title4th International Conference on Algorithmic Decision Theory, ADT 2015
Conference cityLexington, KY
Conference countryUnited States
Book titleAlgorithmic Decision Theory 4th International Conference, ADT 2015, Lexington, KY, USA, September 27-30, 2015, Proceedings
Book authorWalsh, Toby
MetadataShow full item record
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
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 / KeywordsMultiobjective Combinatorial Optimization; Fairness; Lorenz dominance; Two-phase method
Showing items related by title and author.
An efficient procedure for finding best compromise solutions to the multi-objective assignment problem Belhoul, Lyes; Galand, Lucie; Vanderpooten, Daniel (2014) Article accepté pour publication ou publié
An exact method for the bi-objective one-machine problem with maximum lateness and unit family setup cost objectives Artigues, Christian; Jozefowiez, Nicolas; Aloulou, Mohamed Ali (2010) Communication / Conférence