Technische Samenvatting: Tijd- en Voorraadrechtvaardigheid in Elektriciteitsverdeling met k-tijds bin packing

1. Probleemdefinitie

Het artikel behandelt het probleem van rechtvaardige elektriciteitsverdeling in ontwikkelingslanden, waar de totale huishoudelijke vraag de beschikbare leveringscapaciteit ($S$) overtreft. De kernuitdaging is om beperkte elektriciteit te verdelen over $n$ huishoudens met variërende vraag ($D$) op een manier die rechtvaardigheid maximaliseert.

De auteurs definiëren twee onderscheiden optimalisatiedoelen:

1. Egalitaire toewijzing van aansluittijd: Het doel is om de minimale hoeveelheid tijd te maximaliseren dat elk huishouden verbonden is met het net. De nuttigheid van een agent is binair: ze verkrijgen nuttigheid alleen als hun volledige vraag tijdens een tijdsinterval wordt bevredigd; gedeeltelijke vervulling levert geen nuttigheid op. Dit modelleert scenario's waarbij activiteiten een specifieke vermogendrempel vereisen om te functioneren.
2. Egalitaire toewijzing van Watts (voorraad): Het doel is om de minimale hoeveelheid elektrische energie (in kWh) die aan elk huishouden wordt toegewezen, te maximaliseren. In tegenstelling tot het tijdsgebaseerde model, overweegt dit het volume van de geleverde elektriciteit, met als doel de totale energie die door agenten wordt ontvangen te egaliseren, zelfs als hun aansluittijden verschillen.

Het artikel formaliseert het tijdsgebaseerde probleem als een variant van het klassieke Bin Packing-probleem, genaamd k-tijds bin-packing (kBP). In kBP, gegeven een verzameling items (vragen) en bin-capaciteit $S$, is het doel om items te packen in het minimale aantal bins zodat:

• De som van de itemgroottes in elke bin de waarde $S$ niet overschrijdt.
• Elk item precies in $k$ verschillende bins voorkomt.
• Geen enkele bin meer dan één kopie van hetzelfde item bevat.

2. Methodologie en Theoretisch Kader

Theoretische Fundamenten

De auteurs leggen een theoretisch verband tussen het elektriciteitsverdelingsprobleem en kBP.

• Existentie van optimale $k$: Zij bewijzen dat voor elke elektriciteitsverdelingsinstantie met $n$ huishoudens een eindig geheel getal $k$ bestaat, zodat het oplossen van het kBP-probleem optimaal de optimale oplossing oplevert voor het egalitaire aansluittijd-probleem.
• Grenzen voor $k$: Het artikel biedt een bovengrens voor deze $k$ gebaseerd op het aantal huishoudens $n$, specifiek $k \le a(n)$, waarbij $a(n)$ de maximale determinant is van een $n \times n$ binaire matrix (gerelateerd aan Hadamard-matrices). Een ondergrens van $k \ge n-1$ wordt eveneens vastgesteld voor specifieke instanties.
• Onmogelijkheid voor Watts: Omgekeerd bewijzen de auteurs voor de egalitaire toewijzing van watts een onmogelijkheidsresultaat: er bestaat geen eindige $k$ die alleen afhankelijk is van het aantal agenten $n$ om een optimale oplossing te garanderen. Dit komt omdat optimale oplossingen kunnen vereisen dat agenten met kleinere vraag aanzienlijk langere tijden verbonden zijn, wat onbegrensde herhalingsverhoudingen vereist.

Algorithmische Uitbreidingen

Omdat kBP NP-hard is, richt het artikel zich op het uitbreiden van bestaande bin-packing benaderingsalgoritmen naar de kBP-instelling:

1. Snelle constante-factor benaderingen:

   • $FF_k$ (First-Fit): De auteurs breiden het First-Fit-algoritme uit om $k$ kopieën van de invoerinstantie ($D^k$) te verwerken. Zij bewijzen een asymptotische benaderingsratio van $(1.5 + \frac{1}{5k}) \cdot OPT(D^k) + 3k$. Naarmate $k$ toeneemt, nadert de ratio 1.5, wat een verbetering is ten opzichte van de standaard First-Fit-ratio van 1.7.
   • $FFD_k$ (First-Fit Decreasing): De auteurs breiden First-Fit Decreasing uit. Hoewel een strakke bovengrens niet wordt bewezen, veronderstellen zij een asymptotische ratio van $11/9$ (ongeveer 1.22) op basis van simulatiegegevens, wat een verbetering is ten opzichte van de standaard FFD-ratio.
   • $NF_k$ (Next-Fit): De uitbreiding van Next-Fit blijkt een asymptotische ratio van 2 te hebben.

2. Polynoomtijd-benaderingsschema's (PTAS):

   • Het artikel generaliseert de Fernandez de la Vega-Lueker- en Karmarkar-Karp-algoritmen.
   • De uitbreiding van Fernandez de la Vega-Lueker bereikt $(1 + 2\epsilon)OPT(D^k) + k$ bins.
   • De uitbreidingen van Karmarkar-Karp Algoritme 1 en 2 leveren oplossingen op met additieve termen die afhankelijk zijn van $k$ en $\epsilon$, en werken in polynoomtijd.

3. Heuristieken voor Watts-toewijzing:

   • Vanwege de onmogelijkheid van een universele $k$ voor watts-toewijzing, stellen de auteurs vier heuristische algoritmen voor (HA1–HA4).
   • Deze heuristieken maken gebruik van een tweestapsproces:
     1. Identificeer een subset van agenten met de kleinste vraag die continu (de hele tijd) verbonden moeten zijn.
     2. Pas kBP-gebaseerde strategieën (met $FF_k$ of $FFD_k$) toe op de resterende agenten en de gereduceerde voorraad om de minimale watt-toewijzing te maximaliseren.
   • De algoritmen maken gebruik van ternair zoeken om de optimale grootte van de continu verbonden subset ($g$) te bepalen die de leximin-vector maximaliseert (met prioriteit voor de minst bedeelde agent).

3. Belangrijkste Resultaten en Experimentele Evaluatie

Theoretische Resultaten

• Benaderingsratio's: Het artikel biedt rigoureuze bewijzen voor de benaderingsratio's van $FF_k$ en $NF_k$. Voor $FF_k$ verbetert de ratio naarmate $k$ groeit, en convergeert deze theoretisch naar 1.5.
• Onmogelijkheid: Het bewijs dat geen enkele eindige $k$ (die alleen afhankelijk is van $n$) toereikend is voor egalitaire watts-toewijzing, motiveert de verschuiving naar heuristische benaderingen voor deze specifieke variant.

Experimentele Resultaten

De auteurs evalueerden hun algoritmen met twee datasets:

1. Synthetische Data: gegenereerde instanties met bekende optimale oplossingen om de benaderingsratio's van $FF_k$ en $FFD_k$ te verifiëren. De resultaten ondersteunden de veronderstelling dat $FF_k$ een ratio van 1.375 bereikt en $FFD_k$ een ratio van $11/9$ voor $k > 1$.
2. Real-world Data: Een dataset van 367 huishoudens uit Nigeria (van Oluwasuji et al. [34, 35]) die 13 weken aan uurlijkse vraag bestrijkt.

Prestaties op Aansluittijd (Egalitaire Tijd):

• De $FF_k$ en $FFD_k$ algoritmen (getest met $k=100$) presteerden aanzienlijk beter dan bestaande heuristische en op ILP gebaseerde methoden (zoals het Comfort Model en Supply Model uit [35]) wat betreft egalitaire aansluittijd.
• Zij bereikten een maximaal nuttigheidsverschil tussen agenten dat bijna nul was, wat wijst op een zeer rechtvaardige verdeling.
• De algoritmen draaiden in bijna lineaire tijd ten opzichte van het aantal agenten.

Prestaties op Watts-toewijzing (Egalitaire Watts):

• Van de vier heuristieken presteerde HA1 (met $FFD_k$) het beste in het leveren van de maximale hoeveelheid elektriciteit aan de minst bedeelde agent.
• HA4 (met $FF_k$) presteerde beter dan de anderen in totale geleverde watts en totale aansluittijd.
• De heuristieken slaagden erin de afweging te balanceren tussen het continu verbinden van agenten met kleine vraag en het eerlijk verdelen van de resterende voorraad onder agenten met grotere vraag.

4. Betekenis en Beweringen

Het artikel beweert een praktisch, rechtvaardig en efficiënt kader te bieden voor elektriciteitsverdeling in omgevingen met beperkte middelen. De primaire bijdragen zijn:

• Formalisering: Het definiëren van het k-tijds bin-packing-probleem als een wiskundige abstractie voor rechtvaardige middelenallocatie waarbij items over disjuncte verzamelingen moeten worden gerepliceerd.
• Algorithmische Verbetering: Het aantonen dat het uitbreiden van standaard bin-packing heuristieken naar de kBP-instelling betere benaderingsratio's oplevert dan de originele algoritmen, specifiek door het egalitaire resultaat voor aansluittijd te verbeteren.
• Praktische Toepassing: Het valideren dat deze theoretische uitbreidingen last-sheddingproblemen in de echte wereld effectiever kunnen oplossen dan eerdere state-of-the-art methoden, met name bij het maximaliseren van de minimale aansluittijd voor alle huishoudens.
• Nieuwe Benchmarks: Het vaststellen van nieuwe benchmarks voor de egalitaire toewijzing van watts, waarbij wordt aangetoond dat hoewel een theoretisch optimale $k$ niet bestaat, heuristische benaderingen superieure rechtvaardigheidsmetrieken kunnen opleveren in vergelijking met bestaande oplossingen.

De auteurs concluderen dat het gebruik van kBP een haalbare weg biedt naar rechtvaardige elektriciteitsverdeling, vooral wanneer het doel is om de tijd te maximaliseren dat elke agent verbonden is, en dat heuristische aanpassingen noodzakelijk en effectief zijn voor het maximaliseren van de rechtvaardigheid van het geleverde energievolume (watts).