Optimal packing of convex polytopes using quasi-phi-functions

Abstract

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