JuMP で通常の線形計画問題を解くのは JuMP で線型計画問題おためし を参照。
1. 環境の準備
今回用いるパッケージは下記。
- JuMP
- CBC (MILP:混合整数計画問題 のソルバ)
※各 Solver に関しては Getting Solvers を参照
2. ビンパッキング問題
ビンパッキング問題の詳細は Wikipedia を参照してもらうとして、 今回は下記の状況を扱う。
- それぞれ重さの異なる荷物を大きめのビンに詰める事を考える
- 使用するビンの数を最も少なくする格納方法を考えたい
- 荷物 10 個
- 重さ 2 kg: 4 個
- 重さ 3 kg: 3 個
- 重さ 4 kg: 2 個
- 重さ 5 kg: 1 個
- ビンごとの最大容量 5 kg
3. 定式化
荷物の数を n とすると必要なビンの数は最大でも n 個となるので、使われないビンの存在も許容してビンの数を(多めに) n と設定する。
このとき各ビンに荷物が 1 つでも格納されたかどうかを判定する変数 y[1〜n] を、各成分に 0 か 1 が格納されるベクトルで表現する。
\begin{eqnarray} \forall j \in \{ 1, 2, \dots, n \}, \ \ y_{j} \in \{ 0, 1 \} \nonumber . \end{eqnarray} 次に行列 $X = \{ x_{i, j} \}$ を下記で定義する。
- 行(i): 各荷物(1〜n)に対応
- 列(j): 各ビン(1〜n)に対応
- 各 $x_{i, j}$ には 0 か 1 が格納される
最後にベクトル $s$ 及びスカラ $B$ を下記で定義する。
-
$s$: 各荷物の重さ
- 今回の場合は $s = [ 2, 2, 2, 2, 3, 3, 3, 4, 4, 5 ]$
-
$B$: 各ビンごとの最大容量
- 今回の場合は $B = 5$
3.1 目的関数
出来るだけビンの数を少なくしたいので、各 $y_{j}$ の和を最小とする事を考える。 \begin{eqnarray} minimize \sum_{j} y_{j} \end{eqnarray}
3.2 制約条件(1)
まず、各荷物 1〜n がそれぞれ 1 つのビンに必ず格納される事を表現する。
\begin{eqnarray} \forall i, \ \ \sum_{j} x_{i, j} = 1 \nonumber \end{eqnarray}
この条件は n 個の成分が全て 1 であるベクトル $e (\forall i, \ e_{i} = 1)$ を用いて下記のように書き換え可能。 \begin{eqnarray} X \cdot e = 1 \end{eqnarray}
3.3 制約条件(2)
次に、各ビンに格納された荷物の重さの合計が $B$ を以下となる事を表現する。 \begin{eqnarray} \forall j, \ \ \sum_{i} s_{i} \cdot x_{i, j} \leqq B \cdot y_{j} \nonumber \end{eqnarray}
この条件は行列の転置を用いて下記のように書き換え可能。 \begin{eqnarray} {}^t\!X \cdot s \leqq B \cdot y \end{eqnarray}
3.4 制約条件(3)
最後に、行列 $X$ およびベクトル $y$ の各成分に関する条件を表現する。
\begin{eqnarray} \forall i, j, \ \ x_{i, j} \in \{ 0, 1 \} \\ \forall j, \ \ y_{j} \in \{ 0, 1 \} \end{eqnarray}
3.5 まとめ
上記 (1)〜(5) を用いて下記のようにまとめられる。
\begin{eqnarray} minimize & & \sum_{j} y_{j} \nonumber \\ subject \ to & & X \cdot e = 1 \nonumber \\ & & {}^t\!X \cdot s \leqq B \cdot y \nonumber \\ & & \forall i, j, \ \ x_{i, j} \in \{ 0, 1 \} \nonumber \\ & & \forall j, \ \ y_{j} \in \{ 0, 1 \} \nonumber \end{eqnarray}
4. JuMP
JuMP を用いて最適解を求める。
MILP(混合整数線型問題) を扱う事のできる CBC をソルバーに用いる。
using JuMP using Cbc using LinearAlgebra # 荷物の数 => 最大のビンの数 n = 10 # ビンごとの最大容量 B = 5 # 荷物ごとの重さ s = [2, 2, 2, 2, 3, 3, 3, 4, 4, 5] # CBC を用いたモデルを作成 model = Model(Cbc.Optimizer) # 変数を追加 # X: 荷物とビンの関係 # y: ビン使用の有無 # binary = true で 2 値(0 or 1)変数である事を指定 @variable(model, X[i=1:n, j=1:n], binary = true) # (4) @variable(model, y[1:n], binary = true) # (5) # 目的関数を最小化 @objective(model, Min, sum(y)) # (1) # 制約条件を追加 @constraint(model, X * ones(n) .== 1) # (2) @constraint(model, transpose(X) * s .<= B .* y) # (3) # 最適化の実行 optimize!(model) ### 実行結果 ### Welcome to the CBC MILP Solver Version: 2.10.3 Build Date: May 23 2020 command line - Cbc_C_Interface -solve -quit (default strategy 1) Continuous objective value is 6 - 0.00 seconds 〜中略〜 Result - Optimal solution found Objective value: 7.00000000 Enumerated nodes: 0 Total iterations: 83 Time (CPU seconds): 0.37 Time (Wallclock seconds): 0.12 Total time (CPU seconds): 0.37 (Wallclock seconds): 0.12
4.1 実行結果
正常に終了し、各荷物の各ビンへの格納が正しく行われている事を確認できる。
println("TerminationStatus: ", termination_status(model))
# => TerminationStatus: OPTIMAL
println("PrimalStatus: ", primal_status(model))
# => PrimalStatus: FEASIBLE_POINT
println("ObjectiveValue: ", objective_value(model))
# => ObjectiveValue: 7.0
# 荷物の格納されたビンの情報のみを表示
for i = 1:n, j = 1:n
x = value(X[i,j])
if x > 0
println("X[", i, "," , j, "]: ", x)
end
end
X[1,2]: 1.0
X[2,6]: 1.0
X[3,7]: 1.0
X[4,9]: 1.0
X[5,7]: 1.0
X[6,9]: 1.0
X[7,2]: 1.0
X[8,10]: 1.0
X[9,8]: 1.0
X[10,4]: 1.0
ビンと荷物の対応
-
ビン 2:
- 荷物1(2kg)
- 荷物7(3kg)
-
ビン 4:
- 荷物10(5kg)
-
ビン 6:
- 荷物2(2kg)
-
ビン 7:
- 荷物3(2kg)
- 荷物5(3kg)
-
ビン 8:
- 荷物9(4kg)
-
ビン 9:
- 荷物4(2kg)
- 荷物6(3kg)
-
ビン 10:
- 荷物8(4kg)
参考
- 荷物1(2kg)
- 荷物7(3kg)
- 荷物10(5kg)
- 荷物2(2kg)
- 荷物3(2kg)
- 荷物5(3kg)
- 荷物9(4kg)
- 荷物4(2kg)
- 荷物6(3kg)
- 荷物8(4kg)
