ビンパッキング問題入門¶

1. はじめに¶

本資料では、線形計画問題から出発し、整数計画問題を経て、その代表的な応用であるビンパッキング問題(bin packing problem)までを一続きの流れで学ぶ。数式の背景は「線形計画問題入門」(optimization/lp/lp.ipynb)と「整数計画問題入門」(optimization/ip/ip.ipynb)で説明しているので、本資料は「モデルをPythonとPuLPで実際に解く」ことに重点を置く。

学習目標¶

  1. 線形計画問題と整数計画問題の違い(整数制約の影響)を具体例で説明できる。
  2. ビンパッキング問題を0-1整数計画問題として定式化できる。
  3. PuLP で定式化、求解し、結果を整理して読み取れる。

2. 線形計画の復習¶

まず、線形計画問題入門で扱った生産計画問題を例にする。

$$ \begin{align} \max \ \ & z = 3x_1 + 5x_2 \\ \text{s.t. } \ \ & x_1 + 7x_2 \leq 140, \\ & 2x_1 + 4x_2 \leq 100, \\ & 3x_1 + 2x_2 \leq 120, \\ & x_1 \geq 0, \ x_2 \geq 0. \end{align} $$

変数が2つなので、実行可能領域(すべての制約を満たす点の集合)を平面に描ける。目的関数 $z = 3x_1 + 5x_2$ の等高線(点線)を $z$ が大きくなる方向へ平行移動していくと、実行可能領域の頂点で止まる。線形計画問題では、最適解のうち少なくとも1つは実行可能領域の頂点にある。

In [1]:
import numpy as np
import matplotlib.pyplot as plt
import matplotlib as mpl

mpl.style.use('default')
plt.rcParams['mathtext.fontset'] = 'cm'

x1 = np.arange(0, 200, 0.1)
x2_1 = -(1 / 7) * x1 + 20
x2_2 = -(1 / 2) * x1 + 25
x2_3 = -(3 / 2) * x1 + 60

y1 = np.zeros_like(x1)
y2 = np.minimum(np.minimum(x2_1, x2_2), x2_3)

# 目的関数の等高線(z = 60, 142.5)
for i, z in enumerate([60, 142.5]):
    lbl = r'$z=3x_1+5x_2$' if i == 0 else None
    plt.plot(x1, -(3 / 5) * x1 + z / 5, color='red', linestyle='dotted', label=lbl)

plt.plot(x1, x2_1, zorder=0, label=r'$x_1+7x_2=140$')
plt.plot(x1, x2_2, zorder=0, label=r'$2x_1+4x_2=100$')
plt.plot(x1, x2_3, zorder=0, label=r'$3x_1+2x_2=120$')
plt.fill_between(x1, y1, y2, where=y1 < y2, facecolor='yellow', alpha=0.5)
plt.scatter([35], [7.5], color='red', zorder=3)
plt.text(36, 8.5, r'$(35,\ 7.5)$', fontsize=12)

plt.xlim(0, 60)
plt.ylim(0, 30)
plt.xlabel(r'$x_1$', fontsize=13)
plt.ylabel(r'$x_2$', fontsize=13)
plt.legend(fontsize=11)
plt.tight_layout()
plt.show()
No description has been provided for this image

黄色の領域が実行可能領域である。等高線を右上へ動かすと、最後に残るのは頂点 $(35, 7.5)$ であり、ここが最適解になる。PuLP で確認する。なおGoogle Colab で実行する際には、次のセルの2行目のコメントを外して実行すること。

In [2]:
# Google Colab の場合は2行目のコメントを外して実行: ライブラリインストール(1回だけ)
# !pip install pulp matplotlib
In [3]:
import pulp

prob = pulp.LpProblem('LP_example', pulp.LpMaximize)
x1v = pulp.LpVariable('x1', lowBound=0)  # 連続変数
x2v = pulp.LpVariable('x2', lowBound=0)

prob += 3 * x1v + 5 * x2v
prob += x1v + 7 * x2v <= 140
prob += 2 * x1v + 4 * x2v <= 100
prob += 3 * x1v + 2 * x2v <= 120

prob.solve(pulp.PULP_CBC_CMD(msg=0))
print('求解結果:', pulp.LpStatus[prob.status])
print(f'最適解: x1 = {x1v.value()}, x2 = {x2v.value()}')
print('最適値: z =', pulp.value(prob.objective))

求解結果: Optimal
最適解: x1 = 35.0, x2 = 7.5
最適値: z = 142.5

図から読み取ったとおり、最適解は $(x_1, x_2) = (35, 7.5)$、最適値は $z = 142.5$ である。実行可能領域の頂点を効率よくたどって最適解に到達する解法が単体法(simplex method)であり、詳細は授業で扱う。

3. 整数計画へ¶

ところで、$x_1$ と $x_2$ が製品の生産個数のような「数えられる量」なら、$x_2 = 7.5$ という解は使えない。変数に整数条件を課した問題が整数計画問題(integer programming problem)である。まず思いつくのは「線形計画の最適解を丸めればよい」という方法だが、それでよいのかをPuLP で確かめる。変数を整数にするには cat='Integer' を指定するだけでよい。

In [4]:
prob = pulp.LpProblem('IP_example', pulp.LpMaximize)
x1v = pulp.LpVariable('x1', lowBound=0, cat='Integer')  # 整数変数
x2v = pulp.LpVariable('x2', lowBound=0, cat='Integer')

prob += 3 * x1v + 5 * x2v
prob += x1v + 7 * x2v <= 140
prob += 2 * x1v + 4 * x2v <= 100
prob += 3 * x1v + 2 * x2v <= 120

prob.solve(pulp.PULP_CBC_CMD(msg=0))
print('求解結果:', pulp.LpStatus[prob.status])
print(f'整数計画の最適解: x1 = {int(x1v.value())}, x2 = {int(x2v.value())}')
print('整数計画の最適値: z =', int(pulp.value(prob.objective)))

# 線形計画の最適解(35, 7.5)を切り捨てた(35, 7)と比較する
print('丸めた解(35, 7)の目的関数値: z =', 3 * 35 + 5 * 7)

# 念のため、整数解を全列挙して確かめる
best_z, best_sol = -1, None
for a in range(0, 61):
    for b in range(0, 31):
        if a + 7 * b <= 140 and 2 * a + 4 * b <= 100 and 3 * a + 2 * b <= 120:
            if 3 * a + 5 * b > best_z:
                best_z, best_sol = 3 * a + 5 * b, (a, b)
print(f'全列挙による最適値: z = {best_z}, 最適解 = {best_sol}')

求解結果: Optimal
整数計画の最適解: x1 = 34, x2 = 8
整数計画の最適値: z = 142
丸めた解(35, 7)の目的関数値: z = 140
全列挙による最適値: z = 142, 最適解 = (34, 8)

整数計画の最適解は $(34, 8)$ で $z = 142$ である。丸めた解 $(35, 7)$ は実行可能ではあるものの $z = 140$ にとどまり、最適ではない。つまり整数条件は「解いたあとで丸めればよい」ものではなく、問題の構造そのものを変える。整数計画問題の代表的な解法である分枝限定法(branch and bound method)については、授業で扱う。

整数計画になると、施設の設置(0か1)や荷物の割当のような「組合せ」を変数で表せるようになる。次節のビンパッキング問題はその代表例である。

4. ビンパッキング問題¶

4.1 問題の定義¶

$n$ 個の荷物があり、荷物 $j$ のサイズを $s_j$ とする。容器は $m$ 個あり、容器 $i$ の容量は $c_i$ である。容器 $i$ に詰め込む荷物サイズの合計は $c_i$ を超えてはいけない。$n$ 個すべての荷物を詰め込むのに必要な、最小の容器の個数を求めたい。

宅配便のトラック割当、サーバへの仮想マシン配置、板材の切り出しなど、「限られた入れ物に無駄なく詰める」場面に広く現れる問題である。

4.2 定式化¶

決定変数は「容器 $i$ を使うかどうか」を表す $y_i$ と、「荷物 $j$ を容器 $i$ に入れるかどうか」を表す $x_{ij}$ の2種類である。

$$ \begin{align} \min \ \ & z = \sum_{i=1}^{m} y_i \\ \text{s.t. } \ \ & \sum_{j=1}^{n} s_j x_{ij} \leq c_i y_i, \quad \forall i \in \{1, \dots, m\}, \\ & \sum_{i=1}^{m} x_{ij} = 1, \quad \forall j \in \{1, \dots, n\}, \\ & x_{ij} \in \{0, 1\}, \quad y_i \in \{0, 1\}. \end{align} $$

1本目の制約は容量制約である。右辺が $c_i y_i$ になっている点が重要で、容器 $i$ を使わない($y_i = 0$)なら右辺は0となり、その容器には何も入れられない。逆に何か入れるなら $y_i = 1$ にせざるを得ず、目的関数(使う容器の数)に1が加算される。2本目は、どの荷物もちょうど1つの容器に入れることを表す。

4.3 PuLP による実装¶

小さな例で解いてみる。荷物は6個(サイズ 3、5、4、6、2、7)、容器は4個(容量 8、10、12、14)とする。データはサイズのリスト s と容量のリスト c で持つ(s[j-1] が荷物 $j$ のサイズ、c[i-1] が容器 $i$ の容量)。

In [5]:
s = [3, 5, 4, 6, 2, 7]   # 荷物のサイズ
c = [8, 10, 12, 14]      # 容器の容量
n, m = len(s), len(c)
I = list(range(1, m + 1))  # 容器の番号
J = list(range(1, n + 1))  # 荷物の番号

prob = pulp.LpProblem('binpack_example', pulp.LpMinimize)
x = pulp.LpVariable.dicts('x', (I, J), cat='Binary')  # x[i][j]: 荷物j を容器i に入れる
y = pulp.LpVariable.dicts('y', I, cat='Binary')       # y[i]: 容器i を使う

prob += pulp.lpSum(y[i] for i in I)
for i in I:
    prob += pulp.lpSum(s[j - 1] * x[i][j] for j in J) <= c[i - 1] * y[i]
for j in J:
    prob += pulp.lpSum(x[i][j] for i in I) == 1

prob.solve(pulp.PULP_CBC_CMD(msg=0))
print('求解結果:', pulp.LpStatus[prob.status])
print('最小の容器数: z =', int(pulp.value(prob.objective)))
for i in I:
    if y[i].value() == 1:
        items = [j for j in J if x[i][j].value() == 1]
        load = sum(s[j - 1] for j in items)
        print(f'容器{i}(容量{c[i - 1]}): 荷物{items}, 合計サイズ {load}')

# LP ファイルの出力
prob.writeLP('binpack.lp')

求解結果: Optimal
最小の容器数: z = 3
容器2(容量10): 荷物[4], 合計サイズ 6
容器3(容量12): 荷物[1, 5, 6], 合計サイズ 12
容器4(容量14): 荷物[2, 3], 合計サイズ 9
Out[5]:
[x_1_1,
 x_1_2,
 x_1_3,
 x_1_4,
 x_1_5,
 x_1_6,
 x_2_1,
 x_2_2,
 x_2_3,
 x_2_4,
 x_2_5,
 x_2_6,
 x_3_1,
 x_3_2,
 x_3_3,
 x_3_4,
 x_3_5,
 x_3_6,
 x_4_1,
 x_4_2,
 x_4_3,
 x_4_4,
 x_4_5,
 x_4_6,
 y_1,
 y_2,
 y_3,
 y_4]

最小の容器数は3である。全サイズの合計は27であり、容量の大きい2つの容器(12と14)を使っても $12 + 14 = 26 < 27$ なので、2つの容器では物理的に入りきらない。したがって3が最適であることは、この下界からも確認できる。念のため、荷物の割当を全列挙しても確かめる。

In [6]:
import itertools

best_bins = m + 1
for asg in itertools.product(range(1, m + 1), repeat=n):  # asg[j-1] = 荷物j を入れる容器
    load = [0] * (m + 1)
    for j in J:
        load[asg[j - 1]] += s[j - 1]
    if all(load[i] <= c[i - 1] for i in I):
        best_bins = min(best_bins, sum(1 for i in I if load[i] > 0))
print('全列挙による最小の容器数:', best_bins)
print('数理モデルの解と一致:', best_bins == int(pulp.value(prob.objective)))

全列挙による最小の容器数: 3
数理モデルの解と一致: True

5. 課題¶

荷物が8個と、荷物を入れるための容器が4つある。荷物のサイズと容器の容量は次の表で与えられる。すべての荷物を容器に入れるとき、使う容器の数が最小になる組合せを求めよ。

荷物ID 荷物サイズ [cm³]
1 4
2 6
3 5
4 4
5 5
6 2
7 6
8 7
容器ID 容器の容量 [cm³]
1 11
2 12
3 13
4 15

提出物と手順は次のとおりである。

  1. この問題をPuLP で定式化し、求解すること。
  2. 最適値(目的関数の値)と最適解(各変数の値)を見やすい形で出力すること。
  3. LP ファイルを出力すること。ファイル名は「学籍番号_binpack.lp」とする。
  4. 得られた最適値と最適解から問題の答えを整理し、配布している「binpack_課題_学籍番号_氏名.docx」に書くこと。
  5. LP ファイルとdocx をGoogle Classroom から提出すること。

PuLP の使い方は本資料の第4節と、研究室Webサイトの資料(https://sites.google.com/view/kakimoto-lab/research-materials/pulp)を参考にすること。

6. 注意事項¶

  • 定式化が理解できないときは、第4節の小さな例(荷物6個、容器4個)で、容量制約の右辺 $c_i y_i$ に $y_i = 0$ と $y_i = 1$ を代入して意味を確かめること。
  • 単位はこの資料ではcm³としているが、モデルはサイズと容量の単位が揃ってさえいれば何にでも使える。
  • それでも理解できない場合には指導教員まで相談すること。