기술 요약: k-회 이진 패킹을 활용한 전력 배분에서의 시간 및 공급 공정성

1. 문제 정의

본 논문은 개발도상국에서 총 가계 수요가 가용 공급 용량 ($S$) 을 초과하는 상황에서의 공정한 전력 배분 문제를 다룹니다. 핵심 과제는 다양한 수요 ($D$) 를 가진 $n$ 개의 가구에 제한된 전력을 배분하여 공정성을 극대화하는 것입니다.

저자들은 두 가지 명확한 최적화 목표를 정의합니다:

1. 연결 시간의 평등 배분: 모든 가구가 그리드에 연결되는 최소 시간을 극대화하는 것입니다. 에이전트의 효용은 이진적입니다. 즉, 특정 시간 구간에서 전체 수요가 충족될 때만 효용을 얻으며, 부분 충족은 효용 0 을 초래합니다. 이는 특정 전력 임계값이 충족되어야만 작동하는 활동 시나리오를 모델링합니다.
2. 와트 (공급) 의 평등 배분: 모든 가구에 할당되는 최소 전기 에너지 양 (kWh 단위) 을 극대화하는 것입니다. 시간 기반 모델과 달리, 이는 공급된 전력의 양을 고려하여 연결 시간이 다르더라도 에이전트들이 받는 총 에너지를 균등화하는 것을 목표로 합니다.

본 논문은 시간 기반 문제를 고전적인 **이진 패킹 문제 (Bin Packing Problem)**의 변형인 **k-회 이진 패킹 (k-times bin-packing, kBP)**으로 공식화합니다. kBP 에서 주어진 항목 (수요) 집합과 이진 용량 $S$에 대해, 다음 조건을 만족하도록 항목을 최소 개수의 이진에 채우는 것이 목표입니다:

• 각 이진 내 항목 크기의 합이 $S$를 초과하지 않아야 합니다.
• 각 항목은 정확히 $k$개의 서로 다른 이진에 나타나야 합니다.
• 어떤 이진도 동일한 항목의 복사본을 하나 이상 포함해서는 안 됩니다.

2. 방법론 및 이론적 프레임워크

이론적 기초

저자들은 전력 분할 문제와 kBP 간의 이론적 연결고리를 확립합니다.

• 최적 $k$의 존재성: $n$개 가구가 있는 모든 전력 분할 사례에 대해, kBP 문제를 최적적으로 해결하면 평등한 연결 시간 문제에 대한 최적 해를 산출하는 유한한 정수 $k$가 존재함을 증명합니다.
• $k$의 상한 및 하한: 논문은 $n$개 가구의 수에 기반하여 이 $k$에 대한 상한을 제시하며, 구체적으로 $k \le a(n)$입니다. 여기서 $a(n)$은 $n \times n$ 크기의 이진 행렬 (하마드 행렬과 관련됨) 의 최대 행렬식입니다. 또한 특정 사례에 대해 $k \ge n-1$인 하한도 확립되었습니다.
• 와트에 대한 불가능성: 반면, 와트의 평등한 배분에 대해서는 저자들이 불가능성 결과를 증명합니다. 즉, 최적 해를 보장하는 오직 에이전트 수 $n$에만 의존하는 유한한 $k$는 존재하지 않습니다. 이는 최적 해가 수요가 적은 에이전트들이 훨씬 더 긴 시간 동안 연결되도록 요구할 수 있으며, 이는 무제한의 반복 비율을 필요로 하기 때문입니다.

알고리즘적 확장

kBP 가 NP-난해 (NP-hard) 문제이므로, 논문은 기존 이진 패킹 근사 알고리즘을 kBP 설정으로 확장하는 데 중점을 둡니다:

1. 빠른 상수 인자 근사:

   • $FF_k$ (First-Fit): 저자들은 First-Fit 알고리즘을 입력 사례 ($D^k$) 의 $k$개 복사본을 처리하도록 확장합니다. 점근적 근사 비율이 $(1.5 + \frac{1}{5k}) \cdot OPT(D^k) + 3k$임을 증명합니다. $k$가 증가함에 따라 비율은 1.5 에 수렴하여 기존 First-Fit 비율인 1.7 보다 개선됩니다.
   • $FFD_k$ (First-Fit Decreasing): 저자들은 First-Fit Decreasing 을 확장합니다. 엄밀한 상한은 증명되지 않았으나, 시뮬레이션 데이터를 기반으로 점근적 비율이 $11/9$(약 1.22) 일 것이라고 추측하며, 이는 기존 FFD 비율보다 개선된 것입니다.
   • $NF_k$ (Next-Fit): Next-Fit 의 확장은 점근적 비율이 2 임이 입증되었습니다.

2. 다항 시간 근사 스킴 (PTAS):

   • 논문은 Fernandez de la Vega-Lueker 및 Karmarkar-Karp 알고리즘을 일반화합니다.
   • Fernandez de la Vega-Lueker 의 확장은 $(1 + 2\epsilon)OPT(D^k) + k$개의 이진을 달성합니다.
   • Karmarkar-Karp 알고리즘 1 과 2 의 확장은 $k$와 $\epsilon$에 의존하는 가산 항을 가진 해를 제공하며, 다항 시간 내에 실행됩니다.

3. 와트 배분을 위한 휴리스틱:

   • 와트 배분에 대한 보편적인 $k$의 불가능성으로 인해, 저자들은 네 가지 휴리스틱 알고리즘 (HA1–HA4) 을 제안합니다.
   • 이러한 휴리스틱은 두 단계 프로세스를 사용합니다:
     1. 연속적으로(상시) 연결될 최소 수요를 가진 에이전트들의 부분 집합을 식별합니다.
     2. 남은 에이전트와 감소된 공급에 대해 kBP 기반 전략 ($FF_k$ 또는 $FFD_k$ 사용) 을 적용하여 최소 와트 할당을 극대화합니다.
   • 이러한 알고리즘은 **삼분 탐색 (ternary search)**을 활용하여 leximin 벡터 (최악의 상황에 있는 에이전트를 우선시함) 를 극대화하는 연속 연결 부분 집합의 최적 크기 ($g$) 를 결정합니다.

3. 주요 결과 및 실험적 평가

이론적 결과

• 근사 비율: 논문은 $FF_k$ 및 $NF_k$의 근사 비율에 대한 엄밀한 증명을 제공합니다. $FF_k$의 경우, $k$가 커질수록 비율이 개선되어 이론적으로 1.5 로 수렴합니다.
• 불가능성: 평등한 와트 배분에 대해 오직 $n$에만 의존하는 유한한 $k$로는 충분하지 않다는 증명은 이 특정 변형에 대한 휴리스틱 접근법으로의 전환을 동기화합니다.

실험적 결과

저자들은 두 가지 데이터 세트를 사용하여 알고리즘을 평가했습니다:

1. 합성 데이터: $FF_k$ 및 $FFD_k$의 근사 비율을 검증하기 위해 알려진 최적 해를 가진 사례를 생성했습니다. 결과는 $k > 1$일 때 $FF_k$가 1.375 비율을 달성하고 $FFD_k$가 $11/9$를 달성한다는 가설을 지지했습니다.
2. 실제 데이터: 나이지리아의 367 개 가구에 대한 데이터 세트로 (Oluwasuji 등 [34, 35] 에서 제공), 13 주간의 시간당 수요를 포함합니다.

연결 시간 성능 (평등한 시간):

• $FF_k$ 및 $FFD_k$ 알고리즘 ($k=100$으로 테스트) 은 평등한 연결 시간 측면에서 기존 휴리스틱 및 ILP 기반 방법 (예: [35] 의 Comfort Model 및 Supply Model) 보다 현저히 우수한 성과를 보였습니다.
• 에이전트 간 최대 효용 차이가 거의 0 에 수렴하여 매우 공정한 배분을 나타냈습니다.
• 알고리즘은 에이전트 수에 대해 거의 선형 시간으로 실행되었습니다.

와트 배분 성능 (평등한 와트):

• 네 가지 휴리스틱 중 HA1($FFD_k$ 사용) 이 최악의 상황에 있는 에이전트에 공급되는 최대 전력량을 제공하는 데 가장 잘 수행되었습니다.
• HA4($FF_k$ 사용) 는 공급된 총 와트 양과 총 연결 시간 측면에서 다른 것들보다 우수했습니다.
• 휴리스틱은 수요가 적은 에이전트를 연속적으로 연결하는 것과 남은 공급을 수요가 큰 에이전트에게 공정하게 분배하는 것 사이의 균형을 성공적으로 유지했습니다.

4. 의의 및 주장

본 논문은 자원 제약 환경에서 전력 분할을 위한 실용적이고 공정하며 효율적인 프레임워크를 제공한다고 주장합니다. 주요 기여점은 다음과 같습니다:

• 공식화: 항목이 불연속 집합 간에 복제되어야 하는 공정한 자원 할당을 위한 수학적 추상화로서 k-회 이진 패킹 문제를 정의합니다.
• 알고리즘적 개선: 표준 이진 패킹 휴리스틱을 kBP 설정으로 확장하면 원래 알고리즘보다 더 나은 근사 비율을 산출하며, 특히 연결 시간에 대한 평등한 결과를 개선함을 입증합니다.
• 실제 적용: 이러한 이론적 확장이 기존 최첨단 방법보다 실제 부하 차단 문제를 더 효과적으로 해결할 수 있음을 검증했으며, 특히 모든 가구의 최소 연결 시간을 극대화하는 데 효과적입니다.
• 새로운 벤치마크: 와트의 평등한 배분을 위한 새로운 벤치마크를 확립하여, 이론적 최적 $k$는 존재하지 않지만 휴리스틱 접근법이 기존 솔루션보다 우수한 공정성 지표를 제공할 수 있음을 보여줍니다.

저자들은 kBP 를 사용하면 특히 각 에이전트가 연결되는 시간을 극대화하는 것이 목표일 때 공정한 전력 배분을 위한 실현 가능한 경로가 제공되며, 공급된 에너지 양 (와트) 의 공정성을 극대화하기 위해서는 휴리스틱 적응이 필요하고 효과적이라고 결론지었습니다.