Search Advanced

Mathematical Biosciences and Engineering

2020, Volume 17, Issue 6: 6601-6630. doi: 10.3934/mbe.2020344
Previous Article Next Article
Research article Special Issues

Optimized packing multidimensional hyperspheres: a unified approach

  • 1.
    Institute for Mechanical Engineering Problems of the National Academy of Sciences of Ukraine, 2/10 Pozharskogo st., Kharkiv 61046, Ukraine
  • 2.
    Kharkiv National University of Radioelectronics, 14 Nauky ave., Kharkiv 61166, Ukraine
  • 3.
    Kharkiv Aviation Institute, National Aerospace University, 17 Chkalov st., Kharkiv 61070, Ukraine
  • 4.
    Computing Center, Russian Academy of Sciences, Vavilov 40, Moscow, Russia
  • 5.
    Nuevo Leon State University, Monterrey, Nuevo Leon, CP 66455, Mexico
  • 6.
    Technological Institute of Sonora (ITSON), Obregón-City, Sonora, Mexico
  • Received: 20 June 2020 Accepted: 07 September 2020 Published: 28 September 2020

  • In this paper an optimized multidimensional hyperspheres packing problem (HPP) is considered for a bounded container. Additional constraints, such as prohibited zones in the container or minimal allowable distances between spheres can also be taken into account. Containers bounded by hyper- (spheres, cylinders, planes) are considered. Placement constraints (non-intersection, containment and distant conditions) are formulated using the phi-function technique. A mathematical model of HPP is constructed and analyzed. In terms of the general typology for cutting & packing problems, two classes of HPP are considered: open dimension problem (ODP) and knapsack problem (KP). Various solution strategies for HPP are considered depending on: a) objective function type, b) problem dimension, c) metric characteristics of hyperspheres (congruence, radii distribution and values), d) container's shape; e) prohibited zones in the container and/or minimal allowable distances. A solution approach is proposed based on multistart strategies, nonlinear programming techniques, greedy and branch-and-bound algorithms, statistical optimization and homothetic transformations, as well as decomposition techniques. A general methodology to solve HPP is suggested. Computational results for benchmark and new instances are presented.

    Citation: Yuriy Stoyan, Georgiy Yaskov, Tatiana Romanova, Igor Litvinchev, Sergey Yakovlev, José Manuel Velarde Cantú. Optimized packing multidimensional hyperspheres: a unified approach[J]. Mathematical Biosciences and Engineering, 2020, 17(6): 6601-6630. doi: 10.3934/mbe.2020344

    Related Papers:

  • In this paper an optimized multidimensional hyperspheres packing problem (HPP) is considered for a bounded container. Additional constraints, such as prohibited zones in the container or minimal allowable distances between spheres can also be taken into account. Containers bounded by hyper- (spheres, cylinders, planes) are considered. Placement constraints (non-intersection, containment and distant conditions) are formulated using the phi-function technique. A mathematical model of HPP is constructed and analyzed. In terms of the general typology for cutting & packing problems, two classes of HPP are considered: open dimension problem (ODP) and knapsack problem (KP). Various solution strategies for HPP are considered depending on: a) objective function type, b) problem dimension, c) metric characteristics of hyperspheres (congruence, radii distribution and values), d) container's shape; e) prohibited zones in the container and/or minimal allowable distances. A solution approach is proposed based on multistart strategies, nonlinear programming techniques, greedy and branch-and-bound algorithms, statistical optimization and homothetic transformations, as well as decomposition techniques. A general methodology to solve HPP is suggested. Computational results for benchmark and new instances are presented.


    加载中


    [1] T. Cremer, M. Cremer, Chromosome territories, Cold Spring Harbor Perspect. Biol., 2 (2010), 1-22.
    [2] A. Raj, Y. Chen, The wiring economy principle: connectivity determines anatomy in the human brain, PLoS ONE, 6 (2011), 1-11.
    [3] M. Rivera-Alba, S. N. Vitaladevuni, Y. Mishchenko, Z. Lu, S. Takemura, L. Scheffer, et al., Wiring economy and volume exclusion determine neuronal placement in the drosophila brain, Curr. Biol., 21 (2011), 2000-2005.
    [4] Y. Karklin, E. P. Simoncelli, Efficient coding of natural images with a population of noisy Linear-Nonlinear neurons, Advances in neural information processing systems, 2011.
    [5] J. Wang, Packing of unequal spheres and automated radiosurgical treatment planning, J. Comb. Optim., 3 (1999), 453-463. doi: 10.1023/A:1009831621621
    [6] A. Sutou, Y. Day, Global optimization approach to unequal sphere packing problems in 3D, J. Optim. Theory Appl., 114 (2002), 671-694. doi: 10.1023/A:1016083231326
    [7] A. S. Shirokanev, D. V. Kirsh, N. Yu. Ilyasova, A. V. Kupriyanov, Investigation of algorithms for coagulate arrangement in fundus images, Comput. Opt., 42 (2018), 712-721. doi: 10.18287/2412-6179-2018-42-4-712-721
    [8] K. Sugihara, M. Sawai, H. Sano, D. Kim, D, Kim, Disk packing for the estimation of the size of a wire bundle, Jpn. J. Ind. Appl. Math., 21 (2004), 259-278.
    [9] K. A. Dowsland, M. Gilbert, G. Kendall, A local search approach to a circle cutting problem arising in the motor cycle industry, J. Oper. Res. Soc., 58 (2007), 429-438. doi: 10.1057/palgrave.jors.2602170
    [10] Y. Cui, D. Xu, Strips minimization in two-dimensional cutting stock of circular items, Comput. Oper. Res., 37 (2010), 621-629. doi: 10.1016/j.cor.2009.06.005
    [11] I. Yanchevskyi, R. Lachmayer, I. Mozgova, R. B. Lippert, G. Yaskov, T. Romanova, et al., Circular packing for support-free structures, EUDL, 2020 (2020), 1-10.
    [12] T. Romanova, Y. Stoyan, A. Pankratov, I. Litvinchev, K. Avramov, M. Chernobryvko, et al., Optimal layout of ellipses and its application for additive manufacturing, Int. J. Prod. Res., 2019 (2019), 1-16.
    [13] T. Romanova, Y. Stoyan, A. Pankratov, I. Litvinchev, I. Yanchevsky, I. Mozgova, Optimal Packing in Additive Manufacturing, IFAC-PapersOnLine, 52 (2019), 2758-2763. doi: 10.1016/j.ifacol.2019.11.625
    [14] G. E. Mueller, Numerically packing spheres in cylinders, Powder Technol., 159 (2005), 105-110. doi: 10.1016/j.powtec.2005.06.002
    [15] S. S. Halkarni, A. Sridharan, S. V. Prabhu, Experimental investigation on effect of random packing with uniform sized spheres inside concentric tube heat exchangers on heat transfer coefficient and using water as working medium, Int. J. Therm. Sci., 133 (2018), 341-356. doi: 10.1016/j.ijthermalsci.2018.05.023
    [16] L. Burtseva, A. Pestryakov, R. Romero, B. Valdez, V. Petranovskii, Some aspects of computer approaches to simulation of bimodal sphere packing in material engineering, Adv. Mater. Res., 1040 (2014), 585-591. doi: 10.4028/www.scientific.net/AMR.1040.585
    [17] D. Frenkel, Computer simulation of hard-core models for liquid crystals, Mol. Phys., 60 (1987), 1-20. doi: 10.1080/00268978700100011
    [18] S. Yamada, J. Kanno, M. Miyauchi, Multi-sized sphere packing in containers: optimization formula for obtaining the highest density with two different sized spheres, Inf. Media Technol., 6 (2011), 493-500.
    [19] Z. Duriagina, I. Lemishka, I. Litvinchev, J. A. Marmolejo, A. Pankratov, T. Romanova, et al., Optimized filling of a given cuboid with spherical powders for additive manufacturing, J. Oper. Res. Soc. China, (2020).
    [20] A. J. Otaru, A. R. Kennedy, The permeability of virtual macroporous structures generated by sphere packing models: Comparison with analytical models, Scr. Mater., 124 (2016), 30-33. doi: 10.1016/j.scriptamat.2016.06.037
    [21] S. Flaischlen, G. D. Wehinger, Synthetic packed-bed generation for CFD simulations: Blender vs. STAR-CCM+, ChemEngineering, 3 (2019), 1-22.
    [22] C. R. A. Abreu, R. Macias-Salinas, F. W. Tavares, M. Castier, A Monte Carlo simulation of the packing and segregation of spheres in cylinders, Braz. J. Chem. Eng., 16 (1999), 395-405. doi: 10.1590/S0104-66321999000400008
    [23] J. H. Conway, N. J. A. Sloane, Sphere packings, lattices and groups, Springer-Verlag, New York, 2013.
    [24] D. Cullina, N. Kiyavash, Generalized sphere-packing bounds on the size of codes for combinatorial channels, IEEE Trans. Inf. Theory, 62 (2016), 4454-4465. doi: 10.1109/TIT.2016.2565578
    [25] L. Fejes, Ü ber einem geometrischen Satz (German), Math. Z., 46 (1940), 83-85. doi: 10.1007/BF01181430
    [26] T. C. Hales, A proof of the Kepler conjecture, Ann. Math., 162 (2005), 1065-1185. doi: 10.4007/annals.2005.162.1065
    [27] M. S. Viazovska, The sphere packing problem in dimension 8, Ann. Math., 185 (2017), 991-1015. doi: 10.4007/annals.2017.185.3.7
    [28] Z. Z. Zeng, W. Q. Huang, R. C. Xu, Z. H. Fu, An algorithm to packing unequal spheres in a larger sphere, Adv. Mater. Res., 546-547 (2012), 1464-1469.
    [29] M. Hifi, L. Yousef, A local search-based method for sphere packing problems, Eur. J. Oper. Res., 274 (2019), 482-500. doi: 10.1016/j.ejor.2018.10.016
    [30] A. A. Kovalenko, T. E. Romanova, P. I. Stetsyuk, Balance layout problem for 3D-objects: mathematical model and solution methods, Cybern. Syst. Anal., 51 (2015), 556-565. doi: 10.1007/s10559-015-9746-5
    [31] T. Romanova, I. Litvinchev, I. Grebennik, A. Kovalenko, I. Urniaieva, S. Shekhovtsov, Packing convex 3D objects with special geometric and balancing conditions, in Intelligent Computing and Optimization, ICO 2019. Advances in Intelligent Systems and Computing, Springer, Cham, 2020.
    [32] P. I. Stetsyuk, T. E. Romanova, G. Scheithauer, On the global minimum in a balanced circular packing problem, Optim. Lett., 10 (2016), 1347-1360. doi: 10.1007/s11590-015-0937-9
    [33] Y. Stoyan, T. Romanova, A. Pankratov, A. Kovalenko, P. Stetsyuk, Balance layout problems: mathematical modeling and nonlinear optimization, in Space Engineering. Springer Optimization and Its Applications (eds. G. Fasano, J. Pintér), Springer, Cham, 2016,369-400.
    [34] I. V. Grebennik, A. A. Kovalenko, T. E. Romanova, I. A. Urniaieva, S. B. Shekhovtsov, Combinatorial configurations in balance layout optimization problems, Cybern. Syst. Anal., 54 (2018), 221-231. doi: 10.1007/s10559-018-0023-2
    [35] N. Chernov, Y. Stoyan, T. Romanova, Mathematical model and efficient algorithms for object packing problem, Comput. Geom., 43 (2010), 535-553. doi: 10.1016/j.comgeo.2009.12.003
    [36] B. Chazelle, H. Edelsbrunner, L. J. Guibas, The complexity of cutting complexes, Discrete Comput. Geom., 4 (1989), 139-181. doi: 10.1007/BF02187720
    [37] G. Wä scher, H. Hauß ner, H. Schumann, An improved typology of cutting and packing problems, Eur. J. Oper. Res., 183 (2007), 1109-1130. doi: 10.1016/j.ejor.2005.12.047
    [38] L. J. P. Araújo, E. Ö zcan, J. A. D. Atkin, M. Baumers, Analysis of irregular three-dimensional packing problems in additive manufacturing: a new taxonomy and dataset, Int. J. Prod. Res., 57 (2019), 5920-5934. doi: 10.1080/00207543.2018.1534016
    [39] J. L. Lagrange, Recherches d'arithmétique, (French), Nouv. Mém. Acad. Roy. Soc. Belles Lettres, 1773 (1773), 265-312.
    [40] C. F. Gauss, Untersuchungen über die Eigenschaften der positiven ternä ren quadratischen Formen von Ludwig August Seber, (in German), J. Reine Angew. Math., 20 (1840), 312-320.
    [41] Y. G. Stoyan, Mathematical methods for geometric design, Advances in CAD/CAM, Proceedings of PROLAMAT'82, Leningrad, Amsterdam, 1982, 67-86.
    [42] S. J. Wright, Coordinate descent algorithms, Math. Program., 151 (2015), 3-34. doi: 10.1007/s10107-015-0892-3
    [43] W. Q. Huang, Y. Li, H. Akeb, C. M. Li, Greedy algorithms for packing unequal circles into a rectangular container, J. Oper. Res. Soc., 56 (2005), 539-548. doi: 10.1057/palgrave.jors.2601836
    [44] E. G. Birgin, J. M. Gentil, New and improved results for packing identical unitary radius circles within triangles, rectangles and strips, Comput. Oper. Res., 37 (2010), 1318-1327.
    [45] S. I. Galiev, M. S. Lisafina, Linear models for the approximate solution of the problem of packing equal circles into a given domain, Eur. J. Oper. Res., 230 (2013), 505-514. doi: 10.1016/j.ejor.2013.04.050
    [46] I. Litvinchev, L. Infante, E. L. Ozuna, Approximate circle packing in a rectangular container: integer programming formulations and valid inequalities, in Computational Logistics, ICCL 2014, LNCS (eds. R. G. González-Ramírez, et al.), 2014, 47-60.
    [47] I. Litvinchev, L. Infante, L. Ozuna, Packing circular like objects in a rectangular container, J. Comput. Syst. Sci. Int., 54 (2015), 259-267. doi: 10.1134/S1064230715020070
    [48] Y. G. Stoyan, M. V. Zlotnik, A. M. Chugay, Solving an optimization packing problem of circles and non-convex polygons with rotations into a multiply connected region, J. Oper. Res. Soc., 63 (2012), 379-391. doi: 10.1057/jors.2011.41
    [49] Y. Stoyan, G. Yaskov, Packing equal circles into a circle with circular prohibited areas, Int. J. Comput. Math., 89 (2012), 1355-1369. doi: 10.1080/00207160.2012.685468
    [50] X. Zhuang, L. Yan, L. Chen, Packing equal circles in a damaged square, in 2015 International Joint Conference on Neural Networks (IJCNN), Killarney, 2015, 1-6.
    [51] C. O. López, J. E. Beasley, Packing a fixed number of identical circles in a circular container with circular prohibited areas, Optim. Lett., 13 (2019), 1449-1468. doi: 10.1007/s11590-018-1351-x
    [52] H. Akeb, M. Hifi, Algorithms for the circular two-dimensional open dimension problem, Int. Trans. Oper. Res., 15 (2008), 685-704. doi: 10.1111/j.1475-3995.2008.00655.x
    [53] H. Akeb, M. Hifi, S. Negre, An augmented beam search-based algorithm for the circular open dimension problem, Comput. Ind. Eng., 61 (2011), 373-381. doi: 10.1016/j.cie.2011.02.009
    [54] M. Hifi, R. M'Hallah, A literature review on circle and sphere packing problems: models and methodologies, Adv. Oper. Res., 2009 (2009).
    [55] E. Specht, www.packomania.com, 2018. Available from: http://packomania.com.
    [56] I. Kepleri, S. C. Maiest, Mathematici Strena Seu De Niue Sexangula (Latin), Apud Godefridum Tampach, 2014.
    [57] E. G. Birgin, F. N. C. Sobral, Minimizing the object dimensions in circle and sphere packing problems, Comput. Oper. Res., 35 (2008), 2357-2375. doi: 10.1016/j.cor.2006.11.002
    [58] T. Kubach, A. Bortfeldt, T. Tilli, H. Gehring, Greedy algorithms for packing unequal spheres into a cuboidal strip or a cuboid, Asia Pac. J. Oper. Res., 28 (2011), 739-753. doi: 10.1142/S0217595911003326
    [59] J. Liu, Y. Yao, Yu. Zheng, H. Geng, G. Zhou, An effective hybrid algorithm for the circles and spheres packing problems, Combinatorial Optimization and Applications Lecture Notes in Computer Science, COCOA, 2009,135-144.
    [60] Y. G. Stoyan, G. Scheithauer, G. N. Yaskov, Packing unequal Spheres into Various Containers, Cybern. Syst. Anal., 52 (2016), 419-426. doi: 10.1007/s10559-016-9842-1
    [61] Y. Stoyan, G. Yaskov, Packing unequal circles into a strip of minimal length with a jump algorithm, Optim. Lett., 8 (2014), 949-970. doi: 10.1007/s11590-013-0646-1
    [62] A. Kazakov, A. Lempert, T. Thanh Ta, On the algorithm for equal balls packing into a multi-connected set, Proceeding of the VIth International Workshop Critical Infrastructures: Contingency Management, Intelligent, Agent-Based, Cloud Computing and Cyber Security (IWCI 2019), 2019.
    [63] L. Martínez, R. Andrade, E. G. Birgin, J. M. Martínez, Packmol: A package for building initial configurations for molecular dynamics simulations, J. Comput. Chem., 30 (2009), 2157-2164.
    [64] J. M. Martínez, L. Martínez, Packing optimization for automated generation of complex system's initial configurations for molecular dynamics and docking, J. Comput. Chem., 24 (2003), 819-825.
    [65] Institute of Chemistry and Institute of Mathematics, University of Campinas, Institute of Mathematics and Statistics, University of São Paulo, PACKMOL, Initial configurations for Molecular Dynamics Simulations by packing optimization, 2020. Available from: http://m3g.iqm.unicamp.br/packmol/home.shtml.
    [66] L. Burtseva, B. Valdez Salas, F. Werner, V. Petranovskii, Packing of monosized spheres in a cylindrical container: models and approaches, Rev. Mex. Fís., 61 (2015), 20-27.
    [67] L. Burtseva, B. Valdez Salas, R. Romero, F. Werner, Recent advances on modelling of structures of multi-component mixtures using a sphere packing approach, Int. J. Nanotechnol., 13 (2016), 44-59. doi: 10.1504/IJNT.2016.074522
    [68] S. C. Agapie, P. A. Whitlock, Random packing of hyperspheres and Marsaglia's parking lot test, Monte Carlo Methods Appl., 16 (2010), 197-209.
    [69] W. S. Jodrey, E. M. Tory, Computer simulation of close random packing of equal spheres, Phys. Rev. A., 32 (1985), 2347-2351.
    [70] D. P. Fraser, Setting up random configurations, Inf. Q. Comput. Simul. Condens. Phases, 19 (1985), 53-59.
    [71] S. Torquato, O. U. Uche, F. H. Stillinger, Random sequential addition of hard spheres in high Euclidean dimensions, Phys. Rev. E, 74 (2006), 061308. doi: 10.1103/PhysRevE.74.061308
    [72] М. Skoge, A. Donev, F. H. Stillinger, S. Torquato, Packing hyperspheres in high-dimensional Euclidean spaces, Phys. Rev. E, 4 (2006), 041127.
    [73] B. D. Lubachevsky, F. H. Stillinger, Geometric properties of random disk packings, J. Stat. Phys., 60 (1990), 561-583. doi: 10.1007/BF01025983
    [74] P. Morse, M. Clusel, E. Corwin, Polydisperse sphere packing in high dimensions, a search for an upper critical dimension, APS March Meeting 2012, Boston, Massachusetts, 2012.
    [75] Y. Stoyan, G. Yaskov, Packing congruent hyperspheres into a hypersphere, J. Global Optim., 52 (2012), 855-868. doi: 10.1007/s10898-011-9716-z
    [76] G. N. Yaskov, Packing non-equal hyperspheres into a hypersphere of minimal radius, J. Mech. Eng., 17 (2014), 48-53.
    [77] G. Scheithauer, Y. G. Stoyan, T. Y. Romanova, Mathematical Modeling of Interactions of Primary Geometric 3D Objects, Cybern. Syst. Anal., 41 (2005), 332-342. doi: 10.1007/s10559-005-0067-y
    [78] A. Wä chter, L. T. Biegler, On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming, Math. Program., 106 (2006), 25-57. doi: 10.1007/s10107-004-0559-y
    [79] Y. Stoyan, G. Scheithauer, G. Yaskov, Packing of various radii solid spheres into a parallelepiped, Cent. Eur. J. Oper. Res., 11 (2003), 389-407.
    [80] G. М. Yaskov, Optimization problems of packing hyperspheres: mathematical models, methods, applications, The thesis for the degree of Doctor of Technical Sciences in speciality 01.05.02 Mathematical modeling and computational methods, A. Podgorny Institute for Mechanical Engineering Problems, Ukraine, 2019.
    [81] J. Gondzio, HOPDM (version 2.12) - a fast LP solver based on a primal-dual interior point method, Eur. J. Oper. Res., 85 (1995), 221-225. doi: 10.1016/0377-2217(95)00163-K
    [82] C. Meszaros, On numerical issues of interior point methods, SIAM J. Matrix Anal. Appl., 30 (2008), 223-235. doi: 10.1137/050633354
    [83] M. Tawarmalani, N. V. Sahinidis, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103 (2005), 225-249. doi: 10.1007/s10107-005-0581-8
    [84] S. V. Yakovlev, The method of artificial dilation in problems of optimal packing of geometric objects, Cybern. Syst. Anal., 53 (2017), 725-731.
    [85] Y. G. Stoyan, S. V. Yakovlev, Configuration space of geometric objects, Cybern. Syst. Anal., 54 (2018), 716-726. doi: 10.1007/s10559-018-0073-5
    [86] Y. Stoyan, T. Romanova, G. Scheithauer, A. Krivulya, Covering a polygonal region by rectangles, Comput. Optim. Appl., 48 (3), (2011), 675-695.
    [87] T. Romanova, I. Litvinchev, A. Pankratov, Packing ellipsoids in an optimized cylinder, Eur. J. Oper. Res., 285 (2020), 429-443. doi: 10.1016/j.ejor.2020.01.051
    [88] A. Pankratov, T. Romanova, I. Litvinchev, J. A. Marmolejo-Saucedo, An optimized covering spheroids by spheres, Appl. Sci., 10 (2020), 1846.
    [89] I. Litvinchev, Decomposition-aggregation method for convex programming problems, Optimization, 22 (1991), 47-56. doi: 10.1080/02331939108843642
    [90] I. Litvinchev, S. Rangel, Localization of the optimal solution and aposteriori bounds for aggregation, Comput. Oper. Res., 26 (1999), 967-988. doi: 10.1016/S0305-0548(99)00027-1
    [91] I. Litvinchev, Refinement of lagrangian bounds in optimization problems, Comput. Math. Math. Phys., 47 (2007), 1101-1107. doi: 10.1134/S0965542507070032
    [92] I. Litvinchev, L. Ozuna, Lagrangian bounds and a heuristic for the two-stage capacitated facility location problem, Int. J. Energy Optim. Eng., 1 (2012), 59-71
  • Reader Comments
  • © 2020 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索
Mathematical Biosciences and Engineering
3.9

Metrics

Article views(4428) PDF downloads(141) Cited by(23)

Preview PDF
Download XML
Export Citation
Article outline

Figures and Tables

Figures(11)  /  Tables(4)

Other Articles By Authors

Related pages

Tools

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog