Resumen Técnico: Tiempo y Equidad de Suministro en la Distribución de Electricidad mediante Empaquetado en Bins k-veces

1. Definición del Problema

El artículo aborda el problema de la distribución equitativa de electricidad en países en desarrollo, donde la demanda total de los hogares supera la capacidad de suministro disponible ($S$). El desafío central consiste en asignar la electricidad limitada entre $n$ hogares con demandas variables ($D$) de manera que se maximice la equidad.

Los autores definen dos objetivos de optimización distintos:

1. Asignación Egalitaria del Tiempo de Conexión: El objetivo es maximizar la cantidad mínima de tiempo que cualquier hogar permanece conectado a la red. La utilidad de un agente es binaria: solo obtienen utilidad si se satisface su demanda completa durante un intervalo de tiempo; el cumplimiento parcial arroja una utilidad de cero. Esto modela escenarios donde las actividades requieren un umbral específico de potencia para funcionar.
2. Asignación Egalitaria de Vatios (Suministro): El objetivo es maximizar la cantidad mínima de energía eléctrica (en kWh) asignada a cualquier hogar. A diferencia del modelo basado en el tiempo, este considera el volumen de electricidad entregada, buscando igualar la energía total recibida por los agentes, incluso si sus tiempos de conexión difieren.

El artículo formaliza el problema basado en el tiempo como una variante del clásico Problema de Empaquetado en Bins, denominado empaquetado en bins k-veces (kBP). En kBP, dado un conjunto de elementos (demandas) y una capacidad de bin $S$, el objetivo es empaquetar los elementos en el número mínimo de bins de modo que:

• La suma de los tamaños de los elementos en cada bin no exceda $S$.
• Cada elemento aparezca exactamente en $k$ bins distintos.
• Ningún bin contenga más de una copia del mismo elemento.

2. Metodología y Marco Teórico

Fundamentos Teóricos

Los autores establecen un vínculo teórico entre el problema de división de electricidad y kBP.

• Existencia de un $k$ Óptimo: Demuestran que para cualquier instancia de división de electricidad con $n$ hogares, existe un entero finito $k$ tal que resolver el problema kBP de manera óptima produce la solución óptima para el problema de tiempo de conexión egalitario.
• Límites para $k$: El artículo proporciona una cota superior para este $k$ basada en el número de hogares $n$, específicamente $k \le a(n)$, donde $a(n)$ es el determinante máximo de una matriz binaria de $n \times n$ (relacionada con las matrices de Hadamard). También se establece una cota inferior de $k \ge n-1$ para instancias específicas.
• Imposibilidad para Vatios: Por el contrario, para la asignación egalitaria de vatios, los autores prueban un resultado de imposibilidad: no existe un $k$ finito que dependa únicamente del número de agentes $n$ para garantizar una solución óptima. Esto se debe a que las soluciones óptimas pueden requerir que los agentes con demandas más pequeñas permanezcan conectados durante duraciones significativamente más largas, lo que exige ratios de repetición ilimitados.

Extensiones Algorítmicas

Dado que kBP es NP-duro, el artículo se centra en extender los algoritmos de aproximación de empaquetado en bins existentes al entorno kBP:

1. Aproximaciones Rápidas de Factor Constante:

   • $FF_k$ (First-Fit / Primer Ajuste): Los autores extienden el algoritmo First-Fit para procesar $k$ copias de la instancia de entrada ($D^k$). Demuestran una relación de aproximación asintótica de $(1.5 + \frac{1}{5k}) \cdot OPT(D^k) + 3k$. A medida que $k$ aumenta, la relación se acerca a 1.5, superando la relación estándar de First-Fit de 1.7.
   • $FFD_k$ (First-Fit Decreasing / Primer Ajuste Decreciente): Los autores extienden First-Fit Decreasing. Aunque no se prueba una cota superior ajustada, conjeturan una relación asintótica de $11/9$ (aprox. 1.22) basada en datos de simulación, mejorando la relación estándar de FFD.
   • $NF_k$ (Next-Fit / Siguiente Ajuste): Se demuestra que la extensión de Next-Fit tiene una relación asintótica de 2.

2. Esquemas de Aproximación en Tiempo Polinomial (PTAS):

   • El artículo generaliza los algoritmos de Fernandez de la Vega-Lueker y Karmarkar-Karp.
   • La extensión de Fernandez de la Vega-Lueker logra $(1 + 2\epsilon)OPT(D^k) + k$ bins.
   • Las extensiones de los Algoritmos 1 y 2 de Karmarkar-Karp proporcionan soluciones con términos aditivos dependientes de $k$ y $\epsilon$, ejecutándose en tiempo polinomial.

3. Heurísticas para Asignación de Vatios:

   • Debido a la imposibilidad de un $k$ universal para la asignación de vatios, los autores proponen cuatro algoritmos heurísticos (HA1–HA4).
   • Estas heurísticas emplean un proceso de dos pasos:
     1. Identificar un subconjunto de agentes con las demandas más pequeñas para que se conecten continuamente (todo el tiempo).
     2. Aplicar estrategias basadas en kBP (usando $FF_k$ o $FFD_k$) a los agentes restantes y al suministro reducido para maximizar la asignación mínima de vatios.
   • Los algoritmos utilizan búsqueda ternaria para determinar el tamaño óptimo del subconjunto conectado continuamente ($g$) que maximiza el vector leximin (priorizando al agente peor situado).

3. Resultados Clave y Evaluación Experimental

Resultados Teóricos

• Relaciones de Aproximación: El artículo proporciona pruebas rigurosas para las relaciones de aproximación de $FF_k$ y $NF_k$. Para $FF_k$, la relación mejora a medida que crece $k$, convergiendo teóricamente a 1.5.
• Imposibilidad: La prueba de que ningún $k$ finito (dependiente solo de $n$) es suficiente para la asignación egalitaria de vatios motiva el cambio hacia enfoques heurísticos para esta variante específica.

Resultados Experimentales

Los autores evaluaron sus algoritmos utilizando dos conjuntos de datos:

1. Datos Sintéticos: Instancias generadas con soluciones óptimas conocidas para verificar las relaciones de aproximación de $FF_k$ y $FFD_k$. Los resultados respaldaron la conjetura de que $FF_k$ logra una relación de 1.375 y $FFD_k$ logra $11/9$ para $k > 1$.
2. Datos del Mundo Real: Un conjunto de datos de 367 hogares de Nigeria (de Oluwasuji et al. [34, 35]) que cubre 13 semanas de demanda horaria.

Rendimiento en Tiempo de Conexión (Tiempo Egalitario):

• Los algoritmos $FF_k$ y $FFD_k$ (probados con $k=100$) superaron significativamente a los métodos existentes basados en heurísticas e ILP (como el Modelo de Confort y el Modelo de Suministro de [35]) en términos de tiempo de conexión egalitario.
• Lograron diferencias de utilidad máxima casi nulas entre los agentes, indicando una distribución altamente equitativa.
• Los algoritmos se ejecutaron en tiempo casi lineal en relación con el número de agentes.

Rendimiento en Asignación de Vatios (Vatios Egalitarios):

• Entre las cuatro heurísticas, HA1 (usando $FFD_k$) tuvo el mejor desempeño en suministrar la mayor cantidad de electricidad al agente peor situado.
• HA4 (usando $FF_k$) superó a los demás en el total de vatios entregados y en el tiempo total de conexión.
• Las heurísticas equilibraron con éxito la compensación entre conectar continuamente a los agentes de baja demanda y distribuir equitativamente el suministro restante a los agentes de mayor demanda.

4. Significado y Afirmaciones

El artículo afirma proporcionar un marco práctico, equitativo y eficiente para la división de electricidad en entornos con recursos limitados. Sus contribuciones principales son:

• Formalización: Definir el problema de empaquetado en bins k-veces como una abstracción matemática para la asignación equitativa de recursos donde los elementos deben replicarse en conjuntos disjuntos.
• Mejora Algorítmica: Demostrar que extender las heurísticas estándar de empaquetado en bins al entorno kBP produce mejores relaciones de aproximación que los algoritmos originales, mejorando específicamente el resultado egalitario para el tiempo de conexión.
• Aplicación Práctica: Validar que estas extensiones teóricas pueden resolver problemas reales de apagones de carga más eficazmente que los métodos anteriores de vanguardia, particularmente en la maximización del tiempo mínimo de conexión para todos los hogares.
• Nuevas Referencias: Establecer nuevas referencias para la asignación egalitaria de vatios, mostrando que, aunque no existe un $k$ óptimo teórico, los enfoques heurísticos pueden producir métricas de equidad superiores en comparación con las soluciones existentes.

Los autores concluyen que el uso de kBP ofrece una vía viable para la distribución equitativa de electricidad, especialmente cuando el objetivo es maximizar el tiempo que cada agente permanece conectado, y que las adaptaciones heurísticas son necesarias y efectivas para maximizar la equidad del volumen de energía (vatios) entregado.