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...
Gespeichert in:
| Veröffentlicht in: | Проблемы машиностроения |
|---|---|
| Datum: | 2015 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Englisch |
| Veröffentlicht: |
Інстиут проблем машинобудування ім. А.М. Підгорного НАН України
2015
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/99180 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Optimal packing of convex polytopes using quasi-phi-functions / A.V. Pankratov, T.E. Romanova, A.M. Chugay // Проблемы машиностроения. — 2015. — Т. 18, № 2. — С. 55-65. — Бібліогр.: 27 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862727416979390464 |
|---|---|
| author | Pankratov, A.V. Romanova, T.E. Chugay, A.M. |
| author_facet | Pankratov, A.V. Romanova, T.E. Chugay, A.M. |
| citation_txt | Optimal packing of convex polytopes using quasi-phi-functions / A.V. Pankratov, T.E. Romanova, A.M. Chugay // Проблемы машиностроения. — 2015. — Т. 18, № 2. — С. 55-65. — Бібліогр.: 27 назв. — англ. |
| collection | DSpace DC |
| container_title | Проблемы машиностроения |
| 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.
Рассматривается задача упаковки выпуклых многоранников в прямоугольном контейнере минимального объема. Допускаются непрерывные трансляции и повороты многогранников. Учитываются минимально допустимые расстояния, заданные между многогранниками. Для формализвации ограничений размещения применяются свободные от радикалов квази-phi-функции и псевдонормализованные квази-phi-функции. Использование квази-phi-функций, вместо phi-функций, позволяет упростить вид ограничений непересечения многогранников и описать в аналитическом виде ограничения на минимально допустимые расстояния, заданные между многогранниками. Однако процесс оптимизации требует большего числа параметров, включая дополнительные переменные для квази-phi-функций. Строится математическая модель в виде задачи нелинейного программирования. Предлагается эффективный метод решения, включающий: алгоритм, основанный на гомотетических преобразованиях геометрических объектов для построения допустимых стартовых точек, и процедура локальной оптимизации, которая позволила значительно уменьшить размерность задачи, а также сократить вычислительные ресурсы (время и память). Приводятся результаты численных экспериментов, которые демонстрируют эффективность предложенной методологии решения задачи упаковки выпуклых многогранников.
Розглядається задача упаковки опуклих багатогранників у прямокутний контейнер мінімального об’єму. При цьому багатогранники припускають безперервні повороти та трансляції. Крім того, враховуються мінімально припустимі відстані між багатогранниками. Для побудови математичної моделі задачі як задачі нелінійного програмування використовуються вільні від радикалів квазі-phi-функції. Розроблено ефективний алгоритм розв’язання, який дозволяє зменшити розмірність задачі і обчислювальні витрати. Наведено числові приклади.
|
| first_indexed | 2025-12-07T19:02:22Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-99180 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0131-2928 |
| language | English |
| last_indexed | 2025-12-07T19:02:22Z |
| publishDate | 2015 |
| publisher | Інстиут проблем машинобудування ім. А.М. Підгорного НАН України |
| record_format | dspace |
| spelling | Pankratov, A.V. Romanova, T.E. Chugay, A.M. 2016-04-23T18:30:38Z 2016-04-23T18:30:38Z 2015 Optimal packing of convex polytopes using quasi-phi-functions / A.V. Pankratov, T.E. Romanova, A.M. Chugay // Проблемы машиностроения. — 2015. — Т. 18, № 2. — С. 55-65. — Бібліогр.: 27 назв. — англ. 0131-2928 https://nasplib.isofts.kiev.ua/handle/123456789/99180 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-функції. Розроблено ефективний алгоритм розв’язання, який дозволяє зменшити розмірність задачі і обчислювальні витрати. Наведено числові приклади. en Інстиут проблем машинобудування ім. А.М. Підгорного НАН України Проблемы машиностроения Прикладная математика Optimal packing of convex polytopes using quasi-phi-functions Article published earlier |
| spellingShingle | Optimal packing of convex polytopes using quasi-phi-functions Pankratov, A.V. Romanova, T.E. Chugay, A.M. Прикладная математика |
| title | 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_short | Optimal packing of convex polytopes using quasi-phi-functions |
| title_sort | optimal packing of convex polytopes using quasi-phi-functions |
| topic | Прикладная математика |
| topic_facet | Прикладная математика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/99180 |
| work_keys_str_mv | AT pankratovav optimalpackingofconvexpolytopesusingquasiphifunctions AT romanovate optimalpackingofconvexpolytopesusingquasiphifunctions AT chugayam optimalpackingofconvexpolytopesusingquasiphifunctions |