Resumo Técnico: Equidade Temporal e de Fornecimento na Distribuição de Eletricidade usando Empacotamento em K-Bins

1. Definição do Problema

O artigo aborda o problema da distribuição justa de eletricidade em países em desenvolvimento, onde a demanda total das residências excede a capacidade de fornecimento disponível ($S$). O desafio central é alocar a eletricidade limitada entre $n$ residências com demandas variadas ($D$) de forma a maximizar a equidade.

Os autores definem dois objetivos de otimização distintos:

1. Alocação Egalitária de Tempo de Conexão: O objetivo é maximizar a quantidade mínima de tempo que qualquer residência permanece conectada à rede. A utilidade de um agente é binária: eles ganham utilidade apenas se sua demanda total for atendida durante um intervalo de tempo; o atendimento parcial resulta em utilidade zero. Isso modela cenários onde atividades exigem um limiar específico de potência para funcionar.
2. Alocação Egalitária de Watts (Fornecimento): O objetivo é maximizar a quantidade mínima de energia elétrica (em kWh) alocada a qualquer residência. Diferentemente do modelo baseado em tempo, este considera o volume de eletricidade entregue, visando equalizar a energia total recebida pelos agentes, mesmo que seus tempos de conexão diferam.

O artigo formaliza o problema baseado em tempo como uma variante do clássico Problema de Empacotamento em Binários, denominado empacotamento em k-bins (kBP). No kBP, dado um conjunto de itens (demandas) e capacidade do bin $S$, o objetivo é empacotar itens no número mínimo de bins tal que:

• A soma dos tamanhos dos itens em cada bin não exceda $S$.
• Cada item apareça em exatamente $k$ bins distintos.
• Nenhum bin contenha mais de uma cópia do mesmo item.

2. Metodologia e Framework Teórico

Fundamentos Teóricos

Os autores estabelecem uma ligação teórica entre o problema de divisão de eletricidade e o kBP.

• Existência de $k$ Ótimo: Eles provam que, para qualquer instância de divisão de eletricidade com $n$ residências, existe um inteiro finito $k$ tal que resolver o problema kBP de forma ótima produz a solução ótima para o problema de tempo de conexão egalitário.
• Limites para $k$: O artigo fornece um limite superior para este $k$ baseado no número de residências $n$, especificamente $k \le a(n)$, onde $a(n)$ é o determinante máximo de uma matriz binária $n \times n$ (relacionada a matrizes de Hadamard). Um limite inferior de $k \ge n-1$ também é estabelecido para instâncias específicas.
• Impossibilidade para Watts: Por outro lado, para a alocação egalitária de watts, os autores provam um resultado de impossibilidade: não existe um $k$ finito que dependa apenas do número de agentes $n$ para garantir uma solução ótima. Isso ocorre porque soluções ótimas podem exigir que agentes com demandas menores permaneçam conectados por durações significativamente maiores, exigindo razões de repetição ilimitadas.

Extensões Algorítmicas

Como o kBP é NP-difícil, o artigo concentra-se em estender algoritmos de aproximação de empacotamento existentes para o cenário kBP:

1. Aproximações Constantes Rápidas:

   • $FF_k$ (Primeiro Ajuste): Os autores estendem o algoritmo Primeiro Ajuste para processar $k$ cópias da instância de entrada ($D^k$). Eles provam uma razão de aproximação assintótica de $(1.5 + \frac{1}{5k}) \cdot OPT(D^k) + 3k$. À medida que $k$ aumenta, a razão aproxima-se de 1.5, superando a razão padrão do Primeiro Ajuste de 1.7.
   • $FFD_k$ (Primeiro Ajuste Decrescente): Os autores estendem o Primeiro Ajuste Decrescente. Embora um limite superior rigoroso não seja provado, eles conjecturam uma razão assintótica de $11/9$ (aprox. 1.22) com base em dados de simulação, superando a razão padrão do FFD.
   • $NF_k$ (Próximo Ajuste): A extensão do Próximo Ajuste mostra-se com uma razão assintótica de 2.

2. Esquemas de Aproximação em Tempo Polinomial (PTAS):

   • O artigo generaliza os algoritmos de Fernandez de la Vega-Lueker e Karmarkar-Karp.
   • A extensão de Fernandez de la Vega-Lueker alcança $(1 + 2\epsilon)OPT(D^k) + k$ bins.
   • As extensões dos Algoritmos 1 e 2 de Karmarkar-Karp fornecem soluções com termos aditivos dependentes de $k$ e $\epsilon$, executando em tempo polinomial.

3. Heurísticas para Alocação de Watts:

   • Devido à impossibilidade de um $k$ universal para alocação de watts, os autores propõem quatro algoritmos heurísticos (HA1–HA4).
   • Essas heurísticas empregam um processo de duas etapas:
     1. Identificar um subconjunto de agentes com as menores demandas para serem conectados continuamente (o tempo todo).
     2. Aplicar estratégias baseadas em kBP (usando $FF_k$ ou $FFD_k$) aos agentes restantes e ao fornecimento reduzido para maximizar a alocação mínima de watts.
   • Os algoritmos utilizam busca ternária para determinar o tamanho ótimo do subconjunto conectado continuamente ($g$) que maximiza o vetor leximin (priorizando o agente mais prejudicado).

3. Resultados Principais e Avaliação Experimental

Resultados Teóricos

• Razões de Aproximação: O artigo fornece provas rigorosas para as razões de aproximação de $FF_k$ e $NF_k$. Para $FF_k$, a razão melhora conforme $k$ cresce, convergindo teoricamente para 1.5.
• Impossibilidade: A prova de que nenhum $k$ finito (dependente apenas de $n$) basta para a alocação egalitária de watts motiva a mudança para abordagens heurísticas para esta variante específica.

Resultados Experimentais

Os autores avaliaram seus algoritmos usando dois conjuntos de dados:

1. Dados Sintéticos: Instâncias geradas com soluções ótimas conhecidas para verificar as razões de aproximação de $FF_k$ e $FFD_k$. Os resultados apoiaram a conjectura de que $FF_k$ alcança uma razão de 1.375 e $FFD_k$ alcança $11/9$ para $k > 1$.
2. Dados do Mundo Real: Um conjunto de dados de 367 residências da Nigéria (de Oluwasuji et al. [34, 35]) cobrindo 13 semanas de demanda horária.

Desempenho no Tempo de Conexão (Tempo Egalitário):

• Os algoritmos $FF_k$ e $FFD_k$ (testados com $k=100$) superaram significativamente métodos heurísticos existentes e baseados em ILP (como o Modelo de Conforto e o Modelo de Fornecimento de [35]) em termos de tempo de conexão egalitário.
• Eles alcançaram diferenças de utilidade máxima próximas de zero entre os agentes, indicando uma distribuição altamente equitativa.
• Os algoritmos executaram em tempo quase linear em relação ao número de agentes.

Desempenho na Alocação de Watts (Watts Egalitários):

• Entre as quatro heurísticas, a HA1 (usando $FFD_k$) performou melhor no fornecimento da maior quantidade de eletricidade ao agente mais prejudicado.
• A HA4 (usando $FF_k$) superou as outras no total de watts entregues e no tempo total de conexão.
• As heurísticas equilibraram com sucesso o trade-off entre conectar agentes de baixa demanda continuamente e distribuir o fornecimento restante de forma justa para agentes de maior demanda.

4. Significado e Alegações

O artigo alega fornecer um framework prático, justo e eficiente para a divisão de eletricidade em ambientes com recursos limitados. Suas contribuições primárias são:

• Formalização: Definir o problema de empacotamento em k-bins como uma abstração matemática para alocação justa de recursos onde itens devem ser replicados em conjuntos disjuntos.
• Melhoria Algorítmica: Demonstrar que estender heurísticas padrão de empacotamento para o cenário kBP produz melhores razões de aproximação do que os algoritmos originais, melhorando especificamente o resultado egalitário para o tempo de conexão.
• Aplicação Prática: Validar que essas extensões teóricas podem resolver problemas reais de racionamento de carga mais efetivamente do que métodos anteriores de última geração, particularmente na maximização do tempo mínimo de conexão para todas as residências.
• Novos Benchmarks: Estabelecer novos benchmarks para a alocação egalitária de watts, mostrando que, embora um $k$ ótimo teórico não exista, abordagens heurísticas podem produzir métricas de equidade superiores em comparação com soluções existentes.

Os autores concluem que o uso de kBP oferece um caminho viável para a distribuição justa de eletricidade, particularmente quando o objetivo é maximizar o tempo em que cada agente permanece conectado, e que adaptações heurísticas são necessárias e eficazes para maximizar a equidade do volume de energia (watts) entregue.