組合せ最適化問題の解き方の工夫
組合せ最適化問題では、特有の難しさがあります。同じ問題であっても複数のモデル化の方法があり、モデルごとに優劣があります。モデル化の仕方が重要になります。
ここでは、ビンパッキング問題を例に、工夫の仕方を説明します。
ビンパッキング問題とは
| 容量$c(\gt 0)$の箱と$n$個の荷物$N=\{1,\dots,n\}$が与えられている。荷物$i \in N$の容量を$w_i(\gt 0)$とする。全ての荷物を詰合わせるのに必要な箱の個数を最小にする詰合わせを求めよ。 |
例えば、いくつかの重量物を10tトラックで運ぶ場合に、なるべく少ないトラック数を求めるような問題です。
素直なアプローチ
そのまま定式化してみましょう。
| 1段階定式化 | ||
| $\mbox{objective}$ | $\sum_i{y_i}$ | 箱数 |
| $\mbox{variables}$ | $x_{ij} \in \{0, 1\} ~ \forall i, j$ | 荷物$i$に箱$j$を入れるかどうか |
| $y_j \in \{0, 1\} ~ \forall j$ | 箱$j$を使うかどうか | |
| $\mbox{subject to}$ | $\sum_j{x_{ij}} = 1 ~ \forall i$ | 荷物$i$をどれかの箱に入れる |
| $\sum_i{w_i x_{ij}} \le c ~ \forall j$ | 箱$j$の容量を満たす | |
| $x_{ij} \le y_j ~ \forall i, j$ | $y$に関する制約 | |
実は、この定式化は、ソルバーにとって解きにくい形となっており、計算に非常に時間がかかります。
2段階で解く方法
箱の数を仮に固定して解が存在するかどうかを調べ、外側のループで箱の数を変えていく方法の方が結果的に早く解くことができます。
以下に、箱の数を固定した場合の定式化AとBを示します。
| 2段階定式化A | ||
| $\mbox{objective}$ | なし | |
| $\mbox{variables}$ | $x_{ij} \in \{0, 1\} ~ \forall i, j$ | 荷物$i$に箱$j$を入れるかどうか |
| $\mbox{subject to}$ | $\sum_j{x_{ij}} = 1 ~ \forall i$ | 荷物$i$をどれかの箱に入れる |
| $\sum_i{w_i x_{ij}} \le c ~ \forall j$ | 箱$j$の容量を満たす | |
| 2段階定式化B | ||
| $\mbox{objective}$ | $y$ | 容量を超える分 |
| $\mbox{variables}$ | $x_{ij} \in \{0, 1\} ~ \forall i, j$ | 荷物$i$に箱$j$を入れるかどうか |
| $y \ge 0$ | 容量を超える分 | |
| $\mbox{subject to}$ | $\sum_j{x_{ij}} = 1 ~ \forall i$ | 荷物$i$をどれかの箱に入れる |
| $\sum_i{w_i x_{ij}} \le c + y ~ \forall j$ | 箱$j$の容量を満たす | |
以下のような特徴があります。
| 定式化 | 解が存在するとき | 解が存在しないとき |
|---|---|---|
| 2段階定式化A | 非常に時間がかかる | すぐに終わる |
| 2段階定式化B | すぐに終わる | 非常に時間がかかる |
このことから、AとBを並列に実行すれば、解が存在するかどうかすぐにわかります。
箱の数は2分探索すれば、効率的に求められます。
頭の体操 (答えはコメント欄参照)
並列にしないで､時間のかからない方法はあるか？
近似解法でよい場合
厳密解法の定式化では解の対称性(箱Xと箱Yを交換してもよいこと)があるため、効率がよくありません。そこで、実務では近似解法を使うことが多くなるでしょう。
ビンパッキング問題を解く近似解法として列生成法があります。近似解法ではありますが、精度が期待できます。ただし、複雑な方法なので、説明は省略します。興味のある方は、比較的わかりやすい論文(はじめての列生成法)をお読みください。
なお、Pythonでは、"pip install ortoolpy"でインストールできるortoolpy.binpackingで列生成法を行っています。
その他の近似解法としてよく使われるのは、貪欲法や局所探索法ですが、ここでは省略します。
一般的な工夫
組合せ最適化問題は、指数オーダーであることが多いです。このことから、問題が分割できれば、近似解になりますが、高速化することができます。一般的には、分割統治法と呼ばれます。
以上