Bin packing

The problem

You have items of different sizes and an unlimited supply of identical bins, each with capacity C. Put every item in some bin, never overfilling one, and use as few bins as possible.

Replace bins with servers and items with virtual machines, and it's how a cloud provider decides how many hosts to keep running. With trucks and parcels it's load planning; with disks and files it's backup scheduling; with rolls of steel or paper and the lengths customers ordered, it becomes the cutting-stock problem. Memory allocators face the same question every time a program asks for a block.

Formal model

Let x_ij = 1 if item i goes into bin j, and y_j = 1 if bin j is used at all. With item sizes s_i:

The simplest lower bound falls straight out of the capacity constraint. Even with zero waste, the bins must hold the total size, so any packing needs at least L₁ = ⌈Σ s_i ÷ C⌉ bins. The lab compares every rule against it.

Why it's hard

Just deciding whether two bins are enough is the partition problem: can these numbers be split into two halves of equal sum? That's NP-complete, so bin packing is NP-hard. It also means that, unless P = NP, no fast algorithm can guarantee better than 3/2 times the optimum on every input: on an instance that fits in two bins it would have to find that two-bin packing, which answers the partition question.

The number of ways to split n items into groups is the Bell number B_n. Ten items can be grouped 115,975 ways; twenty items, about 51.7 trillion. Exact solvers survive by pruning: any partial packing whose bins plus lower bound already match the best known answer can be dropped.

Data structures

A list of free capacities

Every rule here keeps one number per open bin, its free space, and differs only in how it searches that list. Written as plain loops, as in the lab's pseudo-code, first, best and worst fit cost O(n) per item and O(n²) overall.

Trees that make it O(n log n)

• First fit stores free space in a tournament tree (a segment tree of maxima). To place an item of size s, walk down from the root, always turning left when the left subtree's maximum is at least s. That finds the leftmost bin with room in O(log n).
• Best fit keeps the free spaces in a balanced binary search tree, or a sorted multiset. The tightest bin that fits is the smallest key that's at least s: one lower-bound query.
• Worst fit only needs the roomiest bin: a max-heap.
• Next fit needs nothing but a pointer to the one open bin, which makes it the only rule here that runs in true constant memory.

Search trees for the exact answer

The optimum shown in the comparison chart comes from a depth-first branch and bound. It places items largest first, tries each open bin and then a new one, skips bins whose free space equals one already tried (they're interchangeable), and prunes any branch where the bins used so far plus a lower bound on the rest can't beat the best packing found.

The algorithms

The six rules split into online rules, which place items in arrival order and never move them, and offline rules, which may sort the items first. Their worst-case guarantees are some of the best-known results in approximation algorithms:

Why does next fit never use more than about twice the optimum? Any two consecutive bins it closes together hold more than C, otherwise the second bin's first item would have fit in the first. So at most half the space is wasted.

Why does sorting help so much? Large items, the ones bigger than half a bin, can never share a bin with each other, so they force a bin each no matter what. Placing them first lets small items fill the gaps they leave. Placing small items first, as in the "Small items first" example, packs them tightly together and leaves the large ones nowhere to go.

As an integer program

Pick "Integer program" in the lab to watch the formal model above being solved the way commercial solvers do it: relax every x and y to any value between 0 and 1, solve that linear program with the simplex method, and branch on a variable that came out fractional. The item-by-bin table shows the relaxation literally splitting an item between two bins, something no real packing can do.

The model includes two tricks that matter a lot in practice. Item i may only use bins 1 to i, and bins are opened in order. Without them, every packing would appear many times with the bins merely renumbered, and the search would waste most of its time proving the same thing again. Even so, the assignment model's relaxation is weak (it just says "you need total size ÷ capacity bins"), which is why the view is limited to a few items and why serious solvers switch to the pattern-based formulation described below.

Beyond this lab

• Column generation. The strongest exact solvers don't assign items to bins directly. They choose among patterns, sets of items that fit in one bin, and generate good patterns on demand by solving a knapsack problem. This is the Gilmore–Gomory approach from cutting stock, wrapped in branch and price.
• Approximation schemes. For any ε > 0 there's a polynomial algorithm using at most (1 + ε)·OPT + 1 bins, by rounding item sizes into a few classes and solving the rounded problem exactly.
• Variants. Two- and three-dimensional packing (pallets, shipping containers), vector packing where each item has several dimensions (a virtual machine's CPU and memory), online packing where items arrive one by one, and packing with conflicts between items.

A little history

Leonid Kantorovich wrote about cutting problems in 1939, and Paul Gilmore and Ralph Gomory's 1961 work on cutting stock introduced the column generation still used by exact solvers. Bin packing in its modern form arrived in the early 1970s: David Johnson's 1973 PhD thesis analyzed first fit, best fit and their sorted versions and helped start the field of approximation algorithms. The tight bound for first fit decreasing, 11/9·OPT + 6/9, was only settled by György Dósa in 2007, and the exact ⌊1.7·OPT⌋ bound for first fit by Dósa and Jiří Sgall in 2013.