Advent calendar 初投稿です。よろしくお願いします。
実務寄りの話題をと思ったのですが、書いている途中で論理が破綻したので別の話題を提供します…。
目次
背景
仕事でビンパッキング問題の亜種を解くことがあったのですが、あまり知られていないような気がするのでこの機会に紹介します。
前提: ビンパッキング問題とは？
ChatGPTによる説明:
ビンパッキング問題（Bin Packing Problem, BPP） は、組合せ最適化問題の一つで、限られた容量のビン（箱）に対して与えられた一連のアイテムを効率的に詰め込む方法を見つける問題です。アイテムが収まる最小のビン数を求めることが主な目標です。
ビンパッキング問題はNP困難に分類される問題のため、入力サイズが増えると計算時間が指数的に増加する可能性があり、大規模な問題では最適解を求めるのが難しい。
代表的な解法として、以下のものがあげられる。
- 厳密解法
- 動的計画法
- 分枝限定法
- 整数線形計画法
- 列生成法 ※参考: はじめての列生成法
- 近似解法 ※参考:しっかり学ぶ数理最適化 4.5.2
- Next-Fit法: $O(n)の計算量、$2倍以下の精度保証
- First-Fit法: $O(n^2)$の計算量、1.7倍以下の精度保証
- First-Fit-Decreasing法: $O(n^2)$の計算量、1.7倍以下の精度保証、First-Fitより高精度
整数線形計画法でナイーブに解く場合は、以下のように定式化する。
アイテム数を$N$, ビンの数を$M(\le N)$, アイテム$i$のサイズを$S_i$, ビンの容量を$C$とする。
$x_{ij}$をアイテム$i$のビン$j$への割り当て有無、$y_j$をビン$j$の使用有無を表すバイナリ変数とする。
\displaylines{
\begin{aligned}
&\text{Minimize} & \quad & \sum_{j=1}^m y_{j} \\
&\text{Subject to} & & \sum_{j=1}^m x_{ij} = 1, & \forall i \in \{1, \dots, n\} \\
& & & \sum_{i=1}^n S_i x_{ij} \leq C y_j, & \forall j \in \{1, \dots, m\} \\
& & & x_{ij} \in \{0, 1 \}, & \forall i \in \{1, \dots, n\}, \forall j \in \{1, \dots, m\} \\
& & & y_{j} \in \{0, 1 \} & \forall j \in \{1, \dots, m\}
\end{aligned}
\displaylines}
※参考: はじめての列生成法
分割可能なアイテムのビンパッキング問題
参考文献: Bin packing with fragmentable items: Presentation and approximations
分割可能なビンパッキング問題（Min-FIBP）は、固定された数のビンに対して、アイテムを分割して割り当てる問題である。すべてのアイテムをビンに収める際の分割数を最小に抑えることを目的関数とする。例えばアイテムのサイズが4のとき、一般的なビンパッキングでは割り当てるために容量が4以上のビンが1つ必要だが、Min-FIBPではサイズ1とサイズ3のアイテムに分割して2つのビンに割り当てることが可能になる。
↓ビンのサイズと本数は固定されている。分割なしでは入りきらない。
↓サイズ4のビンをサイズ(1,3)の2つに分割することで、3本のビンに詰め込むことができる
Min-FIBPの特殊なケースとして、全てのビンの容量が一定であるMin-FIBP-EQという亜種の問題がある。この問題はNP完全であることが証明されている。
用途
論文中では代表的な用途として、以下の例を挙げている。
- グループ会計の清算: 複数人のメンバーからなるグループで共通の費用を支払った後、各メンバーがどのようにお金を返し合うかを決定する際に、ビンは返金を受けるメンバーを、アイテムは返金するメンバーを表す。各お金の移動をできるだけ分割することなく実行できる。
- 光ネットワークにおける波長割り当て: 光通信ネットワークでは、ノードがトラフィックを任意の波長で送信できるが、受信ノードは限られた数の波長しか読み取れないため、エネルギー消費を最小限に抑えるために、トラフィックを波長に割り当てる問題を解く必要がある。
解法
(混合)整数計画法
アイテム数を$N$, ビンの数を$M$, アイテム$i$のサイズを$S_i$, ビン$j$の容量を$C_j$とすると、整数線形計画問題として定式化できる。
\displaylines{
\begin{aligned}
&\text{Minimize} & \quad & \sum_{i=1}^n \sum_{j=1}^m y_{ij} \\
&\text{Subject to} & & \sum_{j=1}^m x_{ij} = S_i, & \forall i \in \{1, \dots, n\} \\
& & & \sum_{i=1}^n x_{ij} \leq C_j, & \forall j \in \{1, \dots, m\} \\
& & & x_{ij} \leq S_i y_{ij}, & \forall j \in \{1, \dots, m\}, \forall j \in \{1, \dots, m\} \\
& & & x_{ij} \in \mathbb{Z} _ {+}, y_{ij} \in \{0, 1 \} & \forall i \in \{1, \dots, n\}, \forall j \in \{1, \dots, m\}.
\end{aligned}
\displaylines}
普通のビンパッキング問題の定式化と一部似ているが、アイテム$i$のビン$j$への割り当てが分割されるため0以上の整数となり、各アイテムの分割数をカウントするために$x_{ij}$が正の数であるか否かを表すバイナリ変数$y_{ij}$が必要となる。
目的関数は厳密には分割数ではなくフラグメントの数になっている。一度も分割されなかったとしても、アイテム数と同じN個のフラグメントができることになる。
上記の定式化は、アイテムの分割され得るポイントが(長さ1ずつ)等間隔に存在することが前提になっているが、もしアイテムを任意の位置で分割できる場合は$x_ij$は0以上の実数となり、混合整数線形計画問題として考えればよい。
近似解法
参考文献では、Min-FIBPの中でも以下の条件が成り立つ特殊なケースのみ適用できる、近似精度1.2のアルゴリズムが提案されている。
- すべてのビンの容量$C$が一定である(Min-FIBP-EQ)
- すべてのアイテムのサイズ$S_i$がビンの容量$C$以下である
できれば理解したうえで実装まで紹介したかったのですが、間に合わなかったのでここでは割愛させていただきます。その代わりに、もっと簡単な貪欲法のアルゴリズムを紹介します。
貪欲法
手順
- 空のビン$j$を選択する
- 任意の未割り当てのアイテム$i$を選択する。アイテムがなくなったら終了
- アイテム$i$をアイテム$J$に割り当てる
- もし現在選択しているビン$j$の残容量$R_j$がアイテムのサイズより大きい場合は、
- アイテムを分割せずに割り当てる
- ビンの残容量を$R_j - S_i$に更新する
- 2に戻る
- もし現在選択しているビン$j$の残り容量$R_j$がアイテムのサイズより小さい場合は、
- アイテム$i$をビンの残容量$R_j$と同じサイズに分割し、割り当てる
- 分割後の残りアイテムをのサイズを$S_i = S_i - R_j$とする
- 空のビン$j$を選択し、3に戻る
- もし現在選択しているビン$j$の残容量$R_j$がアイテムのサイズより大きい場合は、
性能
- 計算量: $O(n)$
- 精度(分割数): 最悪のケースで$M-1$
$S_i \leq C$であることに着目すると、最初に選んだビンに対し、最初のアイテムは必ず分割されずに割り当てられる。2回目以降に選んだアイテムが運悪くすべて分割されたとしても、次のビンには必ず入るので、せいぜい分割数はビン1つ当たり1回まで。したがって最悪のケースの分割数は$M-1$となる。
MILPソルバーで解いてみる
実装
ソースコードはこちら
https://github.com/rtonoue/min_fibp
※定式化のtexをChatGPTに入力してコードを書いてもらいました。
from pulp import LpProblem, LpVariable, LpMinimize, lpSum, LpStatus, value
import pandas as pd
import pprint
# 問題のパラメータ
bin_count = 5
bin_capacity = 10
items = [
{"item": "A", "size": 12},
{"item": "B", "size": 8},
{"item": "C", "size": 7},
{"item": "D", "size": 6},
{"item": "E", "size": 5},
{"item": "F", "size": 3},
]
# ビンデータ
bins = list(range(bin_count))
# 問題定義
problem = LpProblem("Min_FIBP", LpMinimize)
# 変数定義
x = LpVariable.dicts("x", ((i["item"], b) for i in items for b in bins), lowBound=0, cat="Continuous")
y = LpVariable.dicts("y", ((i["item"], b) for i in items for b in bins), cat="Binary")
# 目的関数: 分割数を最小化
problem += lpSum(y[i["item"], b] for i in items for b in bins)
# 制約: 各アイテムの合計サイズは元のサイズに等しい
for i in items:
problem += lpSum(x[i["item"], b] for b in bins) == i["size"]
# 制約: 各ビンの容量制限
for b in bins:
problem += lpSum(x[i["item"], b] for i in items) <= bin_capacity
# 制約: x_ij > 0 のとき y_ij = 1
for i in items:
for b in bins:
problem += x[i["item"], b] <= i["size"] * y[i["item"], b]
# 問題を解く
problem.solve()
# 結果の出力
status = LpStatus[problem.status]
used_bins = [b for b in bins if sum(value(x[i["item"], b]) for i in items) > 0]
packed_items = {
b: {i["item"]: value(x[i["item"], b]) for i in items if value(x[i["item"], b]) > 0}
for b in used_bins
}
results = {
"status": status,
"number_of_fragments": problem.objective.value(),
"packed_items": packed_items,
}
# Packed items をCSVに保存
packed_items_df = pd.DataFrame(
[
{"bin": b, "item": i, "packed_size": packed_items[b][i]}
for b in packed_items
for i in packed_items[b]
]
)
packed_items_csv_path = "./data/min_fibp_packed_items.csv"
packed_items_df.to_csv(packed_items_csv_path, index=False)
pprint.pprint(results)
print(packed_items_df)
実行結果
{'number_of_fragments': 7.0,
'packed_items': {0: {'C': 7.0},
1: {'A': 10.0},
2: {'A': 2.0, 'B': 8.0},
3: {'E': 5.0, 'F': 3.0},
4: {'D': 6.0}},
'status': 'Optimal'}
bin item packed_size
0 0 C 7.0
1 1 A 10.0
2 2 A 2.0
3 2 B 8.0
4 3 E 5.0
5 3 F 3.0
6 4 D 6.0
所感
適当に作った近似解法でもそれなりに良い解が出そうで、厳密解法で時間をかけて解く価値があるかどうかは微妙かもしれない。2次元のビンパッキング問題に適用したらめちゃくちゃ難しそうだと思った。