Optimized packing unequal spheres into a multiconnected domain: mixed-integer non-linear programming approach

References

• H. Akeb, A two-stage look-ahead heuristic for packing spheres into a three-dimensional bin of minimum length, in Recent Advances in Computational Optimization, S. Fidanova, eds., Springer International Publishing, Springer, Cham. 610(2016), pp. 127–144.
   Google Scholar
• L.J.P. Araújo, E. Özcan, J.A.D. Atkin, and M. Baumers, Analysis of irregular three-dimensional packing problems in additive manufacturing: A new taxonomy and dataset, Int. J. Prod. Res. 57 (2018), pp. 5920–5934.
   Web of Science ®Google Scholar
• H.R. Baghaee, M. Mirsalim, G.B. Gharehpetian, and H.A. Talebi, MOPSO/FDMT-based Pareto-optimal solution for coordination of overcurrent relays in interconnected networks and multi-DER microgrids, IET. Gener. Transm. Distrib. 12 (2018), pp. 2871–2886.
   Web of Science ®Google Scholar
• H.R. Baghaee, M. Mirsalim, G.B. Gharehpetian, and H. A. Talebi, A decentralized robust mixed H2/H∞ voltage control scheme to improve small/large-signal stability and FRT capability of islanded multi-DER microgrid considering load disturbances, IEEE Syst. J. 12 (2018), pp. 2610–2621.
   Web of Science ®Google Scholar
• E.G. Birgin and F.N.C. Sobral, Minimizing the object dimensions in circle and sphere packing problems, Comput. Oper. Res. 35 (2008), pp. 2357–2375.
   Web of Science ®Google Scholar
• O. Blyuss, L. Koriashkina, E. Kiseleva, and R. Molchanov, Optimal placement of irradiation sources in the planning of radiotherapy: Mathematical models and methods of solving, Comput. Math. Methods. Med. 2015 (2015), article ID 142987. Available at https://doi.org/10.1155/2015/142987.
   Web of Science ®Google Scholar
• L. Burtseva, B.V. Salas, R. Romero, and F. Werner, Recent advances on modelling of structures of multi-component mixtures using a sphere packing approach, Int. J. Nanotechnol. 13 (2016), pp. 44–59.
   Web of Science ®Google Scholar
• Z. Duriagina, I. Lemishka, I. Litvinchev, J.A. Marmolejo, A. Pankratov, T. Romanova, and G. Yaskov, Optimized filling of a given cuboid with spherical powders for additive manufacturing, J. Oper. Res. Soc. China (2020). Available at https://doi.org/10.1007/s40305-020-00314-9.
   Web of Science ®Google Scholar
• M. Garey, and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, San Francisco, 1979.
   Google Scholar
• E.O. Gavriliouk, Unequal Sphere Packing Problem in the Context of Stereotactic Radiosurgery, Shaker Verlag GmbH, Aachen, Germany, 2007.
   Google Scholar
• I. Gibson, D. Rosen, and B. Stucker, Additive Manufacturing Technologies, 3D Printing, Rapid Prototyping, and Direct Digital Manufacturing. Springer-Verlag, New-York, 2015.
   Google Scholar
• I.V. Grebennik, A.V. Pankratov, A.M. Chugay, and A.V. Baranov, Packing n-dimensional parallelepipeds with the feasibility of changing their orthogonal orientation in an n-dimensional parallelepiped, Cybernet. Systems Anal. 46 (2010), pp. 793–802.
   Google Scholar
• M. Hifi, and L. Yousef, A Dichotomous Search-Based Heuristic for the Three-Dimensional Packing Problem, Cogent Engineering, 2:1, 994257, (2015) https://doi.org/10.1080/23311916.2014.994257.
   Google Scholar
• M. Hifi, and L. Yousef, A hybrid algorithm for packing identical spheres into a container, Expert. Syst. Appl. 96 (2018), pp. 249–260.
   Web of Science ®Google Scholar
• M. Hifi, L. Yousef, Handling lower bound and hill-climbing strategies for sphere packing problems, in Recent Advances in Computational Optimization Studies in Computational Intelligence, S. Fidanova ed., Springer, Cham 610 (2016), pp. 145–164.
   Google Scholar
• M. Hifi, and L. Yousef, A local search-based method for sphere packing problems, European J. Oper. Res. 274 (2019), pp. 482–500.
   Web of Science ®Google Scholar
• W.Q. Huang, Y. Li, H. Akeb, and C.M. Li, Greedy algorithms for packing unequal circles into a rectangular container, J. Oper. Res. Soc. 56 (2005), pp. 539–548.
   Web of Science ®Google Scholar
• N. Ilyasova, A. Shirokanev, D. Kirsh, R. Paringer, A. Kupriyanov, and E. Zamycky, Development of coagulate map formation algorithms to carry out treatment by laser coagulation, Procedia. Eng. 201 (2017), pp. 271–279.
   Google Scholar
• J. Kennedy, and R. Eberhart, Particle swarm optimization, International Conference on Neural Networks (ICNN’95), Perth, WA, Australia, Vol. 4, 1995, pp. 1942–1948.
   Google Scholar
• J. Kennedy, and R. C. Eberhart, A discrete binary version of the particle swarm algorithm, 1997 IEEE International Conference on Systems, Man, and Cybernetics. Computational Cybernetics and Simulation, Orlando, FL, USA, Vol. 5, 1997, pp. 4104–4108.
   Google Scholar
• A.A. Kovalenko, T.E. Romanova, and P.I. Stetsyuk, Balance layout problem for 3D-objects: Mathematical model and solution methods. Cybernet. Systems Anal. 51 (2015), pp. 556–565.
   Web of Science ®Google Scholar
• T. Kubach, A. Bortfeldt, T. Tilli, and H. Gehring, Greedy algorithms for packing unequal spheres into a cuboidal strip or a cuboid, Asia-Pac. J. Oper. Res. 28 (2011), pp. 739–753.
   Web of Science ®Google Scholar
• R. Lachmayer, and R.B. Lippert, Additive Manufacturing. Quantifiziert – Visionäre Anwendungen und Stand der Technik, Springer Vieweg Verlag, Berlin, 2017.
   Google Scholar
• M. Lee, Q. Fang, Y. Cho, J. Ryu, L. Liu, and D.-S. Kim, Support-free hollowing for 3D printing via Voronoi diagram of ellipses, Comput.-Aided Des. 101 (2018), pp. 23–36.
   Web of Science ®Google Scholar
• J. Liu, and Y. Ma, A survey of manufacturing oriented topology optimization methods, Adv. Eng. Softw. 100 (2016), pp. 161–175.
   Web of Science ®Google Scholar
• J. Liu, Y. Yao, Yu. Zheng, H. Geng, and G. Zhou, An effective hybrid algorithm for the circles and spheres packing problems, Combinatorial Optimization and Applications Lecture Notes in Computer Science 5573 (2009), pp. 135–144.
   Google Scholar
• J.M. Martínez, and L. Martínez, Packing optimization for automated generation of complex system's initial configurations for molecular dynamics and docking, J. Comput. Chem. 24 (2003), pp. 819–825.
   PubMed Web of Science ®Google Scholar
• L. Martínez, R. Andrade, E.G. Birgin, and J.M. Martínez, Packmol: A package for building initial configurations for molecular dynamics simulations, J. Comput. Chem. 30 (2009), pp. 2157–2164.
   PubMed Web of Science ®Google Scholar
• PACKMOL, Initial Configurations for Molecular Dynamics Simulations by Packing Optimization, Institute of Chemistry and Institute of Mathematics, University of Campinas, Institute of Mathematics and Statistics, University of São Paulo, 2020; available at http://m3g.iqm.unicamp.br/packmol/home.shtml.
   Google Scholar
• A. Parizad, and K. Hatziadoniu, Security/stability-based Pareto optimal solution for distribution networks planning implementing NSGAII/FDMT, Energy 192 (2020), 116644.
   Web of Science ®Google Scholar
• T. Romanova, J. Bennell, Y. Stoyan, and A. Pankratov, Packing of concave polyhedra with continuous rotations using nonlinear optimization, European J. Oper. Res. 268 (2018), pp. 37–53.
   Web of Science ®Google Scholar
• T. Romanova, Y. Stoyan, A. Pankratov, I. Litvinchev, I. Yanchevsky, and I. Mozgova, Optimal packing in additive manufacturing, IFAC-PapersOnLine 52 (2019), pp. 2758–2763. Available at https://doi.org/10.1016/j.ifacol.2019.11.625.
   Google Scholar
• G. Scheithauer, Yu.G. Stoyan, and T.Ye. Romanova, Mathematical modeling of interactions of primary geometric 3D objects, Cybernet. Systems Anal. 41 (2005), pp. 332–342.
   Google Scholar
• A.S. Shirokanev, D.V. Kirsh, N.Y. Ilyasova, and A.V. Kupriyanov, Investigation of algorithms for coagulate arrangement in fundus images, Comput. Opt. 42 (2018), pp. 712–721.
   Web of Science ®Google Scholar
• L. Schewe, and M. Schmidt, Computing feasible points for binary MINLPs with MPECs, Math. Program. Comput. 11 (2019), pp. 95–118.
   Web of Science ®Google Scholar
• P. Stetsyuk, T. Romanova, and G. Scheithauer, On the global minimum in a balanced circular packing problem, Optim. Lett. 10 (2016), pp. 1347–1360.
   Web of Science ®Google Scholar
• Yu.G. Stoyan, On a way of searching for the best solution for a multiextremal problem class, Controlled Systems 3 (1969), pp. 81–88 [in Russian]. Available at http://nas1.math.nsc.ru/aim/journals/us/us3/us03_011.pdf.
   Google Scholar
• Y.G. Stoyan, Mathematical methods for geometric design, Advances in CAD/CAM, PROLAMAT82, May 1982, Leningrad, USSR, North–Holland, Amsterdam, 2003.
   Google Scholar
• Y.G. Stoyan, and A.M. Chugay, Packing different cuboids with rotations and spheres into a cuboid, Advances in Decision Sciences 2014 (2014), article ID 571743. Available at https://doi.org/10.1155/2014/571743.
   Google Scholar
• Y. Stoyan, A. Pankratov, T. Romanova, G. Fasano, J.D. Pinter, Y.E. Stoian, and A. Chugay, Optimized packings in space engineering applications: Part I, in Modeling and Optimization in Space Engineering, G. Fasano and J. Pinter, eds., Springer Optimization and its Applications, New York 144 (2019), pp. 395–437.
   Google Scholar
• Y. Stoyan, I. Grebennik, T. Romanova, and A. Kovalenko, Optimized packings in space engineering applications: Part II, in Modeling and Optimization in Space Engineering, G. Fasano and J. Pinter, eds., Springer Optimization and its Applications, New York 144 (2019), pp. 439–457.
   Google Scholar
• Yu. Stoyan and T. Romanova, Mathematical models of placement optimisation: Two- and three-dimensional problems and applications, in Modeling and Optimization in Space Engineering, G. Fasano and J. Pinter, eds., Springer Optimization and its Applications, New York 73 (2013), pp. 363–388.
   Google Scholar
• Yu.G. Stoyan, G. Scheithauer, and G.N. Yaskov, Packing unequal spheres into various containers, Cybernet. Systems Anal. 52 (2016), pp. 419–426.
   Web of Science ®Google Scholar
• Y.G. Stoyan, V.V. Semkin, and A.M. Chugay, Modeling close packing of 3D objects, Cybernet. Systems Anal. 52 (2016), pp. 296–304.
   Web of Science ®Google Scholar
• Yu.G. Stoyan, and V.Z. Socolovsky, The minimization method for some permutation functionals, Inform. Process. Lett. 8 (1979), pp. 110–111.
   Web of Science ®Google Scholar
• Yu. Stoyan, and G. Yaskov, Packing congruent hyperspheres into a hypersphere, J. Global Optim. 52 (2012). pp. 855–868.
   Web of Science ®Google Scholar
• Y. Stoyan, and G. Yaskov, Packing equal circles into a circle with circular prohibited areas, Int. J. Comput. Math. 89 (2012), pp. 1355–1369.
   Web of Science ®Google Scholar
• Yu. Stoyan, and G. Yaskov, Packing congruent spheres into a multi-connected polyhedral domain, Int. Trans. Oper. Res. 20 (2013), pp. 79–99.
   Web of Science ®Google Scholar
• Yu. Stoyan and G. Yaskov, Packing unequal circles into a strip of minimal length with a jump algorithm, Optim. Lett. 8 (2014), pp. 949–970.
   Web of Science ®Google Scholar
• Yu. Stoyan, G. Yaskov, and G. Scheithauer, Packing of various solid spheres into a parallelepiped, CEJOR Cent. Eur. J. Oper. Res. 11 (2003), pp. 389–407.
   Google Scholar
• Y. Stoyan, G. Yaskov, T. Romanova, I. Litvinchev, S. Yakovlev, and J.M. Velarde Cantú, Optimized packing multidimensional hyperspheres: A unified approach, Math. Biosci. Eng. 17 (2020), pp. 6601–6630. Available at https://doi.org/10.3934/mbe.2020344.
   PubMed Web of Science ®Google Scholar
• A. Sutou, and Y. Day, Global optimization approach to unequal sphere packing problems in 3D, J. Optim. Theory Appl. 114 (2002), pp. 671–694.
   Web of Science ®Google Scholar
• W. Visscher and M. Bolsterli, Random packing of equal and unequal spheres in two and three dimensions, Nature 239 (1972), pp. 504–507.
   Web of Science ®Google Scholar
• A. Wächter and 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), pp. 25–57.
   Web of Science ®Google Scholar
• G. Waescher, H. Haussner, and H. Schumann, An improved typology of cutting and packing problems, European J. Oper. Res. 183 (2007), pp. 1109–1130.
   Web of Science ®Google Scholar
• J. Wang, Packing of unequal spheres and automated radiosurgical treatment planning, J. Comb. Optim. 3 (1999), pp. 453–463.
   Web of Science ®Google Scholar
• S.V. Yakovlev, The method of artificial space dilation in problems of optimal packing of geometric objects, Cybernet. Systems Anal. 53 (2017), pp. 725–731.
   Web of Science ®Google Scholar
• S.V. Yakovlev, Formalization of spatial configuration optimization problems with a special function class, Cybernet. Systems Anal. 55 (2019), pp. 512–523.
   Web of Science ®Google Scholar
• S. Yamada, J. Kanno, and M. Miyauchi, Multi-sized sphere packing in containers: Optimization formula for obtaining the highest density with two different sized spheres, IPSJ Online Transactions 4 (2011), pp. 126–133. Available at https://doi.org/10.2197/ipsjtrans.4.126.
   Google Scholar
• I. Yanchevskyi, R. Lachmayer, I. Mozgova, R-B. Lippert, G. Yaskov, T. Romanova, and I. Litvinchev, Circular packing for support-free structures, EAI Endorsed Transactions (2020). Available at https://doi.org/10.4108/eai.13-7-2018.164561.
   Google Scholar
• G.N. Yaskov, Methodology to solve multidimentional sphere packing problems, Journal of Mechanical Engineering 22 (2019), pp. 67–75. Available at https://doi.org/10.15407/pmach2019.01.067.
   Google Scholar
• G. Yaskov, T. Romanova, I. Litvinchev, and S. Shekhovtsov, Optimal packing problems: From knapsack problem to open dimension problem, in Intelligent Computing and Optimization, P. Vasant, I. Zelinka, G.W. Weber, eds., ICO 2019, Advances in Intelligent Systems and Computing, vol. 1072. Springer, Cham (2020), pp. 671–678.
   Google Scholar
• Z.Z. Zeng, W.Q. Huang, R.C. Xu, and Z.H. Fu, An algorithm to packing unequal spheres in a larger sphere. Adv. Mat. Res. 546–547 (2012), pp. 1464–1469.
   Google Scholar
• J. Zhou, Y. Zhang, and J.K. Chen, Numerical simulation of random packing of spherical particles for powder-based additive manufacturing, ASME. J. Manuf. Sci. Eng. 131 (2009), 031004–031004-8, 8 p. Available at https://doi.org/10.1115/1.3123324.
   Web of Science ®Google Scholar
• H.R. Ghaffari, Optimization models and techniques for radiation treatment planning applied to Leksell Gamma Knife Perfexion, Ph.D. diss., Graduate Department of Mechanical and Industrial Engineering University of Toronto, 2012.
   Google Scholar