Skip to content

Packing problems

Catalogue of combinatorial problems · Catalogue (PDF)

  • Each item \(j\) has a weight \(w_j\); a solution is a partition of the items into bins of capacity \(c\), such that the total weight of the items in every bin is at most \(c\).

  • The objective is to minimize the number of bins; in the cutting stock problem the items are grouped into types with a demand \(d_j\).

Problem Acronym Difference
Bin packing problem BPP The central problem of the family.
Cutting stock problem CSP The CSP is the BPP with \(d_j\) identical copies of every item \(j\), and the BPP is the case \(d_j = 1\) for all \(j\in\Ioggetti\).