An efficient quasi-physical quasi-human algorithm for packing equal circles in a circular container. (English) Zbl 1391.90519
Summary: We propose an efficient quasi-physical quasi-human (QPQH) algorithm for the equal circle packing problem. QPQH is based on our modified Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm, which we call the local BFGS, and a new basin-hopping strategy based on a Chinese proverb: alternate tension with relaxation. Starting from a random initial layout, we apply the local BFGS algorithm to reach a local minimum layout. The local BFGS algorithm fully utilizes the neighborhood information of each circle to considerably speed up the computation of the gradient descent process; this efficiency is very apparent for large-scale instances. When yielding a local minimum layout, the new basin-hopping strategy is used to shrink container sizes to different extents, to generate several new layouts. Experimental results indicate that the new basin-hopping strategy is very efficient, especially for layout types with comparatively dense packing in the center and comparatively sparse packing around the boundary of the container. We tested QPQH on instances in which \(n = 1, 2, \dots, 320\), and obtained 66 new layouts having smaller container sizes than the current best-known results reported in the literature.
MSC:
| 90C27 | Combinatorial optimization |
| 52C15 | Packing and covering in \(2\) dimensions (aspects of discrete geometry) |
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90C26 | Nonconvex programming, global optimization |
| 05B40 | Combinatorial aspects of packing and covering |
Keywords:
circle packing; neighborhood structure; container shrinking strategy; quasi-physical; quasi-humanSoftware:
L-BFGSReferences:
| [1] | Addis, B.; Locatelli, M.; Schoen, F., Disk packing in a square: a new global optimization approach, INFORMS J. Comput., 20, 4, 516-524, (2008) · Zbl 1243.90084 |
| [2] | Addis, B.; Locatelli, M.; Schoen, F., Efficiently packing unequal disks in a circle, Oper. Res. Lett., 36, 1, 37-42, (2008) · Zbl 1151.90035 |
| [3] | Akeb, H.; Hifi, M., A hybrid beam search looking-ahead algorithm for the circular packing problem, J. Comb. Optim., 20, 2, 101-130, (2010) · Zbl 1200.90141 |
| [4] | Akeb, H.; Hifi, M.; MHallah, R., A beam search algorithm for the circular packing problem, Comput. Oper. Res., 36, 5, 1513-1528, (2009) · Zbl 1177.90330 |
| [5] | Akiyama, J.; Mochizuki, R.; Mutoh, N.; Nakamura, G., Maximin distance for n points in a unit square or a unit circle, Discrete and Computational Geometry, 9-13, (2003), Springer · Zbl 1179.68173 |
| [6] | Birgin, E. G.; Martınez, J.; Ronconi, D. P., Optimizing the packing of cylinders into a rectangular container: a nonlinear approach, Eur. J. Oper. Res., 160, 1, 19-33, (2005) · Zbl 1067.90133 |
| [7] | Castillo, I.; Kampas, F. J.; Pintér, J. D., Solving circle packing problems by global optimization: numerical results and industrial applications, Eur. J. Oper. Res., 191, 3, 786-802, (2008) · Zbl 1156.90013 |
| [8] | Demaine, E. D.; Fekete, S. P.; Lang, R. J., Circle packing for origami design is hard, CoRR, (2010) |
| [9] | Flores, J. J.; Martínez, J.; Calderón, F., Evolutionary computation solutions to the circle packing problem, Soft Comput., 1-15, (2015) |
| [10] | Fodor, F., The densest packing of 19 congruent circles in a circle, Geom. Dedic., 74, 2, 139-145, (1999) · Zbl 0927.52024 |
| [11] | Fodor, F., The densest packing of 12 congruent circles in a circle, Beiträge Algebra Geom., 41, 401-409, (2000) · Zbl 0974.52015 |
| [12] | Fodor, F., The densest packing of 13 congruent circles in a circle, Contributions to Algebra and Geometry, 44(2), 431-440, (2003) · Zbl 1039.52015 |
| [13] | Fu, Z.; Huang, W.; Lü, Z., Iterated tabu search for the circular open dimension problem, Eur. J. Oper. Res., 225, 2, 236-243, (2013) · Zbl 1292.90164 |
| [14] | Goldberg, M., Packing of 14, 16, 17 and 20 circles in a circle, Math. Mag., 134-139, (1971) · Zbl 0212.54504 |
| [15] | Graham, R., Sets of points with given minimum separation (solution to problem e1921), Amer. Math. Mon., 75, 192-193, (1968) |
| [16] | Graham, R. L.; Lubachevsky, B. D.; Nurmela, K. J.; Östergård, P. R., Dense packings of congruent circles in a circle, Discrete Math., 181, 1, 139-154, (1998) · Zbl 0901.52017 |
| [17] | Grosso, A.; Jamali, A.; Locatelli, M.; Schoen, F., Solving the problem of packing equal and unequal circles in a circular container, J. Glob. Optim., 47, 1, 63-81, (2010) · Zbl 1190.90161 |
| [18] | He, K.; Huang, M.; Yang, C., An action-space-based global optimization algorithm for packing circles into a square container, Comput. Oper. Res., 58, C, 67-74, (2015) · Zbl 1348.90542 |
| [19] | He, K.; Mo, D.; Ye, T.; Huang, W., A coarse-to-fine quasi-physical optimization method for solving the circle packing problem with equilibrium constraints, Comput. Ind. Eng., 66, 66, 1049-1060, (2013) |
| [20] | Hifi, M.; M’Hallah, R., Approximate algorithms for constrained circular cutting problems, Comput. Oper. Res., 31, 5, 675-694, (2004) · Zbl 1061.90095 |
| [21] | Hifi, M.; MHallah, R., Strip generation algorithms for constrained two-dimensional two-staged cutting problems, Eur. J. Oper. Res., 172, 2, 515-527, (2006) · Zbl 1120.90071 |
| [22] | Hifi, M.; MHallah, R., A dynamic adaptive local search algorithm for the circular packing problem, Eur. J. Oper. Res., 183, 3, 1280-1294, (2007) · Zbl 1135.90037 |
| [23] | Huang, W.; Li, Y.; Akeb, H.; Li, C., Greedy algorithms for packing unequal circles into a rectangular container, J. Oper. Res. Soc., 56, 5, 539-548, (2005) · Zbl 1095.90095 |
| [24] | Huang, W.; Ye, T., Global optimization method for finding dense packings of equal circles in a circle, Eur. J. Oper. Res., 210, 3, 474-481, (2011) · Zbl 1213.90201 |
| [25] | Huang, W. Q.; Li, Y.; Jurkowiak, B.; Li, C. M.; Xu, R. C., A two-level search strategy for packing unequal circles into a circle container, Principles and Practice of Constraint Programming-CP 2003, 868-872, (2003), Springer |
| [26] | Huang, W. Q.; Li, Y.; Li, C. M.; Xu, R. C., New heuristics for packing unequal circles into a circular container, Comput. Oper. Res., 33, 8, 2125-2142, (2006) · Zbl 1086.90063 |
| [27] | Huang, W. Q.; Zhan, S. H., A quasi- physical method of solving packing problems, Acta Math. Appl. Sinica, 2, 176-180, (1982) |
| [28] | Kravitz, S., Packing cylinders into cylindrical containers, Math.Mag., 65-71, (1967) · Zbl 0192.28801 |
| [29] | Liu, D. C.; Nocedal, J., On the limited memory BFGS method for large scale optimization, Math. Program., 45, 1, 503-528, (1989) · Zbl 0696.90048 |
| [30] | Liu, J.; Jiang, Y.; Li, G.; Xue, Y.; Liu, Z.; Zhang, Z., Heuristic-based energy landscape paving for the circular packing problem with performance constraints of equilibrium, Phys. A Stat. Mech.Appl., 431, 166-174, (2015) · Zbl 1400.90262 |
| [31] | Liu, J.; Xue, S.; Liu, Z.; Xu, D., An improved energy landscape paving algorithm for the problem of packing circles into a larger containing circle, Comput. Ind. Eng., 57, 3, 1144-1149, (2009) |
| [32] | Liu, J.; Zhang, K.; Yao, Y.; Xue, Y.; Guan, T., A heuristic quasi-physical algorithm with coarse and fine adjustment for multi-objective weighted circles packing problem, Comput. Ind. Eng., 101, 416-426, (2016) |
| [33] | Lopez, C.; Beasley, J., Packing unequal circles using formulation space search, Comput. Oper. Res., 40, 5, 1276-1288, (2013) · Zbl 1352.90085 |
| [34] | Lü, Z.; Huang, W., Perm for solving circle packing problem, Comput. Oper. Res., 35, 5, 1742-1755, (2008) · Zbl 1211.90198 |
| [35] | Melissen, H., Densest packings of eleven congruent circles in a circle, Geom. Dedic., 50, 1, 15-25, (1994) · Zbl 0810.52013 |
| [36] | Mladenović, N.; Plastria, F.; Urošević, D., Reformulation descent applied to circle packing problems, Comput. Oper. Res., 32, 9, 2419-2434, (2005) · Zbl 1066.90092 |
| [37] | Mller, A.; Schneider, J. J.; Schmer, E., Packing a multidisperse system of hard disks in a circular environment, Phys. Rev. E, 79, 319-354, (2009) |
| [38] | Pirl, U., Der mindestabstand von n in der einheitskreisscheibe gelegenen punkten, Mathematische Nachrichten, 40, 1-3, 111-124, (1969) · Zbl 0182.25102 |
| [39] | Reis, G. E., Dense packing of equal circles within a circle, Math. Mag., 33-37, (1975) · Zbl 0297.52014 |
| [40] | Szabó, P. G.; Markót, M. C.; Csendes, T., Global optimization in geometrycircle packing into the square, Essays and Surveys in Global Optimization, 233-265, (2005), Springer · Zbl 1136.90445 |
| [41] | Wang, H.; Huang, W.; Zhang, Q.; Xu, D., An improved algorithm for the packing of unequal circles within a larger containing circle, Eur. J. Oper. Res., 141, 2, 440-453, (2002) · Zbl 1081.90593 |
| [42] | Ye, T.; Huang, W.; Lü, Z., Iterated tabu search algorithm for packing unequal circles in a circle, CoRR, (2013) |
| [43] | Zeng, Z.; Yu, X.; He, K.; Huang, W.; Fu, Z., Iterated tabu search and variable neighborhood descent for packing unequal circles into a circular container, Eur. J. Oper. Res., 250, 2, 615-627, (2015) · Zbl 1346.90526 |
| [44] | Zhang, D.-f.; Deng, A.-s., An effective hybrid algorithm for the problem of packing circles into a larger containing circle, Comput. Oper. Res., 32, 8, 1941-1951, (2005) · Zbl 1068.90095 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
