Компонування м’яких багатокутників в опуклому полігональному контейнері
The problem of arranging irregular soft polygons into an optimized convex polygonal container given by a set of variable vertices is formulated. Polygons can change their shapes within the given limits of elasticity parameters, provided that their area is preserved. Free translations and continuous...
Saved in:
| Date: | 2024 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
V.M. Glushkov Institute of Cybernetics of NAS of Ukraine
2024
|
| Subjects: | |
| Online Access: | https://jais.net.ua/index.php/files/article/view/424 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Problems of Control and Informatics |
Institution
Problems of Control and Informatics| id |
oai:ojs2.jais.net.ua:article-424 |
|---|---|
| record_format |
ojs |
| institution |
Problems of Control and Informatics |
| baseUrl_str |
|
| datestamp_date |
2025-05-30T09:59:18Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
компонування м’які багатокутники метод phi-функцій нелінійна оптимізація евристика |
| spellingShingle |
компонування м’які багатокутники метод phi-функцій нелінійна оптимізація евристика Melashenko, Oksana Romanova, Tetyana Shekhovtsov, Sergiy Компонування м’яких багатокутників в опуклому полігональному контейнері |
| topic_facet |
компонування м’які багатокутники метод phi-функцій нелінійна оптимізація евристика composition soft polygons phi-function method nonlinear optimization heuristics combinatorial optimization |
| format |
Article |
| author |
Melashenko, Oksana Romanova, Tetyana Shekhovtsov, Sergiy |
| author_facet |
Melashenko, Oksana Romanova, Tetyana Shekhovtsov, Sergiy |
| author_sort |
Melashenko, Oksana |
| title |
Компонування м’яких багатокутників в опуклому полігональному контейнері |
| title_short |
Компонування м’яких багатокутників в опуклому полігональному контейнері |
| title_full |
Компонування м’яких багатокутників в опуклому полігональному контейнері |
| title_fullStr |
Компонування м’яких багатокутників в опуклому полігональному контейнері |
| title_full_unstemmed |
Компонування м’яких багатокутників в опуклому полігональному контейнері |
| title_sort |
компонування м’яких багатокутників в опуклому полігональному контейнері |
| title_alt |
Layout of soft polygons in an optimized convex polygonal container |
| description |
The problem of arranging irregular soft polygons into an optimized convex polygonal container given by a set of variable vertices is formulated. Polygons can change their shapes within the given limits of elasticity parameters, provided that their area is preserved. Free translations and continuous rotations of polygons are allowed. The maximum number of container vertices m is fixed. However, the shape of the container is not fixed and is determined in such a way as to minimize its area/perimeter subject to a container convexity condition, pairwise non-overlapping of soft polygons and containment of each soft polygon into the container. Another interpretation of this problem is the problem of finding the minimum in perimeter/area convex hull with the number of vertices not exceeding m. Tools of mathematical modeling of soft object placement conditions have been constructed in the form of new classes of phi-functions and quasi phi-functions. The corresponding mathematical model of the optimized layout problem of soft irregular polygons is constructed as a nonlinear programming model. An algorithm of constructing feasible starting points for searching for local minima is proposed. A decomposition approach has been developed that allows reducing a large-scale problem to a sequence of nonlinear programming problems of considerably smaller dimension, linear to the number of convex components of irregular soft polygons. The computational results are provided. The optimal solutions for small problems is proven using the global solver BARON. For medium examples, the proposed heuristic and the local solver IPOPT are used. |
| publisher |
V.M. Glushkov Institute of Cybernetics of NAS of Ukraine |
| publishDate |
2024 |
| url |
https://jais.net.ua/index.php/files/article/view/424 |
| work_keys_str_mv |
AT melashenkooksana layoutofsoftpolygonsinanoptimizedconvexpolygonalcontainer AT romanovatetyana layoutofsoftpolygonsinanoptimizedconvexpolygonalcontainer AT shekhovtsovsergiy layoutofsoftpolygonsinanoptimizedconvexpolygonalcontainer AT melashenkooksana komponuvannâmâkihbagatokutnikívvopuklomupolígonalʹnomukontejnerí AT romanovatetyana komponuvannâmâkihbagatokutnikívvopuklomupolígonalʹnomukontejnerí AT shekhovtsovsergiy komponuvannâmâkihbagatokutnikívvopuklomupolígonalʹnomukontejnerí |
| first_indexed |
2025-10-30T02:49:09Z |
| last_indexed |
2025-10-30T02:49:09Z |
| _version_ |
1847373384706424832 |
| spelling |
oai:ojs2.jais.net.ua:article-4242025-05-30T09:59:18Z Layout of soft polygons in an optimized convex polygonal container Компонування м’яких багатокутників в опуклому полігональному контейнері Melashenko, Oksana Romanova, Tetyana Shekhovtsov, Sergiy компонування м’які багатокутники метод phi-функцій нелінійна оптимізація евристика composition soft polygons phi-function method nonlinear optimization heuristics combinatorial optimization The problem of arranging irregular soft polygons into an optimized convex polygonal container given by a set of variable vertices is formulated. Polygons can change their shapes within the given limits of elasticity parameters, provided that their area is preserved. Free translations and continuous rotations of polygons are allowed. The maximum number of container vertices m is fixed. However, the shape of the container is not fixed and is determined in such a way as to minimize its area/perimeter subject to a container convexity condition, pairwise non-overlapping of soft polygons and containment of each soft polygon into the container. Another interpretation of this problem is the problem of finding the minimum in perimeter/area convex hull with the number of vertices not exceeding m. Tools of mathematical modeling of soft object placement conditions have been constructed in the form of new classes of phi-functions and quasi phi-functions. The corresponding mathematical model of the optimized layout problem of soft irregular polygons is constructed as a nonlinear programming model. An algorithm of constructing feasible starting points for searching for local minima is proposed. A decomposition approach has been developed that allows reducing a large-scale problem to a sequence of nonlinear programming problems of considerably smaller dimension, linear to the number of convex components of irregular soft polygons. The computational results are provided. The optimal solutions for small problems is proven using the global solver BARON. For medium examples, the proposed heuristic and the local solver IPOPT are used. Сформульовано задачу компонування довільних м’яких багатокутників в оптимізованому за формою опуклому полігональному контейнері, заданому множиною змінних вершин. Багатокутники мають змінну просторову форму в заданих межах параметрів еластичності за умови збереження їхньої площі. Допускаються вільні трансляції та неперервні повороти багатокутників. Максимальна кількість вершин контейнера m є фіксованою. Однак форма контейнера не задана і визначається таким чином, щоб мінімізувати його площу/периметр за дотримання умов опуклості контейнера, неперетину м’яких багатокутників та їхнього включення до контейнера. Іншою інтерпретацією цієї задачі є пошук мінімальної за периметром/площею опуклої оболонки з кількістю вершин, що не перевищує m. Розроблено засоби математичного моделювання умов розміщення м’яких об’єктів у вигляді нових класів phi-функцій та квазіphi-функцій. Побудовано математичну модель оптимізації компонування довільних м’яких багатокутників як задачу нелінійного програмування. Запропоновано метод побудови допустимих стартових точок для пошуку локальних мінімумів. Розроблено метод декомпозиції, який дозволяє звести задачу великої розмірності до послідовності задач нелінійного програмування значно меншої розмірності, лінійної до числа опуклих компонент нерегулярних м’яких багатокутників. Наведено результати обчислювальних експериментів. Доведено оптимальність розв’язків для задач малої розмірності за допомогою глобального солвера BARON. Для прикладів більшої розмірності застосовано запропоновану евристику та локальний солвер IPOPT. V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2024-12-23 Article Article application/pdf https://jais.net.ua/index.php/files/article/view/424 10.34229/1028-0979-2024-6-2 Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; Том 69 № 6 (2024): Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; 24-32 International Scientific Technical Journal "Problems of Control and Informatics; Том 69 № 6 (2024): International Scientific Technical Journal «Problems of Control and Informatics»; 24-32 International Scientific Technical Journal "Problems of Control and Informatics"; Vol. 69 No. 6 (2024): International Scientific Technical Journal «Problems of Control and Informatics»; 24-32 2786-6505 2786-6491 uk https://jais.net.ua/index.php/files/article/view/424/491 Copyright (c) 2024 Oksana Melashenko, Tetyana Romanova, Sergiy Shekhovtsov https://creativecommons.org/licenses/by-nc-nd/4.0 |