ビンパッキング問題

ビンパッキング問題（ビンパッキングもんだい）とは、離散数学の組合せ論の中のNP困難問題で、与えられた「荷物（重さや個数がついている）」をつめる「箱（ビンやコンテナなど）」の最小数を見つけるものである。問題を解くためにビン型（筒状型）の模型を使うのでこのように呼ばれる。

様々な解決方法（アルゴリズム）が考案されているが、あらゆる場合の箱の最小数を効率的に見つけることができるような万能なアルゴリズムはない（NP困難問題）。

標準的な定義

ゲイリー、ジョンソンによる著書『Computers and Intractability（英語版）』で記述されているビンパッキング問題の定義を以下で説明する^[1]:226。

入力：有限個のアイテム集合 ${\displaystyle I}$ 、およびアイテム ${\displaystyle i\in I}$  ごとのサイズ ${\displaystyle s(i)\in \mathbb {Z} ^{+}}$ 、および容量 ${\displaystyle B}$  をもつビンおよび正の値をとる ${\displaystyle K}$  が与えられる。

問い：集合 ${\displaystyle I}$  を素集合 ${\displaystyle I_{1},\dots ,I_{K}}$  に分割して、それぞれの部分集合 ${\displaystyle I_{j}}$  に含まれるアイテムのサイズの総和が ${\displaystyle B}$  以下となるようなアイテム集合の分割は可能であるか?

ただし、文献によってビンパッキング問題は（同値ではない）別の表記によって定義される場合がある。例として、容量を ${\displaystyle B=1}$  とし、各 ${\displaystyle i\in I}$  に対してそのサイズを ${\displaystyle s(i)\in \mathbb {Q} \cap (0,1]}$  と仮定することが挙げられる。また、研究分野ではビンパッキング問題の条件を満たす最小の ${\displaystyle K}$  を求める最適化問題として扱うことが非常に多い。集合 ${\displaystyle I}$  に対する最適な ${\displaystyle K}$  の値は ${\displaystyle \mathrm {OPT} (I)}$ 、自明な場合は ${\displaystyle \mathrm {OPT} }$  と表記されることが多い。

また、ビンパッキング問題は整数計画問題による定式化を与えることができる:

${\displaystyle \min }$		${\displaystyle K=\sum _{j=1}^{n}y_{j}}$
${\displaystyle \mathrm {s.t.} }$		${\displaystyle K\geq 1,}$
		${\displaystyle \sum _{i\in I}s(i)x_{ij}\leq By_{j},}$		${\displaystyle \forall j\in \{1,\ldots ,n\}}$
		${\displaystyle \sum _{j=1}^{n}x_{ij}=1,}$		${\displaystyle \forall i\in I}$
		${\displaystyle y_{j}\in \{0,1\},}$		${\displaystyle \forall j\in \{1,\ldots ,n\}}$
		${\displaystyle x_{ij}\in \{0,1\},}$		${\displaystyle \forall i\in I,\,\forall j\in \{1,\ldots ,n\}}$

ただし、${\displaystyle y_{j}}$  はビン ${\displaystyle j}$  を使用するならば、${\displaystyle y_{j}=1}$  となる変数であり、${\displaystyle x_{ij}}$  はアイテム ${\displaystyle i}$  をビン ${\displaystyle j}$  に詰めるならば、${\displaystyle x_{ij}=1}$  となる変数である^[2]。

単純な例

8台の新車をトラックで移動する。新車の重量はそれぞれ100キログラム単位で 33, 61, 58, 41, 50, 21, 60, 64 である。各トラックが、12,000 kg の重量まで運べるとき、全ての新車を一度に移動させるのに必要とされるトラックの最小数は、いくつであるか考える。まず、トラックを容量120のビンとし、新車は、そのビンに詰める荷物とする。具体的に調べることによって必要な箱の最小数を見つけることができるが、ここでは決められた手順（アルゴリズム）を使って解いていく。2つのアルゴリズムを紹介する。

アルゴリズムA

1. 荷物を空いている容量が最大のビンに詰める。
2. どのビンにも荷物が入らないとき、新しいビンに詰める。

ビン1  ビン2  ビン3  ビン4  ビン5
|00|   |00|  |00|   |00|  |00|
|61|   |41|  |21|   |00|  |00|
|33|   |58|  |50|   |60|  |64|

この方法だと、ビンは5個（つまりトラック5台）必要となる。

アルゴリズムB

1. 荷物を空いている容量が最小のビンに詰める。
2. どのビンにも荷物が入らないとき、新しいビンに詰める。

ビン1  ビン2  ビン3  ビン4
|00|   |21|  |00|   |00|
|61|   |41|  |60|   |00|
|33|   |58|  |50|   |64|

この方法だと、必要なビンは4個（トラック4台）である。

2つを比べるとAよりもBの方が良いアルゴリズムである。実際にはもっと優良なアルゴリズムがあるかもしれない。

脚注

[脚注の使い方]

1. ^ Garey, M. R.; Johnson, D. S. (1979). Victor Klee. ed. Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Calif.: W. H. Freeman and Co.. pp. x+338. ISBN 0-7167-1045-5. MR519066 
2. ^ Martello & Toth 1990, p. 221.

参考文献

• Martello, Silvano; Toth, Paolo (1990). “Bin-packing problem”. Knapsack Problems: Algorithms and Computer Implementations. Chichester, UK: John Wiley and Sons. ISBN 0471924202. http://www.or.deis.unibo.it/kp/Chapter8.pdf 

関連項目

• ナップサック問題
• 部分和問題
• パッキング問題

外部リンク

• パッキング問題 - opt100
• ビンパッキング問題 — 数理最適化用語集