Bin Packing Problem（ビンパッキング問題） PuLP

Bin Packing Problem（ビンパッキング問題）

Bin Packing Problem（ビンパッキング問題）という問題をPythonで解く例を示します。

ビンパッキング問題とはビン（容器）に物を詰める最適化問題で、ここでは2つの容器に5つのアイテムを詰める例を示します。

まず、必要なライブラリをインストールします:

1
pip install pulp

以下のPythonコードは、このビンパッキング問題を解くためのものです。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
from pulp import *

# ビンの数とアイテムの数を設定
bin_count = 2
item_count = 5

# 各ビンの容量、アイテムの重さを設定
bin_capacity = [10, 10]
item_weight = [2, 5, 4, 7, 1]

# 問題設定
prob = LpProblem("BinPacking", LpMinimize)

# アイテムをビンに入れるかどうかを示すノードを作成（バイナリ変数）
x = [[LpVariable("x(%s,%s)" % (i, j), cat="Binary") for j in range(item_count)] for i in range(bin_count)]

# 目的関数: 使用するビンの数を最小化する
prob += lpSum(x[i][j] for i in range(bin_count) for j in range(item_count))

# 制約条件: 各アイテムは1つのビンにしか入らない
for j in range(item_count):
    prob += lpSum(x[i][j] for i in range(bin_count)) == 1

# 制約条件: 各ビンの容量を超えてアイテムを入れられない
for i in range(bin_count):
    prob += lpSum(item_weight[j] * x[i][j] for j in range(item_count)) <= bin_capacity[i]

# 最適化計算
prob.solve()

# 結果表示
for i in range(bin_count):
    print("*****Bin", i, "*****")
    total_weight = 0
    for j in range(item_count):
        if value(x[i][j])==1:
            print("Item", j)
            total_weight+=item_weight[j]
    print("Total weight:", total_weight)

このコードでは2つのビンに5つのアイテムを最適に配置しています。

出力結果は各ビンに収められたアイテムとその合計重量を表示します。

[実行結果]

*****Bin 0 *****
Item 1
Item 2
Total weight: 9
*****Bin 1 *****
Item 0
Item 3
Item 4
Total weight: 10

ソースコード解説

このコードは、Bin Packing Problem（ビンパッキング問題）を解くためにPuLP（Pythonの最適化モデリングライブラリ）を使用しています。

1. 必要なライブラリのインポート

1
from pulp import *

PuLPからすべての関数をインポートしています。

2. 問題のパラメータ設定

1
2
3
4
bin_count = 2
item_count = 5
bin_capacity = [10, 10]
item_weight = [2, 5, 4, 7, 1]

ビンの数やアイテムの数、各ビンの容量、アイテムの重さを設定しています。

3. 問題の設定

1
prob = LpProblem("BinPacking", LpMinimize)

PuLPを使って「BinPacking」という名前の最小化問題を定義しています。

4. 変数の定義

1
x = [[LpVariable("x(%s,%s)" % (i, j), cat="Binary") for j in range(item_count)] for i in range(bin_count)]

ビンにアイテムを入れるかどうかを示す変数 x をバイナリ変数として定義しています。

5. 目的関数の設定

1
prob += lpSum(x[i][j] for i in range(bin_count) for j in range(item_count))

使用するビンの数を最小化する目的関数を定義しています。

6. 制約条件の設定

1
2
3
4
5
for j in range(item_count):
    prob += lpSum(x[i][j] for i in range(bin_count)) == 1

for i in range(bin_count):
    prob += lpSum(item_weight[j] * x[i][j] for j in range(item_count)) <= bin_capacity[i]

各アイテムが1つのビンにしか入らない制約条件と、各ビンの容量を超えない制約条件を設定しています。

7. 最適化計算

1
prob.solve()

PuLPを使って最適化問題を解いています。

8. 結果表示

1
2
3
4
5
6
7
8
for i in range(bin_count):
    print("*****Bin", i, "*****")
    total_weight = 0
    for j in range(item_count):
        if value(x[i][j])==1:
            print("Item", j)
            total_weight+=item_weight[j]
    print("Total weight:", total_weight)

最適化計算の結果を表示しており、各ビンに入ったアイテムとその総重量を出力しています。