Methodology to Solve Multi-Dimentional Sphere Packing Problems
Keywords:
sphere, hypersphere, sphere packing, knapsack problem, open dimension problem, nonlinear optimizationAbstract
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.
References
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).
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
Hifi, M. & M'Hallah, R. (2009). A. literature review on circle and sphere packing problems: models and methodologies. Advances in Operations Research, vol. 2009, pp. 1–22. https://doi.org/10.1155/2009/150624
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
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
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–8. https://doi.org/10.1155/2015/142987
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
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
Torquato, S. & Stillinger, F. H. (2006). Exactly solvable disordered sphere-packing model in arbitrary-dimensional Euclidean spaces. Physical Review E, vol. 73, iss. 3, 031106. https://doi.org/10.1103/PhysRevE.73.031106
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
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–627. https://doi.org/10.1016/j.ejor.2015.09.001
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
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
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
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
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
Yakovlev, S. 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).
Stoyan, Yu. 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
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.
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
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
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
Yaskov, G. N. (2009). Upakovka bolshogo chisla kongruentnykh krugov v tsilindre [Packing a great number of spheres into a cylinder]. Dopov. Nac. akad. nauk Ukr. −Reports of the National Academy of Sciences of Ukraine, no. 12, pp. 43–49 (in Russian).
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
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
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
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, no. 25, pp. 119−122 (in Russian).
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
Stoyan, Yu. & Yaskov, G. (2014). Packing unequal circles into a strip of minimal length with a jump algorithm. Optimization Letters, vol. 8, iss. 3, pp. 949–970. https://doi.org/10.1007/s11590-013-0646-1
Yaskov, G. N. (2008). Random packing of identical spheres into a cylindrical container. Systemy obrobky informatsii, iss. 1, no. 68, pp. 128−130.
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
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
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
Torquato, S., Uche, O. U., & Stillinger, F. 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
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.
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
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 6th int. sc. and techn. seminar]. Kobleve, pp. 143–144 (in Russian).
Downloads
Published
Issue
Section
License
Copyright (c) 2019 G. N. Yaskov
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.
All authors agree with the following conditions:
- The authors reserve the right to claim authorship of their work and transfer to the journal the right of first publication of the work under the license agreement (the agreement).
- Authors have a right to conclude independently additional agreement on non-exclusive spreading the work in the form in which it was published by the jpurnal (for example, to place the work in institution repository or to publish as a part of a monograph), providing a link to the first publication of the work in this journal.
- Journal policy allows authors to place the manuscript in the Internet (for example, in the institution repository or on a personal web sites) both before its submission to the editorial board and during its editorial processing, as this ensures the productive scientific discussion and impact positively on the efficiency and dynamics of citation of published work (see The Effect of Open Access).
