Iterated dynamic neighborhood search for packing equal circles on a sphere. (English) Zbl 1542.90207
Summary: In this work, we investigate the equal circle packing problem on a sphere (ECPOS), which consists in packing \(N\) equal non-overlapping circles on a unit sphere such that the radius of circles is maximized. The problem is of great interest in biology, engineering and operations research and thus has a rich research history both from theoretical and computational aspects. We propose from the point of view of computational research an effective iterated dynamic neighborhood search (IDNS) algorithm for the ECPOS problem. The algorithm includes a multiple-stage local optimization method, a general dynamic neighborhood search method and an adjustment method of the minimum distance between the points on the unit sphere. Extensive experiments are conducted with the proposed algorithm on 205 instances commonly used in the literature. Computational results show that the algorithm is highly effective by improving the best-known results for 42 instances and matching the best-known results for other 116 instances, while missing the best-known results for only 5 instances. For the remaining 42 instances, the best-known results are reported for the first time by the IDNS algorithm.
MSC:
| 90C27 | Combinatorial optimization |
| 52C17 | Packing and covering in \(n\) dimensions (aspects of discrete geometry) |
| 90C26 | Nonconvex programming, global optimization |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [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] | Anjaly, P., Ratnoo, A., 2018. Tammes problem inspired multi-agent formation control over a manifold. In: 2018 AIAA Information Systems-AIAA Infotech@ Aerospace. p. 0898. |
| [3] | Appelbaum, J.; Weiss, Y., The packing of circles on a hemisphere, Meas. Sci. Technol., 10, 11, 1015 (1999) |
| [4] | Birgin, E. G.; Sobral, F., Minimizing the object dimensions in circle and sphere packing problems, Comput. Oper. Res., 35, 7, 2357-2375 (2008) · Zbl 1177.90332 |
| [5] | Castillo, I.; Kampas, F. J.; Pintér, J. D., Solving circle packing problems by global optimization: numerical results and industrial applications, European J. Oper. Res., 191, 3, 786-802 (2008) · Zbl 1156.90013 |
| [6] | Cheng, L.; Feng, Y.; Yang, J.; Yang, J., Funnel hopping: Searching the cluster potential energy surface over the funnels, J. Chem. Phys., 130, 21, Article 214112 pp. (2009) |
| [7] | Clare, B.; Kepert, D., The closest packing of equal circles on a sphere, Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 405, 1829, 329-344 (1986) · Zbl 0586.52008 |
| [8] | Danzer, L., Finite point-sets on s \({}^2\) with minimum distance as large as possible, Discrete Math., 60, 3-66 (1986) · Zbl 0644.52007 |
| [9] | Demaine, E. D.; Fekete, S. P.; Lang, R. J., Circle packing for origami design is hard (2010), arXiv preprint arXiv:1008.1224v2 |
| [10] | Fejes, T. L., Über die abscätzung des kürzesten abstandes zweier punkte eines auf einer kugelfläche liegenden punktsystemes, Jber. Deut. Math. Ver., 53, 66-68 (1943) · Zbl 0028.07605 |
| [11] | Fiacco, A. V.; McCormick, G. P., Computational algorithm for the sequential unconstrained minimization technique for nonlinear programming, Manage. Sci., 10, 4, 601-617 (1964) |
| [12] | Fowler, P. W.; Tarnai, T.; Kabai, S., Packing regular triplets of circles on a sphere, Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 461, 2060, 2355-2367 (2005) · Zbl 1206.52015 |
| [13] | Gáspár, Z., Some new multi-symmetric packings of equal circles on a 2-sphere, Acta Crystallogr. Sect. B: Struct. Sci., 45, 4, 452-453 (1989) |
| [14] | Grosso, A.; Jamali, A.; Locatelli, M.; Schoen, F., Solving the problem of packing equal and unequal circles in a circular container, J. Global Optim., 47, 1, 63-81 (2010) · Zbl 1190.90161 |
| [15] | Hardin, R. H.; Sloane, N. J.A.; Smith, W. D., Tables of spherical codes with icosahedral symmetry (2012), http://neilsloane.com/icosahedral.codes/ |
| [16] | Huang, H.-X.; Pardalos, P. M.; Shen, Z.-J., A point balance algorithm for the spherical code problem, J. Global Optim., 19, 4, 329-344 (2001) · Zbl 1020.94007 |
| [17] | Huang, W.; Ye, T., Global optimization method for finding dense packings of equal circles in a circle, European J. Oper. Res., 210, 3, 474-481 (2011) · Zbl 1213.90201 |
| [18] | Kottwitz, D. A., The densest packing of equal circles on a sphere, Acta Crystallogr. Sect. A, 47, 3, 158-165 (1991) · Zbl 1176.52007 |
| [19] | Lai, X.; Hao, J.-K.; Yue, D.; Lü, Z.; Fu, Z.-H., Iterated dynamic thresholding search for packing equal circles into a circular container, European J. Oper. Res., 299, 1, 137-153 (2022) · Zbl 1495.90157 |
| [20] | Leary, R. H., Global optimization on funneling landscapes, J. Global Optim., 18, 4, 367-383 (2000) · Zbl 0986.90038 |
| [21] | Lipschütz, H.; Skrodzki, M.; Reitebuch, U.; Polthier, K., Single-sized spheres on surfaces (S4), Comput. Aided Geom. Design, 85, Article 101971 pp. (2021) · Zbl 1469.65050 |
| [22] | 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 |
| [23] | Locatelli, M.; Schoen, F., Efficient algorithms for large scale global optimization: Lennard-Jones clusters, Comput. Optim. Appl., 26, 2, 173-190 (2003) · Zbl 1047.90050 |
| [24] | López, C. O.; Beasley, J. E., A heuristic for the circle packing problem with a variety of containers, European J. Oper. Res., 214, 3, 512-525 (2011) · Zbl 1226.90088 |
| [25] | López, C. O.; Beasley, J. E., A formulation space search heuristic for packing unequal circles in a fixed size circular container, European J. Oper. Res., 251, 1, 64-73 (2016) · Zbl 1346.90710 |
| [26] | Mackay, A.; Finney, J.; Gotoh, K., The closest packing of equal spheres on a spherical surface, Acta Crystallogr. Sect. A, 33, 1, 98-100 (1977) |
| [27] | Melnyk, T. W.; Knop, O.; Smith, W. R., Extremal arrangements of points and unit charges on a sphere: equilibrium configurations revisited, Can. J. Chem., 55, 10, 1745-1761 (1977) · Zbl 0367.52012 |
| [28] | 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 |
| [29] | Musin, O. R.; Tarasov, A. S., The strong thirteen spheres problem, Discrete Comput. Geom., 48, 1, 128-141 (2012) · Zbl 1269.52015 |
| [30] | Musin, O. R.; Tarasov, A. S., The Tammes problem for N=14, Experiment. Math., 24, 4, 460-468 (2015) · Zbl 1327.52042 |
| [31] | Newton, P. K.; Sakajo, T., Point vortex equilibria and optimal packings of circles on a sphere, Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 467, 2129, 1468-1490 (2011) · Zbl 1219.76009 |
| [32] | Robinson, R. M., Arrangement of 24 points on a sphere, Math. Ann., 144, 1, 17-48 (1961) · Zbl 0107.39802 |
| [33] | Saff, E. B.; Kuijlaars, A. B., Distributing many points on a sphere, Math. Intelligencer, 19, 1, 5-11 (1997) · Zbl 0901.11028 |
| [34] | Sloane, N. J.A.; Hardin, R. H.; Smith, W. D., Tables of spherical codes (2022), http://neilsloane.com/packings/index.html |
| [35] | Specht, E., High density packings of equal circles in rectangles with variable aspect ratio, Comput. Oper. Res., 40, 1, 58-69 (2013) · Zbl 1349.90723 |
| [36] | Szabó, P. G.; Markót, M. C.; Csendes, T.; Specht, E.; Casado, L. G.; García, I., (New Approaches to Circle Packing in a Square: with Program Codes. New Approaches to Circle Packing in a Square: with Program Codes, Optimization and its Applications, vol. 6 (2007), Springer Science & Business Media) · Zbl 1128.52012 |
| [37] | Tammes, P. M.L., On the origin of number and arrangement of the places of exit on the surface of pollen-grains, Recueil Travaux Bot. Néerlandais, 27, 1, 1-84 (1930) |
| [38] | Tarnai, T., Polymorphism in multisymmetric close packings of equal spheres on a spherical surface, Struct. Chem., 13, 3, 289-295 (2002) |
| [39] | Tarnai, T.; Fowler, P., Recent results in constrained packing of equal circles on a sphere, MATCH Commun. Math. Comput. Chem., 58, 2, 461-479 (2007) · Zbl 1141.52021 |
| [40] | Tarnai, T.; Fowler, P.; Kabai, S., Packing of regular tetrahedral quartets of circles on a sphere, Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 459, 2039, 2847-2859 (2003) · Zbl 1068.52031 |
| [41] | Tarnai, T.; Gáspár, Z., Improved packing of equal circles on a sphere and rigidity of its graph, (Mathematical Proceedings of the Cambridge Philosophical Society, Vol. 93 (1983), Cambridge University Press), 191-218 · Zbl 0515.52008 |
| [42] | Tarnai, T.; Gáspár, Z., Multi-symmetric close packings of equal spheres on the spherical surface, Acta Crystallogr. Sect. A, 43, 5, 612-616 (1987) · Zbl 1191.52020 |
| [43] | Teshima, Y.; Ogawa, T., Dense packing of equal circles on a sphere by the minimum-zenith method: symmetrical arrangement, Forma, 15, 4, 339-428 (2000) · Zbl 1002.52517 |
| [44] | Tibor, T., Spherical circle-packing in nature, practice and theory, Struct. Topol., 9, 39-58 (1984) · Zbl 0541.52008 |
| [45] | Wales, D. J.; Doye, J. P., Global optimization by basin-hopping and the lowest energy structures of Lennard-Jones clusters containing up to 110 atoms, J. Phys. Chem. A, 101, 28, 5111-5116 (1997) |
| [46] | Wales, D. J.; McKay, H.; Altschuler, E. L., Defect motifs for spherical topologies, Phys. Rev. B, 79, 22, Article 224115 pp. (2009) |
| [47] | Wales, D. J.; Ulker, S., Structure and dynamics of spherical crystals characterized for the Thomson problem, Phys. Rev. B, 74, 21, Article 212101 pp. (2006) |
| [48] | Wang, Z.; Xiang, C.; Zou, W.; Xu, C., MMA regularization: Decorrelating weights of neural networks by maximizing the minimal angles, Adv. Neural Inf. Process. Syst., 33, 19099-19110 (2020) |
| [49] | Yuan, Y.; Tole, K.; Ni, F.; He, K.; Xiong, Z.; Liu, J., Adaptive simulated annealing with greedy search for the circle bin packing problem, Comput. Oper. Res., Article 105826 pp. (2022) · Zbl 1520.90186 |
| [50] | Zeng, Z.-Z.; Yu, X.-G.; Chen, M.; Liu, Y.-Y., A memetic algorithm to pack unequal circles into a square, Comput. Oper. Res., 92, 47-55 (2018) · Zbl 1391.90539 |
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.
