ROADEF 2026>
Algorithmes d'approximation par arrondi itératif pour des problèmes de couverture équitable
Lou Moulin-Roussel  1@  , Patrice Perny  1@  , Nawal Benabbou  1@  , Viet Hung Nguyen  2@  
1 : LIP6
Sorbonne Université, Centre National de la Recherche Scientifique, Centre National de la Recherche Scientifique : UMR7606
2 : Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes
Ecole Nationale Supérieure des Mines de St Etienne, Centre National de la Recherche Scientifique, Université Clermont Auvergne, Institut national polytechnique Clermont Auvergne, Ecole Nationale Supérieure des Mines de St Etienne : UMR6158, Centre National de la Recherche Scientifique : UMR6158, Université Clermont Auvergne : UMR6158, Institut national polytechnique Clermont Auvergne : UMR6158

Nous étudions deux variantes de problèmes de couverture équitable : le problème de couverture multi-ressources équitable par sommets et un problème d'affectation équitable assimilable à un problème de couverture par arêtes. L'équité est modélisée par la minimisation d'un opérateur OWA à poids décroissants, permettant de pénaliser davantage les coûts les plus élevés et ainsi de réduire les disparités entre agents. Comme cette fonction objectif est non linéaire, nous nous appuyons sur plusieurs techniques de linéarisation afin d'obtenir des formulations en programme linéaire en variables mixtes. Nous proposons un algorithme d'arrondi itératif en temps polynomial, adapté à ces variantes équitables. L'approche repose sur la résolution répétée d'une relaxation linéaire et sur la fixation progressive de variables tout en maintenant la faisabilité et en mettant à jour les contraintes issues de l'OWA.
Nous montrons que cet algorithme fournit une garantie de 2-approximation pour chacun des deux problèmes étudiés. Enfin, une étude numérique évalue l'influence des différentes linéarisations de l'OWA sur les temps de calcul et la qualité des solutions obtenues.


Chargement... Chargement...