МЕТОДОЛОГІЯ РОЗВ’ЯЗАННЯ ЗАДАЧ РОЗТАШУВАННЯ БАГАТОВИМІРНИХ КУЛЬ

Автор

Г. М. Яськов, Інститут проблем машинобудування ім. А.М. Підгорного НАН України (61046, Україна, м. Харків, вул. Пожарського, 2/10), e-mail: yaskov@ipmach.kharkov.ua, ORCID: 0000-0002-1476-1818

Анотація

В статті розглядається задача оптимального розміщення куль різної розмірності в контейнерах довіль-них геометричних форм. Згідно з міжнародною класифікацією ця задача належить до класу SPP (Sphere Packing Problems). Вона полягає в розміщенні набору куль (кругів, гіперкуль) заданих радіусів у контейнері з заданими ме-тричними характеристиками. Метою даної роботи є створення єдиної методології розв’язання задач SPP. На-ведено основні постановки задачі: у вигляді задачі про рюкзак і задачі зі змінним розміром контейнера та відпо-відні математичні моделі. На вибір стратегії розв’язання впливають вид постановки задачі, розмірність прос-тору, в якому розміщуються кулі, метричні особливості куль (рівні чи нерівні), кількість розміщуваних куль, гео-метрична форма контейнера, наявність технологічних обмежень, обмеження на час обчислень. Структурними елементами методології є математичні моделі, способи побудови початкових розміщень, методи локальної й глобальної оптимізації. Під час  розробки методу розв’язання використовується побудова допустимих розміщень випадковим, ґратчастим способами, за допомогою жадібного алгоритму й шляхом розв’язання допоміжної зада-чі нелінійного програмування. Як методи локальної оптимізації розглядаються модифікації методу можливих напрямів, метод внутрішньої точки, метод множників Лагранжа та метод оптимізації за групами змінних. Для глобальної оптимізації використовуються метод перебору підмножин куль із заданого набору, метод перебору крайніх точок області допустимих розв’язків, реалізовані за допомогою алгоритму гілок і меж, модифікації ме-тодів околів, що звужуються, метод плавного переходу з одного локального мінімуму в інший на основі збільшен-ня розмірності задачі шляхом уведення додаткових змінних метричних характеристик, метод розв’язання, реалі-зований у вигляді послідовності задач нелінійного програмування зростаючої розмірності, метод мультистарту. Запропоновано стратегії розв’язання задач SPP для різних її постановок.

Ключові слова: куля, гіперкуля, упаковка куль, задача про рюкзак, задача зі змінним розміром, нелінійна оптимізація.

Література

1. Стоян Ю. Г., Яковлев С. В. Математические модели и оптимизационные методы геометрического проектирования. Киев: Наук. думка, 1986. 268 с.
2. Waescher G., Haussner H. An improved typology of cutting and packing problems. Europ. J. Operational Research. 2007. Vol. 183. Iss. 5. P. 1109–1130. https://doi.org/10.1016/j.ejor.2005.12.047
3. Hifi M., M’Hallah R. A literature review on circle and sphere packing problems: models and methodologies. Advances in Operations Research. 2009. Vol. 2009. P. 1–19. https://doi.org/10.1155/2009/150624
4. Snoj L., Ravnik M. Effect of packing fraction variations on the multiplication factor in pebble-bed nuclear reactors. Kerntechnik. 2006. Vol. 71. No. 4. P. 208–213. https://doi.org/10.3139/124.100295
5. Leary M., Merli L., Torti F., Mazur M., Brandt M. Optimal topology for additive manufacture: A method for enabling additive manufacture of support-free optimal structures. Materials and Design. 2014. Vol. 63. P. 678–690. https://doi.org/10.1016/j.matdes.2014.06.015
6. 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 Math. Methods in Medicine. 2015. Vol. 2015. P. 1–8. https://doi.org/10.1155/2015/142987
7. Agapie S. C., Whitlock P. A. Random packing of hyperspheres and Marsaglia’s parking lot test. Monte Carlo Methods and Appl. 2010. Vol. 16. Iss. 3–4. P. 197–209. https://doi.org/10.1515/mcma.2010.019
8. Conway H., Sloane N. J. A Sphere Packings, Lattices, and Groups. New York: Springer-Verlag, 1999. 706 p. https://doi.org/10.1007/978-1-4757-6568-7
9. Torquato S., Stillinger, F. H. Exactly solvable disordered sphere-packing model in arbitrary-dimensional Euclidean spaces. Physical Review E. 2006. Vol. 73. Iss. 3. P. 031–106. https://doi.org/10.1103/PhysRevE.73.031106
10. Hifi M., Yousef L. A dichotomous search-based heuristic for the three-dimensional packing problem. Cogent Eng. 2015. Vol. 1. P. 1–15. https://doi.org/10.1080/23311916.2014.994257
11. Zeng Z., Yu X., He K., Huang W., Fu Z. Iterated Tabu Search and Variable Neighborhood Descent for packing unequal circles into a circular container. Europ. J. Operational Research. 2016. Vol. 250. Iss. 2. P. 615–627.  https://doi.org/10.1016/j.ejor.2015.09.001
12. Sutou A., Dai Y. Global Optimization Approach to Unequal Global Optimization Approach to Unequal Sphere Packing Problems in 3D. J. Optimization Theory and Appl. 2002. Vol. 114. Iss. 3.  P. 671–694.  https://doi.org/10.1023/A:1016083231326
13. 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. Vol. 546–547. P. 1464–1469. https://doi.org/10.4028/www.scientific.net/AMR.546-547.1464
14. Kubach T., Bortfeldt A., Tilli T., Gehring H. Greedy Algorithms for Packing Unequal Spheres into a Cuboidal Strip or a Cuboid. Asia-Pacific J. Operational Research. 2011. Vol. 28. No. 06. P. 739–753. https://doi.org/10.1142/S0217595911003326
15. Birgin E. G., Sobral F. N. C. Minimizing the object dimensions in circle and sphere packing problems. Computers & Operations Research. 2008. Vol. 35. Iss. 7. P. 2357–2375. https://doi.org/10.1016/j.cor.2006.11.002
16. Stoyan Yu., Yaskov G. Packing congruent hyperspheres into a hypersphere. J. Global Optimization. 2012. Vol. 52. Iss. 4. P. 855–868. https://doi.org/10.1007/s10898-011-9716-z
17. Яковлев С. В., Яськов Г. Н., Коробчинский К. П. О методах переменного радиуса в задаче упаковки шаров в контейнеры. Питання прикл. математики i мат. моделювання: зб. наук. пр. Дніпро: ЛІРА. 2017. № 17. С. 265–272.
18. Стоян Ю. Г.,Шайтхауер Г., Яськов Г. Н. Упаковка неравных шаров в различные контейнеры. Кибернетика и систем. анализ. 2016. № 3. С. 97–105.
19. Yaskov G. N. Packing non-equal hyperspheres into a hypersphere of minimal radius. Проблемы машиностроения. 2014. Т. 17. № 1. С. 48–53.
20. Stoyan Y., Yaskov G. Mathematical model and solution method of optimization problem of placement of rectangles and circles taking into account special constraints. Transactions in Operational Research. 1998. Vol. 5. No. 1. P. 45–57. https://doi.org/10.1111/j.1475-3995.1998.tb00101.x
21. Visscher W. M., Bolsterli M. Random Packing of Equal and Unequal Spheres in Two and Three Dimensions. Nature. 1972. Vol. 239. P. 504–507. https://doi.org/10.1038/239504a0
22. Mueller G. Numerically packing spheres in cylinders. Powder Technology. 2005. Vol. 159. Iss. 2. P. 105–110. https://doi.org/10.1016/j.powtec.2005.06.002
23. Яськов Г. Н. Упаковка большого числа конгруэнтных кругов в цилиндре.  Доп. НАН України. № 12. С. 43–49.
24. Chernov N., Stoyan Yu., Romanova T. Mathematical model and efficient algorithms for object packing problem. Computational Geometry. 2015. Vol. 43. Iss. 5. P. 535–553. https://doi.org/10.1016/j.comgeo.2009.12.003
25. Stoyan Y., Pankratov A., Romanova T. Quasi-phi-functions and optimal packing of ellipses. J. Global Optimization. Vol. 65. Iss. 2. P. 283–307. https://doi.org/10.1007/s10898-015-0331-2
26. Stoyan Y., Yaskov G. Packing equal circles into a circle with circular prohibited areas. J. Computer Mathematics. 2012. Vol. 89. Iss. 10. P. 1355–1369. https://doi.org/10.1080/00207160.2012.685468
27. Яськов Г. Н. Метод решения задачи размещения разных кругов с перспективным выбором начальных точек. Зб. наук. праць Харк. ун-ту повітряних сил. 2010. Вип. 3. № 25. С. 119–122.
28. Wächter A., Biegler L. On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming. Math. Programming. 2006. Vol. 106. Iss. 1. P. 25–57. https://doi.org/10.1007/s10107-004-0559-y
29. Stoyan Yu., Yaskov G. Packing unequal circles into a strip of minimal length with a jump Optimization Letters. 2014. Vol. 8. Iss. 3. P. 949–970. https://doi.org/10.1007/s11590-013-0646-1
30. Yaskov G. N. Random packing of identical spheres into a cylindrical container. Системи обробки інформації. 2008. Вип. 1. № 68. С. 128–130.
31. Stoyan Y., Chugay A. Packing cylinders and rectangular parallelepipeds with distances between them into a given region. J. Operational Research. 2009. Vol. 197. Iss. 2. P. 446–455. https://doi.org/10.1016/j.ejor. 2008.07.003
32. Gondzio J. HOPDM (version 2.12) – a fast LP solver based on a primal-dual interior point method. J. Operational Research. 1995. Vol. 85. Iss. 1. P. 221–225. https://doi.org/10.1016/0377-2217(95)00163-K
33. Meszaros C. On numerical issues of interior point methods. SIAM on Matrix Analysis and Appl. 2008. Vol. 30. Iss. 1. P. 223–235. https://doi.org/10.1137/050633354
34. Torquato S., Uche O. U., Stillinger, H. Random sequential addition of hard spheres in high Euclidean dimensions. Physical Review E. 2006. Vol. 74. Iss. 6. P. 061–308. https://doi.org/10.1103/PhysRevE.74.061308
35. Stoyan Y., Scheithauer G., Yaskov G. Packing of various radii solid spheres into a parallelepiped. Central Europ. J. Operations Research. 2003. Vol. 11. No. 4. P. 389–407.
36. Stoyan Y., Yaskov G. Packing Identical Spheres into a Rectangular Parallelepiped. In: Bortfeldt A., Homberger J., Kopfer H., Pankratz G., Strangmeier R. (eds) Intelligent Decision Support. Gabler, 2008. P. 47–67. https://doi.org/10.1007/978-3-8349-9777-7_4
37. Яськов Г. Н. Дерево решений для задачи размещения неравных шаров в шаре заданного радиуса. Інформаційні системи і технології ІСТ-2017: пр 6-ї міжнар. наук.-техн. конф. (Коблеве, 11–16 вер. 2017). Коблеве, 2017. С. 143–144.

Надійшла до редакції 14 січня 2019 р.