The thesis considers the problem of optimal packing of the predefined set of
ellipsoids into a convex container of minimum sizes (appropriate metrical
characteristic). The ellipsoids can be free rotated and translated. The container can be
an arbitrary convex domain, which frontier is formed by cylindrical, elliptical,
spherical surfaces and planes.
The basic ellipsoid packing problem (3DBEP) is stated. Three realizations of the
basic ellipsoid packing problem are formulated depending on the objective function
type (a volume, coefficient of homothety, one of the metrical characteristics of a
container), the container shape (a cuboid, cylinder, sphere, ellipsoid or convex
polytope), the features of metrical characteristics of ellipsoids (homothetic, spheroids,
arbitrary), the restrictions on the orientation of ellipsoids (equally oriented,
continuously rotated), minimum allowable distances: 3DHEP (Homothetic Ellipsoid
Packing) – packing of equally oriented homotetic ellipsoids into a container (a cuboid,
ellipsoid); 3DEP (Ellipsoid Packing) – packing of ellipsoids of revolution (spheroids)
into a container (a cuboid, cylinder); 3DAEP (Approximated Ellipsoid Packing) –
packing of ellipsoids into an arbitrary container taking into account the minimum
allowable distances. For analytical description of the non-overlapping and containment
constraints taking into account minimum allowable distances quasi phi-functions, phifunctions,
adjusted phi-functions and adjusted quasi phi-functions are constructed.
Mathematical models of the basic ellipsoid packing problem and it`s realizations are
provided in the form of NLP-problems, using the developed geometric tools.
Based on the multistart method, a solution strategy for the basic ellipsoid
packing problem is developed. The methods for generating feasible starting points and
searching for local minima are introduced for each realization of the problem 3DBEP.
The local optimization method reduces NLP-problem of a large dimension with a large
25
number of nonlinear inequalities to a sequence of nonlinear programming subproblems
of a smaller dimension with a fewer non-linear inequalities.
The numerical experiments for the realizations of the basic ellipsoid packing
problem in different container are given. The analysis of the results shows the
effectiveness of the developed methods and algorithms.
The results can be used in the computer simulation of the structure of liquids,
crystals, the flow and compression of granular materials, in the thermodynamics,
biological sciences, nuclear medicine, free support additive technologies (3D printing),
as well as, in a robotic problem.
Keywords: packing, ellipsoids, convex container, phi-function technique,
mathematical model, nonlinear optimization.
