板取り問題

オペレーションズ・リサーチにおける板取り問題（いたどりもんだい、）、またはカッティングストック問題とは、定形の母材（ストック（stock）とも。例えばロール紙や板金）から廃材の量が最小になるように特定の大きさの製品群を切り出す問題である。産業上の応用から生じた数学的な最適化問題の1つであり、また計算複雑性理論においてはナップサック問題に還元されるNP困難問題の1つである。整数計画問題として定式化することができる。
1次元の例.
ペーパーロール製造機が、幅5600mmのマスターロールを無限に生産できるとする。ここから下表に示したような13種類の製品ロールを切り出さなければならない。
重要なのは、同一のマスターロールから様々な方法で製品ロールを切り出せること（この切り出し方のそれぞれを「パターン」と呼ぶことにする）である。パターンの総数は一般に膨大な数に上り、列挙することは容易ではない。
この状況で、廃棄部分が最小限となるような製品ロールの最適な切り出し方を求めるのが板取り問題である。
下限の確認.
必要なマスターロールの本数の単純な下限は、全ての製品ロールの幅の総和をマスターロール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つを下表に示す。
分類.
板取り問題はいくつかの方法で分類できる。1つの方法は切断対象の次元による分類である。上に挙げた例は1次元の問題だった。1次元の問題は他にもパイプ、ケーブル、鋼棒を切断するといった場合に適用できる。2次元の問題は家具類や布製品、ガラス製品に当てはまる。母材もしくは製品が 特殊な形状をしている場合（皮革、生地、板金等の加工ではしばしば見られる）は、ネスティング問題（Nesting problem）と呼ばれる。
3次元の切断への適用例はあまり知られていないが、この問題と密接に関連した3次元パッキング問題には、船荷の積み込み等、幅広い産業上の応用がある（例えばコンテナ輸送を参照。これに関連した球充填の問題は17世紀以来研究されている（ケプラー予想））。
紙、フィルム、金属加工品の製造において.
板取り問題の製造業への応用は、比較的大きな母材からより小さな製品ユニットが切り出される場合に顕著である（参考：）。これには紙やプラスチックフィルムの他、鉄や真鍮の板金も該当する。機械や製造過程での制約、顧客からの要求、品質の問題等から、多くの変種問題・追加的制約が生じる。以下はその例である。:
ガラス製造において.
ギロチンカット問題は、定形のガラス板から、端から端までの裁断のみによって（ギロチンカット制約）、指定された大きさのいくつかの長方形を切り出す問題である。
割当問題.
これに関連した1次元の決定問題、つまり、与えられた製品要求を満足するような最適な母材の大きさを定める問題は、割当問題（assortment problem）として知られている。
歴史.
板取り問題はレオニート・ヴィタリエヴィチ・カントロヴィチによって1939年に初めて定式化された。1951年、まだコンピュータが広く実用化されていなかった頃、カントロヴィチとヴィクター・アブラモヴィッチ・ザルガラーは、切断段階における資材の効率的な利用の問題を線形計画法を用いて解くことを提案した。この手法は後にと呼ばれることになる。
数学的定式化と解探索.
板取り問題を数学的に定式化するには（これが唯一の方法ではないが）、まず製品種類の数 "m" と、各製品が要求されている単位数 formula_1（ formula_2）の整理から始める。次に、母材1単位から製品を切り出す方法（これを「パターン」と呼ぶことが多い）を全て挙げてリストを構成する。パターンの総数を formula_3 とする。各パターン formula_4 に、それが何度用いられるかを表す変数 formula_5 （0含む自然数）を対応させる（ formula_6 ）。このとき線形計画問題は次のように定式化できる：
ここで formula_10 は製品 formula_11 がパターン formula_4 の中に現れる回数、 formula_13 はパターン formula_4 のコスト（普通は廃材の量とする）。 量的制約を正確に定式化することで、微妙に異なった様々な数学的特性が現れる。上記の定式化は、最小限の制約条件しか課していない（どの製品も受注分は最低限製造するが、それ以上に製造されても良い）。formula_15 であれば、使用する母材の数量を最小化することになる。製造する製品の制約式を不等号でなく等号に変えたものはビンパッキング問題となる。最も一般的な定式化では、この制約不等式に下限と上限を設ける（このとき、廃棄量を最小化する解は母材の使用量を最小化していないかもしれない）：
この定式化は1次元問題のみに限らない。多くの変種が考えられるが、例えば廃棄量の最小化ではなく製造量の価値の最大化（製品ごとに異なる価値を与えてよいとする）を最適化の目的としてもよい。
一般に、可能なパターンの数は製品種類の数 "m" の関数として爆発的に増大する。製品の種類が増大するにつれて、可能な切断パターンの数の数え上げは事実上不可能になる。
他のアプローチとして、（delayed column-generation）を使うものがある。この手法では、問題を解くのにまず少数のパターンから始めて、必要になるたびにパターンを追加していく。1次元の場合、線形計画の双対変数を使った補助的な最適化問題（この場合ナップサック問題）を解くことで追加するパターンを決定する。ナップサック問題には、分枝限定法や動的計画法といったよく知られた解法がある。遅延列生成法は元の列生成法より一層効率的であり、特に問題のサイズが大きくなっていくとき威力を発揮する。板取り問題への応用としての列生成法アプローチは、 Gilmore と Gomory の1960年代の一連の論文によって切り拓かれた。 Gilmore と Gomory は、列生成法では、前もって可能な全てのパターンを列挙することなしに、解（分数となる場合も含む）へ収束することが保証されることを証明した。
オリジナルの Gilmore と Gomory の手法の難点は端数を上手く扱えないことであり、「解」が分数になり得る（あるパターンを3.67回使用する、のように）。最も近い整数に丸めるのでは上手く行かないことが多い。丸めによって非最適な解や、いくつかの製品を過剰・過少に製造するような解が出てきてしまうからである (さらに、制約条件の上限・下限を満たせなくなるかもしれない)。この困難は現代的なアルゴリズムでは克服されてきており、非常に大きなサイズの問題例（実際的な問題より大きいことが多い）の（廃棄量最小化の意味での）最適化ができるようになってきている。
板取り問題は、廃棄率が同一となるような複数の最適解が存在することで非常に困難になることが多い。これは、廃棄率を変えることなく、製品の切り出し位置が互いに移り変わり得ることから生じる。これに関連して、着目点に応じた諸問題が立てられている。：