Date : May 15, 2024, 2 p.m. - Type : Thesis - Minh Hieu NGUYEN - Amphi 3 - Pôle commun
Bi-objective combinatorial optimization with proportional fairness |
Bi-Objective Combinatorial Optimization (BOCO) is a type of multiple-criteria decision-making with many applications in different scientific areas, such as economics, supply chain, telecommunications, computer science, and social choice. It involves optimizing simultaneously two (conflict) objective functions in a finite feasible set of decision vectors. For BOCO, the concept of Pareto-optimal (non-dominated) solution plays an important role as it distinguishes between efficient and non-efficient solutions. Based on this concept, popular methods for solving BOCO usually construct a representation of the Pareto set that represents different trade-offs between the objectives. Proportional fairness is a widely studied concept in the literature that aims to distribute utilities to ensure fairness and equity among users while optimizing system performance. Related to the proportional changes, it can be used as a standard comparison for two solutions of BOCO, even when the two objectives have different orders of magnitude. The goal of this thesis is to propose a novel criterion for selecting preferred Pareto-optimal solutions in the Pareto set of a general BOCO problem using proportional fairness.
For this purpose, we introduce the concept of the rho-NF (Nash Fairness) solution for BOCO achieving some Nash equilibrium based on proportional fairness. The factor rho > 0 is presented to reflect the relative importance between the two objectives. We first present rho-NF solution concept and its characterization. We then show the Pareto efficiency of rho-NF solutions. In fact, each rho-NF solution is necessarily a Pareto-optimal solution but the inverse is not always true. Finally, we show that rho-NF solutions can be found by optimizing a linear combination of two objectives. This is a crucial aspect in developing efficient algorithms for identifying rho-NF solutions.
Subsequently, we present the exact algorithms to determine the rho-NF solutions for BOCO. In some cases where the existence of rho-NF solution is not guaranteed, we design a binary search algorithm that converges in a logarithmic (of fixed parameters depending on the data) number of iterations to verify the existence of the rho-NF solution and compute one in the affirmative case. In contrast, when there always exists and may be numerous rho-NF solutions, we develop a Newton-like recursive algorithm to identify all the rho-NF solutions. At each recursive call, we find a rho-NF solution by minimizing iteratively linear combinations of two objectives. Notice that the total number of recursive calls is bounded by the number of Pareto-optimal solutions. Furthermore, there exists one case where finding rho-NF solutions is equivalent to solving classical fractional programming. In this setting, we use the Newton-Dinkelbach method which is broadly applied to fractional programming. If two objectives are linear, the method finds rho-NF solutions in a strongly polynomial number of iterations, regardless of the structure of the feasible set.
Finally, we evaluate our algorithms through various instances of BOCO. Computational experiments show the effectiveness of our algorithms, indicating their rapid convergence and efficiency in identifying rho-NF solutions. Furthermore, for some small instances, we compute the whole Pareto set to show that the rho-NF solution set is a strict subset of the Pareto set.
Jury:
- Gautier STAUFFER, Professeur à HEC Lausanne (Rapporteur)
- Kim Thang NGUYEN, Professeur à l’Université Grenoble Alpes (Rapporteur)
- Patrice PERNY, Professeur à Sorbonne Université (Examinateur)
- Sourour ELLOUMI, Professeure à l’ENSTA Paris (Examinatrice)
- Fatiha BENDALI, Professeure à l’Université Clermont Auvergne (Examinatrice)
- Hervé KERIVIN, Maître de conférence à l’Université Clermont Auvergne (Examinateur)
- Mourad BAIOU, Directeur de recherche au CNRS, LIMOS UMR 6158 (Co-encadrant)
- Viet Hung NGUYEN, Professeur à l’Université Clermont Auvergne (Co-encadrant, directeur de thèse).