Optimal packing of convex polytopes using quasi-phi-functions
We study a packing problem of a given collection of convex polytopes into a rectangular container of minimal volume. Continuous rotations and translations of polytopes are allowed. In addition a given minimal allowable distances between polytopes are taking into account. We employ radical free quasi...
Gespeichert in:
| Datum: | 2015 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут енергетичних машин і систем ім. А. М. Підгорного Національної академії наук України
2015
|
| Schlagworte: | |
| Online Zugang: | https://journals.uran.ua/jme/article/view/46687 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Energy Technologies & Resource Saving |
Institution
Energy Technologies & Resource Saving| id |
oai:ojs.journals.uran.ua:article-46687 |
|---|---|
| record_format |
ojs |
| spelling |
oai:ojs.journals.uran.ua:article-466872015-07-14T04:08:18Z Optimal packing of convex polytopes using quasi-phi-functions Pankratov, A. V. Romanova, T. E. Chugay, A. M. packing polytopes continuous rotations non-overlapping allowable distances quasi-phi-functions mathematical model non-linear optimization УДК 519.859 упаковка многогранники непрерывные повороты непересечение допустимые расстояния квази-phi-функции математическая модель нелинейная оптимизация УДК 519.859 упаковка багатогранники безперервні повороти неперетинання припустимі відстані квазі-phi-функції математична модель нелінійна оптимізація УДК 519.859 We study a packing problem of a given collection of convex polytopes into a rectangular container of minimal volume. Continuous rotations and translations of polytopes are allowed. In addition a given minimal allowable distances between polytopes are taking into account. We employ radical free quasi-phi-functions and adjusted quasi-phi-functions to describe placement constraints. The use of quasi-phi-functions, instead of phi-functions, allows us to simplify non-overlapping, as well as, to describe distance constraints, but there is a price to pay: now the optimization has to be performed over a larger set of parameters, including the extra variables used by our new functions. We provide an exact mathematical model of the problem as a nonlinear programming problem. We also develop an efficient solution algorithm which involves a starting point algorithm, using homothetic trasformations of geometric objects and efficient local optimization procedure, which allows us to runtime and memory). We present here a number of examples to demonstrate the efficiency of our methodology. Рассматривается задача упаковки выпуклых многоранников в прямоугольном контейнере минимального объема. Допускаются непрерывные трансляции и повороты многогранников. Учитываются минимально допустимые расстояния, заданные между многогранниками. Для формализвации ограничений размещения применяются свободные от радикалов квази-phi-функции и псевдонормализованные квази-phi-функции. Использование квази-phi-функций, вместо phi-функций, позволяет упростить вид ограничений непересечения многогранников и описать в аналитическом виде ограничения на минимально допустимые расстояния, заданные между многогранниками. Однако процесс оптимизации требует большего числа параметров, включая дополнительные переменные для квази-phi-функций. Строится математическая модель в виде задачи нелинейного программирования. Предлагается эффективный метод решения, включающий: алгоритм, основанный на гомотетических преобразованиях геометрических объектов для построения допустимых стартовых точек, и процедура локальной оптимизации, которая позволила значительно уменьшить размерность задачи, а также сократить вычислительные ресурсы (время и память). Приводятся результаты численных экспериментов, которые демонстрируют эффективность предложенной методологии решения задачи упаковки выпуклых многогранников. Розглядається задача упаковки опуклих багатогранників у прямокутний контейнер мінімального об’єму. При цьому багатогранники припускають безперервні повороти та трансляції. Крім того, враховуються мінімально припустимі відстані між багатогранниками. Для побудови математичної моделі задачі як задачі нелінійного програмування використовуються вільні від радикалів квазі-phi-функції. Розроблено ефективний алгоритм розв’язання, який дозволяє зменшити розмірність задачі і обчислювальні витрати. Наведено числові приклади. Інститут енергетичних машин і систем ім. А. М. Підгорного Національної академії наук України 2015-07-14 Article Article application/pdf https://journals.uran.ua/jme/article/view/46687 Journal of Mechanical Engineering; Vol. 18 No. 2 (2015); 55-65 Проблемы машиностроения; Том 18 № 2 (2015); 55-65 Проблеми машинобудування; Том 18 № 2 (2015); 55-65 2709-2992 2709-2984 en https://journals.uran.ua/jme/article/view/46687/42874 Copyright (c) 2015 A. V. Pankratov, T. E. Romanova, A. M. Chugay https://creativecommons.org/licenses/by-nd/4.0 |
| institution |
Energy Technologies & Resource Saving |
| baseUrl_str |
|
| datestamp_date |
2015-07-14T04:08:18Z |
| collection |
OJS |
| language |
English |
| topic |
packing polytopes continuous rotations non-overlapping allowable distances quasi-phi-functions mathematical model non-linear optimization УДК 519.859 |
| spellingShingle |
packing polytopes continuous rotations non-overlapping allowable distances quasi-phi-functions mathematical model non-linear optimization УДК 519.859 Pankratov, A. V. Romanova, T. E. Chugay, A. M. Optimal packing of convex polytopes using quasi-phi-functions |
| topic_facet |
packing polytopes continuous rotations non-overlapping allowable distances quasi-phi-functions mathematical model non-linear optimization УДК 519.859 упаковка многогранники непрерывные повороты непересечение допустимые расстояния квази-phi-функции математическая модель нелинейная оптимизация УДК 519.859 упаковка багатогранники безперервні повороти неперетинання припустимі відстані квазі-phi-функції математична модель нелінійна оптимізація УДК 519.859 |
| format |
Article |
| author |
Pankratov, A. V. Romanova, T. E. Chugay, A. M. |
| author_facet |
Pankratov, A. V. Romanova, T. E. Chugay, A. M. |
| author_sort |
Pankratov, A. V. |
| title |
Optimal packing of convex polytopes using quasi-phi-functions |
| title_short |
Optimal packing of convex polytopes using quasi-phi-functions |
| title_full |
Optimal packing of convex polytopes using quasi-phi-functions |
| title_fullStr |
Optimal packing of convex polytopes using quasi-phi-functions |
| title_full_unstemmed |
Optimal packing of convex polytopes using quasi-phi-functions |
| title_sort |
optimal packing of convex polytopes using quasi-phi-functions |
| description |
We study a packing problem of a given collection of convex polytopes into a rectangular container of minimal volume. Continuous rotations and translations of polytopes are allowed. In addition a given minimal allowable distances between polytopes are taking into account. We employ radical free quasi-phi-functions and adjusted quasi-phi-functions to describe placement constraints. The use of quasi-phi-functions, instead of phi-functions, allows us to simplify non-overlapping, as well as, to describe distance constraints, but there is a price to pay: now the optimization has to be performed over a larger set of parameters, including the extra variables used by our new functions. We provide an exact mathematical model of the problem as a nonlinear programming problem. We also develop an efficient solution algorithm which involves a starting point algorithm, using homothetic trasformations of geometric objects and efficient local optimization procedure, which allows us to runtime and memory). We present here a number of examples to demonstrate the efficiency of our methodology. |
| publisher |
Інститут енергетичних машин і систем ім. А. М. Підгорного Національної академії наук України |
| publishDate |
2015 |
| url |
https://journals.uran.ua/jme/article/view/46687 |
| work_keys_str_mv |
AT pankratovav optimalpackingofconvexpolytopesusingquasiphifunctions AT romanovate optimalpackingofconvexpolytopesusingquasiphifunctions AT chugayam optimalpackingofconvexpolytopesusingquasiphifunctions |
| first_indexed |
2025-07-17T11:59:30Z |
| last_indexed |
2025-07-17T11:59:30Z |
| _version_ |
1850410931486457856 |