Julia の数理最適化パッケージ JuMP を用いて混合整数線型計画問題を試してみる。
JuMP で通常の線形計画問題を解くのは JuMP で線型計画問題おためしを参照。

1. 環境の準備

今回用いるパッケージは下記。

JuMP
CBC (MILP:混合整数計画問題のソルバ)

※環境構築に関しては JuMP で線型計画問題おためしを参照
※各 Solver に関しては Getting Solvers を参照

2. ビンパッキング問題

ビンパッキング問題の詳細は Wikipedia を参照してもらうとして、今回は下記の状況を扱う。

それぞれ重さの異なる荷物を大きめのビンに詰める事を考える
使用するビンの数を最も少なくする格納方法を考えたい
荷物 10 個
- 重さ 2 kg: 4 個
- 重さ 3 kg: 3 個
- 重さ 4 kg: 2 個
- 重さ 5 kg: 1 個
ビンごとの最大容量 5 kg

※ちなみに「ビン」は「瓶」ではなく「Bin(容器)」の事

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)

参考

はじめての列生成法(宮本裕一郎)

てきどにがんばる統計解析

2020年9月3日木曜日

JuMP でビンパッキング問題おためし