板取り問題のソースを表示

[[オペレーションズ・リサーチ]]における'''板取り問題'''（いたどりもんだい、{{Lang-en-short|cutting stock problem}}）、または'''カッティングストック問題'''とは、定形の母材（ストック（stock）とも。例えばロール紙や板金）から廃材の量が最小になるように特定の大きさの製品群を切り出す問題である。産業上の応用から生じた[[数学]]的な[[最適化問題]]の1つであり、また[[計算複雑性理論]]においては[[ナップサック問題]]に還元される[[NP困難]]問題の1つである。[[整数計画問題]]として定式化することができる。

== 1次元の例 ==
ペーパーロール製造機が、幅5600mmのマスターロールを無限に生産できるとする。ここから下表に示したような13種類の製品ロールを切り出さなければならない。

重要なのは、同一のマスターロールから様々な方法で製品ロールを切り出せること（この切り出し方のそれぞれを「パターン」と呼ぶことにする）である。パターンの総数は一般に膨大な数に上り、列挙することは容易ではない。

この状況で、廃棄部分が最小限となるような製品ロールの最適な切り出し方を求めるのが板取り問題である。

::{| class="wikitable"
|-
! width="80pt" | 幅
! width="80pt" | 本数
|-
| align=center | 1380   || align=center | 22
|-
| align=center | 1520   || align=center | 25
|-
| align=center | 1560   || align=center | 12
|-
| align=center | 1710   || align=center | 14
|-
| align=center | 1820   || align=center | 18
|-
| align=center | 1880   || align=center | 18
|-
| align=center | 1930   || align=center | 20
|-
| align=center | 2000   || align=center | 10
|-
| align=center | 2050   || align=center | 12
|-
| align=center | 2100   || align=center | 14
|-
| align=center | 2140   || align=center | 16
|-
| align=center | 2150   || align=center | 18
|-
| align=center | 2200   || align=center | 20
|}

===下限の確認===
必要なマスターロールの本数の単純な下限は、全ての製品ロールの幅の総和をマスターロール1本の幅で割ることで求められる。この場合、総長は 1380 x 22 + 1520 x 25 + ... + 2200 x 20 = 407160 mm で、マスターロールは 5600 mm なので、割り算をすると72.7本、よって73本は最低でも必要ということになる。

===解===
この簡単な例には、最適解が308通り存在する。どれもマスターロールを73本必要とし、廃棄率は0.401%となる。廃棄率最適（0.401%）という条件の下で、用いる切り出し方（パターン）の数を最小に抑えるような方法をコンピュータで探索すると、その最小値は10であり、それを与えるパターンの組み合わせ方は19通りあることがわかっている。19通りのうちの1つを下表に示す。
:{| class="wikitable" border="0" cellpadding="4"
!反復数
!align=center | パターン
|-
| align=center | 2 || 1820 + 1820 + 1820
|-
| align=center | 3 || 1380 + 2150 + 1930
|-
| align=center | 12 || 1380 + 2150 + 2050
|-
| align=center | 7 || 1380 + 2100 + 2100
|-
| align=center | 12 || 2200 + 1820 + 1560
|-
| align=center | 8 || 2200 + 1520 + 1880
|-
| align=center | 1 || 1520 + 1930 + 2150
|-
| align=center | 16 || 1520 + 1930 + 2140
|-
| align=center | 10 || 1710 + 2000 + 1880
|-
| style="border-bottom:3px solid grey" align=center | 2 || 1710 + 1710 + 2150
|-
|  align=center | '''73'''
|}

== 分類 ==
板取り問題はいくつかの方法で分類できる<ref name="Wäscher2007">Wäscher, G.; Haußner, H.; Schumann, H. ''An Improved Typology of Cutting and Packing Problems''. European Journal of Operational Research Volume 183, Issue 3, 1109-1130</ref>。1つの方法は切断対象の次元による分類である。上に挙げた例は1次元の問題だった。1次元の問題は他にもパイプ、ケーブル、鋼棒を切断するといった場合に適用できる。2次元の問題は家具類や布製品、ガラス製品に当てはまる。母材もしくは製品が 特殊な形状をしている場合（皮革、生地、板金等の加工ではしばしば見られる）は、'''ネスティング問題'''（Nesting problem）と呼ばれる。

3次元の切断への適用例はあまり知られていないが、この問題と密接に関連した3次元[[パッキング問題]]には、船荷の積み込み等、幅広い産業上の応用がある（例えば[[コンテナ輸送]]を参照。これに関連した[[球充填]]の問題は17世紀以来研究されている（[[ケプラー予想]]））。

==紙、フィルム、金属加工品の製造において==
板取り問題の製造業への応用は、比較的大きな母材からより小さな製品ユニットが切り出される場合に顕著である（参考：{{仮リンク|ロールスリッター|en|Roll slitting}}）。これには紙やプラスチックフィルムの他、鉄や真鍮の板金も該当する。機械や製造過程での制約、顧客からの要求、品質の問題等から、多くの変種問題・追加的制約が生じる。以下はその例である:
* 2ステージ制約：（切断）加工が2段階を経る場合。例えば、オフィス用文房具(例：ヨーロッパでの[[ISO 216#A series|A4]]サイズ、アメリカでの[[レターサイズ]]) はそのように製造される。第2段階では使用できる機械がより限定されたものになるため、問題が複雑になる。製造の両段階においてエネルギーと資材を効率的に利用することは重要だが、第1段階での効率化が第2段階での非効率を生むかもしれない（トレードオフが起こる）。スナック菓子の包装に使われる{{仮リンク|金属蒸着フィルム|en|Metallised film}}や、{{仮リンク|飲料包装紙|en|Liquid packaging board}}に使われる紙へのプラスチックの押出し加工においてもこうした制約が生じる。
* 巻付機に起因する、スリット加工（マスターロールを切断し、各ロールを巻き取る過程）上の物理的・論理的な制約：非常によく見られるのは、限られた種類のスリッターナイフしか使用することができず、1度の切り出しで切り出せる製品ロールの本数に上限が課される状況である。巻付機が標準化されていないために、これ以外にも非常に多くの制約が生じることがある。
* 顧客からの要求の例として、母材の端部分からの切り出しが基準不適合となる場合が考えられる。シートの辺縁部分は厚みの変動が大きくなりやすく、製品によってはこのことが重大な問題となる。
* 品質の問題の例として、母材に除去が必要な不良箇所が生じる場合が考えられる。高品質が要求される高価な素材、例えば[[印画紙]]や[[タイベック]]であれば、廃棄部分が最小となるように注意深く最適化しなければならない。
* 複数マシン問題（multi-machine problem）では、大きさの異なる母材を製造する2台以上の機械が利用できるものとする。一般的に、2種類以上の大きさの母材を使用できれば廃棄量を相当に改善することができるが、実際上は追加的な製品の切り出し方法を考慮に入れる必要が生じてくる。
* 半連続問題（semi-continuous problem）では、製品が全く同一の大きさでなくとも、ある変動範囲に収まっていればよいとする。この状況はシート類の注文において典型的に見られ、'''1½次元問題'''（1½ dimensional problem）としても知られている。この変種問題は[[段ボール]]（corrugated cardboard）の製造上生じることがあり、幾分混乱を招く呼称であるが '''corrugator scheduling problem''' と呼ばれることもある。
* ロール紙の製造において、マスターロールの幅が要求される製品ロールより短い場合に、スカイビング（'''skiving'''：削ぎ落とし）（または ''web-welding''）と呼ばれる2段階目の加工を採り入れている工場もある。最初の大きなロールから切り出した2本のロールを端と端を少し重ねて繋ぎ合わせる工程である。マスターロールの幅がより短ければ、全体としての廃棄量を減らすことができる<ref name=Johnson1997>M.P. Johnson, C. Rennick & E. Zak (1997), ''Skiving addition to the cutting stock problem in the paper industry'', SIAM Review, 472-483</ref>。

==ガラス製造において==
[[ギロチンカット問題]]は、定形のガラス板から、端から端までの裁断のみによって（ギロチンカット制約）、指定された大きさのいくつかの長方形を切り出す問題である。

==割当問題==
これに関連した1次元の決定問題、つまり、与えられた製品要求を満足するような最適な母材の大きさを定める問題は、'''割当問題'''（assortment problem）として知られている<ref>{{Cite journal | doi = 10.1111/j.1475-3995.2009.00724.x| title = The generalized assortment and best cutting stock length problems| journal = International Transactions in Operational Research| volume = 17| pages = 35| year = 2010| last1 = Raffensperger | first1 = J. F. }}</ref>。

== 歴史 ==
板取り問題は[[レオニート・カントロヴィチ|レオニート・ヴィタリエヴィチ・カントロヴィチ]]によって1939年に初めて定式化された<ref>L. V. Kantorovich ''Mathematical methods of organizing and planning production''. Leningrad State University. 1939</ref>。1951年、まだコンピュータが広く実用化されていなかった頃、カントロヴィチと[[ヴィクター・アブラモヴィッチ・ザルガラー]]は、切断段階における資材の効率的な利用の問題を線形計画法を用いて解くことを提案した<ref>{{cite book |author=Kantorovich L. V. and Zalgaller V. A. . |title=Calculation of Rational Cutting of Stock |publisher=Lenizdat, Leningrad |year=1951 }}</ref>。この手法は後に'''[[列生成法]]'''と呼ばれることになる。

== 数学的定式化と解探索 ==
板取り問題を数学的に定式化するには（これが唯一の方法ではないが）、まず製品種類の数 ''m'' と、各製品が要求されている単位数 <math>q_j</math>（ <math>j = 1,\ldots,m</math>）の整理から始める。次に、母材1単位から製品を切り出す方法（これを「パターン」と呼ぶことが多い）を全て挙げてリストを構成する。パターンの総数を <math>n</math> とする。各パターン <math>i</math> に、それが何度用いられるかを表す変数 <math>x_i</math>（0含む自然数）を対応させる（ <math>i = 1,\ldots,n</math> ）。このとき線形計画問題は次のように定式化できる：

:<math>\min\sum_{i=1}^n c_i x_i</math>
:<math>\text{s.t.}\sum_{i=1}^n a_{ij} x_i \ge q_j, \quad \quad \forall j=1,\dots,m</math>
:<math>x_i \ge 0</math>, 整数

ここで <math>a_{ij}</math> は製品 <math>j</math> がパターン <math>i</math> の中に現れる回数、 <math>c_i</math> はパターン <math>i</math> のコスト（普通は廃材の量とする）。量的制約を正確に定式化することで、微妙に異なった様々な数学的特性が現れる。上記の定式化は、'''最小限'''の制約条件しか課していない（どの製品も受注分は最低限製造するが、それ以上に製造されても良い）。<math>c_i=1</math> であれば、使用する母材の数量を最小化することになる。製造する製品の制約式を不等号でなく等号に変えたものは[[ビンパッキング問題]]となる。最も一般的な定式化では、この制約不等式に下限と上限を設ける（このとき、廃棄量を最小化する解は母材の使用量を最小化していないかもしれない）：

:<math>q_j \le \sum_{i=1}^n a_{ij} x_i \le Q_j, \quad \quad \forall j=1,\dots,m</math>

この定式化は1次元問題のみに限らない。多くの変種が考えられるが、例えば廃棄量の最小化ではなく製造量の価値の最大化（製品ごとに異なる価値を与えてよいとする）を最適化の目的としてもよい。

一般に、可能なパターンの数は製品種類の数 ''m'' の関数として爆発的に増大する。製品の種類が増大するにつれて、可能な切断パターンの数の数え上げは事実上不可能になる。

他のアプローチとして、[[遅延列生成法]]（delayed column-generation）を使うものがある。この手法では、問題を解くのにまず少数のパターンから始めて、必要になるたびにパターンを追加していく。1次元の場合、線形計画の双対変数を使った補助的な最適化問題（この場合ナップサック問題）を解くことで追加するパターンを決定する。ナップサック問題には、[[分枝限定法]]や[[動的計画法]]といったよく知られた解法がある。遅延列生成法は元の列生成法より一層効率的であり、特に問題のサイズが大きくなっていくとき威力を発揮する。板取り問題への応用としての列生成法アプローチは、Gilmore と Gomory の1960年代の一連の論文によって切り拓かれた<ref name=Gilmore61>Gilmore P. C., R. E. Gomory (1961). ''A linear programming approach to the cutting-stock problem''.  Operations Research 9: 849-859</ref><ref name=Gilmore63>Gilmore P. C., R. E. Gomory (1963). ''A linear programming approach to the cutting-stock problem - Part II''.  Operations Research 11: 863-888</ref>。Gilmore と Gomory は、列生成法では、前もって可能な全てのパターンを列挙することなしに、解（分数となる場合も含む）へ収束することが保証されることを証明した。

オリジナルの Gilmore と Gomory の手法の難点は端数を上手く扱えないことであり、「解」が分数になり得る（あるパターンを3.67回使用する、のように）。最も近い整数に丸めるのでは上手く行かないことが多い。丸めによって非最適な解や、いくつかの製品を過剰・過少に製造するような解が出てきてしまうからである (さらに、制約条件の上限・下限を満たせなくなるかもしれない)。この困難は現代的なアルゴリズムでは克服されてきており、非常に大きなサイズの問題例（実際的な問題より大きいことが多い）の（廃棄量最小化の意味での）最適化ができるようになってきている<ref name=Goulimis1990>Goulimis C (1990). ''Optimal solutions for the cutting stock problem''.  European Journal of Operational Research 44: 197-208</ref><ref name=Carvalho1998>de Carvalho V (1998). ''Exact solution of cutting stock problems using [[column generation]] and branch-and-bound''. International Transactions in Operational Research 5: 35–44</ref>。

板取り問題は、廃棄率が同一となるような複数の最適解が存在することで非常に困難になることが多い。これは、廃棄率を変えることなく、製品の切り出し位置が互いに移り変わり得ることから生じる。これに関連して、着目点に応じた諸問題が立てられている。：
* 最小パターン数問題（minimum pattern count problem）：廃棄量が最小となるような解の中で、用いるパターン数を最小に抑えるものを探す。たとえ最適廃棄量がわかっていたとしても、非常に難しい問題である<ref name=Umetani2003>S. Umetani, M. Yagiura, and T. Ibaraki (2003). ''One dimensional cutting stock problem to minimize the number of different patterns''. European Journal of Operational Research 146, 388–402</ref><ref name=Diegel1996>A. Diegel, E. Montocchio, E. Walters, S. van Schalkwyk and S. Naidoo (1996). ''Setup minimizing conditions in the trim loss problem''. European Journal of Operational Research 95:631-640</ref><ref name=McDiarmid1999>C. McDiarmid (1999). ''Pattern Minimisation in Cutting Stock Problems''. Discrete Applied Mathematics, 121-130</ref>。1次元で制約条件が等号の場合、製品種類が ''n'' 通りであれば、パターン数が ''n'' + 1 以下となる最適解が存在すると[[数学上の未解決問題|予想]]されている。
* 最小スタック問題（minimum stack problem）：各時点で注文数に達していない製品種が多くなり過ぎないような、パターンの使用順序を求める問題。この問題は2007年まで手つかずだったが、動的計画法に基づく効率的なアルゴリズムが発表された<ref name=Banda2007>Maria Garcia de la Banda, P. J. Stuckey. ''Dynamic Programming to Minimize the Maximum Number of Open Stacks''. INFORMS Journal on Computing, Vol. 19, No. 4, Fall 2007, 607-617.</ref>。
* 最小ナイフ交換数問題（minimum number of knife changes problem）（1次元の場合）：スリッターナイフの交換回数を最小にするようなパターンの使用順序を求める問題。これは一般化された[[巡回セールスマン問題]]の特別な場合である。

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 参考文献 ==
* {{cite book |author=[[Václav Chvátal|Chvátal, V.]] |title=Linear Programming |publisher=W.H. Freeman |year=1983 |isbn=978-0-7167-1587-0 }}
* Hatem Ben Amor, J.M. Valério de Carvalho, ''Cutting Stock Problems'' in Column Generation, edited by Guy Desaulniers, Jacques Desrosiers, and Marius M. Solomon, Springer, 2005, XVI, {{ISBN2|0-387-25485-4}}
* M. Delorme, M. Iori, S. Martello, ''Bin packing and cutting stock problems: Mathematical models and exact algorithms'', European Journal of Operational Research 2016, 255, 1–20, doi:10.1016/j.ejor.2016.04.030

{{DEFAULTSORT:いたとりもんたい}}
[[Category:オペレーションズリサーチ]]
[[Category:組合せ最適化]]
[[Category:計算複雑性理論]]
[[Category:機械工学]]
[[Category:数学に関する記事]]