3.2 The bin packing problem¶
Part 1 · Combinatorial optimization problems · Chapter 3 · Chapter 3: Packing problems · Lecture notes, volume 1 (PDF) · Slides · Exercises: Packing problems
Definition 3.1: Bin Packing Problem
Given:
-
an infinite number of bins, each with capacity \(c \in \Z_{\ge 1}\),
-
a set \(\mathscr{I} = \{1,2,\dots,n\}\) of \(n\) items,
-
for each item \(j \in \mathscr{I}\), a weight \(w_j \in \Z_{\ge 1}\),
the Bin Packing Problem (BPP) asks to decide in which bin to place each item, so that the total weight of the items in any bin does not exceed the bin capacity, and the total number of bins used is minimized.
-
A BPP instance is specified by:
-
two integer numbers:
-
the bin capacity \(c \in \Z_{\ge 1}\),
-
the number of items \(n \in \Z_{\ge 1}\),
-
-
one vector of integer numbers of length \(n\):
- \(\vet{w} \in \Z_{\ge 1}^n\), containing the item weights.
-
-
A BPP feasible solution is a family of packing patterns, i.e., subsets of items each assigned to one bin,
\[ \mathcal{P} \subseteq 2^{\mathscr{I}} \]such that:
-
(i) \(\mathcal{P}\) forms a partition of \(\mathscr{I}\) into nonempty packing patterns, namely
\[ \begin{gathered} P\neq \emptyset, \quad \text{for all } \, P\in\mathcal{P},\\ P\cap P'=\emptyset, \quad \text{for all } \, P,P'\in\mathcal{P}\ \text{with } P\neq P',\\ \bigcup_{P\in\mathcal{P}} P=\mathscr{I}; \end{gathered} \] -
(ii) the total weight of every packing pattern in \(\mathcal{P}\) respects the bin capacity, namely
\[ \sum_{j\in P} w_j \le c, \quad \text{for all }\, P\in\mathcal{P}. \]
Accordingly, the BPP can be equivalently stated as the problem of determining a partition of the item set into packing patterns such that the total weight of the items in each packing pattern does not exceed the bin capacity, and the number of packing patterns (bins) is minimized.
Given a BPP instance, the BPP can be formally stated as:
\[\begin{equation*} \label{BPP} \tilde{\mathcal{P}} \in \argmin_{\mathcal{P}\subseteq 2^{\mathscr{I}}} \left\{ |\mathcal{P}| \;:\; \begin{array}{l} P\neq \emptyset, \quad \forall\, P\in\mathcal{P},\\[8pt] P\cap P'=\emptyset, \quad \forall\, P,P'\in\mathcal{P},\, P\neq P',\\[8pt] \displaystyle \bigcup_{P\in\mathcal{P}} P=\mathscr{I},\\[14pt] \displaystyle \sum_{j\in P} w_j \le c, \quad \forall\, P\in\mathcal{P} \end{array} \right\}. \tag{3.1} \end{equation*}\] -
Example 3.1: BPP instances
We consider a bin of capacity \(c = 10\) and a set \(\mathscr{I} = \{1,2,3,4,5\}\) of \(5\) items (\(n = 5\)), with the following item weights:
| Items | \(j=1\) | \(j=2\) | \(j=3\) | \(j=4\) | \(j=5\) | |
|---|---|---|---|---|---|---|
| Weights | \(w_j\) | \(6\) | \(5\) | \(4\) | \(7\) | \(3\) |
In the drawing every bin is a box of height \(c=10\) and every item a block of height \(w_j\). The three bins hold \(\{4,5\}\), \(\{1,3\}\) and \(\{2\}\); we show below that \(3\) bins are the minimum.
We call this BPP instance Example 3.1: it is the reference instance of the chapter.
3.2.1 Assumptions¶
-
We make the following assumptions:
-
The total weight of all items exceeds the bin capacity (otherwise, all items could fit in a single bin). Formally:
\[ \sum_{j \in \mathscr{I}} w_j > c \] -
Each item individually fits into a single bin (otherwise, it cannot be packed at all). Formally:
\[ w_j \le c,~~~~ \forall j \in \mathscr{I} \]
-
3.2.2 Counting the solutions, a first solution and a simple bound¶
-
Candidate solutions. The candidate solutions are the partitions of \(\mathscr{I}\): they are counted by the Bell numbers (Chapter 1 «Combinatorial optimization problems»). For Example 3.1 we have \(B(5) = 52\) partitions.
-
Feasible solutions. A partition is feasible if every bin weighs at most \(10\). Enumeration gives \(11\) feasible partitions: \(1\) with \(5\) bins (one item per bin), \(6\) with \(4\) bins and \(4\) with \(3\) bins. Two bins are not enough, since the total weight \(25\) exceeds \(2 \cdot 10\).
-
A first solution, by eye. We pair the heavy items with the light ones: item \(4\) (weight \(7\)) with item \(5\) (weight \(3\)), and item \(1\) (weight \(6\)) with item \(3\) (weight \(4\)); item \(2\) (weight \(5\)) stays alone. The solution
\[ \mathcal{P} = \big\{\, \{4,5\},~ \{1,3\},~ \{2\} \,\big\} \]uses \(3\) bins, of weights \(10\), \(10\) and \(5\): it is a primal bound, \(\UB = 3 \ge z(I)\).
Observation 3.2: weight bound
Every feasible solution uses at least
bins, so this value is a dual bound.
Proof
If a solution uses \(k\) bins, the total weight it carries is at most \(k \, c\). The total weight of the items is \(\sum_{j} w_j\), hence \(k\,c \ge \sum_{j} w_j\). The number \(k\) is an integer, so \(k \ge \lceil \sum_j w_j / c \rceil\). □
-
The dual bound and the gap. In Example 3.1 we have \(\sum_j w_j = 25\) and \(c = 10\), so \(\LB = \lceil 25/10 \rceil = 3\). The two bounds coincide: the gap is zero, the solution found by eye is optimal and \(z(I) = 3\), without enumerating the partitions.
-
The optimal solution is not unique: there are \(4\) optimal partitions,
\[ \begin{array}{ll} \{\{1\},\{2,3\},\{4,5\}\}, & \{\{2\},\{1,3\},\{4,5\}\},\\[0.5ex] \{\{4\},\{1,5\},\{2,3\}\}, & \{\{4\},\{1,3\},\{2,5\}\}. \end{array} \]