Dans cette thèse, nous étudions le problème de l’optimisation combinatoire bi-objectif (BOCO) et ses applications à certains problèmes de recouvrement de graphes. Notre travail examine deux axes principaux : (i) les solutions de négociation pour les problèmes d’optimisation combinatoire bi-objectif et (ii) des solutions exactes pour différentes versions des problèmes de forêts d’étoiles couvrantes, qui ont de nombreuses applications, notamment en bioinformatique et dans l’industrie automobile.

Dans la première partie, nous étudions BOCO, qui optimise deux objectifs conflictuels sur un ensemble réalisable discret. Comme la construction du front de Pareto est coûteuse en calcul, nous nous concentrons sur des critères de sélection fondés sur l’équité et définis de manière rigoureuse. Nous analysons ainsi la solution de Kalai-Smorodinsky (KS) dans BOCO, en fournissant des définitions formelles, en examinant ses propriétés fondamentales et en donnant une description géométrique de la solution KS dans l’espace discret. Nous démontrons que la solution KS existe toujours et qu’il en existe au plus deux. Nous concevons un algorithme en deux phases fondé sur une recherche dichotomique, comportant un nombre logarithmique d’itérations. Nous introduisons le prix de l’équité et testons notre approche sur le Problème du Sac à Dos Bi-objectif et le Problème de l’Arbre Couvant Bi-objectif, en comparant les solutions KS avec les solutions Nash Fairness, Proportional Fairness et Min-max.

Dans la seconde partie, nous étudions un cas particulier de BOCO, le Bi-objective Spanning Star Forest Problem (BSSFP), qui minimise à la fois le nombre de centres et le poids total des arêtes. Nous développons un cadre de programmation dynamique en deux phases reposant sur des formulations récursives et la relaxation lagrangienne, et nous prouvons que toutes les solutions efficientes de ce problème sur les arbres peuvent être énumérées en temps polynomial. Enfin, nous fournissons une description complète du polytope des forêts d’étoiles couvrantes pour les graphes 4-cactus, nous l’étendons aux graphes cactus généraux par projection, et nous traitons le problème de séparation pour une famille spécifique d’inégalités.