2D Bin Packing

Pack rectangles into the fewest fixed-size bins.

Also called: 2D Bin Packing · 이차원 빈 패킹 · 2BP · 직사각형 빈 패킹

Definition

Pack axis-aligned rectangles, without overlap, into the minimum number of identical fixed-size bins.

Example

Suppose bins of size $4\times4$ and items: two $4\times2$ and two $2\times2$ . Stacking the two $4\times2$ pieces in one bin fills it exactly ( $4\times4$ ), and the two $2\times2$ pieces sit side by side on the floor of a second bin. The minimum is 2 bins — the total area $8+8+4+4=24$ 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).

Claims & evidence

Every relationship is a claim with an evidence grade; applicable problem-to-problem relationships also carry an equivalence level. See the evidence policy.

A–X describes evidence reliability; E0–E4 describes mathematical similarity between problems. The two axes are independent.

Relationships from this entry 9

shares method with
2D Bin Packing to 2D 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.
EvidenceB · Survey / tutorial / community
Equiv.E2 · shared methodology
Sources
- Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems
  Citation details
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
direct benchmark
2D Bin Packing to 2DPackLib
2DPackLib provides standard instances for two-dimensional orthogonal bin packing.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / official2DPackLib: a two-dimensional cutting and packing library
  Citation details
  Iori, M., de Lima, V.L., Martello, S., Monaci, M. (2022). 2DPackLib: a two-dimensional cutting and packing library. Optimization Letters. Focuses on two-dimensional orthogonal cutting and packing instances.
uses method
2D Bin Packing to Branch and Bound
Exact approaches to 2D bin packing have been reported with branch-and-bound (and branch-and-price) formulations.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey
  Citation details
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
uses method
2D Bin Packing to First-Fit Decreasing
First-fit-decreasing (FFD) style constructive heuristics are widely used for fast approximate bin packing.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey
  Citation details
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
uses method
2D Bin Packing to Genetic Algorithm
2D bin packing has also been addressed with metaheuristics such as genetic algorithms.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey
  Citation details
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
uses method
2D Bin Packing to Integer 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.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey
  Citation details
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
uses method
2D Bin Packing to Lower Bounds
Exact methods for 2D bin packing prune the search with strong lower bounds, from area bounds to Martello–Toth-style discrete bounds.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey
  Citation details
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
uses method
2D Bin Packing to Column Generation
Exact approaches to 2D bin packing have been reported with column generation / branch-and-price.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: A — Peer-reviewed / officialUsing Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem
  Citation details
  Pisinger, D., Sigurd, M. (2007). Using Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem. INFORMS Journal on Computing 19(1):36-51. A Dantzig-Wolfe / branch-and-price-and-cut exact method for 2D bin packing.
uses method
2D Bin Packing to Tabu Search
2D bin packing has also been reported with tabu-search-based search.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey
  Citation details
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.

Relationships from this entry
Relationship	Claim	Evidence	Equiv.	Sources
shares method with 2D Bin Packing to 2D 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.	B · Survey / tutorial / community	E2 · shared methodology	Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems Citation details Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
direct benchmark 2D Bin Packing to 2DPackLib	2DPackLib provides standard instances for two-dimensional orthogonal bin packing.	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / official2DPackLib: a two-dimensional cutting and packing library Citation details Iori, M., de Lima, V.L., Martello, S., Monaci, M. (2022). 2DPackLib: a two-dimensional cutting and packing library. Optimization Letters. Focuses on two-dimensional orthogonal cutting and packing instances.
uses method 2D Bin Packing to Branch and Bound	Exact approaches to 2D bin packing have been reported with branch-and-bound (and branch-and-price) formulations.	B · Survey / tutorial / community	—	Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey Citation details Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
uses method 2D Bin Packing to First-Fit Decreasing	First-fit-decreasing (FFD) style constructive heuristics are widely used for fast approximate bin packing.	B · Survey / tutorial / community	—	Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey Citation details Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
uses method 2D Bin Packing to Genetic Algorithm	2D bin packing has also been addressed with metaheuristics such as genetic algorithms.	B · Survey / tutorial / community	—	Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey Citation details Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
uses method 2D Bin Packing to Integer 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 · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey Citation details Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
uses method 2D Bin Packing to Lower Bounds	Exact methods for 2D bin packing prune the search with strong lower bounds, from area bounds to Martello–Toth-style discrete bounds.	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey Citation details Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
uses method 2D Bin Packing to Column Generation	Exact approaches to 2D bin packing have been reported with column generation / branch-and-price.	B · Survey / tutorial / community	—	Source grade: A — Peer-reviewed / officialUsing Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem Citation details Pisinger, D., Sigurd, M. (2007). Using Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem. INFORMS Journal on Computing 19(1):36-51. A Dantzig-Wolfe / branch-and-price-and-cut exact method for 2D bin packing.
uses method 2D Bin Packing to Tabu Search	2D bin packing has also been reported with tabu-search-based search.	B · Survey / tutorial / community	—	Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey Citation details Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.

Relationships to this entry 8

shares method with
1D Cutting Stock to 2D Bin Packing
1D cutting stock and bin packing are closely related members of the same cutting & packing family; both are addressed with pattern/configuration formulations.
EvidenceB · Survey / tutorial / community
Equiv.E3 · structural analogy
Sources
- Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems
  Citation details
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
shares method with
2D Irregular Nesting to 2D Bin Packing
Irregular nesting and 2D bin packing belong to the same cutting & packing family and share metaheuristic search methodology.
EvidenceB · Survey / tutorial / community
Equiv.E2 · shared methodology
Sources
- Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems
  Citation details
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
shares method with
2D Knapsack to 2D Bin Packing
2D knapsack and bin packing share the orthogonal placement core and many exact/heuristic methods.
EvidenceB · Survey / tutorial / community
Equiv.E2 · shared methodology
Sources
- Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems
  Citation details
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
generalizes
3D Bin Packing to 2D Bin Packing
3D bin packing is a higher-dimensional generalization of 2D bin packing and shares many constructive and search methods.
EvidenceB · Survey / tutorial / community
Equiv.E2 · shared methodology
Sources
- Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems
  Citation details
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
variant of
Guillotine Cutting to 2D Bin Packing
Guillotine cutting is a variant of 2D orthogonal cutting & packing with the added constraint that cuts must be edge-to-edge and straight.
EvidenceA · Peer-reviewed / official
Equiv.E1 · same base, different side constraints
Sources
- Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems
  Citation details
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
variant of
Pallet Loading to 2D Bin Packing
(Manufacturer's) pallet loading is a structured variant that fills a single area with identical rectangles, close to 2D orthogonal packing.
EvidenceB · Survey / tutorial / community
Equiv.E2 · shared methodology
Sources
- Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems
  Citation details
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
variant of
Variable-Sized Bin Packing to 2D Bin Packing
Variable-sized bin packing is the bin-packing variant with bins of several sizes/costs, minimizing total bin cost rather than bin count — distinguished along the 'bin assortment' dimension of the Wäscher et al. typology.
EvidenceA · Peer-reviewed / official
Equiv.E1 · same base, different side constraints
Sources
- Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems
  Citation details
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
mentions
Wäscher Typology to 2D Bin Packing
The typology classifies 2D bin packing as an 'input minimization' type — accommodate all items while minimizing the bins used.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems
  Citation details
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.

Relationships to this entry
Relationship	Claim	Evidence	Equiv.	Sources
shares method with 1D Cutting Stock to 2D Bin Packing	1D cutting stock and bin packing are closely related members of the same cutting & packing family; both are addressed with pattern/configuration formulations.	B · Survey / tutorial / community	E3 · structural analogy	Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems Citation details Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
shares method with 2D Irregular Nesting to 2D Bin Packing	Irregular nesting and 2D bin packing belong to the same cutting & packing family and share metaheuristic search methodology.	B · Survey / tutorial / community	E2 · shared methodology	Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems Citation details Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
shares method with 2D Knapsack to 2D Bin Packing	2D knapsack and bin packing share the orthogonal placement core and many exact/heuristic methods.	B · Survey / tutorial / community	E2 · shared methodology	Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems Citation details Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
generalizes 3D Bin Packing to 2D Bin Packing	3D bin packing is a higher-dimensional generalization of 2D bin packing and shares many constructive and search methods.	B · Survey / tutorial / community	E2 · shared methodology	Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems Citation details Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
variant of Guillotine Cutting to 2D Bin Packing	Guillotine cutting is a variant of 2D orthogonal cutting & packing with the added constraint that cuts must be edge-to-edge and straight.	A · Peer-reviewed / official	E1 · same base, different side constraints	Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems Citation details Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
variant of Pallet Loading to 2D Bin Packing	(Manufacturer's) pallet loading is a structured variant that fills a single area with identical rectangles, close to 2D orthogonal packing.	B · Survey / tutorial / community	E2 · shared methodology	Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems Citation details Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
variant of Variable-Sized Bin Packing to 2D Bin Packing	Variable-sized bin packing is the bin-packing variant with bins of several sizes/costs, minimizing total bin cost rather than bin count — distinguished along the 'bin assortment' dimension of the Wäscher et al. typology.	A · Peer-reviewed / official	E1 · same base, different side constraints	Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems Citation details Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
mentions Wäscher Typology to 2D Bin Packing	The typology classifies 2D bin packing as an 'input minimization' type — accommodate all items while minimizing the bins used.	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems Citation details Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.