Skip to Main content Skip to Navigation
Conference papers

Exact Methods for Computing All Lorenz Optimal Solutions to Biobjective Problems

Lucie Galand 1 Thibaut Lust 1
1 DECISION
LIP6 - Laboratoire d'Informatique de Paris 6
Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download

https://hal.sorbonne-universite.fr/hal-01361196
Contributor : Thibaut Lust <>
Submitted on : Tuesday, September 6, 2016 - 5:39:40 PM
Last modification on : Thursday, January 21, 2021 - 11:38:03 AM
Long-term archiving on: : Wednesday, December 7, 2016 - 1:41:00 PM

File

paper_ADTLorenz.pdf
Files produced by the author(s)

Identifiers

Citation

Lucie Galand, Thibaut Lust. Exact Methods for Computing All Lorenz Optimal Solutions to Biobjective Problems. Fourth International Conference on Algorithmic Decision Theory (ADT 2015), Sep 2015, Lexington, United States. pp.305-321, ⟨10.1007/978-3-319-23114-3_19⟩. ⟨hal-01361196⟩

Share

Metrics

Record views

178

Files downloads

412