板取り問題
板取り問題はレオニート・ヴィタリエヴィチ・カントロヴィチによって1939年に初めて定式化された。1951年、まだコンピュータが広く実用化されていなかった頃、カントロヴィチとヴィクター・アブラモヴィッチ・ザルガラーは、切断段階における資材の効率的な利用の問題を線形計画法を用いて解くことを提案した。この手法は後に列生成法(英語版)と呼ばれることになる。
この困難は現代的なアルゴリズムでは克服されてきており、非常に大きなサイズの問題例(実際的な問題より大きいことが多い)の(廃棄量最小化の意味での)最適化ができるようになってきている。
板取り問題は、廃棄率が同一となるような複数の最適解が存在することで非常に困難になることが多い。これは、廃棄率を変えることなく、製品の切り出し位置が互いに移り変わり得ることから生じる。これに関連して、着目点に応じた諸問題が立てられている。:
最小パターン数問題(minimum pattern count problem):廃棄量が最小となるような解の中で、用いるパターン数を最小に抑えるものを探す。たとえ最適廃棄量がわかっていたとしても、非常に難しい問題である。1次元で制約条件が等号の場合、製品種類が n 通りであれば、パターン数が n + 1 以下となる最適解が存在すると予想されている。
最小スタック問題(minimum stack problem):各時点で注文数に達していない製品種が多くなり過ぎないような、パターンの使用順序を求める問題。この問題は2007年まで手つかずだったが、動的計画法に基づく効率的なアルゴリズムが発表された。
最小ナイフ交換数問題(minimum number of knife changes problem)(1次元の場合):スリッターナイフの交換回数を最小にするようなパターンの使用順序を求める問題。これは一般化された巡回セールスマン問題の特別な場合である。
板取り問題はいくつかの方法で分類できる。1つの方法は切断対象の次元による分類である。上に挙げた例は1次元の問題だった。1次元の問題は他にもパイプ、ケーブル、鋼棒を切断するといった場合に適用できる。2次元の問題は家具類や布製品、ガラス製品に当てはまる。母材もしくは製品が 特殊な形状をしている場合(皮革、生地、板金等の加工ではしばしば見られる)は、ネスティング問題(Nesting problem)と呼ばれる。
3次元の切断への適用例はあまり知られていないが、この問題と密接に関連した3次元パッキング問題には、船荷の積み込み等、幅広い産業上の応用がある(例えばコンテナ輸送を参照。これに関連した球充填の問題は17世紀以来研究されている(ケプラー予想))。