Bin Packing Problem¶

Definition¶

The bin packing problem assigns every item to a container, subject to a common capacity per container, and minimizes the number of containers used. If item $i$ has weight $w_i$ and a container has capacity $C$ , the weights assigned to each container must sum to at most $C$ .

Interpretation¶

Bin packing asks how few containers are needed when items of different weights must be grouped without exceeding a common capacity. The difficulty lies in deciding which items share a container: the number of possible groupings grows very quickly with the number of items.

Two containers of capacity 50, one holding items of weight 15 and 35 and the other items of weight 30 and 20, each filled exactly.

The figure shows a packing of the four items $15,30,20,35$ into containers of capacity $C=50$ $50$ . Both containers are filled exactly to $50$ , and no packing can use fewer: one container holds at most $50$ , while the total weight is $100$ .

The constraints have two parts: every item goes whole to exactly one container, and in each container the assigned weights sum to at most $C$ . If items could be split, the containers could be filled one after another up to capacity, and the ceiling $\displaystyle \lceil\sum_i w_i/C\rceil$ containers would be enough. This relaxation is why the total-weight bound is a lower bound on the minimum. A heuristic such as first fit builds a feasible packing quickly, and its number of containers is an upper bound; when the two bounds are equal, the packing is optimal.

A common slip is to treat the total-weight bound as the answer. Three items of weight $30$ with $C=50$ have total weight $90$ , so the bound is $\lceil 90/50\rceil=2$ $2$ , but no two of them fit together because $60>50$ $50$ ; three containers are needed.

Key Results¶

Each item must be packed exactly once without splitting it.
Any feasible packing provides an upper bound on the minimum number of containers.
The total-weight bound is $\displaystyle \lceil\sum_i w_i/C\rceil$ ; it need not be attainable. This follows by aggregating the capacity requirements.

Examples¶

The figure is a separate four-item illustration with weights $15,30,20,35$ and capacity $C=50$ $50$ . Its lower bound is $\lceil100/50\rceil=2$ $2$ , attained by the displayed packing $\{15,35\}$ and $\{30,20\}$ . This proves optimality for the illustrated instance, rather than for the 15-item course exercise.

The exercise has 15 items and container capacity 50.
First-fit uses five containers, while the solution sheet states that four suffice.

Prerequisites¶

Sources¶

OR Modelling · Week 1

Aliases: bin packing Keywords: Container packing Symbols: sum

Last updated: 20 October 2026 03:02