2D Strip Packing

Pack rectangles into a fixed-width strip, minimizing used height.

Also called: 2D Strip Packing · 직사각형 스트립 패킹 · Rectangle strip packing

Definition

Pack axis-aligned rectangles into a strip of fixed width and unbounded height, without overlap, minimizing the used height.

Example

Suppose a strip of width $W = 4$ and items: one $4\times1$ and two $2\times3$ . Placing the two $2\times3$ pieces side by side fills the width ( $2+2=4$ ) at height 3, and the $4\times1$ on top brings the used height to 4. This matches the lower bound — total area $6+6+4=16$ divided by width 4 — so it is optimal.

Relationship to irregular nesting

Strip packing is the orthogonal special case of the broader nesting problem: when every piece is a rectangle, irregular nesting reduces to strip packing. They share constructive placement heuristics (notably bottom-left), recorded as an E2_method_shared link rather than an equivalence — the geometry differs even though the methodology overlaps.

Benchmarks

Unlike irregular nesting (for which 2DPackLib is only adjacent), 2DPackLib is a direct benchmark here: it targets two-dimensional orthogonal cutting and packing. [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 Strip Packing to 2D Irregular Nesting
Rectangle strip packing and irregular nesting share placement heuristics (e.g. bottom-left) and sit in the same cutting & packing family; rectangles are the orthogonal special case.
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.
uses method
2D Strip Packing to Bottom-Left Fill
Bottom-left and bottom-left-fill were introduced for rectangle strip/packing layouts and are standard constructive heuristics here.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialOn genetic algorithms for the packing of polygons
  Citation details
  Jakobs, S. (1996). On genetic algorithms for the packing of polygons. EJOR 88(1):165-181. Origin of the bottom-left-fill placement heuristic.
direct benchmark
2D Strip Packing to 2DPackLib
2DPackLib provides instances directly relevant to two-dimensional orthogonal strip 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 Strip Packing to Genetic Algorithm
Rectangle strip/packing has been addressed with genetic-algorithm search over piece sequence and orientation.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: A — Peer-reviewed / officialOn genetic algorithms for the packing of polygons
  Citation details
  Jakobs, S. (1996). On genetic algorithms for the packing of polygons. EJOR 88(1):165-181. Origin of the bottom-left-fill placement heuristic.
uses method
2D Strip Packing to First-Fit Decreasing
Level-based first-fit-decreasing rules (e.g. FFDH) are classic constructive heuristics for strip 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 Strip Packing to Simulated Annealing
Strip packing has also been reported with simulated-annealing-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.
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.
uses method
2D Strip Packing to Tabu Search
Strip 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.
uses method
2D Strip Packing to Integer Linear Programming
2D strip packing is formulated as an integer linear program, the basis for exact methods.
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.

Relationships from this entry
Relationship	Claim	Evidence	Equiv.	Sources
shares method with 2D Strip Packing to 2D Irregular Nesting	Rectangle strip packing and irregular nesting share placement heuristics (e.g. bottom-left) and sit in the same cutting & packing family; rectangles are the orthogonal special case.	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.
uses method 2D Strip Packing to Bottom-Left Fill	Bottom-left and bottom-left-fill were introduced for rectangle strip/packing layouts and are standard constructive heuristics here.	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialOn genetic algorithms for the packing of polygons Citation details Jakobs, S. (1996). On genetic algorithms for the packing of polygons. EJOR 88(1):165-181. Origin of the bottom-left-fill placement heuristic.
direct benchmark 2D Strip Packing to 2DPackLib	2DPackLib provides instances directly relevant to two-dimensional orthogonal strip 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 Strip Packing to Genetic Algorithm	Rectangle strip/packing has been addressed with genetic-algorithm search over piece sequence and orientation.	B · Survey / tutorial / community	—	Source grade: A — Peer-reviewed / officialOn genetic algorithms for the packing of polygons Citation details Jakobs, S. (1996). On genetic algorithms for the packing of polygons. EJOR 88(1):165-181. Origin of the bottom-left-fill placement heuristic.
uses method 2D Strip Packing to First-Fit Decreasing	Level-based first-fit-decreasing rules (e.g. FFDH) are classic constructive heuristics for strip 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 Strip Packing to Simulated Annealing	Strip packing has also been reported with simulated-annealing-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.
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.
uses method 2D Strip Packing to Tabu Search	Strip 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.
uses method 2D Strip Packing to Integer Linear Programming	2D strip packing is formulated as an integer linear program, the basis for exact methods.	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.

Relationships to this entry 3

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.
generalizes
2D Irregular Nesting to 2D Strip Packing
Irregular nesting generalizes rectangular strip packing: rectangles are a special case of arbitrary polygons.
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 Strip Packing
Guillotine cutting and strip packing share orthogonal placement 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.

Relationships to 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.
generalizes 2D Irregular Nesting to 2D Strip Packing	Irregular nesting generalizes rectangular strip packing: rectangles are a special case of arbitrary polygons.	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 Strip Packing	Guillotine cutting and strip packing share orthogonal placement 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.