The bin packing problem (BPP)¶
Definition 1: The 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.
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} \]
-
What the course does on this problem¶
| Technique | Where |
|---|---|
| Definition | Ch. 3 «Packing problems» |
| Formulations | Ch. 10 «Formulations of packing problems» |
| Heuristics | Ch. 29 «Heuristic algorithms: definitions»; Ch. 30 «Constructive heuristics»; Ch. 31 «Local search»; Ch. 32 «Metaheuristics» |
| MIP heuristics | Ch. 33 «MIP heuristics for the classical problems» |
| Approximation | Ch. 36 «Approximation algorithms for bin packing» |
| Exercises | Ch. 3 (6 exercises); Exercise 7.5; Ch. 10 (5 exercises); Exercise 29.2; Ch. 30 (3 exercises); Ch. 31 (3 exercises); Ch. 32 (2 exercises); Exercise 34.3; Ch. 36 (12 exercises) |
Properties¶
-
Strongly NP-hard: no pseudo-polynomial algorithm exists, unless \(P=NP\) (Ch. 1).
-
Weight bound \(\LB = \lceil \sum_j w_j / c \rceil\); it is not always tight: three items of weight \(6\) with \(c=10\) need \(3\) bins, not \(2\) (Ch. 3).
Formulations¶
-
The model \(\ILP_{\BPP}\) has \(mn\) assignment variables \(x_{jb}\) and \(m\) activation variables \(y_b\) (Ch. 10).
-
Both LP relaxations have value \(\sum_j w_j/c\): rounded up, the weight bound again (Ch. 10).
-
The ratio of the LP bound to the optimum is at least \(\frac12\), and \(\frac12\) is approached (Ch. 10).
Heuristics¶
-
First Fit Decreasing and Best Fit Decreasing find the optimum \(3\) on the instance of Ch. 29; \(FFD(I) \le \frac{11}{9}\, z(I) + \frac{6}{9}\), tight (Ch. 30).
-
The number of bins is flat, so move and swap local search uses the auxiliary objective \(\max \sum_b L_b^2\) (Ch. 31).
-
VND with move and swap reaches the optimum in \(89\) of \(100\) runs on an instance with \(n=12\) (Ch. 31).
-
Large neighbourhood search: on BPP24 the exact repair with \(q\ge 3\) reaches the optimum \(9\) in every run (Ch. 32).
MIP heuristics¶
-
Rounding and fractional diving fail on the instance of Ch. 29: the LP spreads an item over several bins (Ch. 33).
-
The feasibility pump always finds a packing, but it may leave empty bins open (Ch. 33).
-
On an instance with \(n=60\) the whole difficulty is primal: the heuristics of Gurobi decide the solution time (Ch. 33).