Methodological basis of solving sphere packing problem: transformation of knapsack problem to open dimension problem

Abstract

The subject matter of the paper is the problem of optimal packing of spheres of different dimension into a container of arbitrary geometric shape. The goalis to construct a mathematical model which associates different statements of the problem. Sphere packing problems (SPP) are combinatorial optimization problems known as cutting and packing problems. SPP consists in placement of a given set of spheres with given radii into a container of regular or irregular geometric shape. The task to be solved are: to investigate mathematical models of the two formulations according to the classification of cutting and packing problems: knapsack problems (KP) and open dimension problems (ODP); to construct a mathematical model which allow solve KP as ODP. The methodsused are: the phifunction technique, increasing the problem dimension, homothetic transformations. KP is formulated as mixed discrete-continuous programming problem. A new approach which reduces solving KP to solving ODP for packing unequal and equal spheres into a container with the variable coefficient of homothety and allows adopt the jump algorithm for KP is suggested. To this end, for a given set of spheres KP is stated as a nonlinear programming problem in which the coefficient of homothety is an independent variable bounded below. The unit value of the coefficient corresponds to the original size of the container. A graphical illustration of the optimization process is presented. Conclusions. The approach suggested is a methodological basis for solving SPP. The generality of the approach lies in the fact that solvingSPP does not depend on its formulation(KP or ODP). The approach is suitable for packing unequal and equal spheres into containers of arbitrary spatial shapes for which phifunctions can be constructed.

Предметом статті є задача оптимальної упаковки куль різної розмірності в контейнер довільної геометричної форми. Мета полягає в тому, щоб побудувати математичну модель, в якій зв'язуються різні формулювання задачі. Задача упаковки куль (SPP) є задачею комбінаторної оптимізації, відомою як задача розкрою й упаковки. SPP полягає в розміщенні заданого набору куль із заданими радіусами в контейнері правильної або неправильної геометричної форми. Задача, яку необхідно вирішити, полягає в тому, щоб: дослідити математичні моделі двох постановок відповідно до класифікації задач розкрою й упаковки: задачі про рюкзак (KP) та задачі зі змінним розміром (ODP); побудувати математичну модель, яка дозволяє розв’язати задачу KP як задачу ODP. Використовувані методи: метод phi-функцій, збільшення розмірності задачі, гомотетичні перетворення. Задача KP формулюється як змішана задача дискретно-неперервного програмування. Пропонується новий підхід, в якому розв’язання задачі KP зводиться до розв’язання задачі ODP для упаковки нерівних і рівних куль у контейнерізі змінним коефіцієнтом гомотетії й який дозволяє використовувати jump-алгоритм для задачі KP. З цією метою задача KP для даного набору куль представляється у вигляді задачі нелінійного програмування, в якій коефіцієнт гомотетії розглядається в якості незалежної змінної, обмеженою знизу. Коефіцієнт гомотетії, який дорівнює одиниці, відповідає початковому розміру контейнера. Зображена графічна ілюстрація процесу оптимізації. Висновки. Запропонований підхід є методологічною основою для розв’язання задачі SPP. Універсальність підходу полягає в тому, що розв’язання задач іне залежить від її постановки (KP або ODP). Підхід застосовний для упаковки нерівних і рівних куль у контейнерах довільних просторових форм, для яких можуть бути побудовані phi-функції.