Numerical methods for the construction of packings of different balls into convex compact sets

P. D. Lebedev ; A. L. Kazakov ; A. A. Lempert

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 26 (2020) no. 2, pp. 173-187

Résumé

The problem of an optimal packing of incongruent balls into a convex compact set is studied. We consider sets of balls whose radii are proportional to a specified parameter $r$. The aim is to maximize $r$. The maximum possible number of different types of balls is three. The problem belongs to the class of NP-hard problems and is solved numerically. We propose algorithms based on partitioning the given compact set into zones of influence of the centers of the elements (generalized Dirichlet zones). The partition is constructed using the optical-geometric approach developed by the authors earlier. A preliminary result is obtained and then improved by a geometric algorithm based on a step-by-step shift of points aimed at maximizing the radius of the current ball. To find the shift direction, we construct the superdifferential of the function equal to the maximum radius of a packed ball centered at the current point. We derive a formula for the maximum growth direction of this function. The developed algorithms are implemented as a software complex for the construction of a ball packing of a compact set. A numerical experiment was carried out for several examples. Packings with balls of different radii are constructed for containers of different shapes: a cube, a sphere, and a cylinder.

Détail

Keywords: packing, sphere, optimization, generalized Dirichlet zone, directional derivative, superdifferential, optical-geometric approach.

Bibliographie

[1] Castillo I., Kampas F.J., Pinter J.D., “Solving circle packing problems by global optimization: Numerical results and industrial applications”, European J. Operat. Research, 191:3 (2008), 786–802 | DOI | MR | Zbl

[2] Harary F., Randolph W., Mezey P.G., “A study of maximum unit-circle caterpillars – tools for the study of the shape of adsorption patterns”, Discrete Appl. Math., 67:1–3 (1996), 127–135 | DOI | MR | Zbl

[3] Wang J., “Packing of unequal spheres and automated radiosurgical treatment planning”, J. Combinator. Optim., 3:4 (1999), 453–463 | DOI | MR | Zbl

[4] Hales T., “Cannonballs and honeycombs”, Notices of the American Math. Soc., 47 (2000), 440–449 | MR | Zbl

[5] Chernov N., Stoyan Yu., Romanova T., “Mathematical model and efficient algorithms for object packing problem”, Computational Geometry, 43:5 (2010), 535–553 | DOI | MR | Zbl

[6] Stoyan Y.G., Scheithauer G. Yaskov G.N., “Packing Unequal Spheres into Various Containers”, Cybernetics Syst. Anal., 52:3 (2016), 419–426 | DOI | MR | Zbl

[7] Khlud O.M., Yaskov G.N., “Packing homothetic spheroids into a larger spheroid with the jump algorithm”, Control, Navigation and Communication Systems, 6:46 (2017), 131–135

[8] Kubach T., Bortfeldt A., Tilli T., Gehring H., “Greedy algorithms for packing unequal spheres into a cuboidal strip or a cuboid”, Asia Pacific J. Operat. Research, 28 (2011), 739–753 | DOI | MR | Zbl

[9] Huang W.Q., Li Y., Akeb H., Li C.M., “Greedy algorithms for packing unequal circles into a rectangular container”, J. Operat. Research Soc., 56:5 (2005), 539–548 | DOI | Zbl

[10] Hifi M., Yousef L., “Width beam and hill-climbing strategies for the three-dimensional sphere packing problem”, Annals of Computer Science and Information Systems, v. 2, Ser. Polish Information Processing Society, Proc. Federated Conf. on Computer Science and Information Systems, Warsaw, 2014, 421–428 | DOI | MR

[11] Zeng Z.Z., Huang W.Q., Xu R.C., Fu Z.H., “An algorithm to packing unequal spheres in a larger sphere”, Advanced Materials Research, 546–547 (2012), 1464–1469 | DOI

[12] Yamada S., Kanno J., Miyauchi M., “Multi-sized sphere packing in containers: Optimization formula for obtaining the highest density with two different sized spheres”, IPSJ Online Transactions, 4 (2011), 126–133 | DOI

[13] Kazakov A.L., Lebedev P.D., “Algoritmy postroeniya optimalnykh upakovok dlya kompaktnykh mnozhestv na ploskosti”, Vychisl. metody i programmirovanie, 16:3 (2015), 307–317

[14] Ushakov V.N., Lebedev P.D., Lavrov N.G., “Algoritmy postroeniya optimalnykh upakovok v ellipsy”, Vest. YuUrGU. Ser. Mat. modelirovanie i programmirovanie, 10:3 (2017), 67–79 | DOI | Zbl

[15] Kazakov A.L. Lempert A.A. Ta T.T., “The sphere packing problem into bounded containers in three-dimension non-euclidean space”, IFAC PAPERSONLINE, 51:32 (2018), 782–787 | DOI

[16] Lebedev P.D., Lavrov N.G., “Algoritmy postroeniya optimalnykh upakovok v ellipsoidy”, Izv. In-ta matematiki i informatiki UdGU, 52 (2018), 59–74 | DOI | MR

[17] Tot L.F., Raspolozheniya na ploskosti, na sfere i v prostranstve, Fizmatlit, Moskva, 1958, 365 pp.

[18] Subbotin A.I., Obobschennye resheniya uravnenii v chastnykh proizvodnykh pervogo poryadka. Perspektivy dinamicheskoi optimizatsii, In-t kompyuternykh tekhnologii, Moskva; Izhevsk, 2003, 336 pp.

[19] Demyanov V.F., Vasilev L.V., Nedifferentsiruemaya optimizatsiya, Nauka, Moskva, 1981, 384 pp.

[20] Polovinkin E.S., Balashov M.V., Elementy vypuklogo i silno vypuklogo analiza, Fizmatlit, Moskva, 2004, 416 pp.

[21] Tatarevic M., On limits of dense packing of equal spheres in a cube, [e-resource], 2015, 9 pp., arXiv: 1503.07933 | MR

[22] Stoyan Y.G., Yaskov, G., “Packing congruent hyperspheres into a hypersphere”, J. Global Optim., 52:4 (2012), 855–868 | DOI | MR | Zbl

[23] Stoyan Yu.G., Yaskov, G., “Packing identical spheres into a cylinder”, Intern. Trans. Oper. Research, 17:1 (2010), 51–70 | DOI | MR | Zbl

[24] Bukharov D.S., Kazakov A.L., “Programmnaya sistema “Vigolt” dlya resheniya zadach optimizatsii, voznikayuschikh v transportnoi logistike”, Vychislitelnye metody i programmirovanie: novye vychislitelnye tekhnologii, 13:2 (2012), 65–74