Résumé technique : Équité temporelle et d'approvisionnement dans la distribution d'électricité par bin-packing k-fois

1. Définition du problème

L'article aborde le problème de la répartition équitable de l'électricité dans les pays en développement où la demande totale des ménages dépasse la capacité d'approvisionnement disponible ($S$). Le défi central consiste à allouer une électricité limitée parmi $n$ ménages ayant des demandes variables ($D$) de manière à maximiser l'équité.

Les auteurs définissent deux objectifs d'optimisation distincts :

1. Allocation égalitaire du temps de connexion : L'objectif est de maximiser la durée minimale pendant laquelle tout ménage est connecté au réseau. L'utilité d'un agent est binaire : il ne gagne de l'utilité que si sa demande totale est satisfaite pendant un intervalle de temps ; une satisfaction partielle rapporte une utilité nulle. Cela modélise des scénarios où les activités nécessitent un seuil de puissance spécifique pour fonctionner.
2. Allocation égalitaire des Watts (approvisionnement) : L'objectif est de maximiser la quantité minimale d'énergie électrique (en kWh) allouée à tout ménage. Contrairement au modèle basé sur le temps, celui-ci considère le volume d'électricité délivré, visant à égaliser l'énergie totale reçue par les agents, même si leurs temps de connexion diffèrent.

L'article formalise le problème basé sur le temps comme une variante du problème classique du bin-packing, nommé bin-packing k-fois (kBP). Dans le kBP, étant donné un ensemble d'objets (demandes) et une capacité de bac $S$, l'objectif est de ranger les objets dans le nombre minimal de bacs de telle sorte que :

• La somme des tailles des objets dans chaque bac ne dépasse pas $S$.
• Chaque objet apparaît dans exactement $k$ bacs distincts.
• Aucun bac ne contient plus d'une copie du même objet.

2. Méthodologie et cadre théorique

Fondements théoriques

Les auteurs établissent un lien théorique entre le problème de division de l'électricité et le kBP.

• Existence d'un $k$ optimal : Ils prouvent que pour toute instance de division d'électricité avec $n$ ménages, il existe un entier fini $k$ tel que la résolution optimale du problème kBP fournit la solution optimale pour le problème égalitaire du temps de connexion.
• Bornes sur $k$ : L'article fournit une borne supérieure pour ce $k$ basée sur le nombre de ménages $n$, spécifiquement $k \le a(n)$, où $a(n)$ est le déterminant maximal d'une matrice binaire $n \times n$ (liée aux matrices de Hadamard). Une borne inférieure de $k \ge n-1$ est également établie pour des instances spécifiques.
• Impossibilité pour les Watts : À l'inverse, pour l'allocation égalitaire des Watts, les auteurs prouvent un résultat d'impossibilité : il n'existe aucun $k$ fini qui dépende uniquement du nombre d'agents $n$ pour garantir une solution optimale. Cela s'explique par le fait que les solutions optimales peuvent nécessiter que les agents ayant les plus faibles demandes soient connectés pendant des durées significativement plus longues, exigeant des ratios de répétition non bornés.

Extensions algorithmiques

Puisque le kBP est NP-difficile, l'article se concentre sur l'extension des algorithmes d'approximation de bin-packing existants au contexte du kBP :

1. Approximations rapides à facteur constant :

   • $FF_k$ (First-Fit / Premier ajustement) : Les auteurs étendent l'algorithme First-Fit pour traiter $k$ copies de l'instance d'entrée ($D^k$). Ils prouvent un ratio d'approximation asymptotique de $(1,5 + \frac{1}{5k}) \cdot OPT(D^k) + 3k$. À mesure que $k$ augmente, le ratio tend vers 1,5, s'améliorant par rapport au ratio standard de First-Fit de 1,7.
   • $FFD_k$ (First-Fit Decreasing / Premier ajustement décroissant) : Les auteurs étendent First-Fit Decreasing. Bien qu'une borne supérieure stricte ne soit pas prouvée, ils conjecturent un ratio asymptotique de $11/9$ (environ 1,22) basé sur des données de simulation, s'améliorant par rapport au ratio standard FFD.
   • $NF_k$ (Next-Fit / Prochain ajustement) : L'extension de Next-Fit montre un ratio asymptotique de 2.

2. Schémas d'approximation en temps polynomial (PTAS) :

   • L'article généralise les algorithmes de Fernandez de la Vega-Lueker et Karmarkar-Karp.
   • L'extension de Fernandez de la Vega-Lueker atteint $(1 + 2\epsilon)OPT(D^k) + k$ bacs.
   • Les extensions des Algorithmes 1 et 2 de Karmarkar-Karp fournissent des solutions avec des termes additifs dépendant de $k$ et $\epsilon$, s'exécutant en temps polynomial.

3. Heuristiques pour l'allocation des Watts :

   • En raison de l'impossibilité d'un $k$ universel pour l'allocation des Watts, les auteurs proposent quatre algorithmes heuristiques (HA1–HA4).
   • Ces heuristiques emploient un processus en deux étapes :
     1. Identifier un sous-ensemble d'agents ayant les plus faibles demandes pour être connectés en continu (tout le temps).
     2. Appliquer des stratégies basées sur le kBP (utilisant $FF_k$ ou $FFD_k$) aux agents restants et à l'approvisionnement réduit afin de maximiser l'allocation minimale de Watts.
   • Les algorithmes utilisent la recherche ternaire pour déterminer la taille optimale du sous-ensemble connecté en continu ($g$) qui maximise le vecteur leximin (priorisant l'agent le plus défavorisé).

3. Résultats clés et évaluation expérimentale

Résultats théoriques

• Ratios d'approximation : L'article fournit des preuves rigoureuses des ratios d'approximation de $FF_k$ et $NF_k$. Pour $FF_k$, le ratio s'améliore à mesure que $k$ croît, convergeant théoriquement vers 1,5.
• Impossibilité : La preuve qu'aucun $k$ fini (dépendant uniquement de $n$) ne suffit pour l'allocation égalitaire des Watts motive le passage à des approches heuristiques pour cette variante spécifique.

Résultats expérimentaux

Les auteurs ont évalué leurs algorithmes en utilisant deux ensembles de données :

1. Données synthétiques : Instances générées avec des solutions optimales connues pour vérifier les ratios d'approximation de $FF_k$ et $FFD_k$. Les résultats ont étayé la conjecture selon laquelle $FF_k$ atteint un ratio de 1,375 et $FFD_k$ atteint $11/9$ pour $k > 1$.
2. Données réelles : Un ensemble de données de 367 ménages au Nigeria (provenant de Oluwasuji et al. [34, 35]) couvrant 13 semaines de demande horaire.

Performance sur le temps de connexion (Temps égalitaire) :

• Les algorithmes $FF_k$ et $FFD_k$ (testés avec $k=100$) ont nettement surpassé les méthodes heuristiques et basées sur la PLI existantes (telles que le Modèle de Confort et le Modèle d'Approvisionnement de [35]) en termes de temps de connexion égalitaire.
• Ils ont atteint des différences de utilité maximale quasi nulles entre les agents, indiquant une répartition hautement équitable.
• Les algorithmes se sont exécutés en temps presque linéaire par rapport au nombre d'agents.

Performance sur l'allocation des Watts (Watts égalitaires) :

• Parmi les quatre heuristiques, HA1 (utilisant $FFD_k$) a été la plus performante pour fournir la quantité maximale d'électricité à l'agent le plus défavorisé.
• HA4 (utilisant $FF_k$) a surpassé les autres en termes de Watts totaux délivrés et de temps de connexion total.
• Les heuristiques ont réussi à équilibrer le compromis entre connecter en continu les agents à faible demande et distribuer équitablement l'approvisionnement restant aux agents à forte demande.

4. Importance et affirmations

L'article prétend fournir un cadre pratique, équitable et efficace pour la division de l'électricité dans des environnements à ressources contraintes. Ses contributions principales sont :

• Formalisation : Définir le problème de bin-packing k-fois comme une abstraction mathématique pour l'allocation équitable de ressources où les objets doivent être répliqués à travers des ensembles disjoints.
• Amélioration algorithmique : Démontrer que l'extension des heuristiques de bin-packing standard au contexte du kBP produit de meilleurs ratios d'approximation que les algorithmes originaux, améliorant spécifiquement le résultat égalitaire pour le temps de connexion.
• Application pratique : Valider que ces extensions théoriques peuvent résoudre des problèmes réels de délestage plus efficacement que les méthodes de l'état de l'art précédentes, en particulier pour maximiser le temps de connexion minimal pour tous les ménages.
• Nouvelles références : Établir de nouvelles références pour l'allocation égalitaire des Watts, montrant que bien qu'un $k$ optimal théorique n'existe pas, les approches heuristiques peuvent produire des métriques d'équité supérieures par rapport aux solutions existantes.

Les auteurs concluent que l'utilisation du kBP offre une voie viable vers une distribution équitable de l'électricité, particulièrement lorsque l'objectif est de maximiser le temps pendant lequel chaque agent est connecté, et que des adaptations heuristiques sont nécessaires et efficaces pour maximiser l'équité du volume d'énergie (Watts) délivré.