PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 93 (107) (2013), 95–107 DOI:

A NEW NONLINEAR MODEL FOR THE TWO-DIMENSIONAL RECTANGLE PACKING PROBLEM

Aleksandar Savić, Jozef Kratica, and Vladimir Filipović

Communicated by Žarko Mijajlović

Abstract. This paper deals with the rectangle packing problem, of filling a big rectangle with smaller rectangles, while the rectangle dimensions are real numbers. A new nonlinear programming formulation is presented and the validity of the formulation is proved. In addition, two cases of the problem are presented, with and without rotation of smaller rectangles by 90^{∘}. The mixed integer piecewise linear formulation derived from the model is given, but with a simple form of the objective function.

1. Introduction

The packing problem and a closely related cutting problem, encompass a wide range of industry originated problems. Optimal solution or even an approximately good one contributes significantly to savings in both money and new materials.

Most of the previous contributors in the literature deal with the case where the items to be packed have a fixed orientation with respect to the stock unit(s), i.e., it is not allowed to rotate them. The case explained here can be applied in a number of practical contexts, such as cutting of corrugated or decorated material (wood, glass, clothing stripes), or the newspapers’ paging.

For variants allowing rotations (usually by 90^{∘}) and/or constraints on the item’s placement (such as the “guillotine cuts”), the reader is referred to [2, 12], where a three-field classification of the area is also introduced. General surveys on cutting and packing problems can be found in [14–16]. Results of the probabilistic analysis of packing algorithms can be found in [10] and [11].

2010 Mathematics Subject Classification: 90C30; 90C11.

Key words and phrases: nonlinear programming, piecewise linear relaxation, rectangle packing problem.

This research was partially supported by Serbian Ministry of Education and Science under the grant 174010.

Let us introduce the problems in a more formal way. We are given a set of n rectangular items each defined by a width, w_{j}, and a height, h_{j}:

(i) in the Two-Dimensional Bin Packing Problem (2BP), we are further given an unlimited number of identical rectangular bins of width W and height H, and the objective is to allocate all the items into the minimum number of bins;

(ii) in the Two-Dimensional Strip Packing Problem (2SP), we are further given a bin of width W and infinite height (hereafter called strip), and the objective is to allocate all the items to the strip by minimizing the height to which the strip is used.

Both problems are strongly NP-hard, as can easily be seen by transforming a strongly NP-hard (one-dimensional) Bin Packing Problem (1BP), in which n items, each having an associated size h_{j}, have to be partitioned into the minimum number of subsets so that the sum of the sizes in each subset does not exceed a given capacity H [28].

A special case of the above mentioned problems is packing of a set of rectangles into a bounding rectangle.

The rectangle packing problem belongs to a subset of classical cutting and packing problems and has been shown to be NP-complete [22, 26].

The problem of determining whether a set of rectangles can be packed into a bounding rectangle can relate to some practical applications in floor planning, placement problems, or job scheduling problems [13]. One of the most frequent applications of the problem is cutting of smaller pieces of material of rectangular shape from a large rectangle. Another direct application of the problem is organization of warehouse floor space in the most effective way.

Cutting and packing problems [2,4,8,12,20,35] have a wide range of applicability that has been studied for more than 40 years. The two-dimensional cutting stock problems with rectangle shapes are closely related to our problem. In [9], the basic formulation issues and linear programming procedures for solving packing and cutting problem are being discussed, as well as sequential heuristic and hybrid solving procedures.

A NEW NON-LINEAR MODEL FOR THE TWO-DIMENSIONAL PACKING PROBLEM 97

Based on the usage of guillotine or non-guillotine cuts, the problems can be roughly divided into two styles of cutting. Constrained cutting refers to the employment of orthogonal and guillotine cuts under certain copy constraints of the rectangles [17]. Optimal algorithms for orthogonal two-dimension cutting were proposed in [4, 20]. However, they might not be practical for large problems. In the orthogonal packing problem, a set of rectangles are to be packed into a rectangle board with rectangle edges parallel to the x− and y−axes of the board, respectively, and the height is to be minimized. In order to reduce the number of possible orthogonal packing patterns, the so-called BL-condition was introduced, and hybrid algorithm using genetic and deterministic methods was proposed [5,19,24]. In [32], a new and improved algorithm with level heuristics was suggested. In [21,30,35], a various range of metaheuristics were suggested for solving the two-dimensional rectangle packing problem. Very effective quasi-human heuristic was presented in [38]. Some of the newest heuristic approaches, using skyline heuristic [37] and intelligent search [27], represent very effective methods for practical solving of the rectangle and strip packing problems.

There are heuristic approaches which are improving almost on yearly basis. The exact approaches and mathematical modelling are also important part of the research area. New mathematical formulations allow application of many exact methods, which guarantee optimality, though on smaller instances. This optimal solution again can verify usage of wide range of heuristics and metaheuristics. Furthermore, theoretical research in optimization theory can lead to potentially new exact and heuristic approaches to packing problem. One case of this kind is paper [34] relating to linear disjunctive programming, which is specifically applied to the two dimensional packing problem.

In the last decade, there were several papers addressing the issue of modelling and exactly solving the two-dimensional packing problems. The models for level packing problem are represented in paper [29]. The difference from our problem is that paper [29] considers packing strip of fixed width and infinite length separated in levels all of which are packed so that when the width of one level is covered, other rectangles are packed on the next level. The binary tree representation of the rectangle packing problem is given in [36]. But, the tree is of enormous size and solving of the problem is reduced to local search heuristics. In [18] one considers packing of rectangles in a way that one rectangle dominates in size all the others. The given formulation is linear, but can be treated as a variant of a knapsack problem and the proposed method of solving is being reduced to a linear approximation.

Another approach to this problem [25] dealt with finding a minimal bounding box for given set of rectangles. There is an interesting review of previous attempts for solving the same problem. Paper [7] introduces a model where both binary and real variables are presented. Variables representing x coordinates are binary, while y coordinates are real. The model still works only with integer dimensions of rectangles and uses multispatial layers, of which every one contains one specific rectangle. This hybrid discrete/continous-space model can find optimal solutions just in some cases. Global optimality can only be ensured when the specific conditions are met, and they are resource consuming for even a small number of rectangles.

Finally, there are exact methods, which use a branch and bound techniques and are mostly based on procedures explained in [31]. They propose solving to a relaxed two-dimensional strip packing problem by solving one dimensional binpacking problem with side constraints using a modified enumerative algorithm. Lower bound, used in branch and bound method, is calculated by relaxation. Upper bounds are obtained by using some known heuristics, as well as some new ones. The research that addresses the improvement in obtaining the lower bounds with proposed branch and bound method and heuristics using them can be found in [3,6].

This idea was improved by calculating new lower bounds and dominance conditions in [1]. Using the GRASP algorithm, the authors were able to quickly produce lower bound at the root node, obtained either a feasible solution or, in the worst case, an upper bound.

Using general idea of integer grid of the packing space, the paper [23] considers a branch and bound method for perfect packing problems, generalized for two-dimensional strip packing problem. The solution was calculated with two algorithms, the first one obtained better lower bounds and the second used staircase placement of rectangles for branching operations. Both algorithms start from the lower bound and keep the strip height increasing until a feasible solution is found. The improvements in [1] and [23] are still working with integer dimensions and binary variables and do not address the issue of real dimension cases.

2. A nonlinear programming formulation

This paper explains the mathematical model of packing big rectangle with smaller rectangles, where dimensions of the rectangles are real numbers. Moreover, a variant with 90 degrees rotation is taken into consideration. Problem complexity and limited resources made us introduce a mixed integer piecewise linear programming formulation at the end of the paper. Problems formulated in this way can be solved using CPLEX or some other solver.

The problem taken into consideration is two-dimensional packing of a big rectangle with a given number of small rectangles. It is a must that the sides of small rectangles are parallel to the sides of the big rectangle. Two cases are considered in the paper: in the first case, a 90 degree rotation for smaller rectangles is not allowed, and in the second case, the rotation is allowed. Smaller rectangles must be placed completely inside the big rectangle, and they should not overlap. Let the dimensions of the big rectangle be respectively A and B. There are n small rectangles. Let their dimensions be respectively a_{i} and b_{i}, i = 1, …, n, as shown in Fig. 1. It is allowed that small rectangles have the same dimensions.

A  B  a_{n} b_{n} ⋮ a_{2} b_{2} a_{1}  b_{1}

Figure 1. Dimensions of big rectangle and small rectangles

Let us consider the following problem closely related to the above problem mentioned. In xOy coordinate plain, the small rectangle is defined by its dimensions a_{i} and b_{i} and coordinates x_{i} and y_{i} of its middle point (intersection of diagonals). The problem is to find conditions, which must be satisfied by all points outside the rectangle. Using the well-known inequality, which is satisfied by all points outside the square with vertices in (1, 0), (0, 1), (−1, 0), (0, −1) (Fig. 2)

(2.1)  |x| + |y| ⩾ 1

the stated conditions could be found. In order to construct the model, let us determine an affine transformation of a whole plane xOy so that point (x_{i}, y_{i}) is mapped into (0, 0), and any two vertices of the rectangle are mapped to match coordinates of the respective vertices of the above-mentioned square. Without losing generality the vertices (x_{i} + \frac{1}{2}a_{i}, y_{i} + \frac{1}{2}b_{i}), (x_{i} + \frac{1}{2}a_{i}, y_{i} − \frac{1}{2}b_{i}) are mapped into (0, 1) and (1, 0) respectively. Now, with three pairs of points mapped, a system for finding coefficients of affine transformation can be created. Let the affine transformation is defined by

x′ = α_{1}x + β_{1}y + γ_{1}
y′ = α_{2}x + β_{2}y + γ_{2}

where x′ and y′ are the new coordinates and x and y are the old ones and α_{1}, α_{2}, β_{1}, β_{2}, γ_{1} and γ_{2} are the unknown coefficients. The affine transformation is shown in Fig. 2.

[figure: (0, −1); (1, 0); (−1, 0); (0, 1); (x_{i}, y_{i}); (x_{i}+a_{i}/2, y_{i}+b_{i}/2); (x_{i}+a_{i}/2, y_{i}−b_{i}/2)]

Figure 2. Affine transformation

Now the system of equations for finding coefficients of affine transformation is

0 = α_{1}x_{i} + β_{1}y_{i} + γ_{1}
0 = α_{2}x_{i} + β_{2}y_{i} + γ_{2}
0 = α_{1}(x_{i} + \frac{1}{2}a_{i}) + β_{1}(y_{i} + \frac{1}{2}b_{i}) + γ_{1}
1 = α_{2}(x_{i} + \frac{1}{2}a_{i}) + β_{2}(y_{i} + \frac{1}{2}b_{i}) + γ_{2}
1 = α_{1}(x_{i} + \frac{1}{2}a_{i}) + β_{1}(y_{i} − \frac{1}{2}b_{i}) + γ_{1}
0 = α_{2}(x_{i} + \frac{1}{2}a_{i}) + β_{2}(y_{i} − \frac{1}{2}b_{i}) + γ_{2}

After solving the system of linear equations the unknown coefficients are found and are given with

α_{1} = \frac{1}{a_{i}} , β_{1} = −\frac{1}{b_{i}} , γ_{1} = \frac{x_{i}}{a_{i}} + \frac{y_{i}}{b_{i}} ,

α_{2} = \frac{1}{a_{i}} , β_{2} = \frac{1}{b_{i}} , γ_{2} = \frac{x_{i}}{a_{i}} − \frac{y_{i}}{b_{i}} ,

Using this solution, condition (2.1) now becomes

(2.2)  |\frac{x − x_{i}}{a_{i}} − \frac{y − y_{i}}{b_{i}} | + |\frac{x − x_{i}}{a_{i}} + \frac{y − y_{i}}{b_{i}} | ⩾ 1

Finally, condition (2.2) must be satisfied by any point with coordinates (x, y) for it to be outside the rectangle with the middle point in (x_{i}, y_{i}) and sides lengths a_{i} and b_{i} respectively and parallel with coordinate axes. Let us prove this.

Theorem 2.1. Point with the coordinates (x, y) is outside the rectangle with the middle point in (x_{i}, y_{i}) and sides lengths a_{i} and b_{i} respectively and parallel with coordinate axes if and only if condition (2.2) is satisfied.

Proof. (⇒) Let the point (x, y) be outside the triangle. Then at least one of the inequalities |x − x_{i}| ⩾ \frac{1}{2}a_{i} or |y − y_{i}| ⩾ \frac{1}{2}b_{i} is true. Without loss of generality let the former holds. Then, from the triangle inequality, there is

|\frac{x − x_{i}}{a_{i}} − \frac{y − y_{i}}{b_{i}} | + |\frac{x − x_{i}}{a_{i}} + \frac{y − y_{i}}{b_{i}} |

⩾ |\frac{x − x_{i}}{a_{i}} − \frac{y − y_{i}}{b_{i}} + \frac{x − x_{i}}{a_{i}} + \frac{y − y_{i}}{b_{i}} | = 2 |\frac{x − x_{i}}{a_{i}} | ⩾ 1

which means that condition (2.2) is satisfied.

(⇐) Now, let us prove that if a point satisfies condition (2.2), then it is outside the rectangle. Let us assume the opposite. Let a point (x, y) be strictly inside the rectangle, satisfy condition (2.2). Then both inequalities |x − x_{i}| < \frac{1}{2}a_{i} and |y − y_{i}| < \frac{1}{2}b_{i} must be satisfied. Now, let us denote \frac{x−x_{i}}{a_{i}} = α and \frac{y−y}{b_{i}} = β. In this notation, let us find the maximum value of the function |α − β| + |α + β| under the conditions |α| < \frac{1}{2} and |β| < \frac{1}{2}. Without losing generality, let us assume |α| > |β|. Now

|α − β| + |α + β| = \begin{cases}2α, & α − β ⩾ 0, α + β ⩾ 0 \\ −2β, & α − β ⩾ 0, α + β ⩽ 0 \\ 2β, & α − β ⩽ 0, α + β ⩾ 0 \\ −2α, & α − β ⩽ 0, α + β ⩽ 0 \end{cases} ⩽ 2|α| < 1

However, this contradicts the presumption that the point (x, y) satisfies condition (2.2). So, the point satisfying condition (2.2) must be outside the rectangle.

Finally, let us show that two other vertices of the rectangle are mapped by affine transformation to two remaining vertices of the above-mentioned square. Actually,

x′ = \frac{1}{a_{i}} (x_{i} − \frac{1}{2}a_{i}) − \frac{1}{b_{i}} (y_{i} + \frac{1}{2}b_{i}) − \frac{x_{i}}{a_{i}} + \frac{y_{i}}{b_{i}} = −1
y′ = \frac{1}{a_{i}} (x_{i} − \frac{1}{2}a_{i}) + \frac{1}{b_{i}} (y_{i} + \frac{1}{2}b_{i}) − \frac{x_{i}}{a_{i}} − \frac{y_{i}}{b_{i}} = 0

and

x′ = \frac{1}{a_{i}} (x_{i} − \frac{1}{2}a_{i}) − \frac{1}{b_{i}} (y_{i} − \frac{1}{2}b_{i}) − \frac{x_{i}}{a_{i}} + \frac{y_{i}}{b_{i}} = 0

y′ = \frac{1}{a_{i}} (x_{i} − \frac{1}{2}a_{i}) + \frac{1}{b_{i}} (y_{i} − \frac{1}{2}b_{i}) − \frac{x_{i}}{a_{i}} − \frac{y_{i}}{b_{i}} = −1

And finally point (x, y) is outside the rectangle if and only if condition (2.2) is satisfied. □

Now we can conclude that two rectangles with middle points (x_{i}, y_{i}) and (x_{j}, y_{j}) will not overlap if and only if the middle point (x_{j}, y_{j}) is outside the rectangle with the middle point (x_{i}, y_{i}) and with sides of lengths (a_{i} + a_{j}) and (b_{i} + b_{j}), see Fig. 3. In other words, two rectangles will not overlap if and only if the following condition is satisfied

|\frac{x_{j} − x_{i}}{a_{i} + a_{j}} − \frac{y_{j} − y_{i}}{b_{i} + b_{j}} | + |\frac{x_{j} − x_{i}}{a_{i} + a_{j}} + \frac{y_{j} − y_{i}}{b_{i} + b_{j}} | ⩾ 1

[figure: (x_{i}, y_{i}); (x_{j}, y_{j})]

Figure 3. Overlapping of small rectangles

Now we can set vertices of the big rectangle at points (0, 0), (0, B), (A, 0), (A, B). We impose for every small rectangle the following condition: x coordinate must be in the interval [\frac{1}{2}a_{i}, A − \frac{1}{2}a_{i}], i = 1, 2, …, n, or \frac{1}{2}a_{i} ⩽ x_{i} ⩽ A − \frac{1}{2}a_{i}, i = 1, 2, …, n. To avoid overlapping of small rectangles (which will surely happen if the sum of areas of small rectangles is greater than the area of the big rectangle) the second coordinate will be bound only from below (Fig. 4): \frac{1}{2}b_{i} ⩽ y_{i}, i = 1, 2, …, n.

In other words, packing of the big rectangle is transformed in packing of a strip of width A aiming at placing as much as possible small rectangles in the strip’s initial part of length B. Every small rectangle must be placed completely within the big rectangle, which is at the beginning of the lent or to be completely left out. This can be achieved by imposing the following conditions on y coordinate of every small rectangle’s middle point: |y_{i} − B| ⩾ \frac{1}{2}b_{i}, i = 1, 2, …, n.

Figure 4. Overlapping the boundaries of big rectangle

Let us now form a mathematical model for packing the big rectangle with small ones without rotation:

(2.3)  max ∑_{i=1}^{n} \frac{max(0, B − y_{i})}{B − y_{i}}a_{i}b_{i}

subject to

|\frac{x_{j} − x_{i}}{a_{i} + a_{j}} − \frac{y_{j} − y_{i}}{b_{i} + b_{j}} | + |\frac{x_{j} − x_{i}}{a_{i} + a_{j}} + \frac{y_{j} − y_{i}}{b_{i} + b_{j}} | ⩾ 1, \begin{aligned}i & = 1, 2, …, n − 1, \\ j & = i + 1, …, n \end{aligned} (2.4)

|y_{i} − B| ⩾ \frac{1}{2}b_{i}, i = 1, 2, …, n (2.5)

\frac{1}{2}a_{i} ⩽ x_{i} ⩽ A − \frac{1}{2}a_{i}, i = 1, 2, …, n (2.6)

y_{i} ⩾ \frac{1}{2}b_{i}, i = 1, 2, …, n (2.7)

As it was explained earlier, conditions (2.4) do not allow overlapping of any two rectangles. Conditions (2.5) impose any small rectangle to be either within the big rectangle or within the remainder of the strip. Conditions (2.6) and (2.7) ensure that the rectangles are packed in the strip of width A and that none of the small rectangles overlap at the beginning of the strip. Hence, the number of variables is in accordance with the problem and is equal to 2n. In addition, all variables are taking values from a set of real positive numbers. The total number of conditions is \binom{n}{2} + 3n and is rather large, but ensures that there is no overlapping of any of the small rectangles. In formula (2.3) one takes into consideration only those small rectangles that are totally placed within the big rectangle. Solutions to this problem, using formulation (2.3)–(2.7), can be found in [33].

Let us now consider the case where rotation of small rectangles by 90^{∘} is allowed. In order to do so, we shall include one more set of rectangles, which will have dimensions b_{i}, a_{i}, i = 1, 2, …, n respectively. For easier notation, we shall note a_{n+i} = b_{i}, b_{n+i} = a_{i}, i = 1, 2, …, n. In addition, we shall now introduce new variables x_{n+i}, y_{n+i} which will represent the middle points of these newly introduced rectangles. We must avoid the case where the small rectangle and the rotated counterpart will be packed together inside the big rectangle. Let the rectangle with the middle point (x_{i}, y_{i}) be packed. Then the rectangle with the middle point (x_{n+i}, y_{n+i}) can not be packed. To avoid this, the inequality y_{n+i} − \frac{1}{2}b_{n+i} ⩾ B − y_{i} must be satisfied, and vice versa, if a rectangle with the middle point (x_{n+i}, y_{n+i}) is packed, then a rectangle with a middle point (x_{i}, y_{i}) can not be packed. Therefore, the inequality y_{i} − \frac{1}{2}b_{i} ⩾ B − y_{n+i} must also be satisfied. Since we do not know which of these two small rectangles will be packed, at least one of the inequalities y_{i} + y_{n+i} ⩾ B + \frac{1}{2}b_{i}, y_{n+i} + y_{i} ⩾ B + \frac{1}{2}b_{n+i} must be satisfied (Fig. 5a and Fig. 5b) or consequently y_{i} + y_{n+i} ⩾ B + \frac{1}{2} max(b_{i}, b_{n+i}).

Figure 5. Inclusion of only one small rectangle out of two with same dimensions but with different rotation

So finally, the model for packing the big rectangle with small rectangles with allowed rotation is

max ∑_{i=1}^{2n} \frac{max(0, B − y_{i})}{B − y_{i}}a_{i}b_{i}

subject to

|\frac{x_{j} − x_{i}}{a_{i} + a_{j}} − \frac{y_{j} − y_{i}}{b_{i} + b_{j}} | + |\frac{x_{j} − x_{i}}{a_{i} + a_{j}} + \frac{y_{j} − y_{i}}{b_{i} + b_{j}} | ⩾ 1, \begin{aligned}i & = 1, 2, …, 2n − 1, \\ j & = i + 1, …, 2n, j ≠ n + i \end{aligned}

|y_{i} − B| ⩾ \frac{1}{2}b_{i}, i = 1, 2, …, 2n
\frac{1}{2}a_{i} ⩽ x_{i} ⩽ A − \frac{1}{2}a_{i}, i = 1, 2, …, 2n
y_{i} ⩾ \frac{1}{2}b_{i}, i = 1, 2, …, 2n
y_{i} + y_{n+i} ⩾ B + \frac{1}{2} max(b_{i}, b_{n+i}), i = 1, 2, …, 2n

As it can be seen, in this case the number of variables is doubled and is equal to 4n. The total number of conditions is \binom{2n}{2} + 8n.

The complexity of formula (2.3) in the proposed model does not allow application of global optimization or usage of commercial solvers like CPLEX etc., without difficulties. Therefore we suggest a mixed integer piecewise linear programming model. First, let us consider a problem without rotation. The variables x_{i} and y_{i} have the same meaning as before. Let us introduce new binary variables z_{i}, i = 1, 2, …, n defined by

z_{i} = \begin{cases}1, & y_{i} ⩽ B − \frac{1}{2}b_{i} \\ 0, & y_{i} ⩾ B + \frac{1}{2}b_{i} \end{cases}

and let us denote M = ∑_{i=1}^{n} b_{i}. Then, the mixed integer formulation can be given by

max ∑_{i=1}^{n} a_{i}b_{i}z_{i}

subject to

|\frac{x_{j} − x_{i}}{a_{i} + a_{j}} − \frac{y_{j} − y_{i}}{b_{i} + b_{j}} | + |\frac{x_{j} − x_{i}}{a_{i} + a_{j}} + \frac{y_{j} − y_{i}}{b_{i} + b_{j}} | ⩾ 1, \begin{aligned}i & = 1, 2, …, n − 1, \\ j & = i + 1, …, n \end{aligned}

|y_{i} − B| ⩾ \frac{1}{2}b_{i}, i = 1, 2, …, n
\frac{1}{2}a_{i} ⩽ x_{i} ⩽ A − \frac{1}{2}a_{i}, i = 1, 2, …, n

M − \frac{1}{2}b_{i} ⩾ y_{i} ⩾ \frac{1}{2}b_{i}, i = 1, 2, …, n (2.8)

B − y_{i} ⩽ z_{i} ⩽ \frac{1}{M} (B − y_{i}) + 1, i = 1, 2, …, n (2.9)

z_{i} ∈ {0, 1}, i = 1, 2, …, n.

For the problem with rotation there will be twice as many variables z and M = max {∑_{i=1}^{n} a_{i}, ∑_{i=1}^{n} b_{i}}. Then the mixed integer formulation is given by

(2.10)  max ∑_{i=1}^{2n} a_{i}b_{i}z_{i}

subject to

|\frac{x_{j} − x_{i}}{a_{i} + a_{j}} − \frac{y_{j} − y_{i}}{b_{i} + b_{j}} | + |\frac{x_{j} − x_{i}}{a_{i} + a_{j}} + \frac{y_{j} − y_{i}}{b_{i} + b_{j}} | ⩾ 1, \begin{aligned}i & = 1, 2, …, 2n − 1, \\ j & = i + 1, …, 2n \end{aligned}

|y_{i} − B| ⩾ \frac{1}{2}b_{i}, i = 1, 2, …, 2n
\frac{1}{2}a_{i} ⩽ x_{i} ⩽ A − \frac{1}{2}a_{i}, i = 1, 2, …, 2n
M − \frac{1}{2}b_{i} ⩾ y_{i} ⩾ \frac{1}{2}b_{i}, i = 1, 2, …, 2n

y_{i} + y_{n+i} ⩾ B + \frac{1}{2} max(b_{i}, b_{n+i}), i = 1, 2, …, 2n (2.11)

B − y_{i} ⩽ z_{i} ⩽ \frac{1}{M} (B − y_{i}) + 1, i = 1, 2, …, 2n (2.12)

z_{i} ∈ {0, 1}, i = 1, 2, …, 2n.

In both cases, without and with rotation, conditions (2.8)–(2.9) and (2.11)– (2.12) respectively, ensure that the variables z are always between 0 and 1. Hence, formula (2.10) which corresponds to objective function, has now a simple form and directly represents the area of packed rectangles. New binary variables are naturally introduced and they indicate whether the specific rectangle was packed or not.

This paper presents a new mathematical formulation of rectangle packing problems. It addresses the issues that have not been fully considered in any previous research. The dimensions considered in literature are mostly integer and variables are binary and integer. The only paper that allows usage of real variables is [7] and only for the y coordinates. Here both dimensions and variables are real and the proposed model has a piecewise linear programming formulation. The general idea is to optimally pack the big rectangle and to put the rest of small rectangles in a strip of the same width as the big rectangle. Rectangles in the strip (i.e., those that were not packed in the big rectangle) would not be packed optimally into the strip. The big rectangle will represent the beginning of the strip, and it will be the only one to be optimally packed.

3. Conclusions

This paper tackles the two-dimensional rectangle packing problem. We introduce new nonlinear programming formulation and proved the correctness of the corresponding formulation. Numbers of variables were relatively small, compared to the dimension of the problem. In addition, we proposed the mixed integer formulation, with simple formula for objective function to ease the solving of the nonlinear programming model.

This research can be extended in several ways. It would be desirable to investigate the application of some exact method of global optimization by using the proposed formulation or application of some metaheuristics both on proposed nonlinear and relaxed piecewise linear formulation. The other approach is an application of methods of disjunctive programming to a relaxed formulation.

References

1. R. Alvarez-Valdes, F. Parreño, J. M. Tamarit, A branch and bound algorithm for the strip packing problem, OR Spectrum 31 (2009), 431–459.

2. R. Baldacci, M. A. Boschetti, A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem, Eur. J. Oper. Res. 183(3) (2007), 1230–1248.

3. A. Bekrar, I. Kacem, C. Chu, C. Sadfi, An improved heuristic and an exact algorithm for the 2D strip and bin packing problem, Int. J. Product Development 10(1/2/3) (2010), 217–240.

4. J. Beasley, An exact two-dimensional non-guillotine cutting tree search procedure, Oper. Res. 33 (1985), 49–64.

5. K. J. Binkley, M. Hagiwara, Applying self-adaptive evolutionary algorithms to twodimensional packing problems using a four corners’ heuristic, Eur. J. Oper. Res. 183(3) (2007), 1230–1248.

6. M. A. Boschetti, L. Montaletti, An exact algorithm for the two-dimensional strip-packing problem, Oper. Res. 58(6) (2010), 1774–1791.

7. P. M. Castro, J.Ḟ. Oliveira, Scheduling inspired models for two-dimensional packing problems, Eur. J. Oper. Res. 215 (2011), 45–56.

8. N. Christofides, E. Hadjiconstantinou, A n exact algorithm for orthogonal 2-D cutting problems using guillotine cuts, Eur. J. Oper. Res. 83 (1995), 21–38.

9. G. F. Cintra, F. K. Miyazawa, Y. Wakabayashi, E. C. Xavier, Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation, Eur. J. Oper. Res. 191(1) (2008), 59–83.

10. E. G. Jr. Coffman, G. S. Lueker, Probabilistic Analysis of Packing and Partitioning Algorithms, Wiley, Chichester, 1992.

11. E. G. Jr. Coffman, P. W. Shor, Average-case analysis of cutting and packing in two dimensions, Eur. J. Oper. Res. 44 (1990), 134–144.

12. J. R. Correa, Near-Optimal Solutions to Two-Dimensional Bin Packing With 90 Degree Rotations, Electronic Notes in Discrete Math. 18 (2004), 89–95.

13. C. Diegert, Practical automatic placement for standard-cell integrated circuit, Amer. J. Math. Manag. Sci. 8(34) (1988), 309–328.

14. K. A. Dowsland, W. B. Dowsland, Packing problems, Eur. J. Oper. Res. 56 (1992), 2–14.

15. H. Dyckhoff, U. Finke, Cutting and Packing in Production and Distribution, Physica Verlag, Heidelberg, 1992.

16. H. Dyckhoff, G. Scheithauer, J. Terno, Cutting and packing (C and P); in: M. Dell’Amico, F. Maffioli, S. Martello (eds.), Annotated Bibliographies in Combinatorial Optimization, Wiley, Chichester, 1997, 393–413.

17. L. Epstein, L. A. Levin, R. Van Stee, Two-dimensional packing with conflicts, Acta Informatica 45(3) (2008), 155–175.

18. A. V. Fishkin, O. Gerber, K. Jansen, On efficient weighted rectangle packing with large resources; in: X. Deng and D. Du (eds.), ISAAC 2005, LNCS 3827, 1039–1050.

19. J. F. Gonzalves, M. G. C. Resende, A parallel multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem, J. Comb. Optim. 22(2) (2011), 180–201.

20. E. Hadjiconstantinou, N. Christofides N., An optimal algorithm for general orthogonal 2-D cutting problems, Technical report MS-91/2, Imperial College, London, UK.

21. J. M. Harwig, J. W. Barnes, J. T. Moore, An adaptive tabu search approach for 2-dimensional orthogonal packing problems, Military Oper. Res. 11(2) (2006), 5–26.

22. D. S. Hochbaum, W. Maass, Approximation schemes for covering and packing problems in image processing and VLSI, J. ACM 32(1) (1985), 130–136.

23. M. Kenmochi, T. Imamichi, K. Nonobe, M. Yagiura, H. Nagamochi, Exact algorithms for the two-dimensional strip packing problem with and without rotations, Eur. J. Oper. Res. 198 (2009), 73–83.

24. J. Kim, B. R. Moon, A hybrid genetic algorithm for a variant of two-dimensional packing problem; in: F. Rothlauf (ed.), Proceedings of the 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009, 2009, 287–292.

25. R. E. Korf, M. D. Moffitt, M. E. Pollack, Optimal rectangle packing, Ann. Oper. Res. 179 (2010), 261–295.

26. J. Leung, T. Tam, C. S. Wong, G. Young, F. Chin, Packing squares into square, J. Parallel and Distributed Comput. 10 (1990), 271–275.

27. S. C. H. Leung, D. Zhang, K. M. Sim, A two-stage intelligent search algorithm for the twodimensional strip packing problem, Eur. J. Oper. Res. 215 (2011), 57–69.

28. A. Lodi, S. Martello, M. Monaci, Two-dimensional packing problems: A survey, Eur. J. Oper. Res. 141 (2002), 241–252.

29. A. Lodi, S. Martello, D. Vigo, Models and bounds for two-dimensional level packing problems, J. Comb. Optim. 8 (2004), 363–379.

30. S. Lu, Y. Lu, J. Zha, S. Lu, Cross-entropy method for two-dimensional packing problem with rectangle pieces, Beijing Jiaotong Daxue Xuebao/J. Beijing Jiaotong Univ. 33(2) (2009), 39–43.

31. S. Martello, M. Monaci, D. Vigo, An exact approach to the strip-packing problem, INFORMS J. Comp. INFORMS 15(3) (2003), 310–319.

32. F. G. Ortmann, N. Ntene, J. H. van Vuuren, New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems, Eur. J. Oper. Res. 203(2) (2010), 306–315.

33. A. Savić, T. Šukilović, V. Filipović, The solving of two dimensional packing problem with m-M calculus, Yugoslav J. Oper. Res. 21(1) (2011), 93–102.

34. N. Sawaya, I. Grossmann, A hierarchy of relaxations for linear generalized disjunctive programming, Eur. J. Oper. Res. 216 (2012), 70–82.

35. E. M. Toro, A. Garcs, H. Ruiz, Two dimensional packing problem using a hybrid constructive algorithm of variable neighborhood search and simulated annealing, Revista Facultad de Ingenieria 46 (2008), 119–131.

36. V. S. Vassiliadis, Two-dimensional stock cutting and rectangle packing: binary tree model representation for local search optimization methods, J. Food Eng. 70 (2005), 257–268.

37. L. Wei, W. C. Oon, W. Zhu, A. Lim, A skyline heuristic for the 2D rectangular packing and strip packing problems, Eur. J. Oper. Res. 215 (2011), 337–346.

38. Y. L. Wu, W. Huang, S. Lau, C. K. Wong, G. H. Young, An effective quasi-human based heuristic for solving the rectangle packing problem, Eur. J. Oper. Res. 141 (2002), 341–358.

Faculty of Mathematics (Received 09 04 2012) University of Belgrade (Revised 06 09 2012) Studentski trg 16/IV, 11 000 Belgrade Serbia

aleks3rd@gmail.com

Mathematical Institute Serbian Academy of Sciences and Arts Kneza Mihaila 36/III, 11000 Belgrade Serbia

jkratica@mi.sanu.ac.rs

Faculty of Mathematics University of Belgrade Studentski trg 16/IV, 11000 Belgrade Serbia

vladofilipovic@hotmail.com