板取り問題
これに関連した1次元の決定問題、つまり、与えられた製品要求を満足するような最適な母材の大きさを定める問題は、割当問題(assortment problem)として知られている。
ここで a i j {\displaystyle a_{ij}} は製品 j {\displaystyle j} がパターン i {\displaystyle i} の中に現れる回数、 c i {\displaystyle c_{i}} はパターン i {\displaystyle i} のコスト(普通は廃材の量とする)。 量的制約を正確に定式化することで、微妙に異なった様々な数学的特性が現れる。上記の定式化は、最小限の制約条件しか課していない(どの製品も受注分は最低限製造するが、それ以上に製造されても良い)。 c i = 1 {\displaystyle c_{i}=1} であれば、使用する母材の数量を最小化することになる。製造する製品の制約式を不等号でなく等号に変えたものはビンパッキング問題となる。最も一般的な定式化では、この制約不等式に下限と上限を設ける(このとき、廃棄量を最小化する解は母材の使用量を最小化していないかもしれない):
q j ≤ ∑ i = 1 n a i j x i ≤ Q j , ∀ j = 1 , ... , m {\displaystyle q_{j}\leq \sum _{i=1}^{n}a_{ij}x_{i}\leq Q_{j},\quad \quad \forall j=1,\dots ,m}
この定式化は1次元問題のみに限らない。多くの変種が考えられるが、例えば廃棄量の最小化ではなく製造量の価値の最大化(製品ごとに異なる価値を与えてよいとする)を最適化の目的としてもよい。
必要なマスターロールの本数の単純な下限は、全ての製品ロールの幅の総和をマスターロール1本の幅で割ることで求められる。この場合、総長は 1380 x 22 + 1520 x 25 + ... + 2200 x 20 = 407160 mm で、マスターロールは 5600 mm なので、割り算をすると72.7本、よって73本は最低でも必要ということになる。