C&SA | Contents

Volume 59 >>> № 1 JANUARY — FEBRUARY 2023

-->

UDC 519.85

T.E. Romanova¹, P.I. Stetsyuk², A. Fischer³, G.M. Yaskov⁴

¹ A. Pidgorny Institute of Mechanical Engineering Problems of the National Academy of Sciences of Ukraine, Kharkiv, Ukraine

tarom27@yahoo.com

² V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine

stetsyukp@gmail.com

³ Institute of Computational Informatics, Dresden University of Technology, Dresden, Germany

Andreas.Fischer@tu-dresden.de

⁴ A. Pidgorny Institute of Mechanical Engineering Problems of the National Academy of Sciences of Ukraine, Kharkiv, Ukraine

yaskov@ukr.net

PROPOTION PACKING OF CIRCLES IN A CIRCULAR CONTAINER

Abstract. The paper considers the optimization problem of packing circles into a larger fixed circular container with non-standard placement conditions. A family of circles is assigned to a given set of circle types. Proportions of the different types of circles appearing in the packing are defined. The circles are allowed predefined overhanding of the container boundary. The problem is aimed to arrange as much non-overlapping circles in the container as possible subject to the proportion and pseudo-containment conditions. A mathematical model as a mixed integer nonlinear mathematical programming problem (MINLP) is constructed and a solution algorithm is proposed. It reduces the MINLP to a sequence of nonlinear programming problems for packing of circles with variable metrical characteristics meeting the proportion conditions in a given circular container. The computational results are provided.

Keywords: proportional packing, circles, circular container, pseudo-containment, optimization.

full text

REFERENCES

Yanchevskyi I., Lachmayer R., Mozgova I., Lippert R. B., Yaskov G., Romanova T., Litvinchev I. Circular packing for support-free structures. EAI Endorsed Transactions on Energy Web. 2020. Vol. 7, Iss. 30. e3. P. 1–10.

Blyuss O., Koriashkina L., Kiseleva E., 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. Vol. 2015. Article ID 142987. https://doi.org/10.1155/2015/142987.

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. 2021. Vol. 9, Iss. 4. P. 853–868. https://doi.org/10.1007 /s40305-020-00314-9.

Plankovskyy S., Shypul O., Tsegelnyk Ye., Pankratov A., Romanova T., Litvinchev I. Circular layout in thermal deburring. In: Advances in Intelligent Systems and Computing. Shkarlet S., Morozov A., Palagin A. (Eds.). 2021. Vol. 1265. P. 111–120. URL: file:///D:/Downloads/ Springer.pdf.

Chazelle B., Edelsbrunner H., Guibas L.J. The complexity of cutting complexes. Discrete & Computational Geometry. 1989. Vol. 4, Iss. 2. P. 139–181.

Galiev S.I., Lisafina M.S. Linear models for the approximate solution of the problem of packing equal circles into a given domain. European Journal of Operational Research. 2013. Vol. 230, Iss. 3. P. 505–514.

Litvinchev I., Infante L., Ozuna L. Packing circular like objects in a rectangular container. J. Comput. Syst. Sci. Int. 2015. Vol. 54, Iss. 2. P. 259–267.

Stoyan Y., Yaskov G. Packing equal circles into a circle with circular prohibited areas. Int. J. Comput. Math. 2012. Vol. 89, Iss. 10. P. 1355–1369.

Lopez C.O., Beasley J.E. Packing a fixed number of identical circles in a circular container with circular prohibited areas. Optim. Lett. 2019. Vol. 13, Iss. 7. P. 1449–1468.

Akeb H., Hifi M., Negre S. An augmented beam search-based algorithm for the circular open dimension problem. Comput. Ind. Eng. 2011. Vol. 61, Iss. 2. P. 373–381.

Stetsyuk P.I., Romanova T.E., Scheithauer G. On the global minimum in a balanced circular packing problem. Optim. Lett. 2016. Vol. 10, Iss. 6. P. 1347–1360.

Grebennik I.V., Kovalenko A.A., Romanova T.E., Urniaieva I.A., Shekhovtsov S.B. Combinatorial configurations in balance layout optimization problems. Cybernetics and Systems Analysis. 2018. Vol. 54, N 2. P. 221–231. https://doi.org/10.1007/s10559-018-0023-2.

Romanova T., Pankratov O., Litvinchev I., Stetsyuk, P., Lykhovyd O., Marmolejo-Saucedo J.A., Vasant P. Balanced circular packing problems with distance constraints. Computation. 2022. Vol. 10, Iss. 7. 113. https://doi.org/10.3390/computation10070113.

Shor N.Z., Zhurbenko N.G., Likhovid A.P., Stetsyuk P.I. Algorithms of nondifferentiable optimization: development and application. Cybernetics and Systems Analysis. 2003. Vol. 39, N 4. P. 537–548. https://doi.org/10.1023/B:CASA.0000003503.25710.84.

Stetsyuk P.I. Shor’s r-algorithms: theory and practice. In: Optimization Methods and Applications. Butenko S., Pardalos P.M, Shylo V. (Eds). Cham: Springer, 2017. P. 495–520.

Stetsyuk P.I. r-algorithms and ellipsoids. Cybernetics and System Analysis. 1996. Vol. 32, N 1. P. 93–110. https://doi.org/10.1007/BF02366587.

Romanova T., Stoyan Y., Pankratov A., Litvinchev I., Marmolejo J.A. Decomposition algorithm for irregular placement problems. Proc. 2nd International Conference on Intelligent Computing and Optimization 2019 (ICO 2019) (3–4 October 2019, Baywater Resort, Koh Samui, Thailand). Baywater Resort, Koh Samui, 2019. Vol. 1072. P. 214–221.

E. Specht. URL: www.packomania.com. 2018.

Tawarmalani M., Sahinidis N.V. A polyhedral branch-and-cut approach to global optimization. Mathematical Programming. 2005. Vol. 103, Iss. 2. P. 225–249.

Sahinidis N.V. BARON 21.1.13: Global optimization of mixed-integer nonlinear programs, User’s manual. 2021.

Kilinc M.R., Sahinidis N.V. Exploiting integrality in the global optimization of mixed-integer nonlinear programming problems with BARON. Optimization Methods and Software. 2018. Vol. 33, Iss. 3. P. 540–562.

Wachter A., Biegler L.T. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming. 2006. Vol. 106, N 1. P. 25–57.