×

Iterated dynamic thresholding search for packing equal circles into a circular container. (English) Zbl 07479785

Summary: Packing equal circles in a circle is a classic global optimization problem that has a rich research history and a number of relevant applications. The problem is computationally challenging due to the fact that the number of possible packing configurations grows exponentially with the number of circles. In this work, we propose a highly effective iterated dynamic thresholding search algorithm for solving this difficult problem. The algorithm integrates several features including a two-phase local optimization method, a dynamic thresholding search and a container adjustment procedure. Computational experiments on popular benchmark instances with up to \(N=320\) circles show that the algorithm outperforms significantly the state-of-the-art algorithms. In particular, it improves the best-known results for 136 instances, while matching the best-known results for other 175 instances.

MSC:

90Bxx Operations research and management science
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Addis, B.; Locatelli, M.; Schoen, F., Disk packing in a square: A new global optimization approach, INFORMS Journal on Computing, 20, 4, 516-524 (2008) · Zbl 1243.90084
[2] Addis, B.; Locatelli, M.; Schoen, F., Efficiently packing unequal disks in a circle, Operations Research Letters, 36, 37-42 (2008) · Zbl 1151.90035
[3] Akiyama, J.; Mochizuki, R.; Mutoh, N.; Nakamura, G., Maximin distance for n points in a unit square or a unit circle, (Akiyama, J.; Kano, M., Japanese conference on discrete and computational geometry, JCDCG 2002, Tokyo, Japan (2002)), 9-13 · Zbl 1179.68173
[4] Birgin, E. G.; Gentil, J. M., New and improved results for packing identical unitary radius circles within triangles, rectangles and strips, Computers and Operations Research, 37, 1318-1327 (2010) · Zbl 1178.90283
[5] Birgin, E. G.; Sobral, F. N.C., Minimizing the object dimensions in circle and sphere packing problems, Computers and Operations Research, 35, 2357-2375 (2008) · Zbl 1177.90332
[6] Boll, D. W.; Donovan, J.; Graham, R. L.; Lubachevsky, B. D., Improving dense packings of equal disks in a square, The Electronic Journal of Combinatorics, 7, R46 (2000) · Zbl 0962.52004
[7] Castillo, I.; Kampas, F. K.; Pintér, J. D., Solving circle packing problems by global optimization: Numerical results and industrial applications, European Journal of Operational Research, 191, 786-802 (2008) · Zbl 1156.90013
[8] Chen, M.; Tang, X. Y.; Song, T.; Zeng, Z. Z.; Peng, X. C.; Liu, S. Y., Greedy heuristic algorithm for packing equal circles into a circular container, Computers and Industrial Engineering, 119, 114-120 (2018)
[9] Clare, B. W.; Kepert, D. L., The optimal packing of circles on a sphere, Journal of Mathematical Chemistry, 6, 325-349 (1991)
[10] Das, G. K.; Das, S.; Nandy, S. C.; Sinha, B. P., Efficient algorithm for placing a given number of base stations to cover a convex region, Journal of Parallel and Distributed Computing, 66, 1353-1359 (2006) · Zbl 1178.68028
[11] Demaine, E. D., Fekete, S. P., & Lang, R. J. (2010). Circle packing for origami design is hard. CoRR arXiv:1008.1224
[12] Doye, J. P.K.; Leary, R. H.; Locatelli, M.; Schoen, F., Global optimization of morse clusters by potential energy transformations, INFORMS Journal on Computing, 16, 4, 371-379 (2004) · Zbl 1239.90085
[13] Dueck, G.; Scheuer, T., Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing, Journal of Computational Physics, 90, 161-175 (1990) · Zbl 0707.65039
[14] Fiacco, A. V.; McCormick, G. P., Computational algorithm for the sequential unconstrained minimization technique for nonlinear programming, Management Science, 10, 601-617 (1964)
[15] Fodor, F., The densest packing of 19 congruent circles in a circle, Geometriae Dedicata, 74, 139-145 (1999) · Zbl 0927.52024
[16] Fu, Z. H.; Huang, W. Q.; Lü, Z. P., Iterated tabu search for the circular open dimension problem, European Journal of Operational Research, 225, 2, 236-243 (2013) · Zbl 1292.90164
[17] Galiev, S. I.; Lisafina, M. S., Linear models for the approximate solution of the problem of packing equal circles into a given domain, European Journal of Operational Research, 230, 505-514 (2013) · Zbl 1317.52029
[18] Graham, R. L., Sets of points with given minimum separation (solution to problem El921), American Mathematical Monthly, 75, 192-193 (1968)
[19] Graham, R. L.; Lubachevsky, B. D.; Nurmela, K. J.; Östergard, P. R.J., Dense packings of congruent circles in a circle, Discrete Mathematics, 181, 139-154 (1998) · Zbl 0901.52017
[20] Grebennik, I. V.; Kovalenko, A. A.; Romanova, T. E.; Urniaieva, I. A.; Shekhovtsov, S. B., Combinatorial configurations in balance layout optimization problems, Cybernetics and Systems Analysis, 54, 221-231 (2018) · Zbl 1393.90102
[21] Grosso, A.; Jamali, A. R.M. J.U.; Locatelli, M.; Schoen, F., Solving the problem of packing equal and unequal circles in a circular container, Journal of Global Optimization, 47, 63-81 (2010) · Zbl 1190.90161
[22] Hager, W. W.; Zhang, H. C., A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM Journal on Optimization, 16, 170-192 (2005) · Zbl 1093.90085
[23] He, K.; Ye, H.; Wang, Z. L.; Liu, J. F., An efficient quasi-physical quasi-human algorithm for packing equal circles in a circular container, Computers and Operations Research, 92, 26-36 (2018) · Zbl 1391.90519
[24] Hifi, M.; M’Hallah, R., A dynamic adaptive local search algorithm for the circular packing problem, European Journal of Operational Research, 183, 1280-1294 (2007) · Zbl 1135.90037
[25] Hifi, M.; Yousef, L., A local search-based method for sphere packing problems, European Journal of Operational Research, 274, 482-500 (2019) · Zbl 1404.90140
[26] Huang, W. Q.; Ye, T., Greedy vacancy search algorithm for packing equal circles in a square, Operations Research Letters, 38, 378-382 (2010) · Zbl 1202.90226
[27] Huang, W. Q.; Ye, T., Global optimization method for finding dense packing of equal circle in a circle, European Journal of Operational Research, 210, 474-481 (2011) · Zbl 1213.90201
[28] Kravitz, S., Packing cylinders into cylindrical containers, Mathematics Magazine, 40, 65-71 (1967) · Zbl 0192.28801
[29] Leary, R., Global optimization on funneling landscapes, Journal of Global Optimization, 18, 367-383 (2000) · Zbl 0986.90038
[30] Litvinchev, I.; Infante, L.; Espinosa, E. L.Q., Using valid inequalities and different grids in LP-based heuristic for packing circular objects, Lecture Notes in Computer Science, 9622, 681-690 (2016)
[31] Litvinchev, I.; Ozuna, E. L., Approximate packing circles in a rectangular container: Valid inequalities and nesting, Journal of Applied Research and Technology, 12, 716-723 (2014)
[32] Liu, D. C.; Nocedal, J., On the limited memory BFGS method for large scale optimization, Mathematical Programming, 45, 503-528 (1989) · Zbl 0696.90048
[33] Liu, J. F.; Xue, S. J.; Liu, Z. X.; Xu, D. H., An improved energy landscape paving algorithm for the problem of packing circles into a larger containing circle, Computers and Industrial Engineering, 57, 1144-1149 (2009)
[34] Locatelli, M.; Raber, U., Packing equal circles in a square: A deterministic global optimization approach, Discrete Applied Mathematics, 122, 139-166 (2002) · Zbl 1019.90033
[35] Locatelli, M.; Schoen, F., Fast global optimization of difficult Lennard-Jones clusters, Computational Optimization and Applications, 21, 55-70 (2002) · Zbl 0988.90054
[36] López, C. O.; Beasley, J. E., A heuristic for the circle packing problem with a variety of containers, European Journal of Operational Research, 214, 512-525 (2011) · Zbl 1226.90088
[37] López, C. O.; Beasley, J. E., Packing unequal circles using formulation space search, Computers and Operations Research, 40, 1276-1288 (2013) · Zbl 1352.90085
[38] López, C. O.; Beasley, J. E., A formulation space search heuristic for packing unequal circles in a fixed size circular container, European Journal of Operational Research, 251, 64-73 (2016) · Zbl 1346.90710
[39] Lü, Z. P.; Huang, W. Q., PERM for solving circle packing problem, Computers and Operations Research, 35, 5, 1742-1755 (2008) · Zbl 1211.90198
[40] Markót, M. C.; Csendes, T., A new verified optimization technique for the “packing circles in a unit square” problems, SIAM Journal on Optimization, 16, 1, 193-219 (2005) · Zbl 1089.90045
[41] Martínez, L.; Andrade, R.; Birgin, E. G.; Martínez, J. M., Packmol: A package for building initial configurations for molecular dynamics simulations, Journal of Computational Chemistry, 30, 13, 2157-2164 (2009)
[42] Melissen, H., Densest packings of eleven congruent circles in a circle, Geometriae Dedicata, 50, 15-25 (1994) · Zbl 0810.52013
[43] Mladenović, N.; Plastria, K.; Urošević, D., Reformulation descent applied to circle packing problems, Computers and Operations Research, 32, 2419-2434 (2005) · Zbl 1066.90092
[44] Müller, A.; Schneider, J. J.; Schömer, E., Packing a multidisperse system of hard disks in a circular environment, Physical Review E, 79, 021102 (2009)
[45] Pirl, U., Der mindestabstand von n in der einheitskreisscheibe gelegenen punkten, Mathematische Nachrichten, 40, 1-3, 111-124 (1969) · Zbl 0182.25102
[46] Specht, E., High density packings of equal circles in rectangles with variable aspect ratio, Computers and Operations Research, 40, 58-69 (2013) · Zbl 1349.90723
[47] Specht, E. (2020). Packomania website: http://www.packomania.com.
[48] Stetsyuk, P. I.; Romanova, T. E.; Scheithauer, G., On the global minimum in a balanced circular packing problem, Optimization Letters, 10, 1347-1360 (2016) · Zbl 1353.90133
[49] Stoyan, Y.; Scheithauer, G.; Yaskov, G. N., Packing unequal spheres into various containers, Cybernetics and Systems Analysis, 52, 419-426 (2016) · Zbl 1352.52027
[50] Stoyan, Y.; Yaskov, G., Packing unequal circles into a strip of minimal length with a jump algorithm, Optimization Letters, 8, 949-970 (2014) · Zbl 1292.90259
[51] Stoyan, Y.; Yaskov, G.; Romanova, T.; Litvinchev, I.; Yakovlev, S.; Cantú, J. M.V., Optimized packing multidimensional hyperspheres: Aunified approach, Mathematical Biosciences and Engineering, 76, 6, 6601-6630 (2020) · Zbl 1476.90291
[52] Stoyan, Y.; Zlotnik, M.; Chugay, A., Solving an optimization packing problem of circles and non-convex polygons with rotations into a multiply connected region, Journal of the Operational Research Society, 63, 379-391 (2012)
[53] Toledo, F. M.B.; Carravilla, M. A.; Ribeiro, C.; Oliveira, J. F.; Gomes, A. M., The dotted-board model: A new MIP model for nesting irregular shapes, International Journal of Production Economics, 45, 2, 478-487 (2013)
[54] Wang, H. Q.; Huang, W. Q.; Zhang, Q.; Xu, D. M., An improved algorithm for the packing of unequal circles within a larger containing circle, European Journal of Operational Research, 141, 440-453 (2002) · Zbl 1081.90593
[55] Zeng, Z. Z.; Yu, X. G.; He, K.; Huang, W. Q.; Fu, Z. H., Iterated tabu search and variable neighborhood descent for packing unequal circles into a circular container, European Journal of Operational Research, 250, 615-627 (2016) · Zbl 1346.90526
[56] Zhang, D. F.; Deng, A., An efficient hybrid algorithm for the problem of packing the circles into a larger containing circle, Computers and Operations Research, 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.