Optimal packing of convex polytopes using quasi-phi-functions

• Published in: Проблемы машиностроения
• Date: 2015
• Main Authors: Pankratov, A.V., Romanova, T.E., Chugay, A.M.
• Format: Article
• Language: English
• Published: Інстиут проблем машинобудування ім. А.М. Підгорного НАН України 2015
• Subjects: Прикладная математика
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/99180
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Optimal packing of convex polytopes using quasi-phi-functions / A.V. Pankratov, T.E. Romanova, A.M. Chugay // Проблемы машиностроения. — 2015. — Т. 18, № 2. — С. 55-65. — Бібліогр.: 27 назв. — англ.

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-функції. Розроблено ефективний алгоритм розв’язання, який дозволяє зменшити розмірність задачі і обчислювальні витрати. Наведено числові приклади.