Two-dimensional packing problems: A survey

We consider problems requiring to allocate a set of rectangular items to larger rectangular standardized units by minimizing the waste. In two-dimensional bin packing problems these units are finite rectangles, and the objective is to pack all the items into the minimum number of units, while in two-dimensional strip packing problems there is a single standardized unit of given width, and the objective is to pack all the items within the minimum height. We discuss mathematical models, and survey lower bounds, classical approximation algorithms, recent heuristic and metaheuristic methods and exact enumerative approaches. The relevant special cases where the items have to be packed into rows forming levels are also discussed in detail.     

Online strip packing with modifiable boxes

In the strip packing problem the goal is to pack a set of rectangles into a vertical strip so as to minimize the total height of the strip needed. We consider a modified version of the strip packing problem. In this version it is allowed to change the form of the rectangles by lengthening them, keeping the area fixed. We introduce online algorithms to solve this modified problem. Moreover a lower bound is presented, as well.     

A heuristic algorithm for the strip packing problem

The two-dimensional strip packing problem is to pack a given set of rectangles into a strip with a given width and infinite height so as to minimize the required height of the packing. From the computational point of view, the strip packing problem is an NP-hard problem. With the B*-tree representation, this paper first presents a heuristic packing strategy which evaluates the positions used by the rectangles. Then an effective local search method is introduced to improve the results and a heuristic algorithm (HA) is further developed to find a desirable solution. Computational results on randomly generated instances and popular test instances show that the proposed method is efficient for the strip packing problem.     

The two-dimensional cutting stock problem revisited

In the strip packing problem (a standard version of the two-dimensional cutting stock problem), the goal is to pack a given set of rectangles into a vertical strip of unit width so as to minimize the total height of the strip needed. The k-stage Guillotine packings form a particularly simple and attractive family of feasible solutions for strip packing. We present a complete analysis of the quality of k-stage Guillotine strip packings versus globally optimal packings: k=2 stages cannot guarantee any bounded asymptotic performance ratio. k=3 stages lead to asymptotic performance ratios arbitrarily close to 1.69103; this bound is tight. Finally, k=4 stages yield asymptotic performance ratios arbitrarily close to 1.Steve Seiden died in a tragic accident on June 11, 2002. This paper resulted from a number of email discussions between the authors in spring 2002.     

Exact algorithms for the two-dimensional strip packing problem with and without rotations

We propose exact algorithms for the two-dimensional strip packing problem (2SP) with and without 90° rotations. We first focus on the perfect packing problem (PP), which is a special case of 2SP, wherein all given rectangles are required to be packed without wasted space, and design branch-and-bound algorithms introducing several branching rules and bounding operations. A combination of these rules yields an algorithm that is especially efficient for feasible instances of PP. We then propose several methods of applying the PP algorithms to 2SP. Our algorithms succeed in efficiently solving benchmark instances of PP with up to 500 rectangles and those of 2SP with up to 200 rectangles. They are often faster than existing exact algorithms specially tailored for problems without rotations.     

New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems

We consider two types of orthogonal, oriented, rectangular, two-dimensional packing problems. The first is the strip packing problem, for which four new and improved level-packing algorithms are presented. Two of these algorithms guarantee a packing that may be disentangled by guillotine cuts. These are combined with a two-stage heuristic designed to find a solution to the variable-sized bin packing problem, where the aim is to pack all items into bins so as to minimise the packing area. This heuristic packs the levels of a solution to the strip packing problem into large bins and then attempts to repack the items in those bins into smaller bins in order to reduce wasted space. The results of the algorithms are compared to those of seven level-packing heuristics from the literature by means of a large number of strip-packing benchmark instances. It is found that the new algorithms are an improvement over known level-packing heuristics for the strip packing problem. The advancements made by the new and improved algorithms are limited in terms of utilised space when applied to the variable-sized bin packing problem. However, they do provide results faster than many existing algorithms.     

Probabilistic analysis of a new class of strip packing algorithms

A new class of algorithms for online packing of rectangles into a strip is proposed and studied. It is proved that the expectation of the unfilled area for this class of algorithms is O(N ^2/3) in the standard (for this type of problems) probabilistic model for N random rectangles.     

Local search algorithms for the rectangle packing problem with general spatial costs

We propose local search algorithms for the rectangle packing problem to minimize a general spatial cost associated with the locations of rectangles. The problem is to pack given rectangles without overlap in the plane so that the maximum cost of the rectangles is minimized. Each rectangle has a set of modes, where each mode specifies the width and height of the rectangle and its spatial cost function. The spatial costs are general piecewise linear functions which can be non-convex and discontinuous. Various types of packing problems and scheduling problems can be formulated in this form. To represent a solution of this problem, a pair of permutations of n rectangles is used to determine their horizontal and vertical partial orders, respectively. We show that, under the constraint specified by such a pair of permutations, optimal locations of the rectangles can be efficiently determined by using dynamic programming. The search for finding good pairs of permutations is conducted by local search and metaheuristic algorithms. We report computational results on various implementations using different neighborhoods, and compare their performance. We also compare our algorithms with other existing heuristic algorithms for the rectangle packing problem and scheduling problem. These computational results exhibit good prospects of the proposed algorithms. Key words.rectangle packing – sequence pair – general spatial cost – dynamic programming – metaheuristicsMathematics Subject Classification (1991):20E28, 20G40, 20C20     

Improved local search algorithms for the rectangle packing problem with general spatial costs

The rectangle packing problem with general spatial costs is to pack given rectangles without overlap in the plane so that the maximum cost of the rectangles is minimized. This problem is very general, and various types of packing problems and scheduling problems can be formulated in this form. For this problem, we have previously presented local search algorithms using a pair of permutations of rectangles to represent a solution. In this paper, we propose speed-up techniques to evaluate solutions in various neighborhoods. Computational results for the rectangle packing problem and a real-world scheduling problem exhibit good prospects of the proposed techniques.     

A goal-driven approach to the 2D bin packing and variable-sized bin packing problems

In this paper, we examine the two-dimensional variable-sized bin packing problem (2DVSBPP), where the task is to pack all given rectangles into bins of various sizes such that the total area of the used bins is minimized. We partition the search space of the 2DVSBPP into sets and impose an order on the sets, and then use a goal-driven approach to take advantage of the special structure of this partitioned solution space. Since the 2DVSBPP is a generalization of the two-dimensional bin packing problem (2DBPP), our approach can be adapted to the 2DBPP with minimal changes. Computational experiments on the standard benchmark data for both the 2DVSBPP and 2DBPP shows that our approach is more effective than existing approaches in literature.     

A novel non-linear approach to minimal area rectangular packing

This paper discusses the minimal area rectangular packing problem which is to pack a given set of rectangles into a rectangular container of minimal area such that no two rectangles overlap. Current approaches for this problem rely on metaheuristics like simulated annealing, on constraint programming or on non-linear models. Difficulties arise from the non-convexity and the combinatorial complexity. We investigate different mathematical programming approaches for this and introduce a novel approach based on non-linear optimization and the “tunneling effect” achieved by a relaxation of the non-overlapping constraints. We compare our optimization algorithm to a simulated annealing and a constraint programming approach and show that our approach is competitive. Additionally, since it is easy to extend, it is also applicable to a variety of related problems.     

货物尺寸相同的2维装箱问题的等价类(英文)

在生产与储运领域,把小长方体货物（盒子）装入大长方体箱子是一项重要的工作.本文涉及的问题是:把相同尺寸（a×b×c）的盒子装到一个箱子X×Y×Z中,使所装入箱子的盒子数量为最大.由于某些条件的限止,有时要求货物只能按一个重力方向进行装箱,从而使装箱问题变为把尺寸相同的2维盒子（a×b）填装到一个2维箱子X×Y中.本文讨论当盒子尺寸（a×b包括 b×a）给定,箱子尺寸充分大时,在本文所给的等价意义下,共有多少种互不等价的箱子X×Y.     

Resource augmentation in two-dimensional packing with orthogonal rotations

We consider the problem of packing two-dimensional rectangles into the minimum number of unit squares, when 90^° rotations are allowed. Our main contribution is a polynomial-time algorithm for packing rectangles into at most OPT bins whose sides have length (1+ε), for any positive ε. Additionally, we show near-optimal packing results for a number of related packing problems.     

New upper bounds for online strip packing

In this paper, we consider the online strip packing problem, in which a list of online rectangles has to be packed without overlap or rotation into one or more strips of width 1 and infinite height so as to minimize the required height of the packing. By analyzing a two-phase shelf algorithm, we derive a new upper bound 6.4786 on the competitive ratio for online one strip packing. This result improves the best known upper bound of 6.6623. We also extend this algorithm to online multiple strips packing and present some numeric upper bounds on their competitive ratios which are better than the previous bounds.     

Optimal rectangle packing

We consider the NP-complete problem of finding an enclosing rectangle of minimum area that will contain a given a set of rectangles. We present two different constraint-satisfaction formulations of this problem. The first searches a space of absolute placements of rectangles in the enclosing rectangle, while the other searches a space of relative placements between pairs of rectangles. Both approaches dramatically outperform previous approaches to optimal rectangle packing. For problems where the rectangle dimensions have low precision, such as small integers, absolute placement is generally more efficient, whereas for rectangles with high-precision dimensions, relative placement will be more effective. In two sets of experiments, we find both the smallest rectangles and squares that can contain the set of squares of size 1×1, 2×2,…,N×N, for N up to 27. In addition, we solve an open problem dating to 1966, concerning packing the set of consecutive squares up to 24×24 in a square of size 70×70. Finally, we find the smallest enclosing rectangles that can contain a set of unoriented rectangles of size 1×2, 2×3, 3×4,…,N×(N+1), for N up to 25.     

Scheduling inspired models for two-dimensional packing problems

We propose two exact algorithms for two-dimensional orthogonal packing problems whose main components are simple mixed-integer linear programming models. Based on the different forms of time representation in scheduling formulations, we extend the concept of multiple time grids into a second dimension and propose a hybrid discrete/continuous-space formulation. By relying on events to continuously locate the rectangles along the strip height, we aim to reduce the size of the resulting mathematical problem when compared to a pure discrete-space model, with hopes of achieving a better computational performance. Through the solution of a set of 29 test instances from the literature, we show that this was mostly accomplished, primarily because the associated search strategy can quickly find good feasible solutions prior to the optimum, which may be very important in real industrial environments. We also provide a comprehensive comparison to seven other conceptually different approaches that have solved the same strip packing problems.     

A hybrid placement strategy for the three-dimensional strip packing problem

This paper presents a hybrid placement strategy for the three-dimensional strip packing problem which involves packing a set of cuboids (‘boxes’) into a three-dimensional bin (parallelepiped) of fixed width and height but unconstrained length (the ‘container’). The goal is to pack all of the boxes into the container, minimising its resulting length. This problem has potential industry application in stock cutting (wood, polystyrene, etc. – minimising wastage) and also cargo loading, as well as other applications in areas such as multi-dimensional resource scheduling. In addition to the proposed strategy a number of test results on available literature benchmark problems are presented and analysed. The results of empirical testing of the algorithm show that it out-performs other methods from the literature, consistently in terms of speed and solution quality-producing 28 best known results from 35 test cases.     

A branch-and-price algorithm for the two-dimensional level strip packing problem

The two-dimensional level strip packing problem (2LSPP) consists in packing rectangular items of given size into a strip of given width divided into levels. Items packed into the same level cannot be put on top of one another and their overall width cannot exceed the width of the strip. The objective is to accommodate all the items while minimizing the overall height of the strip. The problem is -hard and arises from applications in logistics and transportation. We present a set covering formulation of the 2LSPP suitable for a column generation approach, where each column corresponds to a feasible combination of items inserted into the same level. For the exact optimization of the 2LSPP we present a branch-and-price algorithm, in which the pricing problem is a penalized knapsack problem. Computational results are reported for benchmark instances with some hundreds items.     

Packing into the smallest square: Worst-case analysis of lower bounds

We address the problem of packing a given set of rectangles into the minimum size square. We consider three versions of the problem, arising when the rectangles (i) are squares; (ii) have a fixed orientation; (iii) can be rotated by 90. For each case we study lower bounds, and analyze their worst-case performance ratio. In addition, we evaluate through computational experiments their average performance on instances from the literature.     

Symmetry-breaking constraints for packing identical rectangles within polyhedra

Two problems related to packing identical rectangles within a polyhedron are tackled in the present work. Rectangles are allowed to differ only by horizontal or vertical translations and possibly 90° rotations. The first considered problem consists in packing as many identical rectangles as possible within a given polyhedron, while the second problem consists in finding the smallest polyhedron of a given type that accommodates a fixed number of identical rectangles. Both problems are modeled as mixed integer programming problems. Symmetry-breaking constraints that facilitate the solution of the MIP models are introduced. Numerical results are presented.