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 qua...
Збережено в:
| Опубліковано в: : | Проблемы машиностроения |
|---|---|
| Дата: | 2015 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інстиут проблем машинобудування ім. А.М. Підгорного НАН України
2015
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/99180 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Optimal packing of convex polytopes using quasi-phi-functions / A.V. Pankratov, T.E. Romanova, A.M. Chugay // Проблемы машиностроения. — 2015. — Т. 18, № 2. — С. 55-65. — Бібліогр.: 27 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-99180 |
|---|---|
| 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 |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Optimal packing of convex polytopes using quasi-phi-functions |
| spellingShingle |
Optimal packing of convex polytopes using quasi-phi-functions Pankratov, A.V. Romanova, T.E. Chugay, A.M. Прикладная математика |
| 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 |
| author |
Pankratov, A.V. Romanova, T.E. Chugay, A.M. |
| author_facet |
Pankratov, A.V. Romanova, T.E. Chugay, A.M. |
| topic |
Прикладная математика |
| topic_facet |
Прикладная математика |
| publishDate |
2015 |
| language |
English |
| container_title |
Проблемы машиностроения |
| publisher |
Інстиут проблем машинобудування ім. А.М. Підгорного НАН України |
| format |
Article |
| 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-функції. Розроблено ефективний алгоритм розв’язання, який дозволяє зменшити розмірність задачі і обчислювальні витрати. Наведено числові приклади.
|
| issn |
0131-2928 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/99180 |
| 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 назв. — англ. |
| work_keys_str_mv |
AT pankratovav optimalpackingofconvexpolytopesusingquasiphifunctions AT romanovate optimalpackingofconvexpolytopesusingquasiphifunctions AT chugayam optimalpackingofconvexpolytopesusingquasiphifunctions |
| first_indexed |
2025-12-07T19:02:22Z |
| last_indexed |
2025-12-07T19:02:22Z |
| _version_ |
1850877299063259136 |