2D Bin Packing
Pack rectangles into the fewest fixed-size bins.
Also called: 2D Bin Packing · 이차원 빈 패킹 · 2BP · 직사각형 빈 패킹
Last verified: 2026-05-27
Definition
Pack axis-aligned rectangles, without overlap, into the minimum number of identical fixed-size bins.
Example
Suppose bins of size and items: two and two . Stacking the two pieces in one bin fills it exactly (), and the two pieces sit side by side on the floor of a second bin. The minimum is 2 bins — the total area exceeds a single bin's 16.
Family
Together with 2D Strip Packing and 2D knapsack, this is one of the canonical orthogonal cutting & packing problems in the Wäscher et al. typology. It contrasts with irregular nesting in geometry (rectangles only) while sharing parts of the solution methodology.
Benchmarks
2DPackLib is a direct benchmark (grade A).
Related nodes
See the depth-1 graph below.
Claims & evidence
Every relationship is a claim with an equivalence level and an evidence grade. See the evidence policy.
| Relationship | Claim | Equiv. | Evidence | Sources |
|---|---|---|---|---|
| shares method with2D Strip Packing | 2D bin packing and strip packing share constructive and exact methods; strip packing often appears as a subproblem when filling a single bin. | E2 | B |
|
| direct benchmark2DPackLib | 2DPackLib provides standard instances for two-dimensional orthogonal bin packing. | — | A |
|
| uses methodBranch and Bound | Exact approaches to 2D bin packing have been reported with branch-and-bound (and branch-and-price) formulations. | — | B |
|
| uses methodFirst-Fit Decreasing | First-fit-decreasing (FFD) style constructive heuristics are widely used for fast approximate bin packing. | — | B |
|
| uses methodGenetic Algorithm | 2D bin packing has also been addressed with metaheuristics such as genetic algorithms. | — | B |
|
| uses methodInteger Linear Programming | 2D bin packing is formulated as an integer linear program (ILP), the starting point for exact methods such as branch-and-bound and branch-and-price. | — | A |
|
| uses methodLower Bounds | Exact methods for 2D bin packing prune the search with strong lower bounds, from area bounds to Martello–Toth-style discrete bounds. | — | A |
|
| uses methodColumn Generation | Exact approaches to 2D bin packing have been reported with column generation / branch-and-price. | — | B |
|
| uses methodTabu Search | 2D bin packing has also been reported with tabu-search-based search. | — | B |
|
Neighborhood
Direct graph neighbors. Toggle depth to expand.
See also
Not directly linked, but conceptually close — by the connections and descriptions they share.