# Packing Different Cuboids with Rotations and Spheres into a Cuboid

Authors: Y. G. Stoyan; A. M. Chugay
Journal: Advances in Decision Sciences
 (2014)

---

## Abstract

The paper considers a packing optimization problem of different spheres and cuboids into a cuboid of the minimal height. Translations and continuous rotations of cuboids are allowed. In the paper, we offer a way of construction of special functions (Φ-functions) describing how rotations can be dealt with. These functions permit us to construct the mathematical model of the problem as a classical mathematical programming problem. Basic characteristics of the mathematical model are investigated. When solving the problem, the characteristics allow us to apply a number of original and state-of-the-art efficient methods of local and global optimization. Numerical examples of packing from 20 to 300 geometric objects are given.


---

## Body

## 1. Introduction

At present, scientific research concerning mathematical modeling of optimization packing problems of 3D geometrical objects is intensively performed. The great interest to the given class of problems is motivated by the need of wide use of the problems both in scientific researches and applications in different branches of industry. Therefore, when tackling these classes of problems, development of fundamental bases and tools for mathematical and computer modeling is very important.A state-of-the-art review of bin packing techniques is considered in [1]. It should be noted that there are many publications devoted to packing of cuboids which can be rotated only through 90° around of all coordinate axes.Currently, 3D packing problems of cuboids, for which translations and continuous rotations are allowed, and spheres are poorly investigated.The problem of packing nonoriented polyhedrons can be applied in CAD system for rapid prototyping which uses selective laser sintering process of a special powder [2]. Besides, the problem is applied in nanotechnologies for 3D modeling, visual and quality analysis of structural characteristics and mechanical properties of various composite, firm, liquid, glassy materials, granulated media, and biological systems [3–6]. Packing of spheres and cuboids is used to model heterogeneous and porous material morphologies such as concrete, sand, coal, porous explosives, and solid rocket propellants [7].Also, the problem of packing nonoriented cuboids is applied to car design [8].Various optimization search algorithms for solving 3D layout problems are considered in paper [9]. In the paper, the authors notice that simulated annealing algorithms and genetic algorithms are stochastic methods that are used in a wide variety of 3D problems.A lot of authors traditionally use either spheres or cuboids or regular oriented polyhedrons to solve 3D packing problems. For solving problems, the Minkowski sum [10] is used. The sum can be successfully exploited for lattice packing of geometric objects [4, 11].Torquato and Jiao in paper [4] try to find dense packing of tetrahedra. The authors formulate the problem of generating dense packing of polyhedra within an adaptive fundamental cell subject to periodic boundary conditions as an optimization problem which they call the adaptive shrinking cell scheme.Paper [12] presents a heuristic approach based on mixed integer programming for solving nonstandard 3D problems with additional conditions. The described approach is addressed to standard MINLP solvers exploiting linear substructures of the mathematical model.The packing of 3D tetris-like items with orthogonal rotations, within a convex domain (polyhedron) with additional conditions (separation planes, fixed position or orientation for some items, presence of “holes” within the domain, and balancing conditions), is considered in [13]. The author proposes approach which is based on mixed integer linear/nonlinear programming, from a global optimization point of view with an approximate starting solution.Article [14] is devoted to the review of modern methods of modeling of inclusion, intersection, and contact relations of geometric objects. In the given work, it is noticed that at present one of the perspective approaches for the construction of adequate mathematical models of packing problems is the method of Φ-functions. In work [15], it is shown that the method of Φ-functions allows us to improve results of solution of packing problems of geometrical objects due to application of state-of-the-art nonlinear optimization methods.Work [16] is devoted to the construction of Φ-functions for oriented (rotations are not allowed) 3D objects whose frontiers are sphere, cuboid, cone, and cylinder. Article [17] considers the construction of the Φ-function for two convex oriented polytopes. In paper [18], authors develop Φ-functions that handle any 2D objects whose boundary is formed by linear segments and/or circular arcs. Constructed Φ-functions support free translations and rotations of objects.In this work, we consider packing problem of spheres and cuboids. Our mathematical model and approach support free translations and rotations of cuboids. In this respect, it differs from many other approaches that optimize the position of one object at a time. In addition, the solution of the packing problem reduces to minimization of an objective function on a multidimensional space, which can be done by mathematical programming, while most researchers use heuristics for solving packing problems.The considered packing problem has the following statement. Let there be different cuboidsP
i
=
{
X
=
(
x
,
y
,
z
)
∈
R
3
:
-
l
i
0
≤
x
≤
l
i
0
,
-
w
i
0
≤
y
≤
w
i
0
,
-
h
i
0
≤
z
≤
h
i
0
}, i
∈
I
1
=
{
1,2
,
…
,
n
1
}, different spheres S
j
=
{
X
=
(
x
,
y
,
z
)
∈
R
3
:
x
2
+
y
2
+
z
2
-
(
r
j
0
)
2
≤
0
}, j
∈
I
2
=
{
n
1
+
1
,
n
1
+
2
,
…
,
n
=
n
1
+
n
2
}, and a container (cuboid) P
=
{
X
=
(
x
,
y
,
z
)
∈
R
3
:
-
l
≤
x
≤
l
,
-
w
≤
y
≤
w
,
h
1
≤
z
≤
h
2
,
h
1
>
0
}, where h
1 and h
2 are variables. We suppose that cuboids P
i can be both translated by vectors v
i
=
(
x
i
,
y
i
,
z
i
) and rotated through angles θ
i
=
(
α
i
,
β
i
,
ϖ
i
), i
∈
I
1; that is, the location of P
i is defined by a vector u
i
=
(
v
i
,
θ
i
)
∈
R
6. Spheres S
j can be translated by vectors u
j
=
(
v
j
,
0
)
=
(
x
j
,
y
j
,
z
j
,
0,0
,
0
), j
∈
I
2. Thus, u
i is a motion vector of geometric object O
i, where O
i
=
P
i if i
∈
I
1 and O
i
=
S
i if i
∈
I
2, i
∈
I
=
I
1
∪
I
2. Hence, a vector u
=
(
u
1
,
u
2
,
…
,
u
n
1
,
u
n
1
+
1
,
u
n
1
+
2
,
…
,
u
n
)
∈
R
ω where ω
=
6
n
1
+
3
n
2 determines the location of cuboids P
i, i
∈
I
1 and spheres S
j, j
∈
I
2, in the Euclidean 3D space R
3.In what follows,O
i moved by vector u
i is denoted by O
i
(
u
i
) designated as O
i
(
u
i
) and P of height h
=
h
2
-
h
1 is denoted by P
(
h
).Basic Problem. Define a vector u which ensures an arrangement of geometric objects O
i, i
∈
I, within P
(
h
), without overlapping, so that the height h of P
(
h
) will attain the minimal value.The remainder of the paper is organized as follows. In Section2, we describe a construction of Φ-functions that are used for construction of a mathematical model of the problem. In Section 3, the mathematical model of the problem is constructed and basic characteristics of the model are investigated. Section 4 defines how starting points are derived and Section 5 presents how a local extremum points are calculated. A smooth jump from one local maximum to one another is considered in Section 6. The construction of promising points is discussed in Section 7. In Section 8, we describe the solution algorithm. Section 9 reports the computational results. Some conclusions are drawn in Section 10.


## 2.Φ-Functions

The method ofΦ-functions permits formulating adequate mathematical models of packing problems at which continuous rotations are allowed. The Φ-functions allow describing the conditions of objects nonoverlapping as a collection of inequality systems whose left-hand sides are infinitely differentiable functions. This permits applying state-of-the-art effective methods of local and global optimization for solving the problem under consideration.Definition 1.
An everywhere defined and continuous functionΦ
(
u
1
,
u
2
)
:
R
6
→
R
1 is called a Φ-function for objects O
1
(
u
1
) and O
2
(
u
2
) if the function possesses the following characteristic properties:
(1)
Φ
(
u
1
,
u
2
,
γ
1
,
γ
2
)
=
{
>
0
,
if
O
1
(
u
1
,
γ
1
)
∩
O
2
(
u
2
,
γ
2
)
=
∅
,
=
0
,
if
int
⁡
O
1
(
u
1
,
γ
1
)
∩
int
⁡
O
2
(
u
2
,
γ
2
)
=
∅
,
fr
O
1
(
u
1
,
γ
1
)
∩
fr
O
2
(
u
2
,
γ
2
)
≠
∅
,
<
0
,
if
int
⁡
O
1
(
u
1
,
γ
1
)
∩
int
⁡
O
2
(
u
2
,
γ
2
)
≠
∅
,
where int
⁡
O
i is the interior of O
i and fr
O
i is the frontier of O
i.Thus, for any location of two objectsO
i and O
j in the Euclidean 3D space R
3, the corresponding Φ-function shows how far these objects are from each other, whether they touch each other, or whether they overlap (in the latter case, the one shows how large the overlap is).Consequently, in order to formulate a mathematical model of the problem stated, it needs to constructΦ-functions for pairs of cuboids, cuboid and sphere, and pairs of spheres.


### 2.1.Φ
-Function for Two Cuboids P
i
(
u
i
) and P
j
(
u
j
)

The article [19], describes a construction of Φ-function for pairs of convex polytopes. As an example, the Φ-function for two cuboids is given in the article.


### 2.2.Φ-Function for Cuboid P
i
(
u
i
) and Sphere S
j
(
u
j
)

Let there be a cuboidP
i
=
{
X
=
(
x
,
y
,
z
)
∈
R
3
:
-
l
i
0
≤
x
≤
l
i
0
,
-
w
i
0
≤
y
≤
w
i
0
,
-
h
i
0
≤
z
≤
h
i
0
} and sphere S
j
=
{
X
=
(
x
,
y
,
z
)
∈
R
3
:
x
2
+
y
2
+
z
2
-
r
j
2
≤
0
}. Vertex coordinates of P
i are indexing as follows: V
1
=
(
l
0
,
w
0
,
h
0
), V
2
=
(
-
l
0
,
w
0
,
h
0
), V
3
=
(
l
0
,
-
w
0
,
h
0
), V
4
=
(
-
l
0
,
-
w
0
,
h
0
), V
5
=
(
l
0
,
w
0
,
-
h
0
), V
6
=
(
-
l
0
,
w
0
,
-
h
0
), V
7
=
(
l
0
,
-
w
0
,
-
h
0
), and V
8
=
(
-
l
0
,
-
w
0
,
-
h
0
) (Figure 1).Figure 1
Vertices indexing ofP
i
(
u
i
).TheΦ-function Φ
i
j
P
S
(
u
i
,
u
j
) for a cuboid P
i
(
u
i
) and a sphere S
j
(
u
j
) is completely defined by an interaction of the following subsurfaces of cuboid and sphere:(1)
a spherical surface ofS
i
(
u
i
) and facets of P
j
(
u
j
);
(2)
a spherical surface ofS
i
(
u
i
) and edges of P
j
(
u
j
);
(3)
a spherical surface ofS
i
(
u
i
) and vertices of P
j
(
u
j
).Ifu
i
=
0, then 0-level surface of Φ
i
j
P
S
(
0
,
u
j
) has the form depicted on Figure 2(a). It is easily seen that the 0-level surface consists of subsurfaces of planes (Figure 2(b)), cylinders (Figure 2(c)), and spheres (Figure 2(d)).The 0-level surface ofΦ
i
j
P
S
(
0
,
u
j
).
(a)
(b)
(c)
(d)The first tangency (Figure2(b)) form generates functions χ
i
(
u
i
,
u
j
), i
=
1
,
…
,
6, which are specified as follows:
(2)
χ
1
(
u
i
,
u
j
)
=
x
(
u
i
,
u
j
)
-
l
i
-
r
j
,
χ
2
(
u
i
,
u
j
)
=
-
x
(
u
i
,
u
j
)
-
l
i
-
r
j
,
χ
3
(
u
i
,
u
j
)
=
y
(
u
i
,
u
j
)
-
w
i
-
r
j
,
χ
4
(
u
i
,
u
j
)
=
-
y
(
u
i
,
u
j
)
-
w
i
-
r
j
,
χ
5
(
u
i
,
u
j
)
=
z
(
u
i
,
u
j
)
-
h
i
-
r
j
,
χ
6
(
u
i
,
u
j
)
=
-
z
(
u
i
,
u
j
)
-
h
i
-
r
j
,
where
(3)
x
(
u
i
,
u
j
)
=
R
i
(
x
j
-
x
i
)
,
y
(
u
i
,
u
j
)
=
R
i
(
y
j
-
y
i
)
,
z
(
u
i
,
u
j
)
=
R
i
(
z
j
-
z
i
)
,
R
i
=
(
g
i
ρ
i
q
i
)
=
(
g
i
1
g
i
2
g
i
3
r
i
1
r
i
2
r
i
3
q
i
1
q
i
2
q
i
3
)
,
g
i
1
=
cos
⁡
β
i
cos
⁡
γ
i
,
g
i
2
=
sin
γ
i
cos
⁡
α
i
+
cos
⁡
γ
i
sin
β
i
sin
α
i
,
g
i
3
=
sin
γ
i
sin
α
i
-
cos
⁡
γ
i
sin
β
i
cos
⁡
α
i
,
r
i
1
=
-
sin
γ
i
cos
⁡
β
i
,
r
i
2
=
cos
⁡
γ
i
cos
⁡
α
i
-
sin
γ
i
sin
β
i
sin
α
i
,
r
i
3
=
sin
α
i
cos
⁡
γ
i
+
sin
γ
i
sin
β
i
cos
⁡
α
i
,
q
i
1
=
sin
β
i
,
q
i
2
=
-
cos
⁡
β
i
sin
α
i
,
q
i
3
=
cos
⁡
α
i
cos
⁡
β
i
.It is easily verified that if at least one inequality of kindχ
l
(
u
i
,
u
j
)
>
0, then P
i
(
u
i
)
∩
S
j
(
u
j
)
=
∅. Based on the reasoning and relations (2), we construct the function
(4)
χ
(
u
i
,
u
j
)
=
max
⁡
l
=
1
,
…
,
6
χ
l
(
u
i
,
u
j
)
.Thus, ifχ
(
u
i
,
u
j
)
>
0 holds true, then P
i
(
u
i
)
∩
S
j
(
u
j
)
=
∅. On the other hand, if χ
(
u
i
,
u
j
)
<
0, then there can be both P
i
(
u
i
)
∩
S
j
(
u
j
)
=
∅ and P
i
(
u
i
)
∩
S
j
(
u
j
)
≠
∅ (see Figures 2(c) or 2(d)).The second tangency form derives cylindrical parts of the 0-level surface ofΦ
i
j
P
S
(
u
i
,
u
j
) (see Figure 2(c)). The parts belong to cylinders whose axes pass through edges of P
i
(
u
i
) and are specified by the following equations:
(5)
ψ
l
(
u
i
,
u
j
)
=
φ
x
k
x
2
(
u
i
,
u
j
)
+
φ
y
k
y
2
(
u
i
,
u
j
)
-
r
j
2
=
0
,
l
=
k
x
+
2
k
y
+
1
,
ψ
l
(
u
i
,
u
j
)
=
φ
y
k
y
2
(
u
i
,
u
j
)
+
φ
z
k
z
2
(
u
i
,
u
j
)
-
r
j
2
=
0
,
l
=
k
y
+
2
k
z
+
5
,
ψ
l
(
u
i
,
u
j
)
=
φ
x
k
x
2
(
u
i
,
u
j
)
+
φ
z
k
z
2
(
u
i
,
u
j
)
-
r
j
2
=
0
,
l
=
k
x
+
2
k
z
+
9
,
where φ
k
x
(
u
i
,
u
j
)
=
(
-
1
)
k
x
x
(
u
i
,
u
j
)
-
l
i, φ
y
k
y
(
u
i
,
u
j
)
=
(
-
1
)
k
y
y
(
u
i
,
u
j
)
-
w
i, and φ
z
k
z
(
u
i
,
u
j
)
=
(
-
1
)
k
z
z
(
u
i
,
u
j
)
-
h
i, k
x
,
k
y
,
k
z
∈
{
0,1
}.In order to cut necessary parts of the cylinders, we form the following equations of planes:(6)
χ
~
~
l
(
u
i
,
u
j
)
=
φ
x
k
x
(
u
i
,
u
j
)
+
φ
y
k
y
(
u
i
,
u
j
)
-
r
j
=
0
,
l
=
k
x
+
2
k
y
+
1
,
χ
~
~
l
(
u
i
,
u
j
)
=
φ
y
k
y
(
u
i
,
u
j
)
+
φ
z
k
z
(
u
i
,
u
j
)
-
r
j
=
0
,
l
=
k
y
+
2
k
z
+
5
,
χ
~
~
l
(
u
i
,
u
j
)
=
φ
x
k
x
(
u
i
,
u
j
)
+
φ
z
k
z
(
u
i
,
u
j
)
-
r
j
=
0
,
l
=
k
x
+
2
k
z
+
9
,
which are parallel to edges of P
i
(
u
i
) and pass through pairs of points lying at distance r
j from vertices V
i on the extending of edges of P
i
(
u
i
) (see Figure 3).Figure 3
The helper plane for edge(
V
1
,
V
5
).Making use of the functionsψ
l
(
u
i
,
u
j
) (5) and χ
~
~
l
(
u
i
,
u
j
) (6), l
=
1,2
,
…
,
12, we form the following functions:
(7)
τ
l
(
u
i
,
u
j
)
=
min
⁡
{
ψ
l
(
u
i
,
u
j
)
,
χ
~
~
l
(
u
i
,
u
j
)
}
.It is evident that if at least one of the inequalitiesτ
l
(
u
i
,
u
j
)
>
0, l
=
1
,
…
,
12, holds true, then P
i
(
u
i
)
∩
S
j
(
u
j
)
=
∅. The property allows us to construct the function
(8)
τ
(
u
i
,
u
j
)
=
max
⁡
l
=
1
,
…
,
12
τ
l
(
u
i
,
u
j
)
.Thus, ifτ
(
u
i
,
u
j
)
>
0, then P
i
(
u
i
)
∩
S
j
(
u
j
)
=
∅. On the other hand, if τ
l
(
u
i
,
u
j
)
<
0, then there can be both P
i
(
u
i
)
∩
S
j
(
u
j
)
=
∅ or P
i
(
u
i
)
∩
S
j
(
u
j
)
≠
∅ (see Figure 2(d)).The third tangency form (see Figure2(d)) generates spherical parts of the 0-level surface of Φ
i
j
P
S
(
u
i
,
u
j
). The parts belong to spheres that are formulated by equations
(9)
ϕ
s
(
u
i
,
u
j
)
=
φ
x
k
x
2
(
u
i
,
u
j
)
+
φ
y
k
y
2
(
u
i
,
u
j
)
+
φ
z
k
z
2
(
u
i
,
u
j
)
-
r
j
2
=
0
,
where s
=
k
x
+
2
k
y
+
4
k
z
+
1, k
x
,
k
y
,
k
z
∈
{
0,1
}; that is, s
=
1,2
,
…
,
8.Note that centers of the spheres coincide with verticesV
s, s
=
1,2
,
…
,
8, of cuboid P
i
(
u
i
) correspondently. We need to extract the necessary spherical sectors of the spheres (Figure 2(d)).To this end, we construct for each of verticesV
s, s
=
1,2
,
…
,
8, of P
i
(
u
i
) three elliptic cylinders oriented by a special way with respect to P
i
(
u
i
) and a helper plane. Let us consider the case in detail.Let equations of elliptic cylindersC
k
0, k
=
1,2
,
3, (Figure 4) have the form
(10)
C
1
0
=
2
x
2
+
y
2
-
r
2
=
0
,
C
2
0
=
x
2
+
2
z
2
-
r
2
=
0
,
C
3
0
=
2
y
2
+
z
2
-
r
2
=
0
.Figure 4
The elliptic cylinderC
1
0.We rotate the cylindersC
1
0, C
2
0, and C
3
0 through angles π
/
4 and -
π
/
4 round axes O
y, O
x, and O
z, respectively. As a result, obtained cylinders C
t
1, t
=
1,2
,
…
,
6, (see Figure 5) are specified by the equations, respectively,
(11)
C
1
1
=
(
x
+
z
)
2
+
y
2
-
r
2
=
0
,
C
2
1
=
(
x
-
z
)
2
+
y
2
-
r
2
=
0
,
C
3
1
=
x
2
+
(
y
+
z
)
2
-
r
2
=
0
,
C
4
1
=
x
2
+
(
z
-
y
)
2
-
r
2
=
0
,
C
5
1
=
(
x
+
y
)
2
+
z
2
-
r
2
=
0
,
C
6
1
=
(
y
-
x
)
2
+
z
2
-
r
2
=
0
.Figure 5
The elliptic cylinderC
1
1.It is evident that the intersections of the coordinate planex
O
y and cylinders C
1
1, C
2
1, the coordinate plane x
O
z and cylinders C
3
1, C
4
1, and the coordinate plane y
O
z and cylinders C
5
1, C
6
1 are circles of radius r
j. We rotate cylinders C
t
1, j
=
1,2
,
…
,
6, through the angles π
/
4, 3
π
/
4, 5
π
/
4, and 7
π
/
4 as follows: cylinders C
1
1 and C
2
1: we rotate round axes O
z and, as a result, cylinders C
z
t
2, t
=
1,2
,
.
.
.
8, are obtained (see Figure 6); cylinders C
3
1 and C
4
1: we rotate round axes O
y and, as a result, cylinders C
y
t
2, t
=
1,2
,
…
,
8, are obtained; cylinders C
5
1 and C
6
1: we rotate round axes O
x and, as a result, cylinders C
x
t
2, t
=
1,2
,
…
,
8, are obtained.Figure 6
The elliptic cylinderC
z
1
2.Then, we translate the triple cylindersC
x
t
2, C
y
t
2, and C
z
t
2, t
∈
{
1,2
,
…
,
8
}, by the vectors V
s, s
=
1,2
,
…
,
8. Thus, we obtain at each of the vertices V
s, s
=
1,2
,
…
,
8, of P
i
(
u
i
) three elliptic cylinders C
x
t
3, C
y
t
3, and C
z
t
3 (Figure 7) which are described by the following equations:
(12)
ϕ
~
s
1
(
u
i
,
u
j
)

=

(
2
φ
x
k
x
(
u
i
,
u
j
)

+

φ
y
k
y
(
u
i
,
u
j
)
+
φ
z
k
z
(
u
i
,
u
j
)
)
2
+
(
φ
z
k
z
(
u
i
,
u
j
)
-
φ
y
k
y
(
u
i
,
u
j
)
)
2
-
2
r
j
2
=
0
,
ϕ
~
s
2
(
u
i
,
u
j
)

=

(
φ
x
k
x
(
u
i
,
u
j
)

+

2
φ
y
k
y
(
u
i
,
u
j
)
+
φ
z
k
z
(
u
i
,
u
j
)
)
2
+
(
φ
z
k
z
(
u
i
,
u
j
)
-
φ
x
k
x
(
u
i
,
u
j
)
)
2
-
2
r
j
2
=
0
,
ϕ
~
s
3
(
u
i
,
u
j
)

=

(
φ
x
k
x
(
u
i
,
u
j
)

+

φ
y
k
y
(
u
i
,
u
j
)
+
2
φ
z
k
z
(
u
i
,
u
j
)
)
2
+
(
φ
y
k
y
(
u
i
,
u
j
)
-
φ
x
k
x
(
u
i
,
u
j
)
)
2
-
2
r
j
2
=
0
,
where s
=
k
x
+
2
k
y
+
4
k
z
+
1, k
x
,
k
y
,
k
z
∈
{
0,1
}.Figure 7
The elliptic cylinderC
z
1
3.In order to cut necessary parts of the elliptic cylinders at each of the vertices ofP
i
(
u
i
), we form the following equations of helper planes passing through triples of points lying at distance r
j from vertices V
i on the extending of edges of P
i
(
u
i
) (Figure 8):
(13)
χ
~
s
(
u
i
,
u
j
)

=

φ
x
k
x
(
u
i
,
u
j
)
+
φ
y
k
y
(
u
i
,
u
j
)
+
φ
z
k
z
(
u
i
,
u
j
)
-
r
j
,
where s
=
k
x
+
2
k
y
+
4
k
z
+
1, k
x
,
k
y
,
k
z
∈
{
0,1
}.Figure 8
The helper plane at vertexV
1.Making use of the functions (9)–(13), we form the functions
(14)
ζ
s
(
u
1
,
u
2
)
=
min
⁡
{
ϕ
s
(
u
i
,
u
j
)
,
χ
~
s
(
u
i
,
u
j
)
,
ϕ
~
s
k
(
u
i
,
u
j
)
,
k
=
1,2
,
3
ϕ
s
(
u
i
,
u
j
)
ϕ
s
}
,
s
=
1
,
…
,
8
.It is easily verified that if at least one of the inequalitiesζ
i
(
u
i
,
u
j
)
>
0, s
=
1
,
…
,
8, holds true, then P
i
(
u
i
)
∩
S
j
(
u
j
)
=
∅. Based on (14), we construct the function
(15)
ζ
(
u
i
,
u
j
)
=
max
⁡
s
=
1
,
…
,
8
ζ
s
(
u
i
,
u
j
)
.Thus, ifζ
(
u
i
,
u
j
)
>
0, then P
i
(
u
i
)
∩
S
j
(
u
j
)
=
∅.Note that if at least one of inequalities eitherχ
(
u
i
,
u
j
)
>
0 (4) or τ
(
u
i
,
u
j
)
>
0 (8) or ζ
(
u
i
,
u
j
)
>
0 (15) is satisfied, then P
i
(
u
i
)
∩
S
j
(
u
j
)
=
∅. It allows us to construct the Φ-function for cuboid P
i
(
u
i
) and sphere S
j
(
u
j
) as follows:
(16)
Φ
i
j
P
S
(
u
i
,
u
j
)
=
max
⁡
{
χ
(
u
i
,
u
j
)
,
τ
(
u
i
,
u
j
)
,
ζ
(
u
i
,
u
j
)
}
.


### 2.3.Φ-Function for P
i and Object cl
⁡
(
R
3
∖
P
)

It follows from paper [19] that the Φ-function for P
i
(
u
i
) and cl
⁡
(
R
3
∖
P
) has the form
(17)
Φ
i
P
(
u
i
)
=
min
⁡
{
F
k
j
(
u
i
)
,
k
∈
{
1,2
,
…
,
6
}
,
j
∈
{
1,2
,
…
,
8
}
}
,
where
(18)
F
1
j
(
u
i
)
=
-
x
i
-
g
i
V
j
+
l
,
F
2
j
(
u
i
)
=
x
i
-
g
i
V
j
+
l
,
F
3
j
(
u
i
)
=
-
y
i
-
r
i
V
j
+
w
,
F
4
j
(
u
i
)
=
y
i
-
r
i
V
j
+
w
,
F
5
j
(
u
i
)
=
-
z
i
-
q
i
V
j
+
h
2
,
F
6
j
(
u
i
)
=
z
i
-
q
i
V
j
-
h
1
.


### 2.4.Φ-Function for S
i and Object cl
⁡
(
R
3
∖
P
)

On the ground of (5), theΦ-function for S
i
(
u
i
) and cl
⁡
(
R
3
∖
P
) can be formulated as
(19)
Φ
i
s
(
u
i
)
=
min
⁡
{
F
k
(
u
i
)
,
k
∈
{
1,2
,
…
,
6
}
}
,
where
(20)
F
1
(
u
i
)
=
-
x
i
-
r
i
+
l
,
F
2
(
u
i
)
=
x
i
-
r
i
+
l
,
F
3
(
u
i
)
=
-
y
i
-
r
i
+
w
,
F
4
(
u
i
)
=
y
i
-
r
i
+
w
,
F
5
(
u
i
)
=
-
z
i
-
r
i
+
h
2
,
F
6
(
u
i
)
=
z
i
-
r
i
-
h
1
.


## 2.1.Φ
-Function for Two Cuboids P
i
(
u
i
) and P
j
(
u
j
)

The article [19], describes a construction of Φ-function for pairs of convex polytopes. As an example, the Φ-function for two cuboids is given in the article.


## 2.2.Φ-Function for Cuboid P
i
(
u
i
) and Sphere S
j
(
u
j
)

Let there be a cuboidP
i
=
{
X
=
(
x
,
y
,
z
)
∈
R
3
:
-
l
i
0
≤
x
≤
l
i
0
,
-
w
i
0
≤
y
≤
w
i
0
,
-
h
i
0
≤
z
≤
h
i
0
} and sphere S
j
=
{
X
=
(
x
,
y
,
z
)
∈
R
3
:
x
2
+
y
2
+
z
2
-
r
j
2
≤
0
}. Vertex coordinates of P
i are indexing as follows: V
1
=
(
l
0
,
w
0
,
h
0
), V
2
=
(
-
l
0
,
w
0
,
h
0
), V
3
=
(
l
0
,
-
w
0
,
h
0
), V
4
=
(
-
l
0
,
-
w
0
,
h
0
), V
5
=
(
l
0
,
w
0
,
-
h
0
), V
6
=
(
-
l
0
,
w
0
,
-
h
0
), V
7
=
(
l
0
,
-
w
0
,
-
h
0
), and V
8
=
(
-
l
0
,
-
w
0
,
-
h
0
) (Figure 1).Figure 1
Vertices indexing ofP
i
(
u
i
).TheΦ-function Φ
i
j
P
S
(
u
i
,
u
j
) for a cuboid P
i
(
u
i
) and a sphere S
j
(
u
j
) is completely defined by an interaction of the following subsurfaces of cuboid and sphere:(1)
a spherical surface ofS
i
(
u
i
) and facets of P
j
(
u
j
);
(2)
a spherical surface ofS
i
(
u
i
) and edges of P
j
(
u
j
);
(3)
a spherical surface ofS
i
(
u
i
) and vertices of P
j
(
u
j
).Ifu
i
=
0, then 0-level surface of Φ
i
j
P
S
(
0
,
u
j
) has the form depicted on Figure 2(a). It is easily seen that the 0-level surface consists of subsurfaces of planes (Figure 2(b)), cylinders (Figure 2(c)), and spheres (Figure 2(d)).The 0-level surface ofΦ
i
j
P
S
(
0
,
u
j
).
(a)
(b)
(c)
(d)The first tangency (Figure2(b)) form generates functions χ
i
(
u
i
,
u
j
), i
=
1
,
…
,
6, which are specified as follows:
(2)
χ
1
(
u
i
,
u
j
)
=
x
(
u
i
,
u
j
)
-
l
i
-
r
j
,
χ
2
(
u
i
,
u
j
)
=
-
x
(
u
i
,
u
j
)
-
l
i
-
r
j
,
χ
3
(
u
i
,
u
j
)
=
y
(
u
i
,
u
j
)
-
w
i
-
r
j
,
χ
4
(
u
i
,
u
j
)
=
-
y
(
u
i
,
u
j
)
-
w
i
-
r
j
,
χ
5
(
u
i
,
u
j
)
=
z
(
u
i
,
u
j
)
-
h
i
-
r
j
,
χ
6
(
u
i
,
u
j
)
=
-
z
(
u
i
,
u
j
)
-
h
i
-
r
j
,
where
(3)
x
(
u
i
,
u
j
)
=
R
i
(
x
j
-
x
i
)
,
y
(
u
i
,
u
j
)
=
R
i
(
y
j
-
y
i
)
,
z
(
u
i
,
u
j
)
=
R
i
(
z
j
-
z
i
)
,
R
i
=
(
g
i
ρ
i
q
i
)
=
(
g
i
1
g
i
2
g
i
3
r
i
1
r
i
2
r
i
3
q
i
1
q
i
2
q
i
3
)
,
g
i
1
=
cos
⁡
β
i
cos
⁡
γ
i
,
g
i
2
=
sin
γ
i
cos
⁡
α
i
+
cos
⁡
γ
i
sin
β
i
sin
α
i
,
g
i
3
=
sin
γ
i
sin
α
i
-
cos
⁡
γ
i
sin
β
i
cos
⁡
α
i
,
r
i
1
=
-
sin
γ
i
cos
⁡
β
i
,
r
i
2
=
cos
⁡
γ
i
cos
⁡
α
i
-
sin
γ
i
sin
β
i
sin
α
i
,
r
i
3
=
sin
α
i
cos
⁡
γ
i
+
sin
γ
i
sin
β
i
cos
⁡
α
i
,
q
i
1
=
sin
β
i
,
q
i
2
=
-
cos
⁡
β
i
sin
α
i
,
q
i
3
=
cos
⁡
α
i
cos
⁡
β
i
.It is easily verified that if at least one inequality of kindχ
l
(
u
i
,
u
j
)
>
0, then P
i
(
u
i
)
∩
S
j
(
u
j
)
=
∅. Based on the reasoning and relations (2), we construct the function
(4)
χ
(
u
i
,
u
j
)
=
max
⁡
l
=
1
,
…
,
6
χ
l
(
u
i
,
u
j
)
.Thus, ifχ
(
u
i
,
u
j
)
>
0 holds true, then P
i
(
u
i
)
∩
S
j
(
u
j
)
=
∅. On the other hand, if χ
(
u
i
,
u
j
)
<
0, then there can be both P
i
(
u
i
)
∩
S
j
(
u
j
)
=
∅ and P
i
(
u
i
)
∩
S
j
(
u
j
)
≠
∅ (see Figures 2(c) or 2(d)).The second tangency form derives cylindrical parts of the 0-level surface ofΦ
i
j
P
S
(
u
i
,
u
j
) (see Figure 2(c)). The parts belong to cylinders whose axes pass through edges of P
i
(
u
i
) and are specified by the following equations:
(5)
ψ
l
(
u
i
,
u
j
)
=
φ
x
k
x
2
(
u
i
,
u
j
)
+
φ
y
k
y
2
(
u
i
,
u
j
)
-
r
j
2
=
0
,
l
=
k
x
+
2
k
y
+
1
,
ψ
l
(
u
i
,
u
j
)
=
φ
y
k
y
2
(
u
i
,
u
j
)
+
φ
z
k
z
2
(
u
i
,
u
j
)
-
r
j
2
=
0
,
l
=
k
y
+
2
k
z
+
5
,
ψ
l
(
u
i
,
u
j
)
=
φ
x
k
x
2
(
u
i
,
u
j
)
+
φ
z
k
z
2
(
u
i
,
u
j
)
-
r
j
2
=
0
,
l
=
k
x
+
2
k
z
+
9
,
where φ
k
x
(
u
i
,
u
j
)
=
(
-
1
)
k
x
x
(
u
i
,
u
j
)
-
l
i, φ
y
k
y
(
u
i
,
u
j
)
=
(
-
1
)
k
y
y
(
u
i
,
u
j
)
-
w
i, and φ
z
k
z
(
u
i
,
u
j
)
=
(
-
1
)
k
z
z
(
u
i
,
u
j
)
-
h
i, k
x
,
k
y
,
k
z
∈
{
0,1
}.In order to cut necessary parts of the cylinders, we form the following equations of planes:(6)
χ
~
~
l
(
u
i
,
u
j
)
=
φ
x
k
x
(
u
i
,
u
j
)
+
φ
y
k
y
(
u
i
,
u
j
)
-
r
j
=
0
,
l
=
k
x
+
2
k
y
+
1
,
χ
~
~
l
(
u
i
,
u
j
)
=
φ
y
k
y
(
u
i
,
u
j
)
+
φ
z
k
z
(
u
i
,
u
j
)
-
r
j
=
0
,
l
=
k
y
+
2
k
z
+
5
,
χ
~
~
l
(
u
i
,
u
j
)
=
φ
x
k
x
(
u
i
,
u
j
)
+
φ
z
k
z
(
u
i
,
u
j
)
-
r
j
=
0
,
l
=
k
x
+
2
k
z
+
9
,
which are parallel to edges of P
i
(
u
i
) and pass through pairs of points lying at distance r
j from vertices V
i on the extending of edges of P
i
(
u
i
) (see Figure 3).Figure 3
The helper plane for edge(
V
1
,
V
5
).Making use of the functionsψ
l
(
u
i
,
u
j
) (5) and χ
~
~
l
(
u
i
,
u
j
) (6), l
=
1,2
,
…
,
12, we form the following functions:
(7)
τ
l
(
u
i
,
u
j
)
=
min
⁡
{
ψ
l
(
u
i
,
u
j
)
,
χ
~
~
l
(
u
i
,
u
j
)
}
.It is evident that if at least one of the inequalitiesτ
l
(
u
i
,
u
j
)
>
0, l
=
1
,
…
,
12, holds true, then P
i
(
u
i
)
∩
S
j
(
u
j
)
=
∅. The property allows us to construct the function
(8)
τ
(
u
i
,
u
j
)
=
max
⁡
l
=
1
,
…
,
12
τ
l
(
u
i
,
u
j
)
.Thus, ifτ
(
u
i
,
u
j
)
>
0, then P
i
(
u
i
)
∩
S
j
(
u
j
)
=
∅. On the other hand, if τ
l
(
u
i
,
u
j
)
<
0, then there can be both P
i
(
u
i
)
∩
S
j
(
u
j
)
=
∅ or P
i
(
u
i
)
∩
S
j
(
u
j
)
≠
∅ (see Figure 2(d)).The third tangency form (see Figure2(d)) generates spherical parts of the 0-level surface of Φ
i
j
P
S
(
u
i
,
u
j
). The parts belong to spheres that are formulated by equations
(9)
ϕ
s
(
u
i
,
u
j
)
=
φ
x
k
x
2
(
u
i
,
u
j
)
+
φ
y
k
y
2
(
u
i
,
u
j
)
+
φ
z
k
z
2
(
u
i
,
u
j
)
-
r
j
2
=
0
,
where s
=
k
x
+
2
k
y
+
4
k
z
+
1, k
x
,
k
y
,
k
z
∈
{
0,1
}; that is, s
=
1,2
,
…
,
8.Note that centers of the spheres coincide with verticesV
s, s
=
1,2
,
…
,
8, of cuboid P
i
(
u
i
) correspondently. We need to extract the necessary spherical sectors of the spheres (Figure 2(d)).To this end, we construct for each of verticesV
s, s
=
1,2
,
…
,
8, of P
i
(
u
i
) three elliptic cylinders oriented by a special way with respect to P
i
(
u
i
) and a helper plane. Let us consider the case in detail.Let equations of elliptic cylindersC
k
0, k
=
1,2
,
3, (Figure 4) have the form
(10)
C
1
0
=
2
x
2
+
y
2
-
r
2
=
0
,
C
2
0
=
x
2
+
2
z
2
-
r
2
=
0
,
C
3
0
=
2
y
2
+
z
2
-
r
2
=
0
.Figure 4
The elliptic cylinderC
1
0.We rotate the cylindersC
1
0, C
2
0, and C
3
0 through angles π
/
4 and -
π
/
4 round axes O
y, O
x, and O
z, respectively. As a result, obtained cylinders C
t
1, t
=
1,2
,
…
,
6, (see Figure 5) are specified by the equations, respectively,
(11)
C
1
1
=
(
x
+
z
)
2
+
y
2
-
r
2
=
0
,
C
2
1
=
(
x
-
z
)
2
+
y
2
-
r
2
=
0
,
C
3
1
=
x
2
+
(
y
+
z
)
2
-
r
2
=
0
,
C
4
1
=
x
2
+
(
z
-
y
)
2
-
r
2
=
0
,
C
5
1
=
(
x
+
y
)
2
+
z
2
-
r
2
=
0
,
C
6
1
=
(
y
-
x
)
2
+
z
2
-
r
2
=
0
.Figure 5
The elliptic cylinderC
1
1.It is evident that the intersections of the coordinate planex
O
y and cylinders C
1
1, C
2
1, the coordinate plane x
O
z and cylinders C
3
1, C
4
1, and the coordinate plane y
O
z and cylinders C
5
1, C
6
1 are circles of radius r
j. We rotate cylinders C
t
1, j
=
1,2
,
…
,
6, through the angles π
/
4, 3
π
/
4, 5
π
/
4, and 7
π
/
4 as follows: cylinders C
1
1 and C
2
1: we rotate round axes O
z and, as a result, cylinders C
z
t
2, t
=
1,2
,
.
.
.
8, are obtained (see Figure 6); cylinders C
3
1 and C
4
1: we rotate round axes O
y and, as a result, cylinders C
y
t
2, t
=
1,2
,
…
,
8, are obtained; cylinders C
5
1 and C
6
1: we rotate round axes O
x and, as a result, cylinders C
x
t
2, t
=
1,2
,
…
,
8, are obtained.Figure 6
The elliptic cylinderC
z
1
2.Then, we translate the triple cylindersC
x
t
2, C
y
t
2, and C
z
t
2, t
∈
{
1,2
,
…
,
8
}, by the vectors V
s, s
=
1,2
,
…
,
8. Thus, we obtain at each of the vertices V
s, s
=
1,2
,
…
,
8, of P
i
(
u
i
) three elliptic cylinders C
x
t
3, C
y
t
3, and C
z
t
3 (Figure 7) which are described by the following equations:
(12)
ϕ
~
s
1
(
u
i
,
u
j
)

=

(
2
φ
x
k
x
(
u
i
,
u
j
)

+

φ
y
k
y
(
u
i
,
u
j
)
+
φ
z
k
z
(
u
i
,
u
j
)
)
2
+
(
φ
z
k
z
(
u
i
,
u
j
)
-
φ
y
k
y
(
u
i
,
u
j
)
)
2
-
2
r
j
2
=
0
,
ϕ
~
s
2
(
u
i
,
u
j
)

=

(
φ
x
k
x
(
u
i
,
u
j
)

+

2
φ
y
k
y
(
u
i
,
u
j
)
+
φ
z
k
z
(
u
i
,
u
j
)
)
2
+
(
φ
z
k
z
(
u
i
,
u
j
)
-
φ
x
k
x
(
u
i
,
u
j
)
)
2
-
2
r
j
2
=
0
,
ϕ
~
s
3
(
u
i
,
u
j
)

=

(
φ
x
k
x
(
u
i
,
u
j
)

+

φ
y
k
y
(
u
i
,
u
j
)
+
2
φ
z
k
z
(
u
i
,
u
j
)
)
2
+
(
φ
y
k
y
(
u
i
,
u
j
)
-
φ
x
k
x
(
u
i
,
u
j
)
)
2
-
2
r
j
2
=
0
,
where s
=
k
x
+
2
k
y
+
4
k
z
+
1, k
x
,
k
y
,
k
z
∈
{
0,1
}.Figure 7
The elliptic cylinderC
z
1
3.In order to cut necessary parts of the elliptic cylinders at each of the vertices ofP
i
(
u
i
), we form the following equations of helper planes passing through triples of points lying at distance r
j from vertices V
i on the extending of edges of P
i
(
u
i
) (Figure 8):
(13)
χ
~
s
(
u
i
,
u
j
)

=

φ
x
k
x
(
u
i
,
u
j
)
+
φ
y
k
y
(
u
i
,
u
j
)
+
φ
z
k
z
(
u
i
,
u
j
)
-
r
j
,
where s
=
k
x
+
2
k
y
+
4
k
z
+
1, k
x
,
k
y
,
k
z
∈
{
0,1
}.Figure 8
The helper plane at vertexV
1.Making use of the functions (9)–(13), we form the functions
(14)
ζ
s
(
u
1
,
u
2
)
=
min
⁡
{
ϕ
s
(
u
i
,
u
j
)
,
χ
~
s
(
u
i
,
u
j
)
,
ϕ
~
s
k
(
u
i
,
u
j
)
,
k
=
1,2
,
3
ϕ
s
(
u
i
,
u
j
)
ϕ
s
}
,
s
=
1
,
…
,
8
.It is easily verified that if at least one of the inequalitiesζ
i
(
u
i
,
u
j
)
>
0, s
=
1
,
…
,
8, holds true, then P
i
(
u
i
)
∩
S
j
(
u
j
)
=
∅. Based on (14), we construct the function
(15)
ζ
(
u
i
,
u
j
)
=
max
⁡
s
=
1
,
…
,
8
ζ
s
(
u
i
,
u
j
)
.Thus, ifζ
(
u
i
,
u
j
)
>
0, then P
i
(
u
i
)
∩
S
j
(
u
j
)
=
∅.Note that if at least one of inequalities eitherχ
(
u
i
,
u
j
)
>
0 (4) or τ
(
u
i
,
u
j
)
>
0 (8) or ζ
(
u
i
,
u
j
)
>
0 (15) is satisfied, then P
i
(
u
i
)
∩
S
j
(
u
j
)
=
∅. It allows us to construct the Φ-function for cuboid P
i
(
u
i
) and sphere S
j
(
u
j
) as follows:
(16)
Φ
i
j
P
S
(
u
i
,
u
j
)
=
max
⁡
{
χ
(
u
i
,
u
j
)
,
τ
(
u
i
,
u
j
)
,
ζ
(
u
i
,
u
j
)
}
.


## 2.3.Φ-Function for P
i and Object cl
⁡
(
R
3
∖
P
)

It follows from paper [19] that the Φ-function for P
i
(
u
i
) and cl
⁡
(
R
3
∖
P
) has the form
(17)
Φ
i
P
(
u
i
)
=
min
⁡
{
F
k
j
(
u
i
)
,
k
∈
{
1,2
,
…
,
6
}
,
j
∈
{
1,2
,
…
,
8
}
}
,
where
(18)
F
1
j
(
u
i
)
=
-
x
i
-
g
i
V
j
+
l
,
F
2
j
(
u
i
)
=
x
i
-
g
i
V
j
+
l
,
F
3
j
(
u
i
)
=
-
y
i
-
r
i
V
j
+
w
,
F
4
j
(
u
i
)
=
y
i
-
r
i
V
j
+
w
,
F
5
j
(
u
i
)
=
-
z
i
-
q
i
V
j
+
h
2
,
F
6
j
(
u
i
)
=
z
i
-
q
i
V
j
-
h
1
.


## 2.4.Φ-Function for S
i and Object cl
⁡
(
R
3
∖
P
)

On the ground of (5), theΦ-function for S
i
(
u
i
) and cl
⁡
(
R
3
∖
P
) can be formulated as
(19)
Φ
i
s
(
u
i
)
=
min
⁡
{
F
k
(
u
i
)
,
k
∈
{
1,2
,
…
,
6
}
}
,
where
(20)
F
1
(
u
i
)
=
-
x
i
-
r
i
+
l
,
F
2
(
u
i
)
=
x
i
-
r
i
+
l
,
F
3
(
u
i
)
=
-
y
i
-
r
i
+
w
,
F
4
(
u
i
)
=
y
i
-
r
i
+
w
,
F
5
(
u
i
)
=
-
z
i
-
r
i
+
h
2
,
F
6
(
u
i
)
=
z
i
-
r
i
-
h
1
.


## 3. A Mathematical Model of the Basic Problem and Its Characteristics

In this Section, the mathematical model is constructed as a typical problem of nonsmooth mathematical programming. Characteristics of the mathematical model permit presenting the feasible region as a union of subregions which are specified by the inequality systems whose left-hand sides are infinitely differentiable functions. This allows us to apply the state-of-the-art nonlinear optimization methods to solve the problem.Making use ofΦ-functions described in Section 2, a mathematical model of the stated problem can be formulated as
(21)
h
*
=
min
⁡
h
s
.
t
.
(
u
,
h
)
∈
W
⊂
R
ω
+
2
,
where
(22)
W
=
{
(
u
,
h
)
∈
R
ω
+
2
:
Φ
i
t
P
P
(
u
i
,
u
t
)
≥
0
,
0
<
i
<
t
∈
I
1
,
Φ
i
j
P
S
(
u
i
,
u
j
)
≥
0
,
i
∈
I
1
,
j
∈
I
2
,
Φ
q
j
S
S
(
u
q
,
u
j
)
≥
0
,
0
<
q
<
j
∈
I
2
,
Φ
i
P
(
u
i
,
h
)
≥
0
,
i
∈
I
1
,
Φ
j
S
(
u
j
,
h
)
≥
0
,
j
∈
I
2
}
Φ
i
t
P
P
(
u
i
,
u
t
)
≥
0, Φ
i
j
P
S
(
u
i
,
u
j
)
≥
0, and Φ
i
j
S
S
(
u
i
,
u
j
)
≥
0 ensure nonoverlapping P
i
(
u
i
) and P
t
(
u
t
), P
i
(
u
i
) and S
j
(
u
j
) and S
i
(
u
i
) and S
j
(
u
j
), respectively; Φ
i
P
(
u
i
,
h
)
≥
0 and Φ
j
S
(
u
j
,
h
)
≥
0 guarantee an arrangement of P
i
(
u
i
) and S
j
(
u
j
) within P
(
h
), respectively.It follows from the form ofΦ-functions that the mathematical model possesses the following characteristics.(1)
The feasible regionW is specified by an inequality system which includes operators “max
⁡” and “min
⁡” [20]. The operators contain logical constituents such as set-theoretical operations of conjunction and disjunction, respectively. Thus, in inequalities Φ
i
j
P
P
(
u
i
,
u
j
)
≥
0 and Φ
i
j
P
S
(
u
i
,
u
j
)
≥
0, the operators “max
⁡” generate a “union” or collection of inequality systems whereas the operators “min
⁡” yield inequality systems. This means that the feasible region W can be always represented by a finite union of subregions; that is, W
=
⋃
ξ
=
1
λ
W
ξ, where λ
=
15
6
s
1
·
2
6
s
2, 156, and 26 are quantity of inequality systems in Φ
i
t
P
P
(
u
i
,
u
t
) and Φ
i
j
P
S
(
u
i
,
u
j
), respectively, s
1
=
(
1
/
2
)
n
1
(
n
1
-
1
), s
2
=
n
1
n
2.
(2)
The feasible subregionsW
ξ are described by inequality systems
(23)
{
ϑ
i
t
ξ
ϕ
(
u
i
,
u
t
)
≥
0
,
0
<
i
<
t
∈
I
1
,
ϕ
∈
I
i
t
,
κ
i
j
ξ
π
(
u
i
,
u
j
)
≥
0
,
i
∈
I
1
,
j
∈
I
2
,
π
∈
I
i
j
,
Φ
q
j
s
s
(
u
i
,
u
j
)
≥
0
,
0
<
q
<
j
∈
I
2
,
ξ
∈
J
λ
=
{
1,2
,
…
,
λ
}
,
Φ
i
p
(
u
i
,
h
)
≥
0
,
i
∈
I
1
,
Φ
j
s
(
u
j
,
h
)
≥
0
,
j
∈
I
2
,
whereϑ
i
t
ξ
ϕ
(
u
i
,
u
t
)
≥
0, ϕ
∈
I
i
t, and κ
i
j
ξ
π
(
u
i
,
u
j
)
≥
0, π
∈
I
i
j, are inequality systems of inequality collections which form inequalities Φ
i
t
P
P
(
u
i
,
u
t
)
≥
0 and Φ
i
j
P
S
(
u
i
,
u
j
)
≥
0. Note that functions on the left-hand sides of the inequalities in (23) are nonlinear and infinitely differentiable. Thus, a point (
u
,
h
)
∈
W if at least one of inequality systems (23) is satisfied.
(3)
Since some subregionsW
ξ, ξ
∈
J
λ, can be empty or can be contained in other subregions, then the number σ of the systems is much less than λ.
(4)
Some subregions of kindW
ξ may have common points. This means that if a point u
* is a local minimum with respect to W
ξ, then one has to investigate all other subregions containing u
* to prove that the point is a local minimum with respect to W.
(5)
The matrix of inequality system (23) is strongly sparse.
(6)
The problem (21)-(22) is NP-hard [21].The characteristics involve that a solution algorithm must include the following steps: a construction of starting points, a calculation of local minima, and a nonexhaustive search of local minima which ensures a good approximation to a global minimum.


## 4. Construction of Starting Points

In order to solve the problem (21)-(22), starting points belonging to the feasible region W have to be constructed. When tackling cutting and packing problems, greedy and heuristic algorithms are usually exploited to derive starting points [22]. The algorithms do not permit us to obtain any starting points. This means that the algorithms significantly contract a set of local minima to be considered. Since cuboids are free rotated, then rules of their placement are very complex. This means that time expenditures when constructing starting points using greedy and heuristic algorithms essentially increase in 3D space [23]. The circumstances result in a need of development of new approaches to generate starting points.For construction of starting points, we suggest a method which assumes that all metric characteristics of objects are variable and take values between the minimal and initial values. To find the starting point, a random generation of object placement parameters is executed. In addition, the sizes of the objects essentially diminish. After this, we solve the problem of nonlinear programming providing an increase of object sizes. If, as a result, the point of local maximum is obtained at which all sizes of objects reach the initial values, then the motion vector at the local maximum point and the given height are taken as a starting point for the basic problem.Let us consider one of such approaches.Let sizesγ
i
=
(
l
i
,
w
i
,
h
i
) of cuboids P
i, i
∈
I
1, and radii γ
j
=
r
j of spheres S
j, j
∈
I
2, be variables. Thus, Φ-function for objects O
i
(
u
i
,
γ
i
) and O
j
(
u
j
,
γ
j
) depends on metric characteristics of ones as well; that is, the Φ-function has the kind Φ
i
j
(
u
i
,
u
j
,
γ
i
,
γ
j
).The variablesγ
i, i
∈
I, form a vector γ
=
(
γ
1
,
γ
2
,
…
,
γ
n
)
=
(
l
1
,
w
1
,
h
1
,
l
2
,
w
2
,
h
2
,
…
,
l
n
1
,
w
n
1
,
h
n
1
,
r
n
1
+
1
,
r
n
1
+
2
,
…
,
r
n
)
∈
R
ς, where ς
=
3
n
1
+
n
2. Thus, a vector of all variables is (
X
,
h
)
=
(
u
,
γ
,
h
)
∈
R
μ
+
1, where X
=
(
u
,
γ
), μ
=
ω
+
ς
=
9
n
1
+
4
n
2.We giveh
=
h
0 and a point X
=
X
∇
=
(
u
∇
,
0.1
γ
0
)
=
(
v
∇
,
θ
∇
,
0.1
γ
0
) by a random way so that θ
i
∇
∈
[
0,2
π
], v
i
∇
∈
P
(
h
0
), i
∈
I (Figure 9(a)). The coefficient 0.1 insures a correct construction of Φ-functions.An example of construction of a starting point.
(a)
(b)Then, taking the starting pointX
∇, we solve the problem
(24)
F
(
γ
~
)
=
max
⁡
(
∑
i
=
1
n
1
(
l
i
+
w
i
+
h
i
)
+
∑
j
=
1
n
2
r
j
)
s
.
t
.
X
∈
Ω
⊂
R
μ
,
where
(25)
Ω
=
{
s
4
j
(
r
j
)
=
r
j
0
-
r
j
≥
0
,
r
j
≥
0
,
j
∈
I
2
X
∈
R
μ
:
Φ
i
t
P
P
(
u
i
,
u
t
,
γ
i
,
γ
t
)
≥
0
,
0
<
i
<
t
∈
I
1
,
Φ
i
j
P
S
(
u
i
,
u
j
,
γ
i
,
γ
j
)
≥
0
,
i
∈
I
1
,
j
∈
I
2
,
Φ
q
j
S
S
(
u
q
,
u
j
,
r
i
,
r
j
)
≥
0
,
0
<
q
<
j
∈
I
2
,
Φ
i
P
(
u
i
,
γ
i
,
h
0
)
≥
0
,
s
1
i
(
w
i
)
=
l
i
0
-
l
i
≥
0
,
s
2
i
(
l
i
)
=
w
i
0
-
w
i
≥
0
,
s
3
i
(
h
i
)
=
h
i
0
-
h
i
≥
0
,
l
i
≥
0
,
w
i
≥
0
,
h
i
≥
0
,
i
∈
I
1
,
Φ
j
S
(
u
j
,
r
j
,
h
0
)
≥
0
,
s
4
j
(
r
j
)
=
r
j
0
-
r
j
≥
0
,
r
j
≥
0
,
j
∈
I
2
}
.Note, that as a result of local optimization of the problem, the metric characteristics increase. In addition, they are limited by their initial values due to the inequalitiess
1
i
(
w
i
)
≥
0, s
2
i
(
l
i
)
≥
0, s
3
i
(
h
i
)
≥
0, i
∈
I
1.As a solution result of the problem, a local maximum pointX
~
=
(
u
~
,
γ
~
) is defined (Figure 9(b)).The problem (24)-(25) possesses the characteristics that are similar to the ones of the problem (21)-(22). Furthermore, the problem (24)-(25) is master of additional properties.(1)
IfX
~
=
(
u
~
,
γ
~
) is a local maximum point of the problem (24)-(25) and F
(
γ
~
)
=
∑
i
=
1
n
1
(
l
~
i
+
w
~
i
+
h
~
i
)
+
∑
j
=
1
n
2
r
~
j
=
∑
i
=
1
n
1
(
l
i
0
+
w
i
0
+
h
i
0
)
+
∑
j
=
1
n
2
r
j
0
=
d, then (
u
~
,
h
0
)
∈
W; that is, cuboids P
i
(
u
~
i
), i
∈
I
1, and spheres S
j
(
u
~
j
), j
∈
I
2, are packed into a cuboid P
(
h
0
). This means that, in this case, the point X
~ is a global maximum point of the problem (24)-(25).
(2)
IfX
~
=
(
u
~
,
γ
~
) is such that at least one of components of γ
~ is strictly less matched component of γ
0, then F
(
γ
~
)
<
d and the point X
~ is either a local maximum point or a global maximum point of the problem (24)-(25). In addition, if X
~ is a global maximum point, then cuboids P
i
(
u
~
i
), i
∈
I
1, and spheres S
j
(
u
~
j
), j
∈
I
2, cannot be packed into a cuboid P
(
h
0
).Note that we always can chooseh
=
h
0 so that an arrangement of geometric objects O
i, i
∈
I, within P
(
h
0
) is guaranteed.


## 5. Calculation of Local Minima

Since we deal with a classical problem of mathematical programming, then the nonlinear optimizations methods can be used to search for local minima. The problem characteristics allow reducing solving the problem to solving a sequence of the subproblems whose feasible regions are specified by inequality systems. In addition, the left-hand sides of inequalities are infinity differentiable functions; that is, for solving the subproblems, the optimization gradient methods can be used.IfF
(
γ
~
)
=
d (24), then (
u
~
,
h
0
)
∈
W (22). So, the point is taken as a starting point and the problem (21)-(22) is tackled. As a result, a local minimum point (
u
*
0
,
h
*
0
) is computed (Figure 10).Figure 10
Packing corresponding to a local minimum point.Let(
u
*
i
-
1
,
h
*
i
-
1
) be a local minimum point of the problem (21)-(22) obtained after i
-
1 iterations. We take
(26)
h
i
=
(
h
2
*
i
-
1
-
0.2
5
j
s
)
-
(
h
1
*
i
-
1
+
0.2
5
j
s
)
,
h
*
i
-
1
>
s
>
0
,
j
∈
T
=
{
0,1
,
2
,
…
,
ℓ
<
∞
}
.Assumingj
=
0 in (26), we derive a point (
u
*
i
-
1
,
h
i
). It is evident (
u
*
i
-
1
,
h
i
)
∉
W because of inequalities of kind Φ
t
P
(
u
t
,
h
i
)
≥
0, t
∈
I
1, Φ
q
S
(
u
q
,
h
i
)
≥
0, q
∈
I
2, which are broken at the point (
u
*
i
-
1
,
h
i
) (Figure 11).An example of construction of a point(
u
~
,
h
i
)
∈
W.
(a)
(b)
(c)In order to obtain a point(
u
~
,
h
i
)
∈
W, primarily, we take a starting point (
χ
0
,
X
*
i
-
1
), where χ
0
=
min
⁡
{
Φ
t
P
(
u
t
*
i
-
1
,
γ
t
0
,
h
i
)
,
t
∈
I
1
,
Φ
q
S
(
u
q
*
i
-
1
,
γ
q
0
,
h
0
)
,
q
∈
I
2
}, X
*
i
-
1
=
(
u
*
i
-
1
,
γ
0
), and solve the helper problem
(27)
max
⁡
χ
s
.
t
.
(
χ
,
X
)
∈
G
⊂
R
μ
+
1
,
where
(28)
G
=
{
(
χ
,
X
)
∈
R
μ
+
1
:
Φ
i
t
P
P
(
u
i
,
u
t
,
γ
i
,
γ
t
)

-

χ

≥

0
,
0

<

i
<

t
∈
I
1
,
Φ
i
j
P
S
(
u
i
,
u
j
,
γ
i
,
γ
j
)
-
χ

≥

0
,
i

∈

I
1
,
j

∈

I
2
,
Φ
q
j
S
S
(
u
q
,
u
j
,
r
i
,
r
j
)
-
χ

≥

0
,
0

<

q

<

j
∈
I
2
,
Φ
i
P
(
u
i
,
γ
i
,
h
0
)
-
χ
≥
0
,
s
1
i
(
l
i
,
χ
)
=
l
i
0
-
l
i
-
χ
≥
0
,
s
2
i
(
w
i
,
χ
)
=
w
i
0
-
w
i
-
χ
≥
0
,
s
3
i
(
h
i
,
χ
)
=
h
i
0
-
h
i
-
χ
≥
0
,
i
∈
I
1
,
Φ
j
S
(
u
j
,
r
j
,
h
0
)
-
χ
≥
0
,
s
4
j
(
r
j
,
χ
)

=

r
j
0

-

r
j

-

χ

≥

0
,
j

∈

I
2
,
-
χ

≥

0
(
χ
,
X
)
∈
R
μ
+
1
:
}
.It is easily seen that(
χ
0
,
X
*
i
-
1
)
∈
G.Let(
χ
*
0
,
X
*
0
)
∈
G be a solution of the problem (27)-(28), where χ
*
0
=
0 because of the inequality -
χ
≥
0; that is, (
χ
*
0
,
X
*
0
)
=
(
0
,
X
*
0
) is a global minimum point.Then, taking the starting pointX
*
0, we tackle the problem (24)-(25) and obtain a local maximum point X
~
=
(
u
~
,
γ
~
).Two cases are possible:F
(
γ
~
)
=
d (Figure 11(c)) and F
(
γ
~
)
<
d (Figure 12).Figure 12
Packing corresponding toF
(
γ
~
)
<
d.LetF
(
γ
~
)
=
d; that is, X
~
=
(
u
~
,
γ
~
) is a global maximum of the problem (24)-(25). Hence, (
u
~
,
h
i
)
∈
W. The point (
u
~
,
h
i
) is not in the general case a local minimum point of the problem (21)-(22). So, taking the starting point (
u
~
,
h
i
), we solve the problem (21)-(22). As a result, a new local minimum point (
u
*
i
,
h
*
i
) is computed. Then, we assume j
=
0 in (26), take a starting point (
χ
0
,
X
*
i
)
=
(
χ
0
,
u
*
i
,
γ
0
)
∈
G (28), and sequentially solve the problems (27)-(28), (24)-(25), (21)-(22), and so on until F
(
γ
~
)
<
d is fulfilled.IfF
(
γ
~
)
<
d, we try to transit from the local maximum point X
~ to local maximum point X
~
~ so that F
(
γ
~
~
)
>
F
(
γ
~
) (see Section 6). If we cannot execute such transition, then giving j
=
1 in (26) we take a starting point (
χ
0
,
X
*
i
)
=
(
χ
0
,
u
*
i
,
γ
0
)
∈
G and sequentially solve the problems (27)-(28), (24)-(25), (21)-(22), and so on until h
*
i
-
1
-
h
i
<
ε, where ε is a solution accuracy, is attained.To calculate local extrema of the problems (21)-(22), (24)-(25), and (27)-(28), the modification of the Zoutendijk method of feasible directions [24] along with the concept of ε-active inequalities [23, 25] is used.A computation of local extrema of the problems (21)-(22), (24)-(25), and (27)-(28) is reduced to solving a sequence of optimization subproblems on the feasible subregions W
ξ, ξ
∈
J
λ, Ω
q, q
∈
J
λ, and G
p, p
∈
J
λ, respectively [26].


## 6. Transition from One Local Maximum to Another

Since exhaustive search of all local maxima of problem (24)-(25) is theoretically possible only, then heuristic algorithms, probabilistic approaches, or their combinations are exploited to find approximations to a global maximum.We offer a special approach which provides a jump from a local maximum point to another one so that the objective function value may enlarge.To this aim, we use a helper problem which maximizes sizes of geometric objects at a local maximum point of the problem (24)-(25) without restrictions on their values. It gives us a capability to derive a vector Y
0 of the steepest ascent of the function (24). Since restrictions of the metric characteristics of objects are omitted in the helper problem, then some metric characteristics increase and other ones decrease at the point of local maximum point of the problem (24)-(25). In other words, the vector Y
0 shows whether there exists “free space” which can be exploited to improve a value of the objective function in the problem (24)-(25) and consequently to increase sizes of objects if any.LetX
~
=
(
u
~
,
γ
~
)
=
(
u
~
1
,
u
~
2
,
…
,
u
~
n
,
γ
~
1
,
γ
~
2
,
…
,
γ
~
n
) be a local maximum point of the problem (24)-(25), h
=
h
i, and F
(
γ
~
)
<
d. Since γ
~
≠
γ
0, then the point (
u
~
,
h
i
)
∉
W (22). In order to transit from the point X
~ to the point X
~
~ so that F
(
γ
~
~
)
>
F
(
γ
~
), we consider the helper problem
(29)
F
(
γ
*
)
=
max
⁡
F
(
γ
)
s
.
t
X
∈
G
~
⊂
R
μ
,
where
(30)
G
~
=
{
r
j
≥
0
,
j
∈
I
2
X
∈
R
μ
:
Φ
i
t
P
P
(
u
i
,
u
t
,
γ
i
,
γ
t
)
≥
0
,
i
<
t
∈
I
1
,
Φ
i
j
P
S
(
u
i
,
u
j
,
γ
i
,
γ
j
)
≥
0
,
i
∈
I
1
,
j
∈
I
2
,
Φ
q
j
S
S
(
u
q
,
u
j
,
r
q
,
r
j
)
≥
0
,
q
<
j
∈
I
2
,
Φ
i
P
(
u
i
,
γ
i
,
h
k
)
≥
0
,
l
i
≥
0
,
w
i
≥
0
,
h
i
≥
0
,
i
∈
I
1
,
Φ
j
S
(
u
j
,
r
j
,
h
k
)
≥
0
,
r
j
≥
0
,
j
∈
I
2
}
.
We note that the problem differs from the problem (21)-(22) by absence of restrictions
(31)
s
1
i
(
w
i
)
=
l
i
0
-
l
i
≥
0
,
s
2
i
(
l
i
)
=
w
i
0
-
w
i
≥
0
,
s
3
i
(
h
i
)
=
h
i
0
-
h
i
≥
0
,
i
∈
I
1
,
s
4
j
(
r
j
)
=
r
j
0
-
r
j
≥
0
,
j
∈
I
2
.
This means that sizes of geometric objects can take any nonnegative values.We compute the steepest ascent vectorY
0 at the point X
~
=
(
u
~
,
γ
~
) for the problem (29)-(30) and construct the point
(32)
X
ν
=
X
~
+
0
.
5
ν
-
1
Y
0
=
X
~
+
Y
0
ν
,
v
=
V
=
{
1,2
,
…
}
.The positive elements of the vectorY
0 corresponding to the direction of objects sizes change allow us to define objects whose sizes can be increased in the point X
~ of local maximum. Consequently, there is a “free space” in the neighborhoods of such objects which can be used to increase the local maximum value. Let us suppose that some coordinates of X
ν satisfy the inequalities l
i
ν
>
l
~
i, i
∈
J
11
⊂
I
1, w
i
ν
>
w
~
i, i
∈
J
12
⊂
I
1, h
i
ν
>
h
~
i, i
∈
J
13
⊂
I
1, and r
i
ν
>
r
~
i, i
∈
J
2
⊂
I
2. Let sets J
1
i consist of q
1
i, i
=
1,2
,
3, elements and let J
2 consist of q
2 elements. Then, J
1
=
J
11
∪
J
12
∪
J
13 consists of q
1 elements and q
1
≤
q
11
+
q
12
+
q
13.Remark 2.
IfY
0
≠
0, then there exists such m that if v
≥
m, then X
ν
∈
G
~.We compute(33)
σ
1
i
0
=
min
⁡
{
l
i
0
,
w
i
0
,
h
i
0
}
,
σ
2
i
0
=
min
⁡
⁡
{
{
l
i
0
,
w
i
0
,
h
i
0
}
∖
{
σ
1
i
0
}
}
σ
3
i
0
=
{
l
i
0
,
w
i
0
,
h
i
0
}
∖
{
σ
1
i
0
,
σ
2
i
0
}
,
σ
~
1
i
=
min
⁡
{
l
~
i
,
w
~
i
,
h
~
i
}
,
σ
~
2
i
=
min
⁡
{
l
~
i
,
w
~
i
,
h
~
1
}
∖
{
σ
~
1
i
}
,
σ
~
3
i
=
{
l
~
i
,
w
~
i
,
h
~
1
}
∖
{
σ
~
1
i
,
σ
~
2
i
}
,
σ
1
i
m
=
min
⁡
{
l
i
m
,
w
i
m
,
h
i
m
}
,
σ
2
i
m
=
min
⁡
{
l
i
m
,
w
i
m
,
h
i
m
}
∖
{
σ
1
i
m
}
,
σ
3
i
m
=
{
l
i
m
,
w
i
m
,
h
i
m
}
∖
{
σ
1
i
m
,
σ
2
i
m
}
,
i
∈
I
1
,
ρ
i
m
=
(
l
i
m
)
2
+
(
w
i
m
)
2
+
(
h
i
m
)
2
,
ρ
~
i
=
(
l
~
i
)
2
+
(
w
~
i
)
2
+
(
h
~
i
)
2
,
i
∈
I
1
,
τ
i
m
=
min
⁡
{
l
i
m
,
w
i
m
,
i
m
}
,
τ
~
i
=
min
⁡
{
l
~
i
,
w
~
i
,
h
~
i
}
,
i
∈
I
1
.Letρ
i
m
>
ρ
~
i, i
∈
J
3
⊂
I
1 and τ
j
m
>
τ
~
j, j
∈
J
4
⊂
I
1.On the ground of pointsX
~ and X
m (see Remark 2), we derive coordinates of the vector X
°
=
(
u
1
°
,
u
2
,
°
…
,
u
n
°
,
γ
1
°
,
γ
2
,
°
…
,
γ
n
°
) as follows.(1) Leti
≠
j
∈
I
1 (O
i and O
j are cuboids P
i and P
j),  l
i
0
>
l
~
i or w
i
0
>
w
~
i or h
i
0
>
h
~
i and j
∈
J
1; that is, at least one of metric characteristics of P
i does not reach the initial value and one of metric characteristics of P
j is strictly greater than its value at the point X
~. For example, let the initial sizes of cuboids P
i and P
j be σ
1
i
0
=
w
i
0, σ
2
i
0
=
l
i
0, and σ
3
i
0
=
h
i
0 and σ
1
j
0
=
l
j
0, σ
2
j
0
=
w
j
0, and σ
3
j
0
=
h
j
0 and let sizes at the point X
~ be σ
~
1
i
=
w
~
i, σ
~
2
i
=
l
~
i, and σ
~
3
i
=
h
~
i and σ
~
1
j
=
l
~
j, σ
~
2
j
=
w
~
j, and σ
~
3
j
=
h
~
j, respectively. To the points X
~ and X
m, there corresponds packing shown in Figure 13(a) and Figure 13(b), respectively.An example of construction of a pointX
°
.
(a)
(b)
(c)
(d)Then if inequalities(34)
σ
~
t
j
≤
σ
t
i
m
,
σ
~
t
i
≤
σ
t
j
m
,
t
=
1,2
,
3
,
hold true then coordinates u
i
°, u
j
°, γ
i
° and γ
j
° are constructed as
(35)
u
°
i
=
u
j
m
,
u
j
°
=
u
i
m
,
σ
t
i
°
=
min
⁡
{
σ
t
i
0
,
σ
t
j
m
}
,
σ
t
j
°
=
min
⁡
{
σ
t
i
m
,
σ
t
j
0
}
,
t
=
1,2
,
3
,
where σ
t
i
° is either l
i
° or w
i
° or h
i
° (33). This means that cuboids P
i and P
j are “changed over” relatively their arrangement corresponding to the point X
m (Figure 13(c)).If forj
∈
J
1 at least one of inequalities (34) is broken, then
(36)
u
°
i
=
u
i
m
,
u
j
°
=
u
j
m
,
σ
t
i
°
=
σ
t
i
m
,
σ
t
j
°
=
σ
t
j
m
,
t
=
1,2
,
3
.(2) Leti
≠
j
∈
I
2 (O
i and O
j are spheres S
i and S
j), r
i
0
>
r
~
i and j
∈
J
2, that is radius of S
i does not reach the initial value and radius of S
j is strictly greater than its value at the point X
~. If inequalities
(37)
r
~
j
≤
r
i
m
,
r
~
i
≤
r
j
m
are satisfied then coordinates u
i
°, u
j
°, γ
i
° and γ
j
° take the form
(38)
u
°
i
=
u
j
m
,
u
j
°
=
u
i
m
,
r
i
°
=
min
⁡
{
r
i
0
,
r
j
m
}
,
r
j
°
=
min
⁡
{
r
j
0
,
r
i
m
}
,
where γ
i
°
=
r
i
° and γ
j
°
=
r
j
°.Thus, spheresS
i and S
j are “changed over”.If forj
∈
J
2 at least one of the inequalities (37) is broken, then
(39)
u
°
i
=
u
i
m
,
u
j
°
=
u
j
m
,
r
i
°
=
r
i
m
,
r
j
°
=
r
j
m
.(3) Leti
∈
I
1, j
∈
I
2 (O
i and O
j are cuboid P
i and sphere S
j), ρ
i
0
>
ρ
~
i, and j
∈
J
2; that is, the radius of circle circumscribed round P
i does not reach the initial value and radius of S
j is strictly greater than its value at the point X
~. If inequalities
(40)
ρ
~
i
≤
r
j
m
,
r
~
j
≤
τ
i
m
are satisfied, then
(41)
u
°
i
=
u
j
m
,
u
j
°
=
u
i
m
,
σ
t
i
°
=
min
⁡
{
σ
t
i
0
,
r
j
m
}
,
t
=
1,2
,
3
,
r
j
°
=
min
⁡
{
r
j
0
,
τ
i
m
}
.
Thus, cuboid P
i and sphere S
j are “changed over” relatively their placement corresponding to the point X
m.If forj
∈
J
2 at least one of the inequalities (40) is broken, then
(42)
u
°
i
=
u
i
m
,
u
j
°
=
u
j
m
,
σ
t
i
°
=
σ
t
i
m
,
t
=
1,2
,
3
,
r
j
°
=
r
j
m
.(4) Leti
∈
I
2, j
∈
I
1 (O
i and O
j are sphere S
i and cuboid P
j), r
i
0
>
r
i
m, and j
∈
J
4; that is, radius of S
i does not reach the initial value and the radius of circle circumscribed round P
j is strictly greater than its value at the point X
~. If inequalities
(43)
r
~
i
≤
τ
j
m
,
ρ
~
j
≤
r
i
m
are satisfied, then
(44)
u
°
i
=
u
j
m
,
u
j
°
=
u
i
m
,
r
°
i
=
min
⁡
{
r
i
0
,
r
j
m
}
,
σ
t
j
°
=
min
⁡
{
σ
t
j
0
,
r
i
m
}
,
t
=
1,2
,
3
.
Thus, sphere S
i and cuboid P
j are “changed over” relatively their placement corresponding to the point X
m.If forj
∈
J
3 at least one of the inequalities (43) is broken, then we take
(45)
u
°
i
=
u
i
m
,
u
j
°
=
u
j
m
,
r
i
°
=
r
i
m
,
σ
t
j
°
=
σ
t
j
m
,
t
=
1,2
,
3
.Remark 3.
It is easily seen that there can beX
°
=
X
m; that is, there exists such integer N that, if m
>
N, then X
°
=
X
m.Thus, ifX
°
≠
X
m, then X
° and X
m are in attraction zones of different local maximum points; that is, to the point X
° corresponds the packing of O
i, i
∈
I, obtained from the packing of O
i, i
∈
I, corresponding to the point X
~ in which some objects of O
i, i
∈
I
1, “change over.”LetX
~
~ be a local maximum point obtained from the starting point X
°.Theorem 4.
Ifm
≤
N, then F
(
γ
~
~
)
>
F
(
γ
~
).Proof.
For the sake of simplicity, letX
° and X
~ differ in values of variables γ
j, γ
i, u
j, and u
i only and let j
<
i, and i
,
j
∈
I
1; that is, X
°
=
(
u
1
m
,
u
2
m
,
…
,
u
°
j
,
…
,
u
°
i
,
…
,
u
n
m
,
γ
1
m
,
γ
2
m
,
…
,
γ
°
j
,
…
,
γ
°
i
,
…
,
γ
n
m
,
r
°
), where u
°
j
=
u
i
m
,
u
°
i
=
u
j
m, γ
°
j
=
(
l
°
j
,
w
°
j
,
h
°
j
), γ
°
i
=
(
l
°
i
,
w
°
i
,
h
°
i
), either w
°
j
=
min
⁡
{
w
j
t
m
,
σ
i
0
} or w
°
j
=
w
j
m, either l
°
j
=
min
⁡
{
l
j
t
m
,
σ
i
0
} or l
°
j
=
l
j
m, and either h
°
j
=
min
⁡
{
h
j
t
m
,
σ
i
0
} or h
°
j
=
h
j
m.
Note thatX
°
≠
X
m because of m
≤
N. Hence, the point X
° is not in attraction zone of the local maximum point X
~. It follows from Remark 2 that X
°
∈
G
~; that is, the inequality system {
Φ
i
j
(
u
i
,
u
j
,
γ
i
,
γ
j
)
≥
0
,
0
<
i
<
j
∈
I
,
Φ
i
P
(
u
i
,
γ
i
,
h
0
)
≥
0
,
w
i
≥
0
,
l
i
≥
0
,
h
i
≥
0
,
i
∈
I
1
}, at the point X
° is satisfied. It follows from the relations (35) that inequalities s
1
i
(
w
i
)
=
l
i
0
-
l
i
≥
0, s
2
i
(
l
i
)
=
w
i
0
-
w
i
≥
0, s
3
i
(
h
i
)
=
h
i
0
-
h
i
≥
0, i
∈
I
1, and s
4
j
(
r
j
)
=
r
j
0
-
r
j
≥
0, j
∈
I
2, at the point X
°, are satisfied as well. This means that X
°
∈
Ω. Bearing in mind the inequalities (34), we have ∑
i
=
1
n
1
(
l
°
i
+
w
°
i
+
h
°
i
)
>
∑
i
=
1
n
1
(
l
~
i
+
w
~
i
+
h
~
i
); that is, F
(
γ
°
)
>
F
(
γ
~
). It is evident that F
(
γ
~
~
)
>
F
(
γ
~
) if X
~
~ is a local maximum point obtained from the starting point X
° (see Figure 13(d)). If the number of coordinates of vectors X
° and X
~ differs in the larger number of coordinates, then the theorem holds true all the more. For the cases 2, 3, and 4, the theorem is proved in the same way.


## 7. Construction of Promising Points

The theorem conditions above always ensure a jump from a local maximum point to another one at which the objective functionF
(
γ
) has a more value. However, severe theorem constraints do not always allow us to fulfill such jump although the jump may execute. So, we extend a set of the starting points using points X
~ and X
m (see Section 6). Since, in general case, local maximum points obtained from the starting points do not guarantee an increase of values of F
(
γ
), then in what follows the points are called promising starting ones.Let us consider a way of construction of promising starting points on the ground of the theorem and pointsX
~
∈
R
μ (a local maximum of the problem (24)-(25)), X
m
∈
R
μ (see (32) and Remark 2).Firstly, making use ofX
~ and Y
0 (see the problem (29)-(30)), we derive coordinates of points X
k, ρ
k
=
(
ρ
1
k
,
ρ
2
k
,
…
,
ρ
n
1
k
) and τ
k
=
(
τ
1
k
,
τ
2
k
,
…
,
τ
n
1
k
) as follows:
(46)
u
i
k
=
u
i
m
,
i
∈
I
,
(47)
l
i
k
=
{
l
i
m
if
i
∉
J
11
,
l
~
i
+
0
.
5
k
δ
if
i
∈
J
11
,
w
i
k
=
{
w
i
m
if
i
∉
J
12
,
w
~
i
+
0
.
5
k
δ
if
i
∈
J
12
,
h
i
k
=
{
h
i
m
if
i
∉
J
13
,
h
~
i
+
0
.
5
k
δ
if
i
∈
J
13
,
r
j
k
=
{
r
j
m
if
j
∉
J
2
,
r
~
j
+
0
.
5
k
δ
,
if
j
∈
J
2
,
i
∈
I
1
,
j
∈
I
2
,
(48)
ρ
i
k
=
(
w
i
k
)
2
+
(
l
i
k
)
2
+
(
h
i
k
)
2
,
i
∈
I
1
,
τ
i
k
=
min
⁡
{
w
i
k
,
l
i
k
,
h
i
k
}
,
i
∈
I
1
,
where k
∈
K
=
{
1,2
,
…
}, δ
=
max
⁡
{
l
i
0
,
w
i
0
,
h
i
0
,
i
∈
I
1
,
r
j
0
,
j
∈
I
2
}
-
min
⁡
{
l
i
0
,
w
i
0
,
h
i
0
,
i
∈
I
1
,
r
j
0
,
j
∈
I
2
}.It follows from (46) and (47) that a location of geometric objects corresponding to points X
m and X
k coincides and metric characteristics (sizes) may differ. Real sizes of geometric objects at the points X
m and X
k are the same if l
i
m
≤
l
~
i, i
∉
J
11, w
i
m
≤
w
~
i, i
∉
J
12, h
i
m
≤
h
~
i, i
∉
J
13, and r
i
m
≤
r
~
i, i
∉
J
2. On the other hand, if l
i
m
>
l
~
i, i
∈
J
11, w
i
m
>
w
~
i, i
∈
J
12, h
i
m
>
h
~
i, i
∈
J
13, and r
i
m
>
r
~
i, i
∈
J
2, that is, appropriate coordinates y
i
0
>
0, i
∈
{
ω
1
,
ω
2
,
…
,
ω
μ
}
=
I
μ, μ
=
q
1
+
q
2, of Y
0, then sizes of geometric objects O
i, i
∈
I
μ, increase. Note that the sizes can increase much more. In addition, the less k in (47), the more sizes of geometric objects.Making use of pointsX
m and X
k, the point X
0
k
=
(
u
0
k
,
γ
0
k
) is constructed in the same manner as the point X
° (34)-(35) provided that, in (34), (37), (40), and (43), instead of coordinates of X
m, we take coordinates of X
k. It is easily seen that coordinate values of X
0
k depend on an order of their formation and the order influences on an effectiveness of the promising starting point X
0
k.In order to raise effectiveness of promising pointsX
0
k, k
∈
K, their components are generated in order corresponding to sequences of volume increments of O
i, i
∈
I, obtained when transiting from X
~ to X
m. Furthermore, coordinate values of X
0
k, k
∈
K, are derived in order corresponding to sequences of volume increments of O
i, i
∈
I, which are equal to the differences of initial volumes V
i
0 and volumes of O
i, i
∈
I, at X
m. The sequences are constructed as follows.LetV
~
i and V
i
m be volumes of objects O
i, i
∈
I, at the points X
~ and X
m. We compute
(49)
Λ
i
+
=
V
i
m
-
V
~
i
,
Λ
i
-
=
V
i
0
-
V
i
m
,
i
∈
I
.LetΛ
j
+
>
0, j
∈
Υ
1
⊂
I, where Υ
1 consists of q elements, and Λ
i
-
<
0, i
∈
Υ
2
⊂
I, where Υ
2 consists of p elements. Next, we put Λ
j
+, j
∈
Υ
1, and Λ
i
-, i
∈
Υ
2, in descending order
(50)
Λ
j
1
+
≥
Λ
j
2
+
≥
⋯
≥
Λ
j
q
+
,
(51)
Λ
i
1
-
≥
Λ
i
2
-
≥
⋯
≥
Λ
i
p
-
.
Then, pairs of components (
u
i
0
k
,
γ
i
0
k
), i
∈
I, of X
0
k, k
∈
K, are derived in the order (
u
i
j
0
k
,
γ
i
j
0
k
), j
∈
Υ
1, (see (51)); that is, primarily components (
u
i
0
k
,
γ
i
0
k
), i
∈
I, corresponding to the increments of volumes Λ
j
-
>
0, j
∈
Υ
2, are formed. In addition, values of the coordinates are generated in accordance with the sequence (50); that is, at first values of the coordinates (
u
i
0
k
,
γ
i
0
k
), i
∈
I, corresponding to maximal increments of volumes Λ
j
+
>
0, j
∈
Υ
1, are formed.In other words, firstly we try to “change over” geometric objectO
i
1 with geometric object O
j
1. If such rearrangement is not possible, we try to “change over” geometric object O
i
1 with geometric object O
j
2 and so on until either O
i
1 “change over” with O
j
s or O
j
t, t
=
1,2
,
…
,
q, are exhausted. After that we try to “change over” geometric object O
i
2 with geometric object of the set O
j
s, s
∈
Υ
1, and so on.Then, we putΛ
j
+, j
∈
Υ
1, in ascending order
(52)
Λ
j
1
+
≤
Λ
j
2
+
≤
⋯
≤
Λ
j
q
+
.On the ground of the pointsX
m and X
k, the point X
1
k
=
(
u
1
k
,
γ
1
k
) is formed according to the sequences (51) and (52). The point X
1
k is derived in a way analogous to that used when constructing the point X
0
k. Thus, the construction of X
0
k and X
1
k is distinguished by the order of formation of their coordinate values.Remark 5.
It follows from the proof of the theorem (see Section6) and relations (34)–(45) that X
0
k, X
1
k
∈
Ω (25).It is easily seen that, to the pointX
0
k, there corresponds the placement of geometric objects (Figure 14(b)) which differs from the placement of ones corresponding to the point X
m (Figure 14(a)) by “rearrangements” of some geometric objects (shown by arrows in Figure 14(a)). In addition, if O
j
(
u
i
t
m
,
γ
j
m
)
⊂
O
i
t
(
u
i
t
m
,
γ
i
t
k
) and O
i
t
(
u
i
t
m
,
γ
i
t
m
)
⊂
O
j
(
u
j
m
,
γ
j
k
), then O
j and O
i
t “change over” (Figure 14(b)). The resulting packing corresponding to a starting point X
0
k is illustrated in Figure 14(c).An example of construction of a promising point.
(a)
(b)
(c)Thus, the promising starting pointX
0
k permits us to obtain a global maximum X
~ of the problem (24)-(25).


## 8. Solution Algorithm

Based on the theorem above, we offer the following solution algorithm.A general scheme consists in the following.Solving of the problem begins with a random generation of the object placement parameters so that the origins of the eigen coordinate systems of objects belong to the container of a given height. Here, sizes of objects are greatly reduced. After that, we solve the problem of finding maximal sizes of the objects placed in the container. Taking the placement parameters of the objects at a global maximum point and the given height as a starting point of the basic problem, a local minimum of the basic problem is calculated.Further solving of the problem is reduced to an iterative process. On each stage of the iterative process, the container height is trimmed and a new local maximum of the problem (24)-(25) is calculated. If all object sizes at a local maximum obtained are equal to the initial ones, then the motion vector at the global maximum point and the given height are taken as a starting point for the basic problem and a local minimum of the basic problem is calculated.If for the current value of height at a local maximum point the initial values are not attained, then we solve the problem (29)-(30). The problem permits to construct a vector recognizing those sizes of objects which can increase. Making use of the vector, the iterative process of search for promising starting points is executed. If all promising starting points are exhausted and the initial sizes of objects are not attained, we enlarge the height and solve the problem (24)-(25) again and so on. The iterative process continues until either at a local maximum point the initial sizes are obtained or an increment of the height is less than the given accuracy.The last local minimum point of the basic problem is taken as an approximation to a global minimum point (see Algorithm1).Algorithm 1
Step  1.Take an initial value h
=
h
0 so that a packing of geometric objects O
i, i
∈
I,
into the cuboid P
(
h
0
) is guaranteed.
Step  2.Set index i
=
0.
Step  3.Give a starting point X
=
X
∇ (see Section 4) and solve consequently the problems (24)-(25)
and (21)-(22). As a result, a local minimum point (
u
*
i
,
h
*
i
) of the problems (21)-(22) is computed.
Step  4.  Repeat
Begin
Step  4.1.Set index i
=
i
+
1.
Step  4.2.Set  h
i
=
(
h
2
*
i
-
1
-
s
)
-
(
h
1
*
i
-
1
+
s
) (see (26)).
Step  4.3.Derive a point X
Δ
i
=
(
u
*
i
-
1
,
γ
0
).  Take h
=
h
i and a starting point (
χ
0
,
X
Δ
i
) and
solve the problems (27)-(28). A global maximum point (
0
,
X
*
0
)
=
(
0
,
u
*
0
,
γ
*
0
) is found.
Step  4.4.Take a starting point X
*
0
∈
Ω and calculate a local maximum point X
~
=
(
u
~
,
γ
~
)  of
the problems (24)-(25).
Step  4.5.If F
(
γ
~
)
=
d then take a starting point (
u
~
,
h
i
) and solve the problems (21)-(22). As a
result, a local minimum point (
u
*
i
,
h
*
i
) of the problems (21)-(22) is computed.
End
Until  F
(
γ
~
)
=
d.
Step  5.  Set index j
=
0.
Step  6.  Repeat
Begin
Step  6.1.Set index k
=
0.
Step  6.2.  Repeat
Begin
Step  6.2.1.  Construct a point X
k (46)-(47) on the ground of points  Y
0 and X
~.
Step  6.2.2.  Construct a point X
0
k
∈
Ω.
Step  6.2.3.  If X
0
k
≠
X
k then take the starting point X
0
k and solve the problems (24)-(25)
(as a result, a local maximum point X
~
~ is obtained) else go to
Step  6.2.5.
Step  6.2.4.  If F
(
γ
~
~
)
>
F
(
γ
~
) and F
(
γ
~
~
)
<
d then take X
~
=
X
~
~ and return to Step  6.1.
Step  6.2.5.  If F
(
γ
~
~
)
>
F
(
γ
~
) and F
(
γ
~
~
)
=
d then go to Step  6.4.
Step  6.2.6.  Construct the point X
1
k
∈
Ω.
Step  6.2.7.  If  X
1
k
≠
X
k then take the starting point X
1
k and solve the problems
(24)-(25) (as a result, a local maximum point X
~
~ is obtained) else go to Step  6.2.10.
Step  6.2.8.  If F
(
γ
~
~
)
>
F
(
γ
~
) and F
(
γ
~
~
)
<
d then take X
~
=
X
~
~ and return to
Step  6.1.
Step  6.2.9.  If F
(
γ
~
~
)
>
F
(
γ
~
) and F
(
γ
~
~
)
=
d then go to Step  6.4.
Step  6.2.10.  Set k
=
k
+
1.
End
Until
X
0
k
≠
X
~ or X
1
k
≠
X
~.
Step  6.4.If F
(
γ
~
)
=
d then take a starting point (
u
~
,
h
i
) and solve the problems (21)-(22). As a result,
a local minimum point(
u
*
i
,
h
*
i
) of the problems (21)-(22) is computed.
Return to Step  4.
Step  6.5.  Set  i
=
i
+
1 and j
=
j
+
1.
Step  6.6.  Set h
i
=
(
h
2
*
i
-
1
-
0.2
5
j
s
)
-
(
h
1
*
i
-
1
+
0.2
5
j
s
) (see (26)).
Step  6.7.Form a point X
Δ
i
=
(
u
*
i
-
1
,
γ
0
).  Take h
=
h
i and a starting point (
χ
0
,
X
Δ
i
) and solve the
problems (27)-(28). As a result, a global maximum point (
0
,
X
*
0
)
=
(
0
,
u
*
0
,
γ
*
0
) is found.
Step  6.8.Take a starting point X
*
0
∈
Ω and solve the problems (24)-(25). As a result, a local
maximum pointX
~
=
(
u
~
,
γ
~
) is obtained.
Step  6.9.If F
(
γ
~
)
=
d then return to Step  6.4.
End
Until
h
*
i
-
1
-
h
i
>
ε.
Step  7.The solution process is finished.  Take the point (
u
*
i
-
1
,
h
*
i
-
1
) as an approximation to a global
minimum of problems (21)-(22).


## 9. Numerical Examples

Here, we consider examples packing from 10 to 300 geometric objects. Results of calculations of a number of examples are available onhttp://www.datafilehost.com/d/7e0fb775. Some of the results are shown in Figure 15.Examples of solution results.
(a)
(b)
(c)
(d)
(e)We present the following two test examples.Example 6.
Pack five cuboids and five spheres into a container with base sizesl
=
7 and w
=
5. Sizes of cuboids P
i, i
=
1,2
,
3,4
,
5, and spheres S
j, j
=
1,2
,
3,4
,
5, are given in Table 1.Table 1
Metric characteristics of cuboids and spheres of Example6.
i
l
i
w
i
h
i
r
i
P
1
2
3
3
—
P
2
2
1
3
—
P
3
5
3
2
—
P
4
3
0.5
3
—
P
5
1
2
1
—
S
6
—
—
—
4.4
S
7
—
—
—
1.9
S
8
—
—
—
5
S
9
—
—
—
3.5
S
10
—
—
—
2.7An approximation to the global minimum is equal to 22.506 and is reached at the local minimum point whose coordinates are given in Table2.Table 2
Coordinates of the local minimum point of Example6.
i
x
i
y
i
z
i
α
i
β
i
ϖ
i
P
1
5.000
1.630
4.350
4.832
3.141
6.283
P
2
−5.680
−2.778
19.448
3.165
3.143
1.722
P
3
3.474
0.000
11.228
3.142
3.038
1.571
P
4
1.484
−4.479
17.854
3.159
4.767
6.296
P
5
−1.679
2.517
21.432
6.298
3.217
6.482
S
6
2.600
0.426
17.956
—
—
—
S
7
3.867
−3.095
2.544
—
—
—
S
8
−2.000
0.000
5.000
—
—
—
S
9
−3.456
−1.492
13.247
—
—
—
S
10
−4.282
2.292
18.215
—
—
—The packing of geometric objects corresponding to the point is illustrated in Figure16.Figure 16
Packing corresponding to the local minimum point (Example6).Example 7.
Pack thirty cuboids into a container with base sizesl
=
14 and w
=
10. Sizes of cuboids P
i are given in Table 3. It should be noted that diameters of P
1, P
10, and P
14 are strictly greater than diameter of the container base.Table 3
Metric characteristics of cuboids of Example7.
i
l
i
w
i
h
i
P
1
18.00
2.00
3.00
P
2
1.00
1.50
2.00
P
3
3.00
2.00
3.00
P
4
1.40
3.00
2.00
P
5
2.00
2.30
3.00
P
6
2.50
3.00
2.00
P
7
4.50
3.00
2.00
P
8
2.40
4.00
4.00
P
9
1.50
1.50
2.00
P
10
18.00
2.00
3.00
P
11
4.00
4.00
4.00
P
12
3.00
3.50
1.00
P
13
3.00
4.50
1.50
P
14
19.00
1.00
1.00
P
15
1.50
3.50
1.00
P
16
3.00
1.00
2.50
P
17
3.00
5.50
2.00
P
18
3.00
3.20
2.00
P
19
2.50
3.00
4.00
P
20
3.00
4.00
4.00
P
21
2.50
3.00
2.00
P
22
3.00
5.00
2.00
P
23
3.00
2.00
3.00
P
24
3.50
3.00
2.00
P
25
4.00
3.00
3.00
P
26
2.50
3.00
2.00
P
27
4.50
3.00
2.00
P
28
2.00
2.00
2.00
P
29
1.50
1.50
2.00
P
30
3.00
1.70
2.00An approximation to the global minimum is equal to 32.032 and is attained at the local minimum point given in Table4.Table 4
Coordinates of the local minimum point of Example7.
i
x
i
y
i
z
i
α
i
β
i
ϖ
i
P
1
−0.001
−1.524
14.352
4.455
0.185
0.825
P
2
−6.879
−7.833
9.236
−0.067
2.159
0.126
P
3
−6.852
6.871
29.023
0.000
−0.002
−1.512
P
4
−4.374
−7.918
15.488
2.819
7.137
1.816
P
5
−3.160
−2.972
29.620
1.586
3.175
6.283
P
6
−9.269
−6.208
21.287
3.327
2.177
−0.402
P
7
−10.558
−4.815
4.996
0.103
2.036
1.540
P
8
−0.218
5.765
23.823
4.682
−0.057
5.485
P
9
−1.144
−8.175
29.838
3.159
4.326
4.744
P
10
1.725
6.948
15.769
4.725
3.124
0.941
P
11
3.220
4.476
5.678
2.980
4.091
4.536
P
12
4.774
6.607
27.388
6.229
2.075
−1.596
P
13
10.647
2.411
25.246
4.732
−0.025
6.253
P
14
0.292
−2.042
18.639
4.968
6.023
0.807
P
15
11.740
−7.973
11.845
4.396
5.266
−0.323
P
16
11.361
−0.592
28.919
−0.133
1.606
3.279
P
17
7.748
−2.764
12.134
3.082
−0.807
1.168
P
18
5.483
−7.889
29.004
1.571
6.269
1.572
P
19
−9.286
3.421
10.742
6.319
5.342
0.000
P
20
8.176
−2.250
20.362
3.193
3.903
4.788
P
21
11.628
−5.950
29.048
0.338
1.618
−0.219
P
22
−7.529
−1.249
14.893
3.176
2.515
−2.036
P
23
0.675
−7.823
22.402
3.138
6.089
3.100
P
24
−10.430
−3.171
28.772
1.705
3.143
0.002
P
25
4.353
−1.800
29.014
3.734
1.575
0.979
P
26
0.672
−7.185
5.647
1.467
3.198
3.931
P
27
−4.361
6.529
16.071
2.652
−2.255
2.750
P
28
2.045
6.203
29.322
4.712
6.243
−2.673
P
29
−2.888
8.370
30.471
5.146
4.647
2.008
P
30
−5.977
−2.797
2.704
3.383
4.186
4.910The arrangement of geometric objects corresponding to the local minimum point is shown in Figure17.Figure 17
Packing corresponding to the local minimum point (Example7).All examples are calculated using Intel Core i5 (2.6 Ghz) processor.The curve shown in Figure18 illustrates the dependence of the runtime on n
=
n
1
+
n
2, where n
1
=
n
2.Figure 18
Dependence of the runtime onn.


## 10. Conclusions

The mathematical model describing free translations and rotations of cuboids is offered.TheΦ-function for a cuboid with rotations and a sphere is constructed.The new approach to generate random starting points is developed. A random generation of object placement parameters permits obtaining any starting points. The approach simplifies significantly the construction of starting points and possesses universal properties; that is, we do not need to analyze space forms (shapes) of geometric objects and to develop their placement rules.A new method of transition from one local maximum point to another one when searching for a global maximum point using so-called promising starting points is suggested.The paper shows how a mathematical model of a packing optimization problem of geometric objects provided that appropriateΦ-functions have been derived can be constructed.TheΦ-function technique permitted us to apply methods of nonlinear programming on all stages when solving the problem (21)-(22) (including the construction of starting points, the calculation of local extrema, and searching for approximations to global extrema).Optimization approaches that worked out in the paper can be exploited for solving other packing optimization problems.Iterative processes being used for solving the problem can be easily parallelized.Hopefully, the paper has shown the validity ofΦ-functions when constructing mathematical models and solving 3D packing optimization problems.



---

*Source: 571743-2014-03-10.xml*