# Integer Programming Formulations for Approximate Packing Circles in a Rectangular Container

Authors: Igor Litvinchev; Edith Lucero Ozuna Espinosa
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

A problem of packing a limited number of unequal circles in a fixed size rectangular container is considered. The aim is to maximize the (weighted) number of circles placed into the container or minimize the waste. This problem has numerous applications in logistics, including production and packing for the textile, apparel, naval, automobile, aerospace, and food industries. Frequently the problem is formulated as a nonconvex continuous optimization problem which is solved by heuristic techniques combined with local search procedures. New formulations are proposed for approximate solution of packing problem. The container is approximated by a regular grid and the nodes of the grid are considered as potential positions for assigning centers of the circles. The packing problem is then stated as a large scale linear 0-1 optimization problem. The binary variables represent the assignment of centers to the nodes of the grid. Nesting circles inside one another is also considered. The resulting binary problem is then solved by commercial software. Numerical results are presented to demonstrate the efficiency of the proposed approach and compared with known results.


---

## Body

## 1. Introduction

Packing problems generally consist of packing of a certain number of items of known dimensions into one or more large objects or containers so as to minimize a certain objective (e.g., the unused part of the objects or waste). The shape of items and containers may vary from a circle, a square, a rectangle, and so forth.This problem has been applied in different areas, such as the coverage of a geographical area with cell transmitters, storage of a cylindrical drums into containers or stocking them into an open area, packaging bottles or cans into the smallest box, planting trees in a given region so as to maximize the forest density and the distance between the trees, and so forth [1–3]. One can find other applications in the motor cycle industry, circular cutting, communication networks, facility location, and dashboard layout [4–8].In this paper we address the problem of packing a set of circular items in a rectangular container. There are two principal types of objectives that have been used in the literature: (a) regard the circles (not necessary equal) as being of fixed size and the container as being of variable size and (b) regard the circles and the container as being of fixed size and minimize “waste.”Examples of the first approach include the following [9].(i)
For the square container minimize the length of the side and hence minimize the perimeter and area of the square.(ii)
Minimize the perimeter of the rectangle.(iii)
Minimize the area of the rectangle.(iv)
Considering one dimension of the rectangle as fixed, minimize the other dimension. Problems of this type are often referred to as strip packing problems (or as circular open dimension problems).For the second approach various definitions of the waste can be used. The waste can be defined in relation to circles not packed (e.g., the number of unpacked circles or the perimeter/area of unpacked circles) or introducing a value associated with each circle that is packed (e.g., area of the circles packed), and so forth.Many variants of packing circular objects in the plane have been formulated as nonconvex (continuous) optimization problems with decision variables being coordinates of the centres. The nonconvexity is mainly provided by no overlapping conditions between circles. These conditions typically state that the Euclidean distance separating the centres of the circles is greater than a sum of their radii. The nonconvex problems can be tackled by available nonlinear programming (NLP) solvers; however, most NLP solvers fail to identify global optima. Thus, the nonconvex formulation of circular packing problem requires algorithms which mix local searches with heuristic procedures in order to widely explore the search space. It is impossible to give a detailed overview on the existing solution strategies and numerical results within the framework of a single short paper. We will refer the reader to review papers presenting the scope of techniques and applications for the circle packing problem (see, e.g., [1, 2, 10–13] and the references therein).In this paper we propose a new formulation for approximate solution of packing problems based on using a regular grid to approximate the container. The nodes of the grid are considered as potential positions for assigning centers of the circles. The packing problem is then stated as a large scale linear 0-1 optimization problem. The binary variables represent the assignment of centers to the nodes of the grid. The resulting binary problem is then solved by commercial software. To the best of our knowledge, the idea to use a grid was first implemented by Beasley [14] in the context of cutting problems. Recently this approach was applied in [15, 16] for packing problems. This work is a continuation of [16].


## 2. The Model

Suppose we have nonidentical circlesCk of known radius Rk, k∈K={1,2,…K}. Let at most Mk circles Ck be available for packing, and at least mk of them have to be packed. Denote by i∈I={1,2…,n} the node points of a regular grid covering the rectangular container. Let F⊆I be the grid points lying on the boundary of the container. Denote by dij the Euclidean distance between points i and j of the grid. Define binary variables xik=1 if centre of a circle Ck is assigned to the point i; xik=0, otherwise.In what follows we will distinguish two cases of circle packing, depending on whether nesting circles inside one another is permitted or not. To the best of our knowledge, nesting problem was first mentioned in [6] in the context of packing pipes of different diameters into a shipping container. Compared to the standard packing, packing with nesting is much less investigated.Consider first the problem without nesting. In order to let the circleCk assigned to the point i be nonoverlapping with other circles being packed, it is necessary that xjl=0 for j∈I, l∈K, such that dij<Rk+Rl. For fixed i, k let Nik={j,l:i≠j,dij<Rk+Rl}. Let nik be the cardinality of Nik:nik=|Nik|. Then the problem of maximizing the area covered by the circles can be stated as follows:
(1)max⁡∑i∈I∑k∈KRk2xik,(2)subjecttomk≤∑i∈Ixik≤Mk,k∈K,(3)∑k∈Kxik≤1,i∈I∖F,(4)Rkxik≤min⁡j∈Fdij,i∈I,k∈K,(5)xik+xjl≤1,fori∈I,k∈K,(j,l)∈Nik(6)xik∈{0,1},i∈I,k∈K.
Constraints (2) ensure that the number of circles packed is between mk and Mk; constraints (3) ensure that at most one centre is assigned to any grid point; constraints (4) ensure that the point i cannot be a centre of the circle Ck if the distance from i to the boundary is less than Rk; pairwise constraints (5) guarantee that there is no overlapping between the circles; constraints (6) represent the binary nature of variables.Similar to plant location problems [17] we can state nonoverlapping conditions in a more compact form. Summing up pairwise constraints (5) over (j,l)∈Nik we get
(7)nikxik+∑j,l∈Nikxjl≤nikfori∈I,k∈K.
Note that constraints similar to (7) were used in [15] for packing equal circles.Proposition 1.
Constraints (5) and (6) are equivalent to constraints (6) and (7).Proof.
If (5) are fulfilled, then obviously (7) hold by construction. If (7) are fulfilled, then for xik=1 we have ∑j,l∈Nikxjl≤0 and hence xjl=0 for j,l∈Nik as in (5). If xik=0 in (7), then ∑j,l∈Nikxjl≤nik holds for all xjl∈{0,1}.Thus the problem (1)–(6) is equivalent to the problem (1)–(4), (6), and (7). To compare two equivalent formulations, let
(8)P1={x≥0:xik+xjl≤1,fori∈I,k∈K,(j,l)∈Nik},P2={x≥0:nikxik+∑j,l∈Nikxjl≤nikfori∈I,k∈K}.Proposition 2.
P
1
⊂
P
2.Proof.
Since constraints ofP2 are obtained by summing up some constraints of P1, then P1⊆P2. To show that P1⊂P2 we need to find a point in P2 that is not in P1.
This point can be constructed as follows. By the definition,Nik={j,l:i≠j,dij<Rk+Rl} and hence if (j,l)∈Nik, then (i,k)∈Njl. Choose (i,k) and (j,l)∈Nik such that nik, njl≥2. Set to zero all the variables except xik, xjl. Obviously all constraints (5) corresponding to zero variables are fulfilled. Define xik, xjl to fulfil the two remaining constraints as equalities:
(9)nikxik+xjl=nik,njlxjl+xik=njl
with nik, njl≥2. The corresponding solution is
(10)xik=njl(nik-1)nilnik-1<1,xjl=nik(njl-1)nilnik-1<1
with
(11)xik+xjl=1+1+njlnik-njl-niknilnik-1>1.
Thus this point violates corresponding constraint (5) in P1 and hence P1⊂P2 as desired.As follows from Proposition2, the pairwise formulation (1)–(6) is stronger than the compact one [17].By the definition,Nik={j,l:i≠j,dij<Rk+Rl} and hence if (j,l)∈Nik, then (i,k)∈Njl. Thus a half of the constraints in (5) are redundant:
(12)xik+xjl≤1,fori∈I,k∈K,(j,l)∈Nik,xjl+xik≤1,forj∈I,l∈K,(i,k)∈Njl.
The redundant constraints can be eliminated giving a reduced pairwise nonoverlapping formulation. The overall set of the reduced constraints is independent of whether we will eliminate the first constraint above or the second. However, the way of eliminating redundant constraints will affect the corresponding compact formulation obtained by summing up the reduced constraints.To consider nesting circles inside one another, we only need to modify the nonoverlapping constraints. In order to let the circleCk assigned to the point i be nonoverlapping with other circles being packed (including circles places inside this circle), it is necessary that xjl=0 for j∈I, l∈K, such that Rk-Rl<dij<Rk+Rl. Note that the later condition is always fulfilled for Rk<Rl (dij≥0), such that only smaller circles can be placed inside a given circle. For fixed i, k let Ωik={j,l:i≠j,|Rk-Rl|<dij<Rk+Rl}. Then the problem of packing circles with nesting can be stated as follows:
(13)max⁡∑i∈I∑k∈Kwikxiksubjecttomk≤∑i∈Ixik≤Mk,k∈K,Rkxik≤min⁡j∈Fdij,i∈I,k∈K,xik+xjl≤1,fori∈I,k∈K,(j,l)∈Ωik.
Here weighting coefficients wik may be associated with the area of circles and/or represent the relative importance of subsets of the container.


## 3. Computational Results

A rectangular uniform grid was used in the numerical experiments, such that all grid points are defined by the grid points on its edges. LetL be a horizontal dimension (length) and let W be a vertical dimension (width) of the container; let M be a number of the equidistant grid points on the horizontal edge of the container, while N is a number of the equidistant grid points on its vertical edge. Hence the grid has M×N node points (n=M×N).All optimization problems were solved by the system CPLEX 12.5. The runs were executed on a DELL Power Edge T410, Intel Xeon 2.53 Ghz and 16 Gb RAM.First, we compare different formulations for the case of packing equal circles. The same set of 9 instances as in [15, Table 3] was used for the experiment. The number of circles available for packing was not limited. The following formulations were considered: pairwise formulation (1)–(6) (complete), reduced formulation (1)–(6) without redundant constraints (half), compact formulation (1)–(4), (6), and (7) (compact), and compact formulation obtained from (1)–(6) without redundant constraints (compact half). The results of the numerical experiment are presented in Table 1. Here the first four columns present circle radius, dimension of the quadratic cell used to construct the grid (Δ), the number of grid points (n), and the number of circles packed. For all formulations the same number of circles packed was achieved. The last four columns give CPU time for different formulations (in seconds). For all problem instancesmipgap = 0 was set for running CPLEX. Asterisks in the column indicate that computation was interrupted after the computational time exceeded 15-hour CPU time.Table 1
Results of the numerical experiments.
Circle radius
Δ
Problem dimension
Circle number
Complete
Half
Compact
Compact  half
0.625
0.15625
1403
10
6.4
125.5
144.8
110.6
0.5625
0.0703125
2449
13
50.4
647.0
5034.5
1890.6
0.5
0.125
697
18
2.6
3.2
5.2
24.1
0.4375
0.0546875
3666
21
849.2
310.8
7459.9
3690.5
0.375
0.046875
1425
32
50.0
21.4
3873.5
847.7
0.3125
0.078125
2139
45
403.8
183.9
6514.3
4451.8
0.275
0.06875
2880
61
1032.4
415.3
*
6985.4
0.25
0.0625
3649
74
1234.8
535.5
14645.9
7840.6
0.1875
0.046875
6897
140
1427.3
725.9
*
8765.2As we can see from Table1, CPU time for the complete formulation is typically much lower than for the compact formulation, especially for large problems. Note that according to Proposition 2, complete (pairwise) formulation is stronger than the compact one. Eliminating redundant constraints typically (but not always) reduces CPU time, although for complete formulation eliminating redundancy does not change the continuous relaxation. This effect is well known for users of CPLEX since simply rearranging constraints may result in increase/decrease of computational time, depending on the path selected by branch and bound algorithm. However, we may conclude that eliminating redundant constraints is useful for large problems.Figures1, 2, 3, and 4 present packing pictures, for instance, from Table 1 with radii 0.375, 0.3125, 0.4375, and 0.275, respectively.Figure 1
R
=
0.375.Figure 2
R
=
0.3125.Figure 3
R
=
0.4375.Figure 4
R
=
0.275.Figures5 and 6 present the packing pictures obtained for the container with L=W=30 and R1=0.6, R2=3, and R3=6 using pairwise formulation (1)–(6). We used M=N=31 for Figure 5 and M=N=51 for Figure 6. The solution presented in Figure 5 was obtained in 53.239 sec withmipgap = 0, while for Figure 6 the computation was interrupted after the computational time exceeded 12-hour CPU time withmipgap = 8% achieved.Figure 5Figure 6Figures7 and 8 present packing pictures obtained by the formulation (13) for the quadratic container with L=W=60 and four radii R1=0.7, R2=2, R3=4, and R4=12 with nesting permitted. Figure 7 corresponds to the grid with M=N=41, while M=N=71 was used for Figure 8. We see how packing approximation changes with the parameters of the grid. In Figure 7 the following circles were packed: 741 circles R1, 52 R2, 20 R3, and 3 R4. In Figure 8 we have 932 circles R1, 77 R2, 13 R3, and 5 R4 and there is still room for more circles. For the case of Figures 7 and 8 the computations were interrupted after the computational time exceeded 12-hour CPU time withmipgap = 67% andmipgap = 83%, correspondingly.Figure 7Figure 8


## 4. Conclusions

Different integer formulations were proposed for approximate solution of the circle packing problem. We demonstrate that the pairwise formulation is stronger than the compact one obtained by summing up the nonoverlapping constraints. The presented approach can be easily generalized to the three- (and more) dimensional case and to different shapes of the container, including irregulars. We also proposed a formulation permitting nesting circles inside one another. This problem was mentioned in [7] in the context of packing pipes of different diameters into a shipping container and has not received much attention so far. An interesting direction for the future research is to study the use of Lagrangian relaxation and corresponding heuristics [3] to cope with large dimension of arising problems. Another area for future study is the use of valid inequalities for strengthening the formulations, as well as combining continuous and integer formulations in the solution process. Some complements in these directions are in course [16].



---

*Source: 317697-2014-03-25.xml*