カッティングストック問題#
読み: かってぃんぐすとっくもんだい
英名: Cutting Stock Problem
長さ \(l_1,l_2,\ldots,l_n\) の木材をそれぞれ \(d_1,d_2,\ldots,d_n\) 本用意する必要があるとする．しかし用意できる木材は長さが \(L\) のものだけである（\(L \ge l_i \ \forall i\) とする）．そこで長さが \(L\) の木材から長さ \(l_1,l_2,\ldots,l_n\) を切り出して用意することを考える．このとき長さ \(L\) の木材を最低何本用意すれば，それぞれ \(d_1,d_2,\ldots,d_n\) 本用意することができるか，というのがカッティングストック問題である．
古典的解法としてまず一本の長さ \(L\) の木材から長さ \(l_1,l_2,\ldots,l_n\) の木材をそれぞれ何本ずつ切りだせるかのパターンをすべて列挙する． そのあとにすべての切り出しパターンのデータを使って線形計画問題を解くことに問題を帰着させる，という方法がある． しかし大規模になると，この「すべての切り出しパターンを列挙する」というところで途方もなく計算時間を使ってしまう． そのため現在では解決手法としてパターンを一つとりだしては線形計画問題を解いていくという「列生成法」が考えられている． また現在では現実的な視点として切り出しのパターンをできるだけ少なくするという目的を考慮した問題の定式化 [1] がおこなわれている．
資材切り出しソリューションについてはこちら．
参考文献
梅谷俊治 and 今堀慎治. OR研究の最前線 切出し・詰込み問題とその応用(1)1次元資材切出し問題. オペレーションズ・リサーチ = Communications of the Operations Research Society of Japan : 経営の科学, 50(4):270–276, 2005. URL: https://cir.nii.ac.jp/crid/1520009407085909888.