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     

4-Block heuristic for the rectangle packing problem

In this paper the rectangle packing problem (RPP) is considered. The RPP consists in finding a packing pattern of small rectangles within a larger rectangle such that the area utilization is maximized. We develop new heuristics for the RPP which are based on the G4-heuristic for the pallet loading problem. In addition to the general RPP we take also into account further restrictions which are of practical interest.     

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.     

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

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

Construction heuristics for two-dimensional irregular shape bin packing with guillotine constraints

The paper examines a new problem in the irregular packing literature that has many applications in industry: two-dimensional irregular (convex) bin packing with guillotine constraints. Due to the cutting process of certain materials, cuts are restricted to extend from one edge of the stock-sheet to another, called guillotine cutting. This constraint is common place in glass cutting and is an important constraint in two-dimensional cutting and packing problems. In the literature, various exact and approximate algorithms exist for finding the two dimensional cutting patterns that satisfy the guillotine cutting constraint. However, to the best of our knowledge, all of the algorithms are designed for solving rectangular cutting where cuts are orthogonal with the edges of the stock-sheet. In order to satisfy the guillotine cutting constraint using these approaches, when the pieces are non-rectangular, practitioners implement a two stage approach. First, pieces are enclosed within rectangle shapes and then the rectangles are packed. Clearly, imposing this condition is likely to lead to additional waste. This paper aims to generate guillotine-cutting layouts of irregular shapes using a number of strategies. The investigation compares three two-stage approaches: one approximates pieces by rectangles, the other two approximate pairs of pieces by rectangles using a cluster heuristic or phi-functions for optimal clustering. All three approaches use a competitive algorithm for rectangle bin packing with guillotine constraints. Further, we design and implement a one-stage approach using an adaptive forest search algorithm. Experimental results show the one-stage strategy produces good solutions in less time over the two-stage approach.     

An effective recursive partitioning approach for the packing of identical rectangles in a rectangle

In this work, we deal with the problem of packing (orthogonally and without overlapping) identical rectangles in a rectangle. This problem appears in different logistics settings, such as the loading of boxes on pallets, the arrangements of pallets in trucks and the stowing of cargo in ships. We present a recursive partitioning approach combining improved versions of a recursive five-block heuristic and an L-approach for packing rectangles into larger rectangles and L-shaped pieces. The combined approach is able to rapidly find the optimal solutions of all instances of the pallet loading problem sets Cover I and II (more than 50?000 instances). It is also effective for solving the instances of problem set Cover III (almost 100?000 instances) and practical examples of a woodpulp stowage problem, if compared to other methods from the literature. Some theoretical results are also discussed and, based on them, efficient computer implementations are introduced. The computer implementation and the data sets are available for benchmarking purposes.     

A block-based layer building approach for the 2D guillotine strip packing problem

We examine the 2D strip packing problems with guillotine-cut constraint, where the objective is to pack all rectangles into a strip with fixed width and minimize the total height of the strip. We combine three most successful ideas for the orthogonal rectangular packing problems into a single coherent algorithm: (1) packing a block of rectangles instead of a single rectangle in each step; (2) dividing the strip into layers and pack layer by layer; and (3) unrolling and repacking the top portion of the solutions where usually wasted space occurs. Computational experiments on benchmark test sets suggest that our approach rivals existing approaches.     

A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem

In this paper we address a two-dimensional (2D) orthogonal packing problem, where a fixed set of small rectangles has to be placed on a larger stock rectangle in such a way that the amount of trim loss is minimized. The algorithm we propose hybridizes a placement procedure with a genetic algorithm based on random keys. The approach is tested on a set of instances taken from the literature and compared with other approaches. The computation results validate the quality of the solutions and the effectiveness of the proposed algorithm.     

Finding squares and rectangles in sets of points

A number of problems concerning sets of points in the plane are studied, e.g. establishing whether it contains a subset of size 4, which are the vertices of a square or rectangle. Both the problems of finding axis-parallel squares and rectangles, and arbitrarily oriented squares and rectangles are studied. Efficient algorithms are obtained for all of them. Furthermore, we investigate the generalizations tod-dimensional space, where the problem is to find hyperrectangles and hypercubes. Also, upper and lower bounds are given for combinatorial problems on the maxium number of subsets of size 4, of which the points are the vertices of a square or rectangle. Then we state an equivalence between the problem of finding rectangles, and the problem of findingK _{2, 2} subgraphs in bipartite graphs. Thus we immediately have an efficient algorithm for this graph problem.This work was partially supported by the ESPRIT Basic Research Action No. 3075 (project ALCOM). Work of the second author was also supported by the Dutch Organisation for Scientific Research (N.W.O.).     

Dynamic multi-dimensional bin packing

A natural generalization of the classical online bin packing problem is the dynamic bin packing problem introduced by Coffman et al. (1983) [7]. In this formulation, items arrive and depart and the objective is to minimize the maximal number of bins ever used over all times. We study the oriented multi-dimensional dynamic bin packing problem for two dimensions, three dimensions and multiple dimensions. Specifically, we consider dynamic packing of squares and rectangles into unit squares and dynamic packing of three-dimensional cubes and boxes into unit cubes. We also study dynamic d-dimensional hypercube and hyperbox packing. For dynamic d-dimensional box packing we define and analyze the algorithm NFDH for the offline problem and present a dynamic version. This algorithm was studied before for rectangle packing and for square packing and was generalized only for multi-dimensional cubes. We present upper and lower bounds for each of these cases.     

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.     

An effective quasi-human based heuristic for solving the rectangle packing problem

In this paper, we introduce an effective deterministic heuristic, Less Flexibility First, for solving the classical NP-complete rectangle packing problem. Many effective heuristics implemented for this problem are CPU-intensive and non-deterministic in nature. Others, including the polynomial approximation methodology [J. Assoc. Comput. Mach. 32 (1) (1985) 130] are too laborious for practical problem sizes. The technique we propose is inspired and developed by enhancing some rule-of-thumb guidelines resulting from the generation-long work experience of human professionals in ancient days. Although the Less Flexibility First heuristic is a deterministic algorithm, the results are very encouraging. This algorithm can consistently produce packing densities of around 99% on most randomly generated large examples. As compared with the recent results of a well known simulated annealing based Rectangle Packing (RP) algorithm [IEEE Trans. Computer-aided Design Integrated Circuits Systems 17 (1) (1998) 60], the results are much better both in less dead space² (4% vs 6.7%) and much less CPU time (9.57 vs 331.78 seconds). Experimenting our heuristics on a public rectangle packing data set covering instances of 16–97 rectangles, the average unpack ratio is quite satisfactory (0.92% for bounding boxes limited to be optimum and 2.68% for the completed packing), while most cases spend only a few minutes in CPU time.     

The Three-Dimensional Pallet Chart: An Analysis of the Factors Affecting the Set of Feasible Layouts for a Class of Two-Dimensional Packing Problems

The two-dimensional orthogonal packing problem of packing identical rectangles into a large containing rectangle is important in pallet loading and has recently received much attention in O.R. publications. In this paper, we examine the conditions under which the set of feasible layouts remains unchanged and show that these conditions can be represented by a series of planes in three-dimensional space. We call this representation the three-dimensional pallet chart because it is an extension of the two-dimensional pallet charts presently used in many practical situations. The strength of this result is demonstrated by three examples of its use. Accurate two-dimensional charts are produced from the three-dimensional version with a minimum of calculation, and a complete sensitivity analysis to changes in box and pallet dimensions can be carried out visually by viewing the chart at different angles. Finally, the result is used to generate a new procedure for determining the maximum number of rectangles which can be fitted. This method is shown to be accurate for over 90% of observations in a random sample of 5000—an improvement of 20% over previous methods.     

Counting dissections into integral squares

A squared rectangle is a rectangle dissected into squares. Similarly a rectangled rectangle is a rectangle dissected into rectangles. The classic paper ‘The dissection of rectangles into squares’ of Brooks, Smith, Stone and Tutte described a beautiful connection between squared rectangles and harmonic functions. In this paper we count dissections of a rectangle into a set of integral squares or a set of integral rectangles. Here, some squares and rectangles may have the same size. We introduce a method involving a recurrence relation of large sized matrices to enumerate squared and rectangled rectangles of a given sized rectangle and propose the asymptotic behavior of their growth rates.     

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.     

A new exact method for the two-dimensional orthogonal packing problem

The two-dimensional orthogonal packing problem (2OPP) consists in determining if a set of rectangles (items) can be packed into one rectangle of fixed size (bin). In this paper we propose two exact algorithms for solving this problem. The first algorithm is an improvement on a classical branch&bound method, whereas the second algorithm is based on a new relaxation of the problem. We also describe reduction procedures and lower bounds which can be used within enumerative methods. We report computational experiments for randomly generated benchmarks which demonstrate the efficiency of both methods: the second method is competitive compared to the best previous methods. It can be seen that our new relaxation allows an efficient detection of non-feasible instances.     

A 5/4 algorithm for two-dimensional packing

This paper proposes a new algorithm for a two-dimensional packing problem first studied by Baker, Coffman, and Rivest (SIAM J. Comput. 9, No. 4(1980), 846–855). In their model, a finite list of rectangles is to be packed into a rectangular bin of finite width but infinite height. The model has applications to certain scheduling and stock-cutting problems. Since the problem of finding an optimal packing is NP-hard, previous work has been directed at finding polynomial approximation algorithms for the problem, i.e., algorithms which come within a constant times the height used by an optimal packing. For the algorithm proposed in this paper, the ratio of the height obtained by the algorithm and the height used by an optimal packing is asymptotically bounded by 5/4. This bound is an improvement over the bound of 4/3 achieved by the best previous algorithm.     

A reduction approach for solving the rectangle packing area minimization problem

In the rectangle packing area minimization problem (RPAMP) we are given a set of rectangles with known dimensions. We have to determine an arrangement of all rectangles, without overlapping, inside an enveloping rectangle of minimum area. The paper presents a generic approach for solving the RPAMP that is based on two algorithms, one for the 2D Knapsack Problem (KP), and the other for the 2D Strip Packing Problem (SPP). In this way, solving an instance of the RPAMP is reduced to solving multiple SPP and KP instances. A fast constructive heuristic is used as SPP algorithm while the KP algorithm is instantiated by a tree search method and a genetic algorithm alternatively. All these SPP and KP methods have been published previously. Finally, the best variants of the resulting RPAMP heuristics are combined within one procedure. The guillotine cutting condition is always observed as an additional constraint. The approach was tested on 15 well-known RPAMP instances (above all MCNC and GSRC instances) and new best solutions were obtained for 10 instances. The computational effort remains acceptable. Moreover, 24 new benchmark instances are introduced and promising results are reported.     

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.