×

Globally optimized packings of non-uniform size spheres in \(\mathbb {R}^{d}\): a computational study. (English) Zbl 1400.90265

Summary: In this work we discuss the following general packing problem: given a finite collection of \(d\)-dimensional spheres with (in principle) arbitrarily chosen radii, find the smallest sphere in \(\mathbb {R}^{d}\) that contains the given \(d\)-spheres in a non-overlapping arrangement. Analytical (closed-form) solutions cannot be expected for this very general problem-type: therefore we propose a suitable combination of constrained nonlinear optimization methodology with specifically designed heuristic search strategies, in order to find high-quality numerical solutions in an efficient manner. We present optimized sphere configurations with up to \(n = 50\) spheres in dimensions \(d = 2, 3, 4, 5\). Our numerical results are on average within 1% of the entire set of best known results for a well-studied model-instance in \(\mathbb {R}^{2}\), with new (conjectured) packings for previously unexplored generalizations of the same model-class in \(\mathbb {R}^{d}\) with \(d= 3, 4, 5\). Our results also enable the estimation of the optimized container sphere radii and of the packing fraction as functions of the model instance parameters \(n\) and \(1/n\), respectively. These findings provide a general framework to define challenging packing problem-classes with conjectured numerical solution estimates.

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Black, K., Chakrapani, C., Castillo, I.: Business Statistics for Contemporary Decision Making, 2nd Canadian edn. Wiley, Toronto (2014)
[2] Castillo, I., Kampas, F.J., Pintér, J.D.: Solving circle packing problems by global optimization: numerical results and industrial applications. Eur. J. Oper. Res. 191, 786-802 (2008) · Zbl 1156.90013 · doi:10.1016/j.ejor.2007.01.054
[3] Castillo, I., Sim, T.: A spring-embedding approach for the facility layout problem. J. Oper. Res. Soc. 55, 73-81 (2004) · Zbl 1095.90069 · doi:10.1057/palgrave.jors.2601647
[4] Chaikin, PM; Cates, ME (ed.); Evans, MR (ed.), Thermodynamics and hydrodynamics of hard spheres: the role of gravity, No. 53, 315-348 (2000), Bristol · doi:10.1201/9781420033519.ch13
[5] Chaikin, P.M., Lubensky, T.C.: Principles of Condensed Matter Physics. Cambridge University Press, New York (2000)
[6] Cheng, Z.D., Russell, W.B., Chaikin, P.M.: Controlled growth of hard-sphere colloidal crystals. Nature 401, 893-895 (1999) · doi:10.1038/44785
[7] Cohn, H.: Order and disorder in energy minimization. In: Proceedings of the International Congress of Mathematicians, Hyderabad, India, pp. 2416-2443. Hindustan Book Agency, New Delhi (2010) · Zbl 1236.05058
[8] Cohn, H., Kumar, A., Miller, S.D., Radchenko, D., Viazovska, M.S.: The sphere packing problem in dimension 24. (2016) arXiv:1603.06518v1 · Zbl 1370.52037
[9] Conway, J.H.: Sphere packings, lattices, codes, and greed. In: Proceedings of the International Congress of Mathematicians, Zürich, Switzerland 1994, pp. 45-55. Birkhäuser Verlag, Basel (1995) · Zbl 0853.52016
[10] Conway, J.H., Sloane, N.J.A.: Sphere Packings, Lattices and Groups, 3rd edn. Springer Science + Business Media, New York (1998) · Zbl 0917.11027
[11] de Gennes, P.G.: Granular matter: a tentative view. Rev. Mod. Phys. 71, S374-S382 (1999) · doi:10.1103/RevModPhys.71.S374
[12] Fasano, G.: Solving Non-standard Packing Problems by Global Optimization and Heuristics. Springer, New York (2014) · Zbl 1292.49001 · doi:10.1007/978-3-319-05005-8
[13] Fasano, G., Pintér, J.D. (eds.): Optimized Packings with Applications. Springer, New York (2015) · Zbl 1329.90005
[14] Fejes Tóth, L.: Regular Figures. Pergamon Press, Macmillan, New York (1964) · Zbl 0134.15705
[15] Friedman, E.: Erich’s Packing Center. (2017). http://www2.stetson.edu/ efriedma/packing.html
[16] GNU Project: The GNU Compiler Collection (GCC). (2015). https://gcc.gnu.org/
[17] Griess, R.L.: Positive definite lattices of rank at most 8. J. Number Theory 103, 77-84 (2003) · Zbl 1044.11014 · doi:10.1016/S0022-314X(03)00107-0
[18] Griess, R.L.: An Introduction to Groups and Lattices: Finite Groups and Positive Definite Rational Lattices. International Press, Somerville, MA (2011) · Zbl 1248.11048
[19] Hales, T.C.: A proof of the Kepler conjecture. Ann. Math. 162, 1065-1185 (2005) · Zbl 1096.52010 · doi:10.4007/annals.2005.162.1065
[20] Hifi, M., M’Hallah, R.: A literature review on circle and sphere packing problems: models and methodologies. In: Advances in Operations Research (2009). doi:10.1155/2009/150624 · Zbl 1198.90337
[21] Jadrich, R., Schweizer, K.S.: Equilibrium theory of the hard sphere fluid and glasses in the metastable regime up to jamming. I. Thermodynamics. J. Chem. Phys. (2013a). doi:10.1063/1.4816275
[22] Jadrich, R., Schweizer, K.S.: Equilibrium theory of the hard sphere fluid and glasses in the metastable regime up to jamming. II. Structure and application to hopping dynamics. J. Chem. Phys. (2013b). doi:10.1063/1.4816276
[23] Kampas, F.J., Pintér, J.D.: Configuration analysis and design by using optimization tools in Mathematica. Math. J. 10, 128-154 (2006)
[24] Kepler, J.: The Six-Cornered Snowflake. Oxford Classic Texts in the Physical Sciences (Illustrated reprint). Oxford University Press, Oxford (2014)
[25] Leech, J.: Notes on sphere packings. Can. J. Math. 19, 251-267 (1967) · Zbl 0162.25901 · doi:10.4153/CJM-1967-017-0
[26] Melissen, J.B.M.: Packing and Covering with Circles. Ph.D. Dissertation, Universiteit Utrecht (1997) · Zbl 0880.52008
[27] Nesterenko, V.F.: Dynamics of Heterogeneous Materials. Springer, New York (2001) · doi:10.1007/978-1-4757-3524-6
[28] Olmos, L., Martin, C.L., Bouvard, D.: Sintering of mixtures of powders: experiments and modelling. Powder Technol. 190, 134-140 (2009) · doi:10.1016/j.powtec.2008.04.057
[29] Pintér, J.D.: Global Optimization in Action. Kluwer, Dordrecht (1996) · Zbl 0842.90110 · doi:10.1007/978-1-4757-2502-5
[30] Pintér, JD; Bomze, I. (ed.); Csendes, T. (ed.); Horst, R. (ed.); Pardalos, PM (ed.), LGO—a program system for continuous and Lipschitz global optimization, 183-197 (1997), Dordrecht · Zbl 0886.90136 · doi:10.1007/978-1-4757-2600-8_12
[31] Pintér, J.D.: Globally optimized spherical point arrangements: model variants and illustrative results. Ann. Oper. Res. 104, 213-230 (2001) · Zbl 1014.90075 · doi:10.1023/A:1013107507150
[32] Pintér, J.D.: LGO—A Model Development and Solver System for Global-Local Nonlinear Optimization, User’s Guide, Current edn. Published and distributed by Pintér Consulting Services Inc, Halifax, NS (2016)
[33] Pintér, J.D.: How difficult is nonlinear optimization? A practical solver tuning approach, with illustrative results. Ann. Oper. Res. (2017). doi:10.1007/s10479-017-2518-z · Zbl 1392.90108
[34] Pintér, J.D., Kampas, F.J.: Nonlinear optimization in Mathematica with MathOptimizer Professional. Math. Educ. Res. 10(1), 1-18 (2005)
[35] Pintér, JD; Kampas, FJ; Liberti, L. (ed.); Maculan, N. (ed.), MathOptimizer Professional: key features and illustrative applications, 263-280 (2006), New York · Zbl 1100.90046 · doi:10.1007/0-387-30528-9_9
[36] Pintér, J.D., Kampas, F.J.: Benchmarking nonlinear optimization software in technical computing environments. I. Global optimization in Mathematica with MathOptimizer Professional. TOP 21, 133-162 (2013) · Zbl 1263.65056 · doi:10.1007/s11750-011-0209-5
[37] Pintér, J.D., Kampas, F.J.: Getting Started with MathOptimizer Professional. Published and distributed by Pintér Consulting Services Inc, Halifax, NS (2015)
[38] Riskin, M.D., Bessette, K.C., Castillo, I.: A logarithmic barrier approach to solving the dashboard planning problem. INFOR 41, 245-257 (2003) · Zbl 07682305
[39] Sahimi, M.: Heterogeneous Materials I: Linear Transport and Optical Properties. Springer, New York (2003a) · Zbl 1028.74001
[40] Sahimi, M.: Heterogeneous Materials II: Nonlinear and Breakdown Properties and Atomistic Modeling. Springer, New York (2003b) · Zbl 1028.74002
[41] Sloane, N.J.A.: The sphere-packing problem. (2002) arXiv:math/0207256 · Zbl 0906.11034
[42] Shannon, C.E.: A mathematical theory of communication. Bell Syst. Tech. J. 27, 379-423, 623-656 (1948) · Zbl 1154.94303
[43] Specht, E.: (2017). http://www.packomania.com · Zbl 1156.90013
[44] Stortelder, W.J.H., de Swart, J.J.B., Pintér, J.D.: Finding elliptic Fekete point sets: two numerical solution approaches. J. Comput. Appl. Math. 130, 205-216 (2001) · Zbl 1010.65028 · doi:10.1016/S0377-0427(99)00382-9
[45] Steinby, M., Thomas, W.: Trees and term rewriting in 1910: On a paper by Axel Thue. Bull. Eur. Assoc. Theor. Comput. Sci. 72, 256-269 (2000)
[46] Szabó, P.G., Markót, M.Cs, Csendes, T., Specht, E., Casado, L.G., García, I.: New Approaches to Circle Packing in a Square With Program Codes. Springer, New York (2007) · Zbl 1128.52012
[47] Szpiro, G.G.: Kepler’s Conjecture. Wiley, New York (2003) · Zbl 1097.52007
[48] Thue, A.: Om nogle geometrisk taltheoretiske theoremer. Forhdl. Skand. Naturforsk. 14, 352-353 (1892) · JFM 24.0259.01
[49] Thue, A.: Über die dichteste Zusammenstellung von kongruenten Kreisen in der Ebene. Christ. Vid. Selsk. Skr. 1, 3-9 (1910) · JFM 41.0550.02
[50] Torquato, S.: Random Heterogeneous Materials: Microstructure and Macroscopic Properties. Springer, New York (2002) · Zbl 0988.74001 · doi:10.1007/978-1-4757-6355-3
[51] Viazovska, M.S.: The sphere packing problem in dimension 8. (2016). arXiv:1603.04246 · Zbl 1373.52025
[52] Wolfram Research: Mathematica (Release 11, December 2016). Wolfram Research Inc, Champaign, IL (2016) · Zbl 1362.74029
[53] Zallen, R.: The Physics of Amorphous Solids. Wiley, New York (1983) · doi:10.1002/3527602798
[54] Zohdi, T.I.: Variational bounds for thermal fields in media with heterogeneous microstructure. Math. Mech. Solids 19, 434-439 (2014a) · Zbl 1362.74029 · doi:10.1177/1081286512468372
[55] Zohdi, T.I.: Additive particle deposition and selective laser processing: a computational manufacturing framework. Comput. Mech. 54, 171-191 (2014b) · Zbl 06327160 · doi:10.1007/s00466-014-1012-6
[56] Zong, C.: Sphere Packings (edited by Talbot, J.) Springer, New York (1999) · Zbl 0935.52016
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.