AOCE : Algorithmes exacts et approchés avec garantie de performance pour l’Optimisation Combinatoire Équitable

Les décisions prises au sein des organisations ont souvent un impact sur plusieurs individus, qu’il convient de considérer de manière équitable. Dans ce contexte, l’optimisation équitable vise à produire des solutions efficaces tout en contrôlant l’équilibre des satisfactions des individus vis-à-vis de la solution choisie. Cela peut concerner des problèmes de partage d’objets indivisibles, d’affectation de tâches de façon à équilibrer la charge ou la satisfaction d’individus. L’équilibre peut aussi être recherché dans des problèmes multicritères plutôt que multi-agents pour faire émerger une solutions qui ne néglige aucun critère. Enfin, l’équilibre peut aussi être recherché dans les problèmes de décision dans l’incertain, lorsqu’on cherche une solution robuste, c’est-à-dire qui reste bonne dans les différents scénarios envisagés.

L’objet de ce stage est de fournir de nouveaux modèles computationnels pour la recherche de solutions équilibrées dans des problèmes d’optimisation combinatoire où la qualité d’une solution s’apprécie selon plusieurs points de vues (individus, critères, scénarios). Dans ce contexte, les solutions sont souvent évaluées et comparées en utilisant la moyenne pondérée ordonnée (OWA) ou une sophistication de ce modèle comme WOWA ou l'intégrale de Choquet, la meilleure solution étant celle qui maximise cette quantité. Il s'agit alors pour nous d'améliorer les performances d’algorithmes exacts existants et de concevoir des algorithmes approchés avec garantie de performance pour l'optimisation de l'OWA ou de l'une de ses extensions mentionnées plus haut.

Compétences :
- décision multicritère
- programmation mathématique
- complexité, algorithmique approchée avec garanties de performance (optionnel)

Contact :
- patrice.perny@lip6.fr
- viet_hung.nguyen@uca.fr
- nawal.benabbou@lip6.fr