Skip to content

Packing problems

Part 1 · Combinatorial optimization problems · Chapter 3 · Lecture notes, volume 1 (PDF) · Slides · Exercises: Packing problems

Prerequisites

Objectives

At the end of this chapter you will be able to:

  • state the definition of the bin packing problem and of the cutting stock problem, with instances and feasible solutions;

  • explain the assumptions on the data;

  • count the candidate solutions of a small instance and recognize that they are partitions;

  • find a feasible solution by hand and compute the weight bound;

  • use the two bounds to certify that a solution is optimal.

3.1 Overview of the family

  • The packing problems share the same data: an infinite number of identical bins of capacity \(c \in \Z_{\ge 1}\), a set \(\mathscr{I} = \{1,2,\dots,n\}\) of \(n\) items and, for each item \(j \in \mathscr{I}\), a weight \(w_j \in \Z_{\ge 1}\).

  • A solution assigns every item, or every required copy of an item, to a bin: the total weight of the items in a bin must not exceed the capacity \(c\).

  • The objective is to minimize the number of bins used.

A packing problem places all the items into the fewest bins of capacity \(c\). The members of the family differ in the number of copies of each item that must be packed.

  • The table lists the members of the family, with the section that defines each of them.
Problem Acronym Items to pack Section
bin packing problem BPP one copy of each item 3.2
cutting stock problem CSP \(d_j\) copies of item \(j\) 3.3

  • Overview

    Overview of the family

    Open

  • 3.2 The bin packing problem

    Counting the solutions, a first solution and a simple bound

    Open

  • 3.3 The cutting stock problem

    Counting the solutions, a first solution and a simple bound · Remarks · Typical mistakes · In summary

    Open

Next: 3.2 The bin packing problem

Exercises on this chapter: Packing problems

In depth: what the course does on this problem