技術概要：k 回ビンパッキングを用いた電力分配における時間と供給の公平性

1. 問題定義

本論文は、総世帯需要が利用可能な供給容量（$S$）を上回る発展途上国における公平な電力分配の問題を取り扱っている。核心的な課題は、需要（$D$）が異なる $n$ 世帯の間で限られた電力を割り当て、公平性を最大化することである。

著者らは、2 つの明確な最適化目標を定義している：

1. 接続時間の平等配分：どの世帯もグリッドに接続される最小時間を最大化することを目的とする。エージェントの効用は二元的である。つまり、ある時間区間において完全な需要が満たされた場合にのみ効用を得る。部分的な充足はゼロの効用をもたらす。これは、特定の電力閾値が機能するために必要な活動のシナリオをモデル化するものである。
2. ワット（供給）の平等配分：どの世帯にも割り当てられる電気エネルギー（kWh 単位）の最小量を最大化することを目的とする。時間ベースのモデルとは異なり、これは供給される電力の量を考慮し、接続時間が異なってもエージェントが受け取る総エネルギーを均等化することを目指す。

本論文は、時間ベースの問題を古典的なビンパッキング問題の変種として形式化し、**k 回ビンパッキング（kBP）**と称している。kBP において、アイテム（需要）の集合とビン容量 $S$ が与えられたとき、以下の条件を満たすようにアイテムを最小数のビンに詰めることが目的である：

• 各ビン内のアイテムサイズの合計が $S$ を超えないこと。
• 各アイテムが正確に $k$ 個の異なるビンに現れること。
• どのビンも同じアイテムの複製を 1 つ以上含まないこと。

2. 手法と理論的枠組み

理論的基盤

著者らは、電力分割問題と kBP の間の理論的リンクを確立している。

• 最適 $k$ の存在：$n$ 世帯からなる任意の電力分割インスタンスに対して、kBP 問題を最適に解くことが、平等な接続時間問題の最適解をもたらすような有限整数 $k$ が存在することを証明している。
• $k$ の境界：本論文は、この $k$ の上限を世帯数 $n$ に基づいて提供しており、具体的には $k \le a(n)$ である。ここで $a(n)$ は $n \times n$ 二値行列（ハダマード行列に関連する）の最大行列式である。また、特定のインスタンスに対して $k \ge n-1$ という下限も確立されている。
• ワットに対する不可能性：対照的に、ワットの平等配分については、著者らは不可能性を証明している。つまり、エージェント数 $n$ のみに依存する有限の $k$ が最適解を保証することはあり得ない。その理由は、最適解において需要の小さいエージェントが著しく長い期間接続される必要があり、無限に増大する繰り返し比率が必要となるためである。

アルゴリズム的拡張

kBP は NP 困難であるため、本論文は既存のビンパッキング近似アルゴリズムを kBP 設定に拡張することに焦点を当てている：

1. 高速な定数倍近似：

   • $FF_k$（ファーストフィット）：著者らはファーストフィットアルゴリズムを拡張し、入力インスタンス（$D^k$）の $k$ 個の複製を処理するようにした。漸近的近似比は $(1.5 + \frac{1}{5k}) \cdot OPT(D^k) + 3k$ であることを証明している。$k$ が増加するにつれ、この比は 1.5 に近づき、標準的なファーストフィットの比 1.7 を上回る。
   • $FFD_k$（ファーストフィット減少）：著者らはファーストフィット減少を拡張している。厳密な上限は証明されていないが、シミュレーションデータに基づき、漸近的比は $11/9$（約 1.22）であると予想しており、標準的な FFD の比を改善している。
   • $NF_k$（ネクストフィット）：ネクストフィットの拡張は、漸近的比が 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$ の不可能性により、著者らは 4 つのヒューリスティックアルゴリズム（HA1–HA4）を提案している。
   • これらのヒューリスティックは 2 段階のプロセスを採用している：
     1. 需要が最小のエージェントのサブセットを特定し、これらを連続的（常に）接続する。
     2. 残りのエージェントと削減された供給に対して、最小ワット配分を最大化するために kBP ベースの戦略（$FF_k$ または $FFD_k$ を使用）を適用する。
   • これらのアルゴリズムは、最悪の状況にあるエージェントを優先するレキシミンベクトルを最大化する、連続接続サブセットのサイズ（$g$）を決定するために三分探索を利用している。

3. 主要な結果と実験的評価

理論的結果

• 近似比：本論文は、$FF_k$ および $NF_k$ の近似比に対する厳密な証明を提供している。$FF_k$ については、$k$ が大きくなるにつれて比が改善され、理論的には 1.5 に収束する。
• 不可能性：平等なワット配分に対して、$n$ のみに依存する有限の $k$ では不十分であるという証明は、この特定の変種に対してヒューリスティックアプローチへの転換を促している。

実験結果

著者らは 2 つのデータセットを用いてアルゴリズムを評価した：

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] からのコンフォートモデルおよびサプライモデルなど）を大幅に上回った。
• エージェント間の最大効用差がほぼゼロに達しており、極めて公平な分配を示している。
• これらのアルゴリズムは、エージェント数に対してほぼ線形時間で実行された。

ワット配分（平等なワット）におけるパフォーマンス：

• 4 つのヒューリスティックの中で、HA1（$FFD_k$ を使用）は、最悪の状況にあるエージェントに供給される電力の最大量において最良のパフォーマンスを発揮した。
• HA4（$FF_k$ を使用）は、供給された総ワット量と総接続時間において他を凌駕した。
• これらのヒューリスティックは、需要の小さいエージェントを連続接続することと、残りの供給を需要の大きいエージェントに公平に分配することの間のトレードオフを成功裏にバランスさせた。

4. 意義と主張

本論文は、資源制約のある環境における電力分割のための実用的で公平かつ効率的な枠組みを提供すると主張している。主な貢献点は以下の通りである：

• 形式化：アイテムが互いに素な集合間で複製されなければならない公平な資源配分に対する数学的抽象化として、k 回ビンパッキング問題を定義すること。
• アルゴリズム的改善：標準的なビンパッキングヒューリスティックを kBP 設定に拡張することが、元のアルゴリズムよりも優れた近似比をもたらすことを実証し、特に接続時間の平等な成果を改善すること。
• 実用的応用：これらの理論的拡張が、特にすべての世帯の最小接続時間を最大化する点において、従来の最先端手法よりも効果的に現実世界の負荷削減問題を解決できることを検証すること。
• 新しいベンチマーク：ワットの平等配分に対する新しいベンチマークを確立し、理論的な最適 $k$ は存在しないが、ヒューリスティックアプローチが既存の解決策と比較して優れた公平性指標をもたらすことを示すこと。

著者らは、kBP を使用することが、特に各エージェントが接続される時間を最大化することが目的である場合に、公平な電力分配への viable な道筋を提供すると結論付けている。また、供給されるエネルギー量（ワット）の公平性を最大化するためには、ヒューリスティックの適応が必要であり、かつ効果的であると述べている。