2D Knapsack

Select a subset of rectangles for a single sheet, maximizing value (or area).

Also called: 2D Knapsack · Rectangle knapsack · 직사각형 배낭

Definition

Choose a subset of candidate rectangles and place them, without overlap, on a single fixed-size sheet, maximizing the total value (often area) of the placed pieces.

Example

Suppose a sheet $4\times4$ and candidates $3\times3$ (value 9), $4\times1$ (value 4), $1\times3$ (value 3), and $2\times2$ (value 4). Choosing the first three — $3\times3$ at the bottom-left, $4\times1$ along the top row, $1\times3$ in the right column — tiles the sheet exactly for value $9+4+3=16$ . Adding the $2\times2$ would exceed the sheet area, so this trio is optimal.

Family

A core orthogonal cutting & packing problem alongside bin packing and strip packing. Its "what to include" selection structure on a single sheet shares its name and structure with the one-dimensional 0/1 Knapsack Problem.

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 6

uses method
2D Knapsack to Dynamic Programming
2D knapsack variants have been addressed with dynamic programming and exact/approximate methods built on it.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: A — Peer-reviewed / officialKnapsack Problems
  Citation details
  Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
direct benchmark
2D Knapsack to 2DPackLib
2DPackLib includes two-dimensional orthogonal knapsack instances.
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.
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
2D Knapsack to 0/1 Knapsack Problem
2D knapsack is a two-dimensional generalization of the 1D 0/1 knapsack problem, extending item selection to geometric placement.
EvidenceB · Survey / tutorial / community
Equiv.E2 · shared methodology
Sources
- Source grade: A — Peer-reviewed / officialKnapsack Problems
  Citation details
  Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
uses method
2D Knapsack to Branch and Bound
Exact branch-and-bound algorithms have been proposed for the geometric 2D knapsack, using a one-dimensional knapsack relaxation (rectangle areas as weights) as a bound (Caprara & Monaci 2004).
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialOn the two-dimensional Knapsack Problem
  Citation details
  Caprara, A., Monaci, M. (2004). On the two-dimensional Knapsack Problem. Operations Research Letters 32(1):5-14. Exact branch-and-bound algorithms for the geometric 2D knapsack, using a one-dimensional knapsack relaxation on rectangle areas.
uses method
2D Knapsack to Genetic Algorithm
2D knapsack variants have also been addressed with metaheuristics such as genetic algorithms.
EvidenceB · Survey / tutorial / community
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 from this entry
Relationship	Claim	Evidence	Equiv.	Sources
uses method 2D Knapsack to Dynamic Programming	2D knapsack variants have been addressed with dynamic programming and exact/approximate methods built on it.	B · Survey / tutorial / community	—	Source grade: A — Peer-reviewed / officialKnapsack Problems Citation details Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
direct benchmark 2D Knapsack to 2DPackLib	2DPackLib includes two-dimensional orthogonal knapsack instances.	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.
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 2D Knapsack to 0/1 Knapsack Problem	2D knapsack is a two-dimensional generalization of the 1D 0/1 knapsack problem, extending item selection to geometric placement.	B · Survey / tutorial / community	E2 · shared methodology	Source grade: A — Peer-reviewed / officialKnapsack Problems Citation details Kellerer, H., Pferschy, U., Pisinger, D. (2004). Knapsack Problems. Springer. Standard reference on knapsack problems and dynamic-programming solutions.
uses method 2D Knapsack to Branch and Bound	Exact branch-and-bound algorithms have been proposed for the geometric 2D knapsack, using a one-dimensional knapsack relaxation (rectangle areas as weights) as a bound (Caprara & Monaci 2004).	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialOn the two-dimensional Knapsack Problem Citation details Caprara, A., Monaci, M. (2004). On the two-dimensional Knapsack Problem. Operations Research Letters 32(1):5-14. Exact branch-and-bound algorithms for the geometric 2D knapsack, using a one-dimensional knapsack relaxation on rectangle areas.
uses method 2D Knapsack to Genetic Algorithm	2D knapsack variants have also been addressed with metaheuristics such as genetic algorithms.	B · Survey / tutorial / community	—	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 4

shares method with
2D Strip Packing to 2D Knapsack
Strip packing and 2D knapsack share the orthogonal placement core and 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
Guillotine Cutting to 2D Knapsack
Maximizing on a single sheet under the guillotine constraint is the guillotine 2D knapsack, sharing methodology with 2D knapsack.
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
Pallet Loading to 2D Knapsack
(Manufacturer's) pallet loading — maximizing identical rectangles in a single area — connects to 2D-knapsack-style placement methods.
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.
mentions
Wäscher Typology to 2D Knapsack
The typology classifies 2D knapsack as an 'output maximization' type — maximize the value packed into a fixed resource.
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 2D Strip Packing to 2D Knapsack	Strip packing and 2D knapsack share the orthogonal placement core and 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 Guillotine Cutting to 2D Knapsack	Maximizing on a single sheet under the guillotine constraint is the guillotine 2D knapsack, sharing methodology with 2D knapsack.	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 Pallet Loading to 2D Knapsack	(Manufacturer's) pallet loading — maximizing identical rectangles in a single area — connects to 2D-knapsack-style placement methods.	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.
mentions Wäscher Typology to 2D Knapsack	The typology classifies 2D knapsack as an 'output maximization' type — maximize the value packed into a fixed resource.	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.