Given a set of circles where item
is in radius
and
identical square bins with side length
(w.l.g. for any circle
), the CBPP problem is to locate the center coordinates of each
such that any item is totally inside a container and there is no overlapping between any two items.
The goal is to minimize the number of used bins, denoted as .
A feasible solution to the CBPP is a partition of the items into sets for the bins, and the packing constraints are satisfied in each bin. An optimal solution is the one in which
, the number of bins used, cannot be made any smaller. A summary of the necessary parameters is given in Table 1.
Table 1 Parameter regulation
Assume that the bottom left corner of each bin is placed at (0, 0) in it’s own coordinate system. we formulate the CBPP as a constraint optimization problem.
where
which implies that each circle is packed exactly once. Further, if a bin is used, then
And, finally, for circles that are in the same bin, 1, and
, no overlap is allowed, implying that
Specifically, let the circles be ordered by their radii so that . To ensure that no item passes across the boundary of the bin, we ask that
Conditions (1)–(4) along with (5) are the constraints for CBPP. The overall goal of CBPP is to use as few bins as possible to pack the circles, which is
In this section, we introduce two general optimization search frameworks for constraint optimization problem that we will use for the development of our CBPP algorithm. The two frameworks are Large Neighborhood Search (LNS), and a variation of the well-studied simulated annealing process [45], Adaptive Large Neighborhood Search (ALNS) [46]. A particular advantage of ALNS is the capacity to move the iterated solution out of the local optimum.
3.1. Large neighborhood search
Large neighborhood search (LNS) is a technique to iteratively solve constraint optimization problems [46, 47]. At each iteration, the goal is to find a more promising candidate solution to the problem, and traverse a better search path through the solution space.
Definition 1. (Constraint optimization problem, COP). A constraint optimization problem is de-fined by an array of
variables that can take values from a given domain
, subject to a set of constraints
is the objective function to measure the performance of assignment. An assignment is an array of values
. A constraint
is a predicate that decides whether an assignment
is locally valid. A solution to
is an assignment
that is locally valid for all constraints in
, i.e.
is true for all
. The optimal solution of
is a solution that maximizes the objective function
.
At each iteration, LNS relaxes and repairs the solution by randomly generating and then completing a partial solution (Alg. 1). If the new assignment has higher objective function value, the previous assignment
will be replaced.
2 initial temperature;
3 휃 Θ;
4 for to
do 5
generate_partial_solution (
); 6
complete_partial_solution(
); 7 if acceptMove(
) then 8
;
9 end
11 end
4.1. Domain and objective function
For the CBPP as a constraint optimization problem (COP), we define its domain as follows. For each circle
, its assignment variables include
. We simplify the notation to
if
. The corresponding domain
defines all possible assignments of a circle in the bin–coordinate space. Since each circle
is constrained by an indicator function to be put only in a single bin, we abuse the notation slightly, simply use
to denote
, and place an emphasis on the circles rather than the containers, and each of the components where
is a 3-tuple denoted as
. Thus, when referring to a solution to
, we write
, and
corresponds to the domain for the
tuple variables. So
denotes a possible packing.
Let be the area of a bin, the density of
of a packing is defined as
where is the set of items assigned to
. Let
be the number of used bins for a solution
, so
Here denotes the density of the sparsest bin and
the density of the densest bin. We define a useful objective function, which will form part of our algorithm as
The larger the value of is, the better the packing is, since an increase in
corresponds to a denser packing as circles move out of lower density bins. In order to clarify the process for taking a complete candidate solution
for
to a partial solution, the following formal definitions are required.
Note that , this term is used for regularization. It implies that using fewer bins is preferable, that a difference in the number of bins is enough to compare two candidate solutions. With the same number of used bins in different solutions, we focus on the fullest bin and the emptiest bin on each candidate solution. The more dense the fullest bin is, the less wasted space is. The more sparse the emptiest bin is, the more concentrated the remaining stillreserved space is, which means it would be easier for assigning subsequent circles. So, the difference in density between the fullest bin and the emptiest bin determines the quality of each candidate solution.
4.2. Construct initial solution
An initial solution can be quickly constructed by our greedy algorithm GACOA (Alg. 3).
For each circle, GACOA computes a set of candidate positions by greedily moving on to the next bin if a circle cannot be packed in any of the previous bins. In particular, each circle is packed according to the following criteria.
Definition 5. (Candidate packing position). A candidatepacking position of a circle in a bin is any position that places the circle tangent to a) any two packed items, or b) a packed item and the border of the bin, or c) two perpendicular sides of the bin (i.e. the corner).
Definition 6. (Feasible packing position). A packing position of a circle in a bin is feasible if it does not violate any constraints: circles do not overlap and be fully contained in a bin. (See Eq. (1)–(5) for detailed constraints).
Definition 7. (Quality of packing position). The distance between the feasible packing position and the border of the bin is given by
where (resp.
) is a distance between the center of the circle and the closer side of the bin in the horizontal (resp. vertical) direction. For a circle in the current target bin, all
feasible positions in the bin are sorted in dictionary order of . The smaller, the better.
We call an action that places a circle onto one of its candidate packing positions a Corner Occupying Action (COA). GACOA works by packing circles one by one in the decreasing order of their radii. Each circle considers the target bin in the increasing order of the bin index . For bin
, a feasible candidate packing position with the highest quality is selected, i.e. a feasible assignment that maximizes
will be executed. Thus, the best feasible COA is selected that favours positions closer to the border of the bin. If there is no feasible assignment in bin
, we will try to pack in the next bin
. The pseudo code is given in Alg. 3.
Partial solutions are generated from a complete solution by selecting two bins at random and do perturbations. We randomly select a rectangular area of equal size in each bin, all circles that intersect the two rectangular areas will be taken out and added to the remain2assign set, and the complete solution becomes a partial solution. The unassigned circles will be reassigned based on the partial solution. This is equivalent to perturbing a complete solution that has reached a local optimum. Let function random_intsreturns
distinct integers randomly selected from set
. Let function random_real
returns a random real number
.
Alg. 5 randomly selects a circle in the non-empty bin, and then randomly generates a rectangular area with the circle center be the center of the area. This guarantees that at
least one circle will intersect the generated rectangular area (Here we simply use the envelope rectangle of the circle to check its intersection with the area). In most cases, more than one circle items intersect the rectangular area and will be unassigned at each iteration. We choose to select two bins and generate one rectangular area for each bin. Only one bin can be sampled at a time, but when the partial solution and unassigned circle set are continued to be placed in the future, in the worst case, it will be put back as it is to obtain the same complete solution as before. The worst instance is that the previous partial solution did not leave enough free space to allocate the unassigned circles except for the generated area. If there is only one bin and one rectangular area, the unassigned circles are very likely to be put back into the previous generated rectangular area during the iteration, which means that this iteration process has no effect and does not help jump out of the local optimum. Thus, two bins are selected for each iteration so that the unassigned circles have more free space to be allocated. Even in the worst case, the algorithm will try to exchange the circles in the two rectangular areas, which ensures that there will be some disturbance per iteration. Of course, an alternative way is to sample only one bin and generate two rectangular areas for the bin, but two rectangular areas in different bins can increase the randomness.
4.3. Complete a partial solution
Completing a partial solution is performed efficiently by the GACOA algorithm (Alg. 3) restricted to the bins from which circles were unassigned in the previous step.
is the partial solution generated by generate_partial_solution(). GACOA is used to complete the partial solution.
4.4. Acceptance metric
A solution is accepted if it increases the objective function or if the decrease in the objective function is probabilistically allowed given the current annealing temperature
. This is the well-known simulated annealing move acceptance criteria [45],
4.5. ALNS for CBPP
The complete algorithm for solving CBPP requires various steps from the above. The ALNS procedure is started using the initial solution along with the temperature and the number of iterations
. The initial solution is then broken using Alg. 4 and re-completed using the new solution filled by GACOA. This procedure outputs a new candidate solution, which is then either accepted or rejected based on the acceptance metric with simulated annealing. At which point,
Table 2 Experimental results on the fixed benchmarks with square bins when . The average improvement is 0.19.
if the iteration limit has not reached, the process restarts using the new solution as an input
An illustration of the entire parameter setup flow of ALNS algorithm is shown in Figure 1.
To evaluate the competency of the proposed approach, we implemented the ALNS for CBPP using the Visual C++ programming language. All results were generated by setting (Alg. 2) and obtained in a computer with Intel Core i7-8550U CPU @ 1.80GHz.
We generated benchmarks based on two groups of instances downloaded from www.packomonia.com for Single Circle Packing Problem (SCCP): for wide variation instances and
for smaller variation instances. On the packomania website, we use the range seed (number of circles for SCCP) from 8 to 20, and generate sets of benchmarks as follows: For each square bin, the best solution found in [48] for the SCPP was used to fix the bin size
as the best known record
and we generate two sets of benchmarks called “fixed" and “random".Let
be the set of circles packed in the current best solution for SCPP . The fixed set of CBPP benchmarks contains exactly 5 copies of each circle packing for SCPP. The rand set of CBPP benchmarks contains a random number (
)
of copies of each circle (i.e., the number of copies of each circle varies across the same benchmark) packed for SCPP.
In the following tables we get generated instances from the two groups of instances, we compare the number of bins and the objective value for the best solution obtained by our search algorithm ALNS with the solution obtained from our constructive algorithm GACOA. They contain, for each original number of circles (
) and actual number of replicated circles in the CBPP benchmark (
), two rows showing the bin densities for ALNS (A) and GACOA (G) algorithm. The last two columns contain the final value of the objective function obtained in each algorithm and the relative improvement of ALNS over GACOA. Figure 2 shows in depth the typical behavior in comparison of ALNS and GACOA on the two benchmark instances. The objective function (
) in the y-axis under the number of circles in the x-axis. We can observe the packing occupying rate of ALNS is higher than that of GACOA. An in-depth analysis is explained in Section 5.1 and Section 5.2.
5.1. Comparison on 푟 = 푖
We run ALNS and GACOA on the benchmark instances of . The number of unequal circle items ranges from 8 to 20 seeds for both fixed and random square settings. Table 2 shows the computational results of the fixed copies of 5 for each
. Table 3 displays the random number of copies of the circle items ranging from
of the corresponding
Figure 1: The parameter setup flow of ALNS.
Figure 2: ALNS vs. GACOA.
Figure 3: Solution for the fixed benchmark when
seed. From Table 2 we can observe that when or 60 on the fixed benchmark, ALNS utilises 5 bins, while GACOA uses 6 bins to pack the circle items. Figure 3 illustrates the packing layout for
. On the other hand, for the random instances in Table 3 when
or 72, ALNS also minimizes the number of bins by packing circles in 4 bins while GACOA packs in 5 bins. Figure 4 illustrates the packing layout for
. In summary, from the results of all the instances, ALNS returns feasible results, and has an overall average improvement of 19% for the fixed benchmarks and 12% for the random benchmarks when compared to GACOA.
5.2. Comparison on 푟푖 =√푖
Similarly we also run ALNS and GACOA on the benchmark instances of , which contains a smaller variation of radii. Table 4 contains fixed instances while Table 5 contains random instances. The instances also range from 8 to 20 seeds. As an illustration, we select
and
from Table 4 and illustrate the layout in Figure 5. The occupying rate for the first three bins is higher for ALNS when compared to that of GACOA, showing that most circle items have maximally occupied each bin’s area. The fourth last bin’s density of the packed items for ALNS is lower than that of GACOA, indicating that ALNS contains fewer packed circle items in the last bin. On the random benchmarks in Table 5 for
at instance 8, 12, 13, 14 and
Table 3 Experimental results on the random benchmarks for . The average improvement is 0.12.
15, we also observe that ALNS uses one lesser bin in total when compared to GACOA. The average improvement of ALNS over GACOA is 22% for the fixed instances and 23% for the random instances, respectively.
5.3. Further discussion
The run-times for ALNS at each benchmark are shown in Table 6 (column of in seconds). We see that ALNS computes the instances efficiently in less than 300 seconds for 100 items. By comparison, as a greedy algorithm, GACOA
Table 4 Experimental results on the fixed benchmarks when . The average improvement of 0.22. .
8 7
7 7
Figure 5: Solution for the fixed benchmark when
completes the calculation in microseconds on any of these benchmarks. Such property facilitates the high efficiency of the ALNS algorithm.
In summary, for all the generated instances, we compare the number of bins and the objective value for the best solution obtained by ALNS algorithm with solutions obtained by GACOA. The results clearly show that ALNS consis-
tently improves the objective function value as compared to GACOA over all sets of benchmarks, and it was even able to reduce the number of bins used in some benchmarks.
Table 5 Experimental results on the random benchmarks for . The average improvement is 0.23.
The results show that our objective function does guide the ALNS algorithm to search for dense packing and promote reducing the number of bins used.
We address a new type of packing problem, two dimensional circle bin packing problem (2D-CBPP), and propose an adaptive local search algorithm for solving this NP-Hard problem. The algorithm adopts a simulated annealing search on our greedy constructive algorithm. The initial solution is
Table 6 Runtimes for ALNS execution in all benchmarks.
built by the greedy algorithm. Then during the search, we generate a partial solution by randomly selecting rectangular areas in two bins and remove the circle items that intersect the areas. And we implement our greedy algorithm for completing partial solutions during the search. To facilitate the search, we design a new form of objective function, embedding the number of containers used and the maximum gap of the densities of different containers. A new solution is conditionally accepted by simulated annealing, completing one iteration of the search.
Despite to all the improvements in this work, it is highly noted that the proposed problem is indeed challenging for combinatorial optimization heuristics and future researches are needed to get better solutions and generate high quality benchmarks. Implementing an adaptive local neighborhood search seems to be an attractive meta-heuristic to adopt. we would like to explore the idea to other circle bin packing problems, and extend our approach in addressing three dimensional circle bin packing problem which is more challenging with many applications that deserves proper attention.
This work was supported by the National Natural Science Foundation of China (Grant No. U1836204, U1936108) and the Fundamental Research Funds for the Central Universities (2019kfyXKJC021).
[1] E. Specht, A precise algorithm to detect voids in polydisperse circle packings, Proceedings of the Royal Society of London Series A 471 (2015) 19.
[2] M. M. Akbar, M. S. Rahman, M. Kaykobad, E. Manning, G. Shoja, Solving the multidimensional multiple-choice knapsack problem by constructing convex hulls, Computers & Operations Research 33 (2006).
[3] S. P. G., M. C. Markot, T. Csendes, E. Specht, L. G. Casado, I. Gar- cia a, New Approaches to Circle Packing in a Square: With Program
Codes (Springer Optimization and Its Applications), Springer-Verlag, 2007.
[4] S. G, Greco.O, Conca.P, Cutello.V, P. M, N. G, Packing equal disks in a unit square: an immunological optimization approach, in: International Workshop on Artificial Immune Systems (AIS), 2015, pp. 1–5.
[5] P. Thapatsuwan, P. Pongcharoen, C. Hicks, W. Chainate, Develop- ment of a stochastic optimisation tool for solving the multiple container packing problems, International Journal of Production Economics 140 (2012) 737 – 748.
[6] T. A. Toffolo, E. Esprit, T. Wauters, G. V. Berghe, A two-dimensional heuristic decomposition approach to a three-dimensional multiple container loading problem, European Journal of Operational Research 257 (2017) 526 – 538.
[7] G. WÃďscher, H. Hauçner, H. Schumann, An improved typology of cutting and packing problems, European Journal of Operational Research 183 (2007) 1109 – 1130.
[8] M. A, Colla.V, Nastasi.G, S. M., I. V, A bin packing algorithm for steel production, 2016, pp. 19–24.
[9] A. Freund, J. S. Naor, Approximating the advertisement placement problem, Journal of Scheduling 7 (2004) 365–374.
[10] M. Dawande, S. Kumar, C. Sriskandarajah, A note on the minspace problem, Journal of Scheduling 8 (2005) 97–106.
[11] B. E. G, M. J.M.z, R. D.Pn, Optimizing the packing of cylinders into a rectangular container: A nonlinear approach, European Journal of Operational Research 160 (2005) 19 – 33.
[12] L. Junqueira, R. Morabito, D. S. Yamashita, Three-dimensional con- tainer loading models with cargo stability and load bearing constraints, Computers & Operations Research 39 (2012) 74 – 85.
[13] M. L. Demaine, S. P. Fekete, R. J. Lang, Circle packing for origami design is hard, ArXiv abs/1008.1224 (2010).
[14] B. An, S. Miyashita, A. Ong, M. T. Tolley, M. L. Demaine, E. D. Demaine, R. J. Wood, D. Rus, An end-to-end approach to self-folding origami structures, IEEE Transactions on Robotics 34 (2018) 1409– 1424.
[15] F. Bolyai, Wolfgangi bolyai de bolya: Tentamen iuventutem stu- diosam in elementa math-eseos purae elementaris ac sublimioris methodo intuitiva evidentiaque huic propria introducendi,cum appendice triplici. in latin. marosvasarhelyini,second edition in 1904 2 (1832-33) 119–122.
[16] R. L. Graham, B. D. Lubachevsky, Dense packings of equal disks in an equilateral triangle: From 22 to 34 and beyond, J. of Combinatorics 2 (1995) pp. (electronic).
[17] R. L. G. B. D. Lubachevsky, Dense packings of equal disks in an equi- lateral triangle: From 22 to 34 and beyond, The Electronic Journal of
Combinatorics 2 (1995), A1 (2004) 39.
[18] C. LÃşpez, J. Beasley, A heuristic for the circle packing problem with a variety of containers, European Journal of Operational Research 214 (2011) 512 – 525.
[19] M. Hifi, R. MâĂŹHallah, A dynamic adaptive local search algorithm for the circular packing problem, European Journal of Operational Research 183 (2007) 1280 – 1294.
[20] K. He, W. Huang, An efficient placement heuristic for three- dimensional rectangular packing, Computers & Operations Research 38 (2011) 227 – 233.
[21] K. He, M. Dosh, A greedy heuristic based on corner occupying action for the 2d circular bin packing problem, Springer Singapore (2017) 75 – 85.
[22] Z. Zeng, X. Yu, K. He, W. Huang, Z. Fu, Iterated tabu search and variable neighborhood descent for packing unequal circles into a circular container, European Journal of Operational Research 250 (2016) 615–627.
[23] W. Dickinson, D. Guillot, A. Keaton, S. Xhumari, Optimal packings of up to five equal circles on a square flat torus, Contributions to Algebra and Geometry 52 (2011) 315–333.
[24] W. Huang, Y. Li, B. Jurkowiak, C. Li, R. Xu, A two-level search strat- egy for packing unequal circles into a circle container, in: Principles and Practice of Constraint Programming, Springer Berlin Heidelberg, 2003, pp. 868–872.
[25] W. Huang, Y. Li, C. Li, R. Xu, New heuristics for packing unequal circles into a circular container, Computers & Operations Research 33 (2006) 2125 – 2142.
[26] W. Huang, Y. Li, H. Akeb, C. Li, Greedy algorithms for packing un- equal circles into a rectangular container, Journal of the Operational Research Society 56 (2005) 539–548.
[27] Z. LÃij, W. Huang, Perm for solving circle packing problem, Com- puters & Operations Research 35 (2008) 1742 – 1755.
[28] H. P. Hsu, V. Mehra, W. Nadler, G. Peter, Growth based optimization algorithm for lattice heteropolymers, Phys. Rev. E 68 (2003) 021113.
[29] W. Huang, Z. P. Lu, H. Shi, Growth algorithm for finding low energy configurations of simple lattice proteins, Physics Review E 72 (2005) 016704.
[30] M. Hifi, R. MHallah, Approximate algorithms for constrained circular cutting problems, Computers & Operations Research 31 (2004) 675 – 694.
[31] M. Hifi, R. MâĂŹHallah, Adaptive and restarting techniques based algorithms for circular packing problems, Computational Optimization and Applications 39 (2008) 17–35.
[32] H. Akeb, M. Hifi, A hybrid beam search looking-ahead algorithm forÂătheÂăcircular packing problem, Journal of Combinatorial Optimization 20 (2010) 101–130.
[33] I. Castillo, F. J. Kampas, J. D. PintÃľr, Solving circle packing prob- lems by global optimization: Numerical results and industrial applications, European Journal of Operational Research 191 (2008) 786 – 802.
[34] D. Zhu, Quasi-human seniority-order algorithm for unequal circles packing, Chaos, Solitons & Fractals 89 (2016) 506 – 517.
[35] J. Liu, J. Li, Z. LÃij, Y. Xue, A quasi-human strategy-based improved basin filling algorithm for the orthogonal rectangular packing problem with mass balance constraint, Computers & Industrial Engineering 107 (2017) 196 – 210.
[36] K. He, H. Ye, Z. Wang, J. Liu, An efficient quasi-physical quasi- human algorithm for packing equal circles in a circular container, Computers & Operations Research 92 (2018) 26 – 36.
[37] K. He, M. Huang, C. Yang, An action-space-based global optimiza- tion algorithm for packing circles into a square container, Computers & Operations Research 58 (2015) 67 – 74.
[38] K. He, M. Dosh, S. Zou, Packing unequal circles into a square con- tainer by partitioning narrow action, spaces and circle items, CoRR abs/1701.00541 (2017).
[39] D. Zhang, A. Deng, An effective hybrid algorithm for the problem of packing circles into a larger containing circle, Computers & Operations Research 32 (2005) 1941 – 1951.
[40] F. Glover, Tabu searchâĂŤpart 1, ORSA Journal on computing 1 (1989) 190–206.
[41] F. Glover, Tabu searchâĂŤpart ii, ORSA Journal on computing 2 (1990) 4–32.
[42] Z. Zeng, X. Yu, K. He, Z. Fu, Adaptive tabu search and variable neigh- borhood descent for packing unequal circles into a square, Applied Soft Computing 65 (2018) 196 – 213.
[43] A. Lodi, S. Martello, D. Vigo, Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems, Journal on Computing 11 (1999) 345–357.
[44] N. Bansal, A. Lodi, M. Sviridenko, A tale of two dimensional bin packing, in: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS, 2005, pp. 657–666.
[45] S. Kirkpatrick, C. Gelatt, M. Vecchi, Optimization by simulated an- nealing, Science 220 (1983) 671–80.
[46] M. Gendreau, J.-Y. Potvin, et al., Handbook of metaheuristics, Vol. 272, Springer International Publishing, 2010.
[47] C. Larsson, Chapter 5 - optimization techniques, Academic Press, 2018, pp. 103 – 122.
[48] E. Specht, Packomania website 2018 www.packomania.com (2018).