Optimal clustering of polyhedra

Abstract

Cutting and packing problems have a wide spectrum of applications. when dealing with polyhedra, an important problem is the identification of the optimal clustering of two objects. within this paper we consider a containing region (cuboid, sphere, cylinder) of variable sizes and two polyhedra that can be continuously translated and rotated. In addition minimal allowable distances between objects and between each object and the frontier of a containing region may be imposed. The objects should be arranged within a containing region such that a given objective will reach its minimal value. we consider a volume or metrical characteristics of the containing region as the objective, which depends on the variable parameters associated with the objects and the containing region. The paper presents a mathematical model in the form of nonlinear optimisation problem, based on the phi-function technique. we also developed a solution algorithm and provide new benchmark instances of finding the containing region that has either minimal volume or homothetic coefficient of a given containing region. Задачи упаковки и раскроя имеют широкий спектр применения. При размещении многогранников важной задачей является поиск оптимальной кластеризации двух объектов. В качестве области размещения рассматривается контейнер (кубоид, шар, цилиндр) с переменными метрическими характеристиками и два многогранника, которые допускают непрерывные трансляции и вращения. Учитываются ограничения на минимально допустимые расстояния между объектами и между каждым объектом и границей области размещения. Объекты должны быть размещены в контейнере таким образом, чтобы заданная функция цели достигала минимального значения. В качестве функции цели рассматривается объем или метрические характеристики контейнера. функция цели зависит от переменных параметров, зависящих от объектов размещения и вида контейнера. В статье представлена математическая модель в виде задачи нелинейной оптимизации, основанная на методе phi-функций. Предлагается алгоритм решения и приводятся новые результаты для поиска контейнера минимального объема или с минимальным коэффициентом гомотетии. Задачі упаковки і розкрою мають широкий спектр застосування. При розміщенні багатогранників важливою задачею є знаходження оптимальної кластеризації двох об’єктів. У статті розглядається контейнер (кубоід, куля, циліндр) зі змінними метричними характеристиками та два багатогранника, які допускають безперервні трансляції та обертання. Враховуються обмеження на мінімально допустимі відстані між об’єктами і між кожним об’єктом і границею області. Об’єкти повинні бути розташовані в контейнері таким чином, щоб задана функція мети досягала мінімального значення. як функція мети розглядається об’єм або метричні характеристики контейнера. функція мети залежить від змінних параметрів, залежних від об’єктів і типу контейнера. У статті представлена математична модель у вигляді задачі нелінійної оптимізації яка заснована на методі phi-функцій. Запропоновано алгоритм розв’язання та наведено нові результати пошуку контейнеру мінімального об’єму або з мінімальним коефіцієнтом гомотетії.