L'optimisation combinatoire bi-objectif (BOCO) est un type de prise de décision multicritère avec de nombreuses applications dans différents domaines scientifiques, tels que l'économie, la chaîne d'approvisionnement, les télécommunications, l'informatique et les choix sociaux. Cela implique d’optimiser simultanément deux fonctions objectives (de conflit) dans un ensemble fini et réalisable de vecteurs de décision. Pour BOCO, le concept de solution Pareto-optimale (non dominée) joue un rôle important car il distingue les solutions efficaces et non efficaces. Sur la base de ce concept, les méthodes populaires de résolution de BOCO construisent généralement une représentation de l'ensemble de Pareto qui représente différents compromis entre les objectifs. L’équité proportionnelle est un concept largement étudié dans la littérature qui vise à répartir les services publics pour garantir la justice et l’équité entre les utilisateurs tout en optimisant les performances du système. Concernant les changements proportionnels, il peut être utilisé comme comparaison standard pour deux solutions de BOCO, même lorsque les deux objectifs ont des ordres de grandeur différents. Le but de cette thèse est de proposer un nouveau critère pour sélectionner les solutions Pareto-optimales préférées dans l'ensemble Pareto d'un problème BOCO général utilisant l’équité proportionnelle.

À cette fin, nous introduisons le concept de la solution rho-NF (Nash Fairness) pour que BOCO obtienne un certain équilibre de Nash basé sur l’équité proportionnelle. Le facteur rho > 0 est présenté pour refléter l'importance relative entre les deux objectifs. Nous présentons dans un premier temps le concept de solution rho-NF et sa caractérisation. Nous montrons ensuite l'efficacité Pareto des solutions rho-NF. En fait, chaque solution rho-NF est nécessairement une solution Pareto-optimale mais l'inverse n'est pas toujours vrai. Enfin, nous montrons que des solutions rho-NF peuvent être trouvées en optimisant une combinaison linéaire de deux objectifs. Il s'agit d'un aspect crucial dans le développement d'algorithmes efficaces pour identifier les solutions rho-NF.

Ensuite, nous présentons les algorithmes exacts pour déterminer les solutions rho-NF pour BOCO. Dans certains cas où l'existence de la solution rho-NF n'est pas garantie, nous concevons un algorithme de recherche binaire qui converge vers un nombre logarithmique (de paramètres fixes en fonction des données) d'itérations pour vérifier l'existence de la solution rho-NF et calculez-en une dans le cas affirmatif. En revanche, lorsqu'il existe toujours et qu'il peut y avoir de nombreuses solutions rho-NF, nous développons un algorithme récursif de type Newton pour identifier toutes les solutions rho-NF. A chaque appel récursif, on trouve une solution rho-NF en minimisant les combinaisons itératives linéaires de deux objectifs. Notez que le nombre total d'appels récursifs est limité par le nombre de solutions Pareto-optimales. De plus, il existe un cas où trouver des solutions rho-NF équivaut à résoudre la programmation fractionnaire classique. Dans ce contexte, nous utilisons la méthode de Newton-Dinkelbach qui est largement appliquée à la programmation fractionnaire. Si deux objectifs sont linéaires, la méthode trouve des solutions rho-NF dans un nombre d'itérations fortement polynomial, quelle que soit la structure de l'ensemble des possibles.

Enfin, nous évaluons nos algorithmes à travers diverses instances de BOCO. Les expériences informatiques montrent l'efficacité de nos algorithmes, indiquant leur convergence rapide et leur efficacité dans l'identification de solutions rho-NF. De plus, pour quelques petites instances, nous calculons l'ensemble de Pareto entier pour montrer que l'ensemble de solutions rho-NF est un sous-ensemble strict de l'ensemble de Pareto.

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).