Exact Solution Techniques for Two-dimensional Cutting and Packing

1 Introduction

• Cutting and packing are strongly correlated because packing items into containers can correspond to cutting them from stock units, which the paper collectively calls bins.Some applications use a single strip of theoretically infinite height.Source: §1 · p. 1

Books and surveys

• The survey literature spans one-dimensional, two-dimensional rectangular and irregular-shape, multidimensional, and integrated cutting and packing problems.The cited reviews address different problem classes and methods, including exact and heuristic algorithms, relaxations, and mathematical models.Source: Books and surveys · pp. 2–3
• Over the last 20 years, publication totals were 1,410 in Google Scholar, 774 in Scopus, and 575 in Web of Science.Figure 1 presents publication trends in major databases.Source: Books and surveys · p. 3, Figure 1 · p. 3
• The field’s activity is also reflected in special issues, a comprehensive book, a visual application, and the ESICUP working group.The cited resources include special issues in INFOR, European Journal of Operational Research, and International Journal of Production Economics.Source: Books and surveys · p. 3

2 Problems and Definitions

• The considered problems use rectangular items and bins with orthogonal placements, so item edges remain parallel to bin edges.Items are assumed to have fixed orientation unless otherwise specified; 90-degree rotation is treated as a variant.Source: §2 · p. 4
• A bin has integer width W and height H, while each rectangular item i has integer width w_i and height h_i.Copies of identical items are treated as distinct unless otherwise specified.Source: §2 · p. 4
• A placement assigns each item i the bottom-left coordinates (x_i, y_i) relative to the bin’s bottom-left corner.The bin is represented in the Cartesian plane with its bottom-left corner at the origin.Source: §2 · p. 4
• Feasibility requires every item’s coordinates to keep it inside the bin and every pair of items to be separated along at least one axis.The coordinate bounds enforce containment, while the interval-disjointness condition on x or y prevents overlap.Source: §2 · pp. 4–5

2.1 Problems

• The section introduces the four problem definitions and uses a ten-item example to illustrate their variants.Figure 2(a) shows the items, with panels (b)–(d) showing example strip, bin-packing, and knapsack solutions.Source: §2.1 · p. 5, Figure 2 · p. 6

Two-Dimensional Strip Packing Problem

• The Two-Dimensional Strip Packing Problem minimizes the height used when packing all items into a single fixed-width strip of infinite height.Figure 2(b) depicts a minimum-height arrangement.Source: Two-Dimensional Strip Packing Problem · p. 5, Figure 2 · p. 6

Two-Dimensional Bin Packing Problem

• The Two-Dimensional Bin Packing Problem partitions all items into the fewest subsets that can each be packed into an identical finite bin.The Two-Dimensional Cutting Stock Problem generalizes it by specifying a demand d_i for each item type.Source: Two-Dimensional Bin Packing Problem · p. 5

Two-Dimensional Knapsack Problem

• The Two-Dimensional Knapsack Problem selects a feasible subset of items for one bin to maximize total profit.When each item’s profit equals its area, it is a special case called the Two-Dimensional Rectangular Packing Problem.Source: Two-Dimensional Knapsack Problem · p. 5, Figure 2 · p. 6

Two-Dimensional Orthogonal Packing Problem

• The Two-Dimensional Orthogonal Packing Problem asks whether a given item set has a feasible packing into one bin.Although it is a yes/no decision problem, practical applications generally also request the packing itself; it can occur as a subproblem in optimization problems.Source: Two-Dimensional Orthogonal Packing… · p. 5

2.2 Typologies

• Dyckhoff’s typology labels 2D-BPP, 2D-CSP, and 2D-KP as 2/V/I/M, 2/V/I/R, and 2/B/O/, respectively, but does not formally define 2D-SPP or 2D-OPP.The paper gives these correspondences to help readers identify the same problems under differing literature terminology.Source: §2.2 · p. 6
• The Lodi–Martello–Vigo three-field typology uses 2SP|O|F, 2BP|O|F, and 2KP|O|F for 2D-SPP, 2D-BPP, and 2D-KP, but leaves 2D-OPP unclassified.Its fields can also denote allowed rotation (R rather than O) and required guillotine cuts (G rather than F).Source: §2.2 · pp. 6–7
• The Wäscher–Haußner–Schumann typology calls 2D-SPP the Open Dimension Problem, 2D-BPP the Single Bin Size Bin Packing Problem, and 2D-CSP the Single Stock Size Cutting Stock Problem.It names 2D-KP as the Single Knapsack Problem or, with item copies, the Single Large Object Placement Problem; 2D-OPP can be interpreted as 2D-BPP’s recognition version.Source: §2.2 · p. 7

• A 2D-SPP strip of width W or a 2D-BPP bin of width W and height 1 encodes a 1D-BPP instance.In both cases, the 2D packing solution solves the original 1D-BPP instance.Source: §2.3 · p. 7
• For the 2D-KP, assigning each item profit 1 makes the minimum bin height yielding value n equal the optimal 1D-BPP solution value.Source: §2.3 · p. 7
• A 2D-OPP bin of width W and height k answers whether the 1D-BPP items fit into k bins.Source: §2.3 · p. 7
• The 2D-SPP, 2D-BPP, and 2D-KP are strongly NP-hard, while the 2D-OPP is strongly NP-complete.A polynomial-time algorithm for any of the four problems would imply one for the 1D-BPP.Source: §2.3 · p. 7

2.4 Variants

• Practical applications motivate variants of two-dimensional packing problems.Source: §2.4 · p. 7

Orthogonal Rotation

• Allowing 90-degree rotation can produce denser packings for uniform surfaces, but adds decisions and usually increases model size.Rotation may be forbidden for corrugated or decorated stock; models commonly use a rotate-or-not binary variable or rotated item copies with mutual exclusion.Source: Orthogonal Rotation · pp. 7–8

Guillotine Cuts

• Guillotine cuts are edge-to-edge cuts parallel to bin edges; staged variants alternate cut directions and may allow trimming.Two-stage packing is level packing; three-stage packing distinguishes restricted shelves whose height matches the tallest item from unrestricted shelves.Source: Guillotine Cuts · p. 8, Figure 3 · p. 8

Variable-Sized Bins

• Variable-sized bin packing uses different bin types with specific dimensions, costs, and availability, and seeks minimum total cost.Accounting for bin sizes in enumeration or pricing adds computational effort and typically makes these problems more challenging.Source: Variable-Sized Bins · p. 8

Loading and Unloading Constraints

• Loading and unloading constraints require items to be accessible in customer-visit order without moving other items.They can be modeled through item positions or handled with additional branch-and-bound fathoming criteria.Source: Loading and Unloading Constraints · p. 9

3.1 Sets of Points

• Normal patterns preserve optimality by shifting items down and left until their edges touch another item or the bin.With integer item and bin sizes, integer point coordinates suffice; smaller position sets reduce the search domain.Source: §3.1 · pp. 9–10
• Reduced raster points remove positions whose feasible right-side item combinations are covered by another position; meet-in-the-middle patterns are never larger than normal patterns.Meet-in-the-middle patterns left-align positions before a threshold and right-align those beyond it, and are usually smaller in practice.Source: §3.1 · p. 10

3.2 Preprocessing Techniques

• Optimality-preserving preprocessing fixes decisions or modifies input parameters; the latter methods apply across problems, while extending the former is not straightforward.The width-based procedures are presented in an advised execution order; bin problems can use heights instead, unlike strip problems.Source: §3.2 · p. 10

Packing a Subset of Items

• For the 2D-SPP, sufficiently narrow items can be packed beside items wider than half the strip, then fixed at the bottom when their total height fits the wide items’ heights.The method iterates on the reduced instance and updates its item sets when the required side packing is not found.Source: Packing a Subset of Items · p. 10

Shrinking the Size of the Bin

• A subset-sum calculation can shrink the bin or strip width to the largest achievable total item width not exceeding its original width.Source: Shrinking the Size of the Bin · pp. 10–11

Lifting the Size of the Items

• An item’s width can be increased when the maximum width sum of other items fitting beside it leaves unused bin width.Related methods also remove small items and increase the widths of large items.Source: Lifting the Size of the Items · p. 11

4 Relaxations

• Relaxations provide lower bounds for the 2D-SPP and 2D-BPP, upper bounds for the 2D-KP, and infeasibility proofs for the 2D-OPP.Some are also used as a basis for heuristic solutions.Source: §4 · p. 11

4.1 Continuous Relaxation

• The continuous relaxation splits items into unit squares and uses area-based bounds; its bounds can be computed in linear time.For the 2D-KP, the upper bound sorts items by value-to-area ratio and considers a fractional final item.Source: §4.1 · p. 11

4.2 Combinatorial Bounds

• For the 2D-BPP, combinatorial bounds partition items into sets that cannot share bins and compute an overall bound in O(n^2) time.These low-cost bounds can be effective in branch-and-bound.Source: §4.2 · pp. 11–12

4.3 Linear Relaxation and Column Generation

• Column generation iteratively adds improving item-combination patterns to a restricted set-covering LP with exponentially many possible columns.The relaxation underlies branch-and-price for the 2D-BPP and related variants, including guillotine-cut problems.Source: §4.3 · p. 12

4.4 Dual Feasible Functions

• Applying dual feasible functions to item widths and heights creates transformed instances whose relaxations remain valid for the original problem.Conservative scales are instance-dependent, whereas dual feasible functions have general validity.Source: §4.4 · p. 12
• Carlier, Clautiaux, and Moukrim provided the tightest tested polynomial-time lower bounds for the 2D-BPP in Serairi and Haouari 's comparison.Source: §4.4 · p. 13

4.5 Contiguous One-Dimensional Relaxations

• The 1D-CBPP cuts items into unit-height slices and requires each item’s slices to occupy consecutive one-dimensional bins, yielding a lower bound on 2D-SPP height.It remains strongly NP-hard; related work uses exact branch-and-bound, ILP, and a weaker bar relaxation.Source: §4.5 · p. 13

4.6 State Space Relaxations

• State space relaxation modifies a dynamic-programming recursion and can omit item-copy limits in the guillotine 2D-KP, enabling pseudo-polynomial solution of the relaxed problem.Non-negative integer item multipliers have been used to strengthen this relaxation.Source: §4.6 · p. 14

5 Heuristics

• Heuristics often initialize exact algorithms, while a comprehensive review is outside this survey’s scope.The cited comparison of 252 strip-packing heuristics illustrates the breadth of the area.Source: §5 · p. 14

5.1 Approximation and On-line Algorithms

• A polynomial-time 1.89-approximation for the rotated 2D-KP broke the previous 2-approximation barrier.For strip packing, a 5/4 + ε algorithm closed the gap to the stated inapproximability bound.Source: §5.1 · pp. 14–15
• Online 2D-SPP research established worst-case bounds, with further results for square-item strip packing and square-item bin packing.Pseudo-polynomial approximation for strip packing is also bounded: no ratio better than 5/4 unless P = NP.Source: §5.1 · pp. 14–15

5.2 Constructive Heuristics, Local Search, and Metaheuristics

• Bottom-left packs each item in the lowest left-justified position; best-fit chooses an item that better fits the lowest available area.Local search also explores alternatives by unpacking part of a solution or changing the item sequence.Source: §5.2 · p. 15

Single-solution Metaheuristics

• GRASP and tabu search were applied to the 2D-KP, 2D-SPP, and rectangular packing; tabu search also supported binary search for strip packing.Some metaheuristics extend to three-dimensional bin packing or routing with loading constraints.Source: Single-solution Metaheuristics · p. 15

Population-Based Metaheuristics

• For 2D-SPP, population-based methods include a hybrid tabu search–genetic algorithm and other genetic approaches.Genetic algorithms were also proposed for 2D-KP and 2D-BPP, including a biased random-key method.Source: Population-Based Metaheuristics · p. 15

5.3 Set covering based heuristics

• Set-covering heuristics use generated patterns for 2D-BPP, while column-generation heuristics address guillotine 2D-CSP and 2D-SPP variants.The surveyed examples include dynamic-programming-based methods for k-staged and non-staged cases and a 3-staged 2D-CSP heuristic.Source: §5.3 · p. 16

6.1 Polynomial Models

• Polynomial models link variables to items, while pseudo-polynomial models add variables for positions where items may be packed.Polynomial formulations cover general relative placements and several staged guillotine variants.Source: §6.2 · p. 16, §6.1 · p. 16

6.2 Pseudo-polynomial Models

• Beasley’s pseudo-polynomial 2D-KP model discretizes candidate bottom-left positions and prevents multiple items covering any unit square.Adaptations address rotations, stability and unloading order, and packing into the smallest square.Source: §6.2 · p. 16
• Other pseudo-polynomial formulations extend arc-flow, one-cut, and scheduling-based models to two-dimensional problems.The one-cut model represents feasible cuts; scheduling formulations use disjunctive constraints for relative item positions.Source: §6.2 · pp. 16–17

6.3 Exponential Models

• Exponential models commonly use feasible-pattern variables or Benders decomposition, yielding exponentially many columns or rows, respectively.Pattern formulations include set covering or partitioning for bin packing and cutting stock, and set packing for knapsack.Source: §6.3 · p. 17

Branch(-and-cut)-and-price

• Column generation solves the pattern model’s LP relaxation; embedding it in enumeration yields branch-and-price or branch-and-cut-and-price.Belov and Scheithauer proposed the first such branch-and-cut-and-price algorithm known to the survey for 2D-KP with 2-staged guillotine constraints.Source: Branch(-and-cut)-and-price · p. 17

Benders’ Decomposition

• Benders methods divide models into master and slave problems, with the slave either generating cuts or checking packing feasibility.For strip packing, a scheduling master sets x-coordinates and a slave checks y-coordinates; a minimal infeasible item set can generate a combinatorial cut.Source: Benders’ Decomposition · pp. 17–18

7 Exact Methods based on Implicit Enumeration

• Implicit enumeration methods search without explicitly using MILP models or requiring a solver.Branch-and-bound approaches include bottom-left-derived strategies for placing items at feasible positions.Source: §7 · p. 18, §7.1 · p. 18

7.1 Branch-and-Bound

• Staircase and niche placement enumerate item bottom-left positions at corner points determined by the partial packing.Staircase corners occur where the envelope changes slope; niche placement considers the lowest, then leftmost, horizontal segment and its left endpoint.Source: §7.1 · p. 18, Staircase Placement · p. 19, Niche Placement · p. 19

Niche Placement

• Niche branching considers each non-overlapping item placement at the niche and an additional branch that closes the niche.The scheme has at most n + 1 nodes per iteration.Source: Niche Placement · pp. 19–20

Other Enumeration Schemes

• Other enumeration schemes search item subsets, guillotine cuts, builds, or checkerboard patterns, often using bounds or relaxations.Four-staged guillotine knapsack methods also use label setting with reduction, filtering, and state-space relaxation.Source: Other Enumeration Schemes · p. 20

7.2 Graph-Based Approaches

• Graph-based approaches represent cutting patterns as paths or packing relationships through interval graphs and related graph structures.Interval graphs encode overlap of item projections along horizontal and vertical dimensions and support feasibility detection.Source: §7.2 · pp. 20–21

7.3 Constraint Programming

• Constraint programming addresses packing through relative-position constraints, propagation, and LP-based pruning.Related approaches reduce feasibility to SAT or test whether a contiguous one-dimensional relaxation yields a feasible two-dimensional packing.Source: §7.3 · p. 21

8 Open Problems

• 322 of 500 instances in the 10 classes benchmark are solved to proven optimality; some 20-item 2D-SPP instances and 40-item guillotine cases remain open.Recent sophisticated algorithms still cannot prove optimality for some specific 20-item strip-packing instances.Source: §8 · p. 21
• With rotation, only 176 of the 500 benchmark instances are solved to optimality, and 56 open instances contain just 20 items.Source: §8 · p. 22
• The pallet-loading problem retains a few dozen unsolved instances; more than 200 rectangle-packing instances remain unsolved, including 50 with 15 items.Source: §8 · p. 22
• Many 10-class 2D-BPP instances with n ≥60, and some with n = 40, remain unsolved despite a one-bin gap between best bounds.Source: §8 · p. 22
• For variable-sized 2D-BPP, 164 of 500 instances were solved, leaving 29 open with 20 items and 62 with 40 items.Source: §8 · p. 22
• A 32-item 2D-KP instance remains open, as do guillotine 2D-KP instances with 25 or 50 items.Source: §8 · p. 22
• In 2D-OPP, 18 of 1,080 instances with 20 items remain unsolved, while only 39 of 91 instances with about 70 items have been solved to optimality.For 2D-OPP with unloading constraints, only 2,179 of 3,282 instances have been solved to proven optimality.Source: §8 · p. 22

• The review covers over 180 papers, and about half of its references appeared in the last decade, while just 20% predate 2000.It also provides an extensive list of instances whose optimal solution remains unknown.Source: §9 · p. 23
• Table 1 summarizes publications from the last 20 years by problem, variant, and exact-method technique.Its technique columns include MILP, branch-and-bound, branch-and-price, Benders’ decomposition, graph-based methods, constraint programming, and relaxations.Source: §9 · p. 23, Table 1 · p. 24
• 20 papers studied 2D-SPP, 17 studied 2D-BPP and/or 2D-CSP, 14 studied 2D-KP, and 19 studied 2D-OPP.Guillotine cases were the most studied variant; MILP and branch-and-bound were the most popular methods, with 14 references each.Source: §9 · p. 23
• Constraint programming has recently led to consistent computational improvements on 2D problems, and the authors see potential for further gains.They propose further research on it as a stand-alone algorithm or as a subproblem in decomposition methods.Source: §9 · p. 23
• Benders’ decompositions are relatively recent in this field, yet represent the state of the art for some classical problems and have solved several open instances to proven optimality.The authors suggest adapting them to additional variants by placing new features in either the master or slave problem.Source: §9 · p. 23
• Research is increasingly addressing 2D problems with additional constraints, including loading and unloading, stability, and fragility.Source: §9 · p. 23
• Many reviewed techniques can extend to three or more dimensions, although not always straightforwardly; research there remains limited despite many applications.The authors identify 3D problems as a direction for future work, starting from 2D approaches.Source: §9 · p. 23