Сучасні інформаційні системи (May 2019)
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 goal is 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 methods used are: the phi-function 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 solving SPP 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 phi-functions can be constructed.
Keywords
