Résumé technique : Une analyse des formulations de programmation linéaire en nombres entiers (mixte) pour le problème de regroupement maximal de diversité

Définition du problème

Le problème de regroupement maximal de diversité (MDGP - Maximally Diverse Grouping Problem) est un problème d'optimisation combinatoire classique de type NP-difficile. Étant donné un ensemble d'éléments $I$ et un ensemble de groupes $G$, l'objectif est d'assigner chaque élément à exactement un groupe de telle sorte que la diversité totale au sein des groupes soit maximisée. La diversité d'une paire d'éléments $(i, j)$ est définie par un paramètre $d_{ij} \geq 0$. La diversité totale est la somme de toutes les diversités par paires pour les éléments assignés au même groupe. Le problème est soumis à des contraintes sur le nombre d'éléments par groupe, définies par des bornes inférieures $l_g$ et des bornes supérieures $u_g$ pour chaque groupe $g \in G$.

Les applications du MDGP incluent l'assignation d'étudiants à des groupes ou des cours, la formation d'équipes de projet, la création de groupes de réviseurs et la planification d'examens finaux. Bien que les approches heuristiques soient courantes dans la littérature, les méthodes de résolution exacte ont historiquement été limitées à de petites instances de problèmes.

Méthodologie et formulations de modèles

L'article analyse et compare quatre formulations distinctes de programmation linéaire en nombres entiers (mixte) (MILP) :

1. Formulation standard (Weitz et Lakshminarayanan, 1998) :

   • Variables : Variables binaires $x_{ig}$ indiquant si l'élément $i$ est assigné au groupe $g$. Variables binaires auxiliaires $y_{ijg}$ représentant si les éléments $i$ et $j$ sont tous deux dans le groupe $g$.
   • Mécanisme : L'objectif est linéarisé à l'aide de contraintes $y_{ijg} \leq x_{ig}$ et $y_{ijg} \leq x_{jg}$.
   • Faiblesse : La relaxation linéaire (LP) est faible. Dans la relaxation, les éléments peuvent être assignés de manière fractionnaire à tous les groupes ($x_{ig} = 1/|G|$), ce qui fait que la valeur de l'objectif somme toutes les paires $d_{ij}$ possibles, constituant une borne supérieure inatteignable pour les solutions entières réalisables.

2. Formulation de Papenberg et Klau (2021) :

   • Variables : Variables binaires $z_{ij}$ indiquant si les éléments $i$ et $j$ sont assignés au même groupe, sans spécifier lequel.
   • Mécanisme : Utilise des contraintes de transitivité (par exemple, $-z_{ij} + z_{ik} + z_{jk} \leq 1$) pour assurer la cohérence et une contrainte garantissant que chaque élément est groupé avec exactement $|I|/|G| - 1$ autres éléments.
   • Force : La ramification (branching) se produit sur les assignations élément-élément ($z_{ij}$), qui influencent directement la fonction objectif. La relaxation LP est nettement plus forte car les contraintes limitent le nombre de paires par élément selon la taille du groupe.
   • Limitation : Conçue à l'origine uniquement pour des groupes de tailles égales.

3. Formulation combinée :

   • Mécanisme : Fusionne la formulation standard avec l'approche de Papenberg et Klau en liant $z_{ij} = \sum_{g \in G} y_{ijg}$.
   • Contribution : Ajoute des contraintes de transitivité au modèle standard et adapte les contraintes de taille de groupe pour des tailles variables. L'article prouve que pour des groupes de tailles égales, cette formulation possède une relaxation LP au moins aussi forte que la formulation de Papenberg et Klau.

4. Formulation de Papenberg et Klau adaptée (pour des tailles de groupes variables) :

   • Mécanisme : Étend le modèle de Papenberg et Klau pour gérer des tailles de groupes variables ($l_g \neq u_g$) en introduisant un « élément fictif » (dummy item) pour chaque groupe.
   • Variables : Les éléments sont assignés à des éléments fictifs (représentant les groupes) via $z_{i, \text{dummy}}$.
   • Contraintes : Des contraintes de transitivité s'appliquent à tous les éléments, y compris les éléments fictifs. Les contraintes garantissent que chaque élément réel est assigné à exactement un groupe fictif et que la taille du cluster autour de chaque groupe fictif respecte $l_g$ et $u_g$.

Principales contributions

• Analyse comparative : L'article fournit une comparaison théorique et empirique entre la formulation standard d'assignation élément-groupe et la formulation d'assignation élément-élément.
• Aperçu théorique : Il démontre que la ramification sur les variables d'assignation élément-élément ($z_{ij}$) est supérieure à la ramification sur les variables d'assignation élément-groupe ($x_{ig}$) car la première restreint directement la valeur de la fonction objectif et produit une relaxation LP plus serrée.
• Nouvelles formulations : Deux nouvelles formulations sont présentées pour traiter le cas général de tailles de groupes variables, étendant l'applicabilité de la logique plus forte d'assignation élément-élément.
• Rupture de symétrie : L'article traite et transfère les contraintes de rupture de symétrie au cas général pour la formulation standard.

Résultats computationnels

Une étude computationnelle complète a été menée à l'aide de CPLEX 12.9 sur des instances allant de 10 à 30 éléments et 2 à 10 groupes. Les scénarios de groupes de tailles égales et de tailles variables ont tous deux été testés.

• Qualité de la relaxation LP : La formulation de Papenberg et Klau ainsi que ses adaptations ont systématiquement produit des bornes supérieures nettement plus serrées (écarts plus faibles) par rapport à la formulation standard. Les écarts de la relaxation LP de la formulation standard étaient souvent supérieurs à 100 %, tandis que les formulations élément-élément restaient beaucoup plus bas.
• Performance de résolution :
  • Groupes de tailles égales : La formulation de Papenberg et Klau a résolu presque toutes les instances à l'optimalité plus rapidement que la formulation standard.
  • Tailles de groupes variables : La formulation de Papenberg et Klau adaptée (Section 3.4) a été la plus performante, résolvant des instances allant jusqu'à 30 éléments à l'optimalité ou avec de faibles écarts dans la limite de temps de 1800 secondes.
  • Formulation standard : A rencontré des difficultés importantes, échouant souvent à réduire l'écart ou à résoudre des instances de plus de 15 éléments dans le temps imparti.
  • Formulation combinée : Bien que théoriquement forte, la formulation combinée n'a pas montré d'amélioration substantielle de performance par rapport à la formulation standard lors de la ramification sur les variables $x_{ig}$, suggérant que les contraintes de transitivité seules sont insuffisantes pour surmonter la faiblesse de la stratégie de ramification élément-groupe.

Signification et affirmations

L'article affirme que le principal moteur de la performance supérieure des nouvelles formulations est la stratégorie de ramification (branching strategy). En effectuant la ramification sur les assignations élément-élément plutôt que sur les assignations élément-groupe, le solveur peut plus efficacement élaguer l'espace de recherche grâce à la relaxation LP plus forte fournie par les contraintes de transitivité.

L'étude conclut que pour le MDGP, en particulier dans les contextes de tailles de groupes variables, l'adaptation de la formulation de Papenberg et Klau est l'approche exacte la plus efficace actuellement disponible. Elle étend avec succès les avantages de la logique d'assignation élément-élément aux contraintes de regroupement générales, surmontant les limitations de la formulation standard vieille de plusieurs décennies. Les auteurs notent que bien que la formulation adaptée soit la plus performante, les instances avec des tailles de groupes variables restent plus difficiles à résoudre que celles à tailles égales, probablement en raison de la flexibilité accrue de l'espace de solution.