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.