METHODOLOGY TO SOLVE MULTI-DIMENTIONAL SPHERE PACKING PROBLEMS

Author

Georgiy N. Yaskov, A. Podgorny Institute of Mechanical Engineering Problems of NASU (2/10, Pozharskyi Str., Kharkiv, 61046, Ukraine), e-mail: yaskov@ipmach.kharkov.ua, ORCID: 0000-0002-1476-1818

Abstract

This paper discusses the problem of optimally packing spheres of various dimensions into containers of arbitrary geometrical shapes. According to the international classification, this problem belongs to Sphere Packing Problems (SPPs). The problem is to pack a set of spheres (circles, hyperspheres) with given radii into a container with given metric characteristics. The aim of this work is to create an integrated methodology for solving SPPs. The basic formulations of the problem are presented: in the form of the knapsack problem (KP), open dimension problem (ODP), and their corresponding mathematical models. The solution strategy selection is influenced by the form of problem statement, dimension of the space where the spheres are to be packed, metric peculiarities of the spheres (equal or unequal), number of the spheres to be packed, geometric shape of the container, presence of technological restraints, and count time limit. The structural elements of the methodology are mathematical models, methods for constructing initial packings, and methods of local and global optimization. In developing the solution method, we construct the initial feasible packings by using both the random and lattice methods, using a greedy algorithm and solving an auxiliary nonlinear programming problem. As local optimization methods, we consider the modifications of the feasible direction method, interior point method, Lagrange multiplier method, and method of optimization in groups of variables. For global optimization, we use the method of enumerating the subsets of spheres of a given set and method of enumerating the extreme points of the feasible region, which are implemented by using the branch and bound algorithm, the modifications of the decremental neighborhood search method, method of smooth transition from one local minimum to another by increasing problem dimensionality and introducing additional variable metric characteristics, solution method implemented as a sequence of non-linear programming problems of increasing dimensionality, and a multi-start method. Strategies for solving different SPP statements are proposed.

Keywords: sphere, hypersphere, sphere packing, knapsack problem, open dimension problem, nonlinear optimization.

Full text: Download in PDF

References

1. Stoyan, Yu. G. & Yakovlev, S. V. (1986). Matematicheskiye modeli i optimizatsionnyye metody geometricheskogo proyektirovaniya [Mathematical models and optimisation methods of geometric design]. Kiyev: Naukova Dumka, 268 p. (in Russian).
2. Waescher, G. & Haussner, H. (2007). An improved typology of cutting and packing problems. European Journal of Operational Research, vol. 183, iss. 5, pp. 1109–1130. https://doi.org/10.1016/j.ejor.2005.12.047
3. Hifi, M. & M’Hallah, R. (2009). A. literature review on circle and sphere packing problems: models and methodologies. Advances in Operations Research, 2009, pp. 1–22. https://doi.org/10.1155/2009/150624
4. Snoj, L. & Ravnik, M. (2006). Effect of packing fraction variations on the multiplication factor in pebble-bed nuclear reactors. Kerntechnik, vol. 71, no. 4, pp. 208–213. https://doi.org/10.3139/124.100295
5. Leary, M., Merli, L., Torti, F., Mazur, M., & Brandt, M. (2014). Optimal topology for additive manufacture: A method for enabling additive manufacture of support-free optimal structures. Materials and Design, vol. 63, pp. 678–690. https://doi.org/10.1016/j.matdes.2014.06.015
6. Blyuss, O., Koriashkina, L., Kiseleva, E., & Molchanov, R. (2015). Optimal Placement of Irradiation Sources in the Planning of Radiotherapy: Mathematical Models and Methods of Solving. Computational and Mathematical Methods in Medicine, vol. 2015, pp. 1– https://doi.org/10.1155/2015/142987
7. Agapie, S. C. & Whitlock, P. A. (2010). Random packing of hyperspheres and Marsaglia’s parking lot test. Monte Carlo Methods and Applications, vol. 16, iss. 3–4, pp. 197–209.  https://doi.org/10.1515/mcma.2010.019
8. Conway, J. H. & Sloane, N. J. (1999). A sphere packings, lattices, and groups. New York: Springer-Verlag, 706 p. https://doi.org/10.1007/978-1-4757-6568-7
9. Torquato, S. & Stillinger, F. H. (2006). Exactly solvable disordered sphere-packing model in arbitrary-dimensional Euclidean spaces. Physical Review E, vol. 73, iss. 3, https://doi.org/10.1103/PhysRevE.73.031106
10. Hifi, M. & Yousef, L. (2015). A dichotomous search-based heuristic for the three-dimensional packing problem. Cogent Engineering, vol. 2 (1), pp. 1–15. https://doi.org/10.1080/23311916.2014.994257
11. Zeng, Z., Yu, X., He, K., Huang, W., & Fu, Z. (2016). Iterated tabu search and variable neighborhood descent for packing unequal circles into a circular container. European Journal of Operational Research, vol. 250, iss. 2, pp. 615– https://doi.org/10.1016/j.ejor.2015.09.001
12. Sutou, A. & Dai, Y. (2002). Global Optimization Approach to Unequal Global Optimization Approach to Unequal Sphere Packing Problems in 3D. Journal of Optimization Theory and Applications, vol. 114, iss. 3, pp. 671–694. https://doi.org/10.1023/A:1016083231326
13. Zeng, Z. Z., Huang, W. Q., Xu, R. C., & Fu, Z. H. (2012). An algorithm to packing unequal spheres in a larger sphere. Advanced Materials Research, vol. 546–547, pp. 1464–1469. https://doi.org/10.4028/www.scientific.net/AMR.546-547.1464
14. Kubach, T., Bortfeldt, A., Tilli, T., & Gehring, H. (2011). Greedy algorithms for packing unequal spheres into a cuboidal strip or a cuboid. Asia-Pacific Journal of Operational Research, vol. 28, no. 06, pp. 739–753. https://doi.org/10.1142/S0217595911003326
15. Birgin, E. G. & Sobral, F. N. C. (2008). Minimizing the object dimensions in circle and sphere packing problems. Computers & Operations Research, vol. 35, iss. 7, pp. 2357–2375. https://doi.org/10.1016/j.cor.2006.11.002
16. Stoyan, Yu. & Yaskov, G. (2012). Packing congruent hyperspheres into a hypersphere. Journal of Global Optimization, vol. 52, iss. 4, pp. 855–868. https://doi.org/10.1007/s10898-011-9716-z
17. Yakovlev, V., Yaskov, G. N., & Korobchinskiy, K. P. (2017). O metodakh peremennogo radiusa v zadache upakovki sharov v konteynery. [On variable radius methods in problems of packing spheres into containers]. Pytannia prykl. matematyky i mat. modeliuvannia: zb. nauk. pr. − Problems of Applied Mathematics and Mathematical Modeling. Collection of scientific papers, Dnirpo: LIRA, iss. 17, pp. 265−272 (in Russian).
18. Stoyan, G., Scheithauer, G., & Yaskov, G. N. (2016). Packing unequal spheres into various containers. Cybernetics and Systems Analysis, vol. 52, iss. 3, pp. 419−426. https://doi.org/10.1007/s10559-016-9842-1
19. Yaskov, G. N. (2014). Packing non-equal hyperspheres into a hypersphere of minimal radius. Journal of Mechanical Engineering, vol. 17, no. 1, pp. 48–53.
20. Stoyan, Y. & Yaskov, G. (1998). Mathematical model and solution method of optimization problem of placement of rectangles and circles taking into account special constraints. International Transactions in Operational Research, vol. 5, no. 1, pp. 45–57. https://doi.org/10.1111/j.1475-3995.1998.tb00101.x
21. Visscher, W. M. & Bolsterli, M. (1972). Random packing of equal and unequal spheres in two and three dimensions. Nature, vol. 239, pp. 504–507. https://doi.org/10.1038/239504a0
22. Mueller, G. E. (2005). Numerically packing spheres in cylinders. Powder Technology, vol. 159, iss. 2, pp. 105–110. https://doi.org/10.1016/j.powtec.2005.06.002
23. Yaskov, G. N. (2009). Upakovka bolshogo chisla kongruentnykh krugov v tsilindre [Packing a great number of spheres into a cylinder]. Nac. akad. nauk Ukr. −Reports of the National Academy of Sciences of Ukraine, no. 12, pp. 43–49 (in Russian).
24. Chernov, N., Stoyan, Yu., & Romanova, T. (2015). Mathematical model and efficient algorithms for object packing problem. Computational Geometry, vol. 43, iss. 5, pp. 535–553. https://doi.org/10.1016/j.comgeo.2009.12.003
25. Stoyan, Y., Pankratov, A., & Romanova, T. (2016). Quasi-phi-functions and optimal packing of ellipses. Journal of Global Optimization, vol. 65, iss. 2, pp. 283–307. https://doi.org/10.1007/s10898-015-0331-2
26. Stoyan, Y. & Yaskov, G. (2012). Packing equal circles into a circle with circular prohibited areas. International Journal of Computer Mathematics, vol. 89, iss. 10, pp. 1355–1369. https://doi.org/10.1080/00207160.2012.685468
27. Yaskov, G. N. (2010). Metod resheniya zadachi razmeshcheniya raznykh krugov s perspektivnym vyborom nachalnykh tochek [Method of solving the problem of packing different circles with choice of perspective initial points]. Zb. nauk. prats Kharkivskogo universitetu povitryanyh syl − Scientific Works of Kharkov National Air Force University, iss. 3, 25, pp. 119−122 (in Russian).
28. Wächter, A. & Biegler, L. T. (2006). On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming. Mathematical Programming, vol. 106, iss. 1, pp. 25–57. https://doi.org/10.1007/s10107-004-0559-y
29. Stoyan, Yu. & Yaskov, G. (2014). Packing unequal circles into a strip of minimal length with a jump Optimization Letters, vol. 8, iss. 3, pp. 949–970. https://doi.org/10.1007/s11590-013-0646-1
30. Yaskov, G. N. (2008). Random packing of identical spheres into a cylindrical container. Systemy obrobky informatsii, iss. 1, 68, pp. 128−130.
31. Stoyan, Y. & Chugay, A. (2009). Packing cylinders and rectangular parallelepipeds with distances between them into a given region. European Journal of Operational Research, vol. 197, iss. 2, pp. 446–455. https://doi.org/10.1016/j.ejor.2008.07.003
32. Gondzio, J. (1995). HOPDM (version 2.12) – a fast LP solver based on a primal-dual interior point method. European Journal of Operational Research, vol. 85, iss. 1, pp. 221–225. https://doi.org/10.1016/0377-2217(95)00163-K
33. Meszaros, C. (2008). On numerical issues of interior point methods. SIAM Journal on Matrix Analysis and Applications, vol. 30, iss. 1, pp. 223–235. https://doi.org/10.1137/050633354
34. Torquato, S., Uche, O. U., & Stillinger, H. (2006). Random sequential addition of hard spheres in high Euclidean dimensions. Physical Review E, vol. 74, iss. 6, pp. 061308. https://doi.org/10.1103/PhysRevE.74.061308
35. Stoyan, Y., Scheithauer, G., & Yaskov, G. (2003). Packing of various radii solid spheres into a parallelepiped. Central European Journal of Operations Research, vol. 11, no. 4, pp. 389–407.
36. Stoyan, Y. & Yaskov, G. (2008). Packing identical spheres into a rectangular parallelepiped. In: Bortfeldt, A., Homberger, J., Kopfer, H., Pankratz, G., & Strangmeier, R. (eds) Intelligent Decision Support. Gabler, pp. 47–67. https://doi.org/10.1007/978-3-8349-9777-7_4
37. Yaskov, G. N. (2007). Derevo resheniy dlya zadachi razmeshcheniya neravnykh sharov v share zadannogo radiusa. Informatsiini systemy i tekhnologii IST-2017: pr 6-i mizhnar. nauk.-tekhn. konf. (Kobleve, 11–16 ver. 2017) [Solution tree for the problem of packing unequal spheres in a sphere of a given radius. Informational systems and technologies IST-2017: Proceedings of 6^th sc. and techn. seminar]. Kobleve, pp. 143–144 (in Russian).

Received 14 January 2019

Published 30 March 2019