The problem of packing unequal circles of fixed radius into a circle of minimum radius is considered. An approach to improving local solutions obtained by any of the known methods is proposed. The approach is based on the idea of expanding the space of variables. The dimension of the problem expands if we assume that the radii of the circles are considered as independent variables. In this case, an additional rigid system of constraints is constructed in such a way that the convergence of variable radii to the initial fixed values is ensured in the process of the algorithm. To construct such a system of constraints, the combinatorial structure of the problem is used.The numerical results of solving test problems of packing various numbers of circles are presented and the analysis of the results obtained is carried out.
The problems of packing circles and spheres in containers of various shapes are given constant attention from scientists. Problem statements differ in the space dimension, the shape of containers, the specifics of accounting for metrical parameters (sizes) of objects and containers, etc. [1 – 7]. In recent times, the number of publications in this area has increased [8 – 12]. This, on the one hand, is due to the fact that the problems have numerous practical applications. On the other hand, these problems have become a testing benchmark for new methods of global optimization, since they are characterized as multi-extremum and of high dimension.
According to the typology proposed by Wäscher et al [13] the problems can be considered as the Knapsack Problems (KP) or Open Dimension Problems (ODP): 2DCKP, 3DSKP, 2DCODP, 3DSODP. The subject of this article is the problem of packing unequal circles into a circle of minimum radius. However, the approach proposed below can be easily extended to pack both circles and spheres into an arbitrary container and even into multiple containers.
The main idea of the proposed approach is to identify the combinatorial structure of the problem and artificially expand the space of variables (lifting) to create new possible directions for improving the objective function. Note that increasing the dimension of the problem due to the variable radii of the spheres (circles) is used in Jump Algorithm [14], where successively the auxiliary problems of minimizing the unused domain of the container are solved. This allows the transition from one local extremum to another, with the best value of the objective function.
The problems of optimal packing of unequal circles and spheres have wide practical application. Such problems arise in various industries, materials science, powder metallurgy, nanotechnology, radiosurgery, laser coagulation, monitoring systems design, studying various structures in biology, layout problems in logistics systems and space technology, coding, classification, information security, etc. [15 – 21].
Let be given a set of circles S1, S2 ,..., Sn , the radii of which are equal rˆ1, rˆ2 ,..., rˆn respectively. Without loss of generality, suppose rˆ1 rˆ2 ... rˆn . The problem is to place the circles S1, S2 ,..., Sn in a circle S0 of minimum radius r0 with a center at the point p0 = 0,0 . We denote the coordinates of the centers by pi = ui , vi , i Jn = 1,2,..., n. Then the mathematical model of the problem will take the form subject to
r0 min , ui2 vi2 (r0 rˆi )2 , i J n , i Jn , j J n ,i < j.
Thus, we have a nonlinear optimization problem with variables r0 , ui , vi , i J n , which we call
Problem 1 is multiextremal due to the nonconvexity of constraints (2). The use of numerical methods for nonlinear optimization allows finding only its local solutions, depending on the choice of initial values r0 , ui , vi , i J n . Traditionally, methods of directed search of local solutions are further used. At the same time, multi-start schemes are effective, in which starting points are generated randomly or according to some special rule. This paper proposes a new approach that improves local solutions obtained by known methods. The approach is based on the idea of the method of artificial extension of the dimension of space, first proposed in [22] using the concept of the configuration space of geometric objects [23]. In this case, generalized variables of the configuration space are the metrical and placement parameters of geometric objects. First of all, let us use the combinatorial structure of the problem as a Euclidean combinatorial optimization problem [24].
We will consider the radii r1 ,r2 ,...,rn of the circles as independent variables and form the system n n ri = rˆi , i=1 i=1
W ri rˆi W J n , iW i=1 n n ri 2 = rˆi 2 , i=1 i=1 where elements of subsets W Jn of capacity W in increasing order, and
1 n τ = rˆi . (7)
n i=1
System (4-6) is such that the set of its solutions coincides with the permutation set of real numbers rˆ1, rˆ2 ,..., rˆn. This property is a partial case and follows from the general concept of continuous representations and functional extensions of Euclidean combinatorial sets. Representation (4-6) is called polyhedral-spherical [25], because, as is easy to see, it describes a set that is the intersection of the permutation polyhedron (5) and the hypersphere (6) with center at point (7). Optimization problems on polyhedral-spherical sets have interesting properties, which are investigated in the theory of convex extensions on vertex-located sets [25].
Let us consider the function optimization problem (1) with restrictions ui2 vi2 (r0 ri )2 , i J n , (1) (2) (3) (4) (5) (6) (8) i J n , j J n , i < j, (9) where variables ri , i J n satisfy conditions (4-7).
The problem of nonlinear optimization (1), (4-9) with variables r0 , ui , vi , ri , i J n is called
Theorem 1. Both Problem 1 and Problem 2 are equivalent in the sense of the coincidence of their global solutions.
The proof of the theorem is based on the uniqueness of the polyhedral-spherical representation of the Euclidean set of permutations [24, 25] generated by the set of radii of the circles.
It is known that the equality of global solutions in multiextremal problems does not imply the coincidence of their local solutions. It is this fact that makes it possible to obtain different local solutions for the same initial points when implementing numerical optimization methods.
Note that Problem 1 has a dimension 2n+1, and the dimension of Problem 2 is equal to 3n+1. Thus, we have implemented an approach of artificial expansion of the space of variables, based on the general scheme proposed in [22]. Applied to the problem of packing circles and spheres, this approach will be called the variable radius method.
The method of variable radii allows one to realize the idea of improving solutions of Problem 1. Indeed, we choose the local solution obtained as the starting point and consider the radii of the circles as independent variables r1, r2 ,..., rn satisfying constraint system (4-9). As a result, it is possible by variables to overcome the neighborhood of attraction of a local extremum and direct to a new, possibly better, local solution. The initial values of the variable radii can be chosen as equal to the initial values, or generated randomly in (r1, rn ) .
The main difficulties in implementing the proposed approach are associated with an increase in the dimension of Problem 2. It is easy to see that the number of linear constraints in system (5) is equal to 2n 2 , which already at n >20 leads to difficulties in applying modern numerical methods of nonlinear optimization. On the one hand, using the properties of linear and quadratic functions on combinatorial polyhedra allows one to partially overcome the arising difficulties. However, this does not greatly expand the capabilities of methods in large-scale problems.
On the other hand, it is possible to select only l < n circles with variable radii. Let are fixed, and the M = m1, m2,..., ml J n be the numbers of circles, whose radii rˆm1 rˆm2 ... rˆml set M = Jn \ M be of ordered numbers of circles with variables radii ri , i M . Form a system of restrictions ui2 vi2 (r0 rˆi )2 , i M ui2 vi2 (r0 ri )2 , i M (ui u j )2 (vi v j )2 (rˆi rˆj )2 , i M , j M , i < j. (ui u j )2 (vi v j )2 (ri rj )2 , i M , j M , i < j, (10) (11) (12) (13) i M , j M . ri = rˆi iM iM
W ri rˆm W M iW i=1 i ri ˆ2 = rˆi ˆ2 , iM iM ˆ = 1 l
rˆm . l i=1 i
q Q = Q k
k=0 Q0 = rˆm1 , rˆm2 ,..., rˆml0 , Qk = rm1 , rm2 ,..., rmlk , k Jq .
Form a system of restrictions ui2 vi2 (r0 rˆi )2 , i M 0 , ui2 vi2 (r0 ri )2 , i J n \ M 0 , (ui u j )2 (vi v j )2 (rˆi rˆj )2, i M 0, j M 0, i < j, (ui u j )2 (vi v j )2 (ri rj )2 , i J n \ M 0 , j J n \ M 0 , i < j, (ui u j )2 (vi v j )2 (rˆi rj )2, i M 0, j J n \ M 0. where where where
The problem of nonlinear optimization (1), (10-18) in the space of variables r0 , ui , vi , i J n , and rj , j M we call Problem 3.
Theorem 2. The sets of global solutions of both Problem 1 and Problem 3 are the same for any M = m1, m2 ,..., ml Jn . The proof is based on the uniqueness of the polyhedral-spherical representation of the set of permutations generated by the radii of the circles with numbers from M = Jn \ M . Let us expand the above reasoning. Consider a set Q = r1, r2 ,..., rn and part it onto q 1 pairwise disjoint subsets as follows. Let be q M k = Jn , (19) k=0 q
M k = m1, m2 ,..., mlk , m1 < m2 < ... < mlk , k Jq0 = 0Jq , k=0lk = n , l0 0 . Let us consider the set (14) (15) (16) (17) (18) (20) (21) (22) (23) (24) (25)
For each set Q k , k J q , we write where ri = iM k rˆi iM k
W ri rˆm , W M k iW i=1 i ri k 2 = rˆi k 2 , iM k iM k k = 1 lk
rˆ . lk i=1 mi (26) (27) (28) (29)
The problem of nonlinear optimization (1), (21-29) in the space of variables r0 , ui , vi , i J n , and rj , j Jn \ M 0 we call Problem 4.
Let us generalize the statements of Theorem 1 and Theorem 2.
Theorem 3. The sets of global solutions of both Problem 1 and Problem 4 are the same for any M 0 = m1, m2 ,..., ml0 J n . The choice of the method of partitioning Q = r1, r2 ,..., rn onto a sets Qk = rm1 , rm2 ,..., rm
, k J q0 with the subsequent formation of constraints (12-14), forms a family lk of modifications of the method of variable radius.
The ability to control the variable radii of the circles in the process of solving the problem allows us to propose various strategies for the formation of initial points and the sequential search of local decisions in order to improve them. Suppose that at the initial stage (0-th iteration) a local solution was obtained r0(0) , ui(0) , vi(0) , ri(0) = rˆi , i J n . Strategies for improving this solution are associated both with the method of forming the parameters for placing the circles and with the rule for choosing the radii, which we will consider as variables. Classical approaches are associated with the choice of a new starting point from an extended neighborhood of the placement parameters ui(0) , vi(0) with fixed radii ri(0) = rˆi and the search for a new local solution r0(1) , ui(1) , vi(1) , ri(1) = rˆi , i J n (1-st iteration). At the k-th iteration, the initial values for the placement parameters are chosen, corresponding to the best current value of the local solution for fixed values of the radii of the circles. In this paper, it is proposed at each iteration to fix the placement parameters of the circles, setting them equal to the corresponding best current local solution. In this case, the formation of new local solutions is carried out by considering the radii of the circles as variables. We conducted the following computational experiments. For local optimization, the IPOPT software package was used (https://projects.coin-or.org/Ipopt), which implements an internal point method for continuous nonlinear programming problems. Computer with following characteristics was used to perform the computation: i3/8G/SSD 256G.
At first, test problems with the number of circles less than 15 were considered. A series of 30 problems was formed in which the radii of the circles were randomly generated uniformly in the interval (1, 15). For each test, the coordinates of the circle centers from a square (-100,100) x (-100,100) were generated randomly. The values obtained were chosen as initial for the implementation of the local optimization method in Problem 1. Then, with the same initial data, Problem 2 was solved, in which the radii of the circles are variables. The initial values for the variable radii ri , i J n in Problem 2 were randomly generated from the interval (1, 15). Thus, we compared the solutions of both Problem 1 and Problem 2 using the same local optimization method for the same starting point.
In 80% of test problems, local solutions of Problem 2 turned out to be better than in Problem 1. The average time to complete Problem 2 was only 1.5 times higher. Note that initially we intended to improve local solutions. Therefore, in the future, solutions to Problem 1 were chosen as the starting point for the implementation of Problem 2. In all cases, improvements to local solutions were obtained. However, when we tried to improve solutions to Problem 2, we succeeded in 86% of cases. An attempt to improve the new best solution at the next iteration was successful only in 43% of cases. As a rule, there were no improvements after the 7-th iteration. This is natural, since the better the initial local solution, the more difficult it is to improve.
In the problem of packing circles for n 15 , the numerical experiment was carried out using three strategies, depending on the rules for forming a set of circles with fixed and variable radii. The first strategy corresponds to the case when we fixed the radii of the circles (Problem 1). For the second strategy, the radii of l = 7 circles were assumed to be variables (Problem 3).
At the same time, a series of 10 test tasks was formed in which the radii of circles were uniformly randomly generated in the interval (1,100). For each test, textit problem 1 was solved, in which the initial values of the coordinates of the centers of the circles were also randomly generated from the set 500,500 500,500 . Then the solutions obtained were improved using Strategies 1,2. Improvements were received for all tests reviewed. The average runtime for Strategy 2 was 1.6 times higher, but the average solution quality was 4.3% better on average.
The third strategy was used for large-scale problems and involved decomposing a set Q into subsets.
The choice of the set Q decomposition method has a significant impact on the result. Experimentally, the best results corresponded to the groupings obtained as a result of partition of a set Q = rˆ1, rˆ2 ,..., rˆn, in non-decreasing order of rˆ1 rˆ2 ... rˆn (Strategy 3).
The proposed approach was tested on the placing of 60 circles, the radii of which were chosen randomly and ordered. In this way Q = rˆ1, rˆ2 ,..., rˆ60=6, 6, 8, 9, 10, 10, 13, 13, 15, 17, 18, 20, 23, 25, 25, 26, 26, 30, 31, 32, 32, 33, 34, 34, 35, 37, 38, 39, 41, 42, 42, 45, 48, 49, 49, 51, 55, 55, 56, 58, 58, 59, 61, 62, 63, 65, 66, 66, 69, 69, 70, 73, 73, 75, 76, 79, 80, 82, 82, 83. First, a local solution of Problem 1 was obtained with fixed radii from Q . The starting point for the numerical optimization method was randomly generated uniformly from the square 500,500 500,500. Radius r0(0) = 450.88 was obtained in 362 sec. Then, the set Q was partitioned in accordance with Strategy 3 and Problem 4 was solved. At each subsequent iteration, the coordinates of the centers of the circles corresponding to the best local solution were chosen as the starting point for the numerical local optimization method. In this case, the set Q = rˆ1, rˆ2 ,..., rˆn was partitioned into 10, 12, 15, 20, 30 groups of 6, 5, 4, 3, 2 elements, respectively. At subsequent iterations were obtained r0(1) = 434.72, r0(2) = 433.15, r0(3) = 431.22, r0(4) = 430.90,
r0(5) = 430.90. Finally, a solution was reached r0(6) = 426.74 and the coordinates ui , vi , i J n of the circle centers are shown in Table 1. The runtime was 968 sec.
This article proposed a new approach for improving local solutions to the problem of packing unequal circles in a circular container of minimum radius. The basic idea is to expand the variable space of the optimization problem, assuming that the radii of the circles are considered as variables. At the same time, an additional constraint system for variable radii is being constructed using the permutation structure of the problem. It is guaranteed that, as a result of the decision at the last stage, the radii will take their initial values. This approach differs from the known ones in that it allows overcoming the attraction zones of local extrema of the problem not only by changing the coordinates of the centers of the circles, but also by partially varying their radii. This provides additional directions for improving the objective function, which ultimately improves the result. The method of variable radii can be extended to containers of various shapes and even to several containers. In this case, of course, the restrictions on the placement of circles inside the container change. Moreover, the proposed approach can be used in solving problems of packing unequal spheres into an arbitrary container. In these cases, systems of restrictions on one or more metric parameters are formed by analogy with round objects. The combinatorial structure of the problem will be generated by the same system of constraints as for the radii of circles.Thus, the field of application of the variable radius method for improving the obtained solutions can be significantly expanded. 6. References [1] M. Hifi, R. M'Hallah 2009 A literature review on circle and sphere packing problems: models and methodologies Advances in Operation Research vol. 2009 pp. 1-22 https://doi.org/10.1155/2009/150624 [2] I. Castillo, F.J. Kampas, J.D. Pinter 2008 Solving circle packing problems by global optimization: numerical results and industrial applications Eur.J. Oper. Res. vol. 191(3) pp. 786-802 https://doi.org/10.1016 / j.ejor.2007.01.054 [3] C.O. López, J.E. Beasley 2013 Packing unequal circles using formulation space search Comput.
Oper. Res. vol. 40(5) pp. 1276-1288 https://doi.org/10.1016/j.cor.2012.11.022 [4] J. Liu, Y. Yao, Yu. Zheng, H. Geng, G. Zhou 2009 An effective hybrid algorithm for the circles and spheres packing problems Combinatorial Optimization and Applications, Lecture Notes in Computer Science vol. 5573 pp. 135-144 https://doi.org/10.1007/978-3-642-02026-1_12 [5] K. He, M. Huang, C. Yang 2015 An action-space-based global optimization algorithm for packing circles into a square container Computers & Operations Research vol. 58 pp. 67-74 https://doi.org/10.1016/j.cor.2014.12.010 [6] Y. Shang 2014 A novel method for equal and unequal circle packing problem Applied