Optimal packing of convex polytopes using quasi-phi-functions
We study a packing problem of a given collection of convex polytopes into a rectangular container of minimal
 volume. Continuous rotations and translations of polytopes are allowed. In addition a given minimal allowable
 distances between polytopes are taking into account. We employ...
Saved in:
| Published in: | Проблемы машиностроения |
|---|---|
| Date: | 2015 |
| Main Authors: | , , |
| Format: | Article |
| Language: | English |
| Published: |
Інстиут проблем машинобудування ім. А.М. Підгорного НАН України
2015
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/99180 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Optimal packing of convex polytopes using quasi-phi-functions / A.V. Pankratov, T.E. Romanova, A.M. Chugay // Проблемы машиностроения. — 2015. — Т. 18, № 2. — С. 55-65. — Бібліогр.: 27 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860267333692424192 |
|---|---|
| author | Pankratov, A.V. Romanova, T.E. Chugay, A.M. |
| author_facet | Pankratov, A.V. Romanova, T.E. Chugay, A.M. |
| citation_txt | Optimal packing of convex polytopes using quasi-phi-functions / A.V. Pankratov, T.E. Romanova, A.M. Chugay // Проблемы машиностроения. — 2015. — Т. 18, № 2. — С. 55-65. — Бібліогр.: 27 назв. — англ. |
| collection | DSpace DC |
| container_title | Проблемы машиностроения |
| description | We study a packing problem of a given collection of convex polytopes into a rectangular container of minimal
volume. Continuous rotations and translations of polytopes are allowed. In addition a given minimal allowable
distances between polytopes are taking into account. We employ radical free quasi-phi-functions and adjusted
quasi-phi-functions to describe placement constraints. The use of quasi-phi-functions, instead of phi-functions,
allows us to simplify non-overlapping, as well as, to describe distance constraints, but there is a price to pay:
now the optimization has to be performed over a larger set of parameters, including the extra variables used by
our new functions. We provide an exact mathematical model of the problem as a nonlinear programming problem.
We also develop an efficient solution algorithm which involves a starting point algorithm, using homothetic
trasformations of geometric objects and efficient local optimization procedure, which allows us to runtime and
memory). We present here a number of examples to demonstrate the efficiency of our methodology.
Рассматривается задача упаковки выпуклых многоранников в прямоугольном контейнере минимального объема. Допускаются непрерывные трансляции и повороты многогранников. Учитываются минимально допустимые расстояния, заданные между многогранниками. Для формализвации ограничений размещения применяются свободные от радикалов квази-phi-функции и псевдонормализованные квази-phi-функции. Использование квази-phi-функций, вместо phi-функций, позволяет упростить вид ограничений непересечения многогранников и описать в аналитическом виде ограничения на минимально допустимые расстояния, заданные между многогранниками. Однако процесс оптимизации требует большего числа параметров, включая дополнительные переменные для квази-phi-функций. Строится математическая модель в виде задачи нелинейного программирования. Предлагается эффективный метод решения, включающий: алгоритм, основанный на гомотетических преобразованиях геометрических объектов для построения допустимых стартовых точек, и процедура локальной оптимизации, которая позволила значительно уменьшить размерность задачи, а также сократить вычислительные ресурсы (время и память). Приводятся результаты численных экспериментов, которые демонстрируют эффективность предложенной методологии решения задачи упаковки выпуклых многогранников.
Розглядається задача упаковки опуклих багатогранників у прямокутний контейнер мінімального об’єму. При цьому багатогранники припускають безперервні повороти та трансляції. Крім того, враховуються мінімально припустимі відстані між багатогранниками. Для побудови математичної моделі задачі як задачі нелінійного програмування використовуються вільні від радикалів квазі-phi-функції. Розроблено ефективний алгоритм розв’язання, який дозволяє зменшити розмірність задачі і обчислювальні витрати. Наведено числові приклади.
|
| first_indexed | 2025-12-07T19:02:22Z |
| format | Article |
| fulltext |
ПРИКЛАДНАЯ МАТЕМАТИКА
ISSN 0131–2928. Пробл. машиностроения, 2015, Т. 18, № 2 55
A. V. Pankratov,
Doctor of Engineering Science
T. E. Romanova,
Doctor of Engineering Science
A. M. Chugay,
Ph.D of Engineering Science
A. N. Podgorny Institute for Mechanical
Engineering Problems, National Acad-
emy of Sciences of Ukraine,
Kharkiv, е-mail: impankratov@mail.ru,
sherom@kharkov.ua,
chugay@ipmach.kharkov.ua
Ключові слова: упаковка, багатогранники,
безперервні повороти, неперетинання, припус-
тимі відстані, квазі-phi-функції, математична
модель, нелінійна оптимізація.
УДК 519.859
OPTIMAL PACKING OF CONVEX
POLYTOPES USING QUASI-PHI-
FUNCTIONS
Розглядається задача упаковки опуклих багатогранників у
прямокутний контейнер мінімального об’єму. При цьому ба-
гатогранники припускають безперервні повороти та транс-
ляції. Крім того, враховуються мінімально припустимі від-
стані між багатогранниками. Для побудови математичної
моделі задачі як задачі нелінійного програмування використо-
вуються вільні від радикалів квазі-phi-функції. Розроблено
ефективний алгоритм розв’язання, який дозволяє зменшити
розмірність задачі і обчислювальні витрати. Наведено числові
приклади.
Introduction
Optimal packing problem is a part of operational research and computational geometry [1]. It has a
wide spectrum of applications in modern biology, mineralogy, medicine, materials science, nanotechnology,
robotics, pattern recognition systems, control systems, space apparatus control systems, as well as in the
chemical industry, power engineering, mechanical engineering, shipbuilding, aircraft construction, civil en-
gineering, etc. At present, the interest in finding effective solutions for packing problems is growing rapidly.
This is due to a large and growing number of applications and an extreme complexity of methods used to
handle many of them.
These problems are NP-hard [2], and, as a result, solution methodologies generally employ heuristics
e. g., [3–13]. Some researchers develop approaches based on mathematical modeling and general optimiza-
tion procedures; e. g., [14–19].
We consider a practical problem of packing a collection of a given non-identical convex polytopes
into a rectangular container of minimal volume.
In the paper [16] authors present an efficient solution method for packing polytopes within the
bounds of a polytope container. The central geometric operation of the method is an exact one-dimensional
translation of a given polytope to a position which minimizes its volume of overlap with all other polytopes.
The translation algorithm is used as part of a local search heuristic and a meta-heuristic technique, guided
local search, is used to escape local minima. Additional details are given for the three-dimensional case and
results are reported for the problem of packing polytopes in a rectangular parallelepiped. Utilization of con-
tainer space is improved by an average of more than 14 percentage points compared to previous methods
proposed in [20]. However, in the experiments the largest total volume of overlap allowed in a solution cor-
responds to one percent of the total volume of all polytopes for the given problem.
Our approach is based on mathematical modeling of relations between geometric objects and thus
reducing the packing problem to a nonlinear programming problem. To this end we use the phi-function
technique (see e. g. [21]) for analytic description of objects placed in a container taking into account their
continuous rotations and translations. At present phi-functions for the simplest 3D-objects, such as paral-
lelepipeds, convex polytopes and spheres are considered in [22, 23]. Some of phi-functions (especially for
3D-objects, i.e. polytopes) happen to be rather complicated, analytically (involve a lot of radicals, operations
of maximum), and difficult in practical use (to apply NLP-solvers).
In this paper we apply the concept of phi-functions, extending their domains by including auxiliary
variables. The new functions, called quasi-phi-functions, can be described by analytical formulas that are
A. V. Pankratov, T. E. Romanova, A. M. Chugay, 2015
ПРИКЛАДНАЯ МАТЕМАТИКА
ISSN 0131–2928. Пробл. машиностроения, 2015, Т. 18, № 2 56
substantially simpler than those used for phi-functions, for some types of objects, in particular, for polytopes.
In addition we construct an adjusted phi-function for describing distance constraints for a pair of polytopes.
One way to tackle the packing problem is use the existing phi-functions for rotating polytopes
described in [22]. In the paper we propose alternative way to solve the problem which is based on quasi-phi-
functions [24], is capable of finding a good local-optimal solution in reasonable computational time. The use
of quasi-phi-functions, instead of phi-functions, allows us to simplify non-overlapping, as well as, to
describe distance constraints, but there is a price to pay: now the optimization has to be performed over a
larger set of parameters, including the extra variables used by our new functions, but this is a small price. We
believe our quasi-phi-functions and our optimization algorithm described below are more flexible and
efficient than other techniques.
The paper is organized as follows: in Section 2 we formulate the polytope packing problem. In Sec-
tion 3 we define our quasi-phi-functions (adjusted-quasi-phi-functions) for an analytical description of non-
overlapping, containment and distance constraints in the problem. In Section 4 we propose a mathematical
model as a nonlinear programming problem by means of quasi-phi-functions. In Section 5 we develop a so-
lution algorithm, which involves a fast starting point algorithm and efficient local optimization procedures.
In Section 6 we present our computational results for some new instances and several instances studied be-
fore. In Section 7 we give some conclusions.
2. Problem formulation
We consider here a packing problem in the following setting. Let Ω denote a rectangular domain
Ω = {(x, y, z) ∈ R
3
: 0 ≤ x ≤ l, 0 ≤ y ≤ w, 0 ≤ z ≤ h}. It should be noted that each of the three dimensions (l or
w or h) may be fixed. In particular three of dimensions of l, w, h may be variable. Suppose a set of polytopes
Ki, i ∈ {1, 2, …, n} = In, is given to be placed in Ω without overlaps. Each polytope Ki is defined by its verti-
ces p
i
j, 1, ...., ij m= , whose values are fixed. With each polytope iK
we associate its local coordinate sys-
tem whose origin is called a pole of the polytope. Without loss of generality, we assume that the pole of a
polytope Ki coincides with the center point of its circumscribed sphere Si of radius ri. We also use a fixed
coordinate system attached to the container Ω.
The location and orientation of polytope Ki is defined by a variable vector of its placement
parameters (vi, θi). Here vi = (xi, yi, zi) is a translation vector, θi = (θi
1, θi
2, θi
3) is a vector of rotation
parameters, where θ1
i, θ
2
i, θ
3
i are appropriate angels from axis OX to OY, from axis OY to OZ and
from axis OX to OZ from axis OX to OY, from axis OY to OZ and from axis OX to OZ in the local
coordinate system of polytope Ki.
The translation of polytope Ki by vector vi, the rotation of polytope Ki by vector θi is defined
by Ki(ui) = {p ∈ R
3
: p = vi + M(θi)⋅p
0
, ∀p
0
∈ Ki
0}, Ki
0 denotes the non-translated and non-rotated
polytope Ki with λi = 1, M(θi) = M1(θi
1
)⋅M2(θi
2
)⋅M3(θi
3
) is a rotation matrix, where
.
cos0sin
010
sin0cos
=)(,
cossin0
sincos0
001
=)(,
100
0cossin
0sincos
=)(
33
33
3
3
22
222
2
11
11
1
1
θθ−
θθ
θ
θθ
θ−θθ
θθ
θ−θ
θ
ii
ii
i
ii
iiiii
ii
i
MMM
Between each pair of polytopes Ki and Kj, as well as, between polytope Ki and the walls of domain Ω
appropriate minimal allowable distances −ρ
ij
and −ρ
i
may be given.
Polytope packing optimization problem. Pack the set of polytopes Ki(ui), i ∈ In, within a rec-
tangular domain Ω of minimal volume F = l⋅w⋅h taking into account minimal allowable distances.
3. Mathematical modeling of placement constraints
To describe non-overlapping and containment constraints we use quasi-phi-functions and phi-
functions. To describe distance constraints we apply adjusted quasi-phi-functions and adjusted phi-functions.
Clear definitions of a phi-function (a quasi-phi-function), an adjusted phi-function (an adjusted quasi-phi-
function) one can find in papers [21, 24].
ПРИКЛАДНАЯ МАТЕМАТИКА
ISSN 0131–2928. Пробл. машиностроения, 2015, Т. 18, № 2 57
To describe non-overlapping constraint ∅=21 intint KK I , we
use quasi-phi-function 21KKΦ′ for two convex polytopes K1 and K2.
Let K1(u1) and K2(u2) be convex polytopes, given by their verti-
ces pi
1
, i = 1, …, m1, and pj
2
, j = 1, …, m2.
Let }0:),,{()( ≤µ+⋅γ+⋅β+⋅α=ψ=
PPP
zyxzyxuP be a half-
space, where ,sin yPθ=α ,cossin yPxP θ⋅θ−=β
yPxP θ⋅θ=γ coscos (note
that 1222 =γ+β+α ) and ),,( PPyPxPu µθθ= .
Suppose ),( 1
1
P
PK
uuΦ is the normalised phi-function for K1(u1)
and a half-space P(uP) [21] and ),( 2
2
P
PK
uu
∗
Φ is the normalised phi-
function for K2(u2) and )(int\)( 3*
PP uPRuP = , where
)(min),( 1
1
1
1
1
iP
mi
P
PK
puu ψ=Φ
≤≤
and ))((min),(
2
1
2
2
*
2
jP
mj
P
PK
puu ψ−=Φ
≤≤
.
A function defined by
)},(),,(min{),,( 2121
2121
P
PK
P
PK
P
KK
uuuuuuu
∗
ΦΦ=Φ′ , (1)
is a quasi-phi-function for K1(u1) and K2(u2) [24].
Figure 1 shows that if two convex polytopes K1 and K2 do not have common points then there is al-
ways exist additional variables ),,( PPyPxPu µθθ= such that 0max 21 >Φ′ KK
uP
.
Thus, ⇔≥Φ′ 0max 21KK
uP
∅=21 intint KK I . We follow here the important characteristic of a quasi-
phi-function: if 021 ≥Φ′ KK
for some uP, then ∅=21 intint KK I .
Let ),(min),(dist
21 ,
21 badKK
KbKa ∈∈
= , where d(a, b) stands for the Euclidean distance between points
3
, Rba ∈ and let 012 >ρ− denote minimal allowable distances between polytopes K1(u1) and K2(u2).
To describe distance constraint −ρ≥ 1221 ),(dist KK , we use adjusted quasi-phi-function 12Φ′
)
for poly-
topes K1(u1) and K2(u2).
An adjusted quasi-phi-function for convex polytopes K1(u1) and K2(u2) is derived by
−ρ−Φ′=Φ′
122121 5.0),,(),,( 2121
P
KK
P
KK
uuuuuu
)
. (2)
Thus,
−
∈
ρ≥⇔≥Φ′
1221
'
),dist(0max 21 KK
KK
Uu
)
.
It follows from (2) that −− ρ≥⇒≥ρ−Φ′
12211221 ),dist(05.0),,(21 KKuuu P
KK
.
To describe containment constraint ∅=Ω⇔Ω⊂ *
11 int IKK we use phi-function
*
1ΩΦK
for a
convex polytope K1(u1) and object Ω=Ω int\3*
R .
Let K1(u1) be convex polytope, given in its local coordinate system by their vertices ,1
ip 1,....,1 mi = ,
where ),,(
1111
ziyixii pppp = .
A phi-function for a convex polytope K1(u1) and object Ω*
may be defined as
}.6,...,1),(minmin{)(
1
1
1
1
1
*
1 =ϕ=Φ
≤≤
Ω
jpu ij
mi
K
(3)
.)()(,)(,)()(
,)(,)()(,)(
1
1
1
16
1
1
1
15
1
1
1
14
1
1
1
13
1
1
1
12
1
1
1
11
hpzppzpwpyp
pyplpxppxp
ziiziiyii
yiixiixii
++−=ϕ+=ϕ++−=ϕ
+=ϕ++−=ϕ+=ϕ
1K
2K
*
P
−
P
+
ψP = 0
Fig. 1. A separating plane for
two convex polytopes K1 and K1
ПРИКЛАДНАЯ МАТЕМАТИКА
ISSN 0131–2928. Пробл. машиностроения, 2015, Т. 18, № 2 58
To describe containment constraint taking into account minimal allowable distance −ρ≥Ω 1
*
1 ),(dist K
we use adjusted phi-function 1Φ′
)
for a convex polytope K1(u1) and object Ω*
.
An adjusted phi-function for a convex polytope K1(u1) and object Ω*
is defined by
.)()( 111
*
1
*
1 −ΩΩ ρ−Φ=Φ uu
KK
)
(4)
4. Mathematical model
First we assemble a complete set of variables for our optimization problem. The vector u ∈ R
σ
of all
our variables can be described as follows: ,),,...,,,,,( 21
σ∈τ= Ruuuhwlu
n
where (l, w, h) denote the variable
dimensions (length, width and height) of the rectangular container Ω and ),,,,,(),( 321
iiiiiiiii
zyxvu θθθ=θ= is
the vector of placement parameters for the polytope Ki, i ∈ In. Here ),...,(
1 m
PP
uu=τ denotes the vector of ad-
ditional variables, where ),,,( kk
y
k
x
k
P
PPP
u µθθ= are additional variables for the k
th
pair of polytopes, according
to (1)–(4), k = 1, …, m, m = 0.5(n – 1)n. Lastly we derive the number of the problem variables
σ = 3 + 6n + 3m.
Now a mathematical model of the polytope packing optimization problem may be stated in the form
)(min uF
RWu
σ⊂∈
, (5)
},,...,2,1,,...,2,1,0,0:{ ijnjniRuW
iij
>==≥Φ≥Φ′∈= σ
))
, (6)
where F(u) = l⋅w⋅h,
ij
Φ′
)
is a radical free adjusted quasi phi-function (2) defined for the pair of polytopes Ki
and Kj, taking into account minimal allowable distance −ρ
ij
,
i
Φ′ is a radical free adjusted phi-function (4) de-
fined for the polytope Ki and the object
*Ω (to hold the containment constraint), also taking into account
minimal allowable distance
i
ρ −
.
If 0
ij
ρ − = and 0
i
ρ − = we replace the adjusted quasi-phi-function
ij
Φ′
)
by a radical free
quasi-phi-function '
ijΦ defined by (1) for each pair of polytopes to enforce the non-overlapping
constraint and the adjusted phi-function
i
Φ′
)
with a radical free phi-function
i
Φ defined by (3) for
each polytope and the object Ω*
to enforce the containment constraint.
Our problem (5)–(6) is a constrained multiextremal optimization problem. Each quasi-phi-function
inequality in (6) is presented by a system of inequalities with infinitely differentiable functions. The frontier
of W is made of nonlinear surfaces containing valleys and ravines. Our model is non-convex and continuous
nonlinear programming problem. Problem (5)–(6) is an exact formulation for the polytope packing optimiza-
tion problem.
5. A solution strategy
Our solution strategy involves the following steps:
1) Generate a number of starting points from the feasible set of the problem (5)–(6). We employ a
new starting point algorithm (SPA). See Subsection 5.1.
2) Search for a local minimum of the objective function F(u) of problem (5)–(6), starting from each
point obtained at Step 1. We employ a special optimisation procedure – Local Optimization with Feasible
Region Transformation (LOFRT-3D). See Subsection 5.2.
3) Choose the best local minimum from those found at Step 2. This is our best solution of the prob-
lem (5)–(6).
An essential part of our local optimization scheme (Step 2) is the LOFRT procedure that reduces the
dimension of the problem and computational time. The reduction scheme used by our LOFRT algorithm is
described below. The actual search for a local minimum is performed by a standard IPOPT algorithm [25],
ПРИКЛАДНАЯ МАТЕМАТИКА
ISSN 0131–2928. Пробл. машиностроения, 2015, Т. 18, № 2 59
which is available at an open access noncommercial software depository (https://projects.coin-
or.org/Ipopt) .
5.1 Starting point algorithm (SPA)
In order to find a starting point u
0
that belongs to the feasible set W we apply the following algorithm
based on homothetic transformation of polytopes.
The algorithm consists of the following steps:
1. Choose starting dimensions (length and width) for the container Ω0
. They must be sufficiently
large to allow for a placement of all our polytopes with required distance constraints within Ω0
. For example,
we can set
}.max,maxmax{,)1(2
,
1
0000 −
∈
−
∈
−−
=
ρρ=ρρ++==== ∑ i
Ii
ij
Iji
n
i
i
nn
nrhlwl
2. Generate randomly, within Ω0
, a set of n randomly chosen center points ),,,( 0'0'0'
iii
zyx
i = 1, 2, …, n of circumbsribed spheres Si of radius λri. We assume here that λ is a homothetic coefficient for
all our spheres Si and 0 ≤ λ ≤ 1.
3. Take the starting point )0,,,,...,,,(
0'0'0'0'0'
1
0'
1
0'
1
0' =λ=
nnn
zyxzyxu and solve the following auxiliary op-
timization problem, assuming that l = l
0
, w = w
0
and h = h
0
:
λ
∈′ '
max
Wu
, (7)
}0,01,,...,2,1,0,0:R{
*
13 ≥λ≥λ−=<≥Φ≥Φ∈′=′ Ω+
njiuW iji SSSn
))
, (8)
where ),,,,...,,,( 111 λ=′
nnn
zyxzyxu ,
,)()()()( 2222
jijijiji
SS
rrzzyyxx
ji λ+ρ+λ−−+−+−=Φ −
)
is an adjusted phi-function for sphere Si of radius λri and sphere Sj of radius λrj,
}6,...,1,min{
*
=ϕ=Φ Ω
k
ki
S i
)
,
−−−
−−−
ρ−λ−=ϕρ−λ−+−=ϕρ−λ−=ϕ
ρ−λ−+−=ϕρ−λ−=ϕρ−λ−+−=ϕ
iiiiiiiiiiii
iiiiiiiiiiii
rzrhzry
rwyrxrlx
4
0
54
0
32
0
1
,,
,,,
is an adjusted phi-function for sphere Si of radius λri and object Ω*
.
We denote the point of global maximum of problem (7)–(8) by ),,,,...,,,( '*'*'*'*'*
1
'*
1
'*
1
'* λ=
nnn
zyxzyxu .
Remark. Note that if an optimal global solution point is found, then λ'
*
= 1. The solution automati-
cally respects all the non-overlapping and containment constraints.
Our use of homothetic transformations of spheres here is similar to the use of variable radii for opti-
mal packing of nD-spheres, which was proposed in [26].
4. Form feasible starting point ),,...,,,,,( 000
2
0
1
0000 τ=
n
uuuhwlu for problem (5)–(6):
– Form a vector of starting placement parameters ),,,( 00000
iiiii
zyxu θ= for each polytope Ki,
i = 1, …, n, where ),,(),,( '*'*'*000
iiiiii
zyxzyx = and ),,( 0000
yixizii
θθθ=θ are randomly generated rotation parame-
ters.
– Find values for the vector of additional variables ),...,(
0010 m
PP
uu=τ , ),,( 0000 kk
y
k
x
k
P
PPP
u µθθ= by a
special optimization procedure that solves an auxiliary problem of searching for ),,(max 00
3
k
jiij
Ru
Pk
P
uuuΦ′
∈
)
for each quasi-phi-function (or, respectively, adjusted phi-function) that is involved in (6), under
fixed parameters ),,,( 00000
iiiii
zyxu θ= , i = 1, 2, …, n.
To solve the above auxiliary problem we use the following model:
ПРИКЛАДНАЯ МАТЕМАТИКА
ISSN 0131–2928. Пробл. машиностроения, 2015, Т. 18, № 2 60
'
'..,max µ∈µ Wuts ,
where }),,(:),{(
004' µ≥Φ′∈µ=µ
k
jiij
k
PP
uuuRuW
)
, 1
R∈µ , is a new auxiliary variable,
k
P
u is the vector of auxil-
iary variables and ),(
00
ji
uu are fixed placement parameters for our adjusted phi-functions (respectively,
quasi-phi-functions), k = 1, …, m.
As a result we form a feasible starting point ),,...,,,,,( 000
2
0
1
0000 τ=
n
uuuhwlu . Thus all our adjusted
quasi-phi-functions (or quasi-phi-functions) and adjusted phi-functions (or phi-functions) for our polytopes
at the point u
0
take non-negative values.
Figure 2 gives illustrations to steps 1)–4) in our starting point algorithm SPA.
Lastly, our algorithm returns the vector u
0
as a starting point for a subsequent search for a local
minimum of the problem (5)–(6).
5.2 Algorithm of Local Optimization with Feasible Region Transformation for 3D packing
(LOFRT-3D)
The algorithm based on LOFRT procedure proposed in [27] for optimal ellipse packing problem. We
extended the algorithm to 3D case for packing of convex polytopes.
Let u
0
∈ W be one of the starting points found by SPA. The main idea of the LOFRT-3D algorithm
is as follows.
First we take sphere Si of radius ri circumscribed around each polytope Ki, i = 1, 2., …, n. Then we
extend the radius of each sphere Si by −ρ5.0 (derived above at step 1 of SPA) and for each extended sphere
Si construct an "individual" rectangular container
iii
KS ⊃⊃Ω with equal half-sides of length
ε+ρ+ −5.0
i
r , i = 1, 2, …, n, so that Si, Ki and Ωi have the same center ),,( 000
iii
zyx . We take the epsilon pa-
rameter of the LOFTR-3D procedure as nr
n
i
i /
1
∑
=
=ε . Further we fix the position of each individual container
Ωi and let the local optimization algorithm move the extended sphere Si (and the appropriate polytope Ki)
only within the individual container Ωi. It is clear that if Ωi and Ωj do not overlap each other (i. e.
0≥Φ
ΩΩ ji ), then we do not need to check the non-overlapping constraint for the corresponding pair of poly-
topes Ki and Kj, taking into account distance constraints. Here
}6,...,1,max{ =ϕ=Φ
ΩΩ
k
k
ij
ji ,
where, assuming ε+ρ++= −
2)(
jiij
rrR ,
.)(,)(,)(
,)(,)(,)(
006005004
003002001
ijjiijijjiijijjiij
ijjiijijjiijijjiij
RzzRyyRxx
RzzRyyRxx
−−−=ϕ−−−=ϕ−−−=ϕ
−−=ϕ−−=ϕ−−=ϕ
a) b) c) d)
Fig. 2. Illustration of steps 1)-4) in SPA:
a) – step 1; b) – step 2; c) – step 3; d) – step 4
ПРИКЛАДНАЯ МАТЕМАТИКА
ISSN 0131–2928. Пробл. машиностроения, 2015, Т. 18, № 2 61
By analogy if Ωi and *
εΩ do not overlap each other (i. e. 0≥Φ
∗
εΩΩi ), then we do not need to check
the containment constraint for the corresponding polytope Ki and
},,:),,{( 3 ε−≤≤εε−≤≤εε−≤≤ε∈=Ωε hzwylxRzyx .
Appropriate phi-function
∗
εΩΩΦ i for polytope Ki and εε Ω=Ω int\3*
R has the form
}6,...,1,min{ =ψ=Φ
∗
εΩΩ
k
k
ij
i ,
where assuming ε+ρ+= − 2
ii
rR ,
.,,
,,,
060504
030201
iiiiiiiii
iiiiiiiii
RhzRwyRlx
RzRyRx
−+−=ψ−+−=ψ−+−=ψ
−=ψ−=ψ−=ψ
The above key idea allows us to extract subsets of our feasible set W of the problem (5)–(6) at each
step of our optimization procedure as follows.
We create an inequality system of additional constraints on the translation vector ),,(
iiii
zyxv = of
each polytope Ki in the form: 01 ≥Φ
∗Ω iiS
, i = 1, 2, …, n, where
},,,,,min{ 0000001 ε+−ε+−ε+−ε++−ε++−ε++−=Φ
∗Ω
iiiiiiiiiiii
S
zzyyxxzzyyxxii ,
is the phi-function for the extended sphere Si and
ii
R 1
3*
1 int\ Ω=Ω .
We generate an “artificial” subset εΠ1 of the following form:
}.,...,1,0,0,0
,0,0,0:{
)0()0()0(
)0()0()0(
1
nizzyyxx
zzyyxxRu
iiiiii
iiiiii
k
=≥ε+−≥ε+−≥ε+−
≥ε++−≥ε++−≥ε++−∈=Π σ−σε
Then we form a new subregion εΠ= 11 IWW defined by
},,,,,...,2,1,0,,0,),(,0:{ 000211
11 ε−≥ε−≥ε−≥=≥ΦΞ∈≥Φ′Ξ∈≥Φ′∈=
∗Ωσ−σ
hhwwllniijiRuW iiS
iij
))
where },...,2,1,0:),{( 11
1 njiji ji =><Φ=Ξ
ΩΩ
, },...,2,1,0:{
*
1
2 nii i =<Φ=Ξ ΩΩ
.
In other words, we delete from the system, which describes feasible set W, quasi-phi-function ine-
qualities for all pairs of polytopes whose individual containers do not overlap and we add additional ine-
qualities 01 ≥Φ
∗Ω iiS
, which describe the containment of the extended spheres Si in their individual containers
Ω1i, i = 1, 2, …, n. Thus, we reduce the number of additional variables by σ1. Then our algorithm searches
for a point of local minimum
*
1w
u of the subproblem )(min
11
11
w
RWu
uF
w
σ−σ⊂∈
.
When the point
*
1wu is found, it is used to construct a starting point u
(1)
for the second iteration of our
optimization procedure (note that the σ1 previously deleted additional variables τ1 have to be redefined by a
special procedure used in SPA, assuming l
0
= 1).
At that iteration we again identify all the pairs of polytopes with non-overlapping individual contain-
ers, form the corresponding subset W2 (analogously to W1) and let our algorithm search for a local minimum
2
*
2
Wuw ∈ . The resulting local minimum
*
2wu is used to construct a starting point u
(2)
for the third iteration,
etc.
On the k
th
iteration we form starting point u(k–1) from the local minimum *
)1( −kwu and solve the
following k
th
subproblem on a subset εΠ= kk WW I :
)(min
kk
kkw
w
RWu
uF
σ−σ⊂∈
,
ПРИКЛАДНАЯ МАТЕМАТИКА
ISSN 0131–2928. Пробл. машиностроения, 2015, Т. 18, № 2 62
},,,,,...,2,1,0
,,0,),(,0:{
)1()1()1(
21
1
ε−≥ε−≥ε−≥=≥Φ
Ξ∈≥Φ′Ξ∈≥Φ′∈=
−−−Ω
σ−σ
∗
kkkS
k
i
k
ijk
hhwwllni
ijiRuW
kii
))
where },...,2,1,0:),{(1 njiji kjkik =><Φ=Ξ
ΩΩ
, },...,2,1,0:{
*
2 nii kik =<Φ=Ξ ΩΩ
.
If the point
*
kwu of local minimum of the k
th
subproblem belongs to the frontier of an “artificial” sub-
set
},,...,1,0,0,0
,0,0,0:{
)1()1()1(
)1()1()1(
nizzyyxx
zzyyxxRu
k
ii
k
ii
k
ii
k
ii
k
ii
k
iik
k
=≥ε+−≥ε+−≥ε+−
≥ε++−≥ε++−≥ε++−∈=Π
−−−
−−−σ−σε
(i. e.
*
kw
u
εΠ∈ kfr ), we take the point
)(* k
w uu
k
= as a center point for a new subset ε
+Π 1k and continue our
optimization procedure, otherwise (i. e.
k
wk
u εΠ∈ int
*
) we stop our LOFRT-3D procedure.
We note that ε≥
+
),(dist
**
1kk ww uu , if
k
w fru
k εΠ∈
+
*
1
, and the value of ε is considerably greater than the
accuracy of IPOPT (10
–8
). Thus, we may conclude that the stopping condition of the LOFRT procedure is
always reached in a finite number of iterations.
We claim that the point
σ∈τ== Ruuu kw
k
k
),(
***)(*
is a point of local minimum of the problem
(5)–(6), where k
k
Ruw
σ−σ∈*
is the last point of our iterative procedure and *
kτ is a vector of redefined values
of the previously deleted additional variables kRk
σ∈τ (the values can be redefined by the special procedure
used in SPA). The assertion comes from the fact that any arrangement of each pair of polytopes Ki and Kj
subject to k
ji 1\),( ΞΞ∈ guarantees that there always exists a vector kτ of additional variables such that
k
ij ji 1\),(,0 ΞΞ∈≥Φ′
)
at the point
*)(k
u . Here },...,2,1),,{( njiji =>=Ξ . Therefore the values of additional
variables of the vector kτ have no effect on the value of our objective function, i. e )()(
*)(* k
w uFuF
k
= . That
is why, indeed, we do not need to redefine the deleted additional variables of the vector kτ at the last step of
our algorithm.
So, while there are O(n
2
) pairs of polytopes in the container, our algorithm may in most cases only
actively controls O(n) pairs of polytopes (this depends on the sizes of polytopes and the value of ε ), because
for each polytope only its “ε-neighbors” have to be monitored.
The epsilon parameter provides a balance between the number of inequalities in each nonlinear pro-
gramming subproblem and the number of the subproblems which we need to generate and solve in order to
get a local optimal solution of problem (5)–(6). The LOFTR-3D procedure allows us to reduce considerably
computational costs (time and memory).
Thus our LOFRT-3D algorithm allows us to reduce the problem (5)–(6) with O(n
2
) inequalities and a
O(n
2
)-dimensional feasible set W to a sequence of subproblems, each with O(n) inequalities and a O(n)-
a) b) c) d)
Fig. 3. Placement of polytopes of LOFRT-3D procedure corresponding to feasible points:
a) – )0(
u ; b) – )4(*
4
uuw = ; c) – )8(*
8
uu
w
= ; d) – )20(*
20
uu
w
=
ПРИКЛАДНАЯ МАТЕМАТИКА
ISSN 0131–2928. Пробл. машиностроения, 2015, Т. 18, № 2 63
dimensional solution subset Wk. This reduction is of a paramount importance, since we deal with nonlinear
optimization problems.
6. Computational results
Here we present a number of examples to demonstrate the efficiency of our methodology. We have
run our experiments on an AMD Athlon 64 X2 5200+ computer, and for local optimization we used the
IPOPT code (https://projects.coin-or.org/Ipopt) developed by [25]. We take sizes of polytopes from paper
[20] and set ε = 5 for LOFRT-3D procedure in our examples.
Example 1. We consider the collection of polytopes of example 1 given in [20]. Figure 4 shows the
local optimal placement of n = 7 convex polytopes. The container has dimensions and volume: a)
(l
*
, w
*
, h
*
) = (14.875640, 7.000000, 16.322287) and F(u
*
) = 1699.63 with ρ–
= 0 (Fig. 4, a); b)
(l
*
, w
*
, h
*
) = (12.214109, 22.585451, 10.119288) and F(u
*
) = 2791.52 with ρ–
= 1.5 (Fig. 4, b).
Example 2. We consider the collection of polytopes of example 2 given in [20]. Figure 5 shows the
local optimal placement of n = 12 convex polytopes. The container has dimensions and volume: a)
(l
*
, w
*
, h
*
) = (19.062599, 11.588046, 14.178271) and F(u
*
) = 3131.96 with ρ–
= 0 (Fig. 5, a); b)
(l
*
, w
*
, h
*
) = (16.474352, 18.375541, 16.930069) and F(u
*
) = 5125.15 with ρ–
= 1.5 (Fig. 5, b).
Example 3. We consider the collection of polytopes of example 3 given in [20]. Figure 6 shows the
local optimal placement of n = 25 convex polytopes. The container has dimensions and volume: a)
(l
*
, w
*
, h
*
) = (17.215330, 18.020337, 18.542389) and F(u
*
) = 5752.33 with ρ–
= 0 (Fig. 6, a); b)
(l
*
, w
*
, h
*
) = (21.794149, 22.043191, 20.602907) and F(u
*
) = 9897.9 with ρ–
= 1.5 (Fig. 6, b).
For each the example the minimal volume of the container found by our method happens to be
smaller than the best solution reported in [20]. The improvement is 65%, 43.7% and 30.3% in Examples 1, 2
and 3 respectively.
Example 4. We generate a collection of n = 98 convex polytopes, consisting of the 7 types of poly-
topes of example 1 given in [20] and taken by 14 of each type. Figure 7 shows the local optimal placement of
n=98 convex polytopes. The container
has dimensions (l
*
, w
*
, h
*
) = (30.932420,
28.189778, 26.506470) and volume
F(u
*
) = 23113.06.
7. Concluding remarks
Now, using our radical free
quasi-phi-functions and phi-functions we
can develop exact nonlinear program-
ming model for optimal packing of con-
vex polytopes taking into account dis-
tance constraints and applied our meth-
odology to search for “good” local opti-
mal solutions. The values of the objective
a) b)
Fig. 4. Local optimal placement
of polytopes in Example 1:
a) – ρ–
= 0; b) – ρ–
= 1.5
a) b)
Fig.5. Local optimal placement
of polytopes in Example 2:
a) – ρ–
= 0; b) – ρ–
= 1.5
a) b)
Fig. 6. Local optimal placement of polytopes in Example 3:
a) – ρ–
= 0; b) – ρ–
= 1.5
ПРИКЛАДНАЯ МАТЕМАТИКА
ISSN 0131–2928. Пробл. машиностроения, 2015, Т. 18, № 2 64
function, as well as, the computational time reported in Section 6 for
several examples is achieved presently, but we expect that it will be re-
duced in the future. The methodology may be extended for a case of
non-convex polytopes.
References
1. Wаscher, G. An improved typology of cutting and packing problems/
G. Wаscher, H. Hauner, H. Schumann // Eur. J. Oper. Res. – 2007. –
Vol. 183, № 3. – P. 1109–1130.
2. Chazelle, B. The complexity of cutting complexes / B. Chazelle,
H. Edelsbrunner, L. J. Guibas // Discr. & Comput. Geom. – 1989. – № 4
(2). – P. 139–81.
3. Aladahalli, C. Objective function effect based pattern search – theoretical
framework inspired by 3D component layout / C. Aladahalli, J. Cagan,
K. Shimada // J. Mech. Design. – 2007. – № 129. – P. 243–254.
4. Cagan, J. A survey of computational approaches to three-dimensional lay-
out problems / J. Cagan, K. Shimada, S. Yin // Comp.-Aided Des. – 2002. – № 34. – P. 597–611.
5. Egeblad, J. Heuristics for multidimensional packing problems / PhD Thesis – 2008.
6. Egeblad, J. Fast neighborhood search for two- and three-dimensional nesting problems / J. Egeblad, B. K. Nielse,
A. Odgaar // Eur. J. Oper. Res. – 2007. – № 183 (3). – P. 1249–1266.
7. Fasano, G. MIP-based heuristic for non-standard 3D-packing problems / G. Fasano // 4OR Quart. J. Belgian,
French and Italian Oper. Res. Soc. – 2008. – № 6 (3). – P. 291–310.
8. Predicting Packing Characteristics of Particles of Arbitrary Shapes / M. Gan, N. Gopinathan, X. Jia, R. A. Williams
// KONA. – 2004.– № 22. – P. 82–93.
9. Validation of a digital packing algorithm in predicting powder packing densities / X. Jia, M. Gan, R. A. Williams,
D. Rhodes // Powder Tech. – 2007. – № 174. – P. 10–13.
10. Korte, A. C. J. Random packing of digitized particles / A. C. J. Korte, H. J. H. Brouwers // Powder Techn. – 2013. –
№ 233. – P. 319–324.
11. Li, S. X. Sphere assembly model and relaxation algorithm for packing of non-spherical particles / S. X. Li, J. Zhao //
Chin. J. Comp. Phys. – 2009. –№ 26 (3). – P. 167–173.
12. Li, S. X. Maximum packing densities of basic 3D objects / S. X. Li, J. Zhao, P. Lu, Y. Xie // Chin. Scien. Bull. –
2010. – № 55 (2). – P. 114–119.
13. Sriramya, P. A State-of-the-Art Review of Bin Packing Techniques / P. Sriramya, P. B. Varthini // Eur. J. Scien.
Res. – 2012. – № 86 (3) – P. 360–364.
14. Orthogonal packing of rectagular items within arbitrary convex regions by nonlinear optimization / E. G. Birgin,
J. M. Martinez, F. H. Nishihara, D. P. Ronconi //Comput. Oper. Res. – 2006. – № 33. – P. 3535–3548.
15. Birgin, E. Optimizing the packing of cylinders into a rectangular container A nonlinear approach / E. Birgin,
J. Martínez, D. Ronconi // Eur. J. of Oper. Res. – 2005. – № 160 (1). – P. 19–33.
16. Egeblad, J. Translational packing of arbitrary polytopes / J. Egeblad, B. K. Nielsen, M. Brazil // Comp. Geom. –
2009. – № 42 (4). – P. 269–288.
17. Fasano, G. A. Global Optimization point of view for non-standard packing problems / G. A. Fasano // J. Glob. Op-
tim. – 2013. – № 55 (2). – P. 279–299.
18. Petrov, M. S. Numerical method for modelling the microstructure of granular materials / M. S. Petrov,
V. V. Gaidukov, R. M. Kadushnikov // Powder Metall. and Metal Ceram. – 2004. – № 43 (7–8). – P. 330–335.
19. Torquato, S. Dense polyhedral packings Platonic and Archimedean solids / S. Torquato, Y. Jiao // Phys. Rev. –
2009. – № 80. – P. 041104.
20. Packing of convex polytopes into a parallelepiped / Y. Stoyan, N. Gil, G. Scheithauer, A. Pankratov, I. Magdalina //
Optimization. – 2005. – № 54 (2). – P. 215–235.
21. Chernov, N. Mathematical model and efficient algorithms for object packing problem / N. Chernov, Y. Stoyan,
T. Romanova // Comput. Geom. Theory and Appl. – 2010. – № 43 (5). – P. 535–553.
22. Stoyan, Y. Mathematical modeling of the interaction of non-oriented convex polytopes / Y. Stoyan, А. Chugay //
Cyber. and Syst. Anal. – 2012. –№ 48 (6). – P. 837–845.
23. Stoyan, Yu. Construction of radical free phi-functions for spheres and non-oriented polytopes / Yu. Stoyan,
A. Chugay // Rep. of NAS of Ukraine. – 2011. – № 12. – P. 35–40.
24. Quasi-phi-function for mathematical modelling of geometric objects interactions / Yu. Stoyan, А. Pankratov, Т. Ro-
manova, N. Chernov / Rep. of NAS of Ukraine. – 2014. – № 9. – P. 53–57.
Fig.7. Local optimal placement
of polytopes in Example 4
|
| id | nasplib_isofts_kiev_ua-123456789-99180 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0131-2928 |
| language | English |
| last_indexed | 2025-12-07T19:02:22Z |
| publishDate | 2015 |
| publisher | Інстиут проблем машинобудування ім. А.М. Підгорного НАН України |
| record_format | dspace |
| spelling | Pankratov, A.V. Romanova, T.E. Chugay, A.M. 2016-04-23T18:30:38Z 2016-04-23T18:30:38Z 2015 Optimal packing of convex polytopes using quasi-phi-functions / A.V. Pankratov, T.E. Romanova, A.M. Chugay // Проблемы машиностроения. — 2015. — Т. 18, № 2. — С. 55-65. — Бібліогр.: 27 назв. — англ. 0131-2928 https://nasplib.isofts.kiev.ua/handle/123456789/99180 519.859 We study a packing problem of a given collection of convex polytopes into a rectangular container of minimal
 volume. Continuous rotations and translations of polytopes are allowed. In addition a given minimal allowable
 distances between polytopes are taking into account. We employ radical free quasi-phi-functions and adjusted
 quasi-phi-functions to describe placement constraints. The use of quasi-phi-functions, instead of phi-functions,
 allows us to simplify non-overlapping, as well as, to describe distance constraints, but there is a price to pay:
 now the optimization has to be performed over a larger set of parameters, including the extra variables used by
 our new functions. We provide an exact mathematical model of the problem as a nonlinear programming problem.
 We also develop an efficient solution algorithm which involves a starting point algorithm, using homothetic
 trasformations of geometric objects and efficient local optimization procedure, which allows us to runtime and
 memory). We present here a number of examples to demonstrate the efficiency of our methodology. Рассматривается задача упаковки выпуклых многоранников в прямоугольном контейнере минимального объема. Допускаются непрерывные трансляции и повороты многогранников. Учитываются минимально допустимые расстояния, заданные между многогранниками. Для формализвации ограничений размещения применяются свободные от радикалов квази-phi-функции и псевдонормализованные квази-phi-функции. Использование квази-phi-функций, вместо phi-функций, позволяет упростить вид ограничений непересечения многогранников и описать в аналитическом виде ограничения на минимально допустимые расстояния, заданные между многогранниками. Однако процесс оптимизации требует большего числа параметров, включая дополнительные переменные для квази-phi-функций. Строится математическая модель в виде задачи нелинейного программирования. Предлагается эффективный метод решения, включающий: алгоритм, основанный на гомотетических преобразованиях геометрических объектов для построения допустимых стартовых точек, и процедура локальной оптимизации, которая позволила значительно уменьшить размерность задачи, а также сократить вычислительные ресурсы (время и память). Приводятся результаты численных экспериментов, которые демонстрируют эффективность предложенной методологии решения задачи упаковки выпуклых многогранников. Розглядається задача упаковки опуклих багатогранників у прямокутний контейнер мінімального об’єму. При цьому багатогранники припускають безперервні повороти та трансляції. Крім того, враховуються мінімально припустимі відстані між багатогранниками. Для побудови математичної моделі задачі як задачі нелінійного програмування використовуються вільні від радикалів квазі-phi-функції. Розроблено ефективний алгоритм розв’язання, який дозволяє зменшити розмірність задачі і обчислювальні витрати. Наведено числові приклади. en Інстиут проблем машинобудування ім. А.М. Підгорного НАН України Проблемы машиностроения Прикладная математика Optimal packing of convex polytopes using quasi-phi-functions Article published earlier |
| spellingShingle | Optimal packing of convex polytopes using quasi-phi-functions Pankratov, A.V. Romanova, T.E. Chugay, A.M. Прикладная математика |
| title | Optimal packing of convex polytopes using quasi-phi-functions |
| title_full | Optimal packing of convex polytopes using quasi-phi-functions |
| title_fullStr | Optimal packing of convex polytopes using quasi-phi-functions |
| title_full_unstemmed | Optimal packing of convex polytopes using quasi-phi-functions |
| title_short | Optimal packing of convex polytopes using quasi-phi-functions |
| title_sort | optimal packing of convex polytopes using quasi-phi-functions |
| topic | Прикладная математика |
| topic_facet | Прикладная математика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/99180 |
| work_keys_str_mv | AT pankratovav optimalpackingofconvexpolytopesusingquasiphifunctions AT romanovate optimalpackingofconvexpolytopesusingquasiphifunctions AT chugayam optimalpackingofconvexpolytopesusingquasiphifunctions |