2020, issue 4, p. 39-46

Received 18.11.2020; Revised 09.12.2020; Accepted 17.12.2020

Published 31.12.2020; First Online 22.01.2021


Previous  |  Full text (in Ukrainian)  |  Next


MSC 90C15, 49M27

Optimized Layout of Spherical Objects in a Polyhedral Domain

Tatyana Romanova 1 * ORCID ID favicon Big,   Georgiy Yaskov 1 ORCID ID favicon Big,   Andrey Chugay 1 ORCID ID favicon Big,   Yurii Stoian 1 ORCID ID favicon Big

1 A.M. Pidgorny Institute of Mechanical Engineering Problems of the NAS of Ukraine, Kharkiv

* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.


Introduction. The article studies the problem of arranging spherical objects in a bounded polyhedral domain in order to maximize the packing factor. The spherical objects have variable placement parameters and variable radii within the given upper and lower bounds. The constraints on the allowable distance between each pair of spherical objects are taken into account.

The phi-function technique is used for analytical description of the placement constraints, involving object non-overlapping and containment conditions.

The problem is considered as a nonlinear programming problem. The feasible region is described by a system of inequalities with differentiable functions.

To find the local maximum of the problem the decomposition algorithm is used. We employ the strategy of active set of inequalities for reducing the computational complexity of the algorithm. IPOPT solver for solving nonlinear programming subproblems is used.

The multistart strategy allows selecting the best local maximum point.

Numerical results and the appropriate graphic illustration are given.

The purpose of the article is presenting a mathematical model and developing a solution algorithm for arranging spherical objects in a polyhedral region with the maximum packing factor. It allows obtaining a locally optimal solution in a reasonable time.

Results. A new formulation of the problem of arranging spherical objects in a polyhedral domain is considered, where both the placement parameters and the radii of the spherical objects are variable. A mathematical model in the form of nonlinear programming problem is derived. A solution approach based on the decomposition algorithm and multistart strategy is developed. The numerical results combined with the graphical illustration are given.

Conclusions. The proposed approach allows modeling optimized layouts of spherical objects into a polyhedral domain.


Keywords: layout, spherical objects, polyhedral domain, phi-function.


Cite as: Romanova T., Yaskov G., Chugay A., Stoian Y. Optimized Layout of Spherical Objects in a Polyhedral Domain. Cybernetics and Computer Technologies. 2020. 4. P. 39–46. (in Ukrainian) https://doi.org/10.34229/2707-451X.20.4.3



           1.     Liu J., Ma Y. A survey of manufacturing oriented topology optimization methods, Advances in Engineering Software. 2016. 100. P. 161–175. https://doi.org/10.1016/j.advengsoft.2016.07.017

           2.     Duriagina Z., Lemishka I., Litvinchev I., Marmolejo J.A., Pankratov A., Romanova T., Yaskov G. Optimized filling of a given cuboid with spherical powders for additive manufacturing. Journal of the Operations Research Society of China. 2020. https://doi.org/10.1007/s40305-020-00314-9

           3.     Burtseva L., Valdez Salas B., Romero R., Werner F. Recent advances on modelling of structures of multi-component mixtures using a sphere packing approach. International Journal of Nanotechnology. 2016. 13. P. 44–59. https://doi.org/10.1504/IJNT.2016.074522

           4.     Blyuss O., Koriashkina L., Kiseleva Е., Molchanov R. Optimal Placement of Irradiation Sources in the Planning of Radiotherapy : Mathematical Models and Methods of Solving. Computational and Mathematical Methods in Medicine. 2015. Article ID 142987. https://doi.org/10.1155/2015/142987

           5.     Adler J.R., Schweikard A., Achkire Y., Blanck O., Bodduluri R.M, Ma L., Zhang H. Treatment Planning for Self-Shielded Radiosurgery. Cureus. 2017. 9 (9): e1663. https://doi.org/10.7759/cureus.1663

           6.     Ilyasova N., Shirokanev A., Kirsh D., Paringer R., Kupriyanov A., Zamycky E. Development of coagulate map formation algorithms to carry out treatment by laser coagulation. Procedia Engineering. 2017. 201. P. 271–279. https://doi.org/10.1016/j.proeng.2017.09.623

           7.     Stoyan Y., Pankratov A., Romanova T., Fasano G., Pinter J.D., Stoian Y.E., Chugay A. Optimized packings in space engineering applications : Part I. Modeling and Optimization in Space Engineering : book / eds. G. Fasano and J. Pinter. Cham : Springer, 2019. 144. P. 395–437. https://doi.org/10.1007/978-3-030-10501-3_15

           8.     Stoyan Y., Grebennik I., Romanova T., Kovalenko A. Optimized packings in space engineering applications : Part II. Modeling and Optimization in Space Engineering : book / eds. G. Fasano and J. Pinter. Cham : Springer, 2019. 144. P. 439–457. https://doi.org/10.1007/978-3-030-10501-3_15

           9.     Stoyan Y., Yaskov G., Romanova T., Litvinchev I., Yakovlev S., Cantú J.M.V. Optimized packing multidimensional hyperspheres: a unified approach. Mathematical Biosciences and Engineering. 2020. 17 (6). P. 6601–6630. https://doi.org/10.3934/mbe.2020344

       10.     Birgin E.G., Sobral F.N.C. Minimizing the object dimensions in circle and sphere packing problems. Computers & Operations Research. 2008. 35. P. 2357–2375. https://doi.org/10.1016/j.cor.2006.11.002

       11.     Martínez J.M., Martínez L. Packing optimization for automated generation of complex system's initial configurations for molecular dynamics and docking. Journal of Computational Chemistry. 2003. 24. P. 819–825. https://doi.org/10.1002/jcc.10216

       12.     Hifi M., Yousef L. A local search-based method for sphere packing problems. European Journal of Operational Research. 2019. 274. P. 482–500. https://doi.org/10.1016/j.ejor.2018.10.016

       13.     Stoyan Yu.G., Scheithauer G., Yaskov G.N. Packing unequal Spheres into Various Containers. Cybernetics and Systems Analysis. 2016. 52. P. 419–426. https://doi.org/10.1007/s10559-016-9842-1

       14.     Zeng Z.Z., Huang W.Q., Xu R.C., Fu Z.H. An algorithm to packing unequal spheres in a larger sphere. Advanced Materials Research. 2012. 546–547. P. 1464–1469. https://doi.org/10.4028/www.scientific.net/AMR.546-547.1464

       15.     Stoyan Y., Yaskov G. Optimised packing unequal spheres into a multiconnected domain: mixed-integer non-linear programming approach. International Journal of Computer Mathematics : Computer Systems Theory. 2020. https://doi.org/10.1080/23799927.2020.1861105

       16.     Stoyan Y., Romanova T. Mathematical models of placement optimisation : two- and three-dimensional problems and applications. Modeling and Optimization in Space Engineering : book / eds. G. Fasano and J. Pintér. New York : Springer, 2012. 73. P. 363–388. https://doi.org/10.1007/978-1-4614-4469-5_15

       17.     Scheithauer G., Stoyan Yu.G., Romanova T.Ye. Mathematical modeling of interactions of primary geometric 3D objects. Cybernetics and Systems Analysis. 2005. 41. P. 332–342. https://doi.org/10.1007/s10559-005-0067-y

       18.     Romanova T.E., Stetsyuk P.I., Chugay A.M., Shekhovtsov S.B. Parallel Computing Technologies for Solving Optimization Problems of Geometric Design. Cybernetics and Systems Analysis. 2019. V. 55. P. 894–904. https://doi.org/10.1007/s10559-019-00199-4



ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Previous  |  Full text (in Ukrainian)  |  Next




Copyright © 2019-2021 V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine,

National Academy of Sciences of Ukraine.

All rights reserved.