箱詰め問題

🔥 Vibe プロンプト

「OR-Tools CP-SATで箱詰めを解決：容積[48,30,19,36,36,27,42,42,36,24,30]、箱容量100。箱数を最小化。」

箱詰め問題とは？

箱詰め問題（Bin Packing） は、様々なサイズのアイテムを固定容量の箱に最小の箱数で詰める組合せ最適化問題です。

| 実世界の例 | |-----------| | 📦 クラウド: VMを物理サーバーに配置（サーバー最小化） | | 🚚 物流: 荷物をトラックに積載（トラック最小化） | | 📰 印刷: 広告をページに配置（ページ最小化） | | 💾 ストレージ: ファイルをディスクに割り当て（ディスク最小化） |

CP-SATによる実装

from ortools.sat.python import cp_model

items = [48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30]
bin_capacity = 100
num_items = len(items)
num_bins = num_items

model = cp_model.CpModel()

# 変数
x = [[model.NewBoolVar(f'x_{i}_{b}') for b in range(num_bins)] for i in range(num_items)]
used = [model.NewBoolVar(f'y_{b}') for b in range(num_bins)]

# 制約1: 各アイテムは1つの箱に
for i in range(num_items):
    model.Add(sum(x[i][b] for b in range(num_bins)) == 1)

# 制約2: 箱の容量制限
for b in range(num_bins):
    model.Add(sum(items[i] * x[i][b] for i in range(num_items)) <= bin_capacity)

# 制約3: y[b] = 箱bが使用中
for b in range(num_bins):
    model.Add(sum(x[i][b] for i in range(num_items)) >= used[b])
    model.Add(sum(x[i][b] for i in range(num_items)) <= num_items * used[b])

# 目的: 箱数を最小化
model.Minimize(sum(used))

solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 10
status = solver.Solve(model)

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f"\n=== 箱詰め結果 ===")
    print(f"使用箱数: {int(solver.ObjectiveValue())}")
    print(f"アイテム: {items}")
    
    for b in range(num_bins):
        if solver.Value(used[b]):
            bin_items = [i for i in range(num_items) if solver.Value(x[i][b])]
            vol = sum(items[i] for i in bin_items)
            print(f"\n箱{b}: 容量{vol}/{bin_capacity}")
            print(f"  アイテム: {bin_items} → サイズ: {[items[i] for i in bin_items]}")

貪欲法（大規模インスタンス用）

First-Fit Decreasing (FFD)

def first_fit_decreasing(items, capacity):
    bins = []
    for item in sorted(items, reverse=True):
        placed = False
        for i, remaining in enumerate(bins):
            if remaining >= item:
                bins[i] -= item
                placed = True
                break
        if not placed:
            bins.append(capacity - item)
    return len(bins)

items = [48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30]
print(f"FFD箱数: {first_fit_decreasing(items, 100)}")

手法比較

| アルゴリズム | 箱数 | 時間 | 保証 | |-----------|------|------|------| | 最適 (CP-SAT) | 4 | ~1秒 | 100% | | FFD | 4 | ~1ms | ≤ 11/9 × OPT | | BFD | 4 | ~1ms | ≤ 11/9 × OPT | | Next-Fit | 6 | ~0.1ms | ≤ 2 × OPT |

応用

クラウドVM配置: 物理サーバーの使用率最適化
データセンターネットワーク: 帯域予約
倉庫管理: パレットへの商品配置
メモリ管理: ページ割り当て
広告配置: 雑誌/Webページの広告レイアウト

まとめ

箱詰め問題 = NP困難、最小箱数を見つける
CP-SAT = 小〜中規模（<50アイテム）に最適
FFD/BFD = 大規模に高速な近似解（11/9近似比）
応用: クラウド、物流、倉庫、メモリ管理