Cutting stock problem (CSP)

Catalogue of combinatorial problems · Packing problems · Catalogue (PDF)

Definition 1: Cutting stock problem

Given:

1. an infinite number of bins, each with capacity \(c \in \Z_{\ge 1}\),

2. a set \(\mathscr{I} = \{1,2,\dots,n\}\) of \(n\) items,

3. for each item \(j \in \mathscr{I}\), a weight \(w_j \in \Z_{\ge 1}\) and a number of required copies \(d_j \in \Z_{\ge 1}\),

the Cutting Stock Problem (CSP) asks to decide in which bin to place each copy of every item, so that the total weight of all item copies in any bin does not exceed the bin capacity, the required number of copies of each item is placed into the bins, and the total number of bins used is minimized.

Assumptions

• We make the following assumptions:

  1. The total weight of all required item copies exceeds the bin capacity (otherwise, all copies could fit in a single bin). Formally:

     \[ \sum_{j\in \mathscr{I}} d_j\, w_j \;>\; c. \]

  2. Each item individually fits into a single bin (otherwise, no copy of that item can be packed at all). Formally:

     \[ w_j \le c, \qquad \forall\, j\in \mathscr{I}. \]

What the course does on this problem

Technique	Where
Definition	Ch. 3 «Packing problems»
Formulations	Ch. 10 «Formulations of packing problems»
Exercises	Exercise 3.4; Exercise 10.6