Packing non-equal hyperspheres into a hypersphere of minimal radius
The problem of packing different hyperspheres into a hypersphere of minimal radius is considered. All hypersphere radii are supposed to be variable. Solving the problem is reduced to solving a sequence of mathematical programming problems. A special way of construction of starting pointsis suggested...
Gespeichert in:
| Veröffentlicht in: | Проблемы машиностроения |
|---|---|
| Datum: | 2014 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Englisch |
| Veröffentlicht: |
Інстиут проблем машинобудування ім. А.М. Підгорного НАН України
2014
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/80974 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Packing non-equal hyperspheres into a hypersphere of minimal radius / G.N. Yaskov // Проблемы машиностроения. — 2014. — Т. 17, № 1. — С. 48-53. — Бібліогр.: 12 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860191630897709056 |
|---|---|
| author | Yaskov, G.N. |
| author_facet | Yaskov, G.N. |
| citation_txt | Packing non-equal hyperspheres into a hypersphere of minimal radius / G.N. Yaskov // Проблемы машиностроения. — 2014. — Т. 17, № 1. — С. 48-53. — Бібліогр.: 12 назв. — англ. |
| collection | DSpace DC |
| container_title | Проблемы машиностроения |
| description | The problem of packing different hyperspheres into a hypersphere of minimal radius is considered. All hypersphere radii are supposed to be variable. Solving the problem is reduced to solving a sequence of mathematical programming problems. A special way of construction of starting pointsis suggested. A smooth transition from one local minimum point to another providing a decrease of the objective value is realized using the jump algorithm is fulfilled. Then, solution results are improved due to reduction of the solution space dimension by step-by-step fixing radii of hyperspheres and rearrangements of hypersphere pairs. Non-linear mathematical programming problems are solved with the IPOPT (Interior Point Optimizer) solver and the concept of active inequalities. A number of numerical results are given.
Рассматривается задача упаковки разных гипершаров в гипершаре минимального радиуса. Считается, что радиусы всех гипершаров являются переменными. Решение задачи сводится к решению последовательности задач математического программирования. Используя jump-алгоритм, выполняется плавный переход от одной точки локального минимума к другой, в которой уменьшается значение целевой функции. В дальнейшем результаты решения улучшаются благодаря уменьшению размерности пространства решений за счет фиксации радиусов гипершаров и перестановки пар гипершаров. Приведено несколько численных примеров.
Розглядається задача упаковки різних гіперкуль у гіперкулю мінімального радіуса. Вважається, що радіуси всіх гіперкуль є змінними. Розв’язання задачі зводиться до розв’язання послідовності задач математичного програмування. Використовуючи jumpалгоритм, виконується плавний перехід від однієї точки локального мінімуму до іншої, в якій зменшується значення цільової функції. В подальшому результати розв’язання покращуються завдяки зменшенню розмірності простору розв’язків за рахунок фіксації радіусів гіперкуль та перестановки пар гіперкуль. Наведені декілька чисельних прикладів.
|
| first_indexed | 2025-12-07T18:06:48Z |
| format | Article |
| fulltext |
ПРИКЛАДНАЯ МАТЕМАТИКА
ISSN 0131–2928. Пробл. машиностроения, 2014, Т. 17, № 2 48
UDC 519.85
G. N. Yaskov, PhD
A.N. Podgorny Institute for Mechanical Engineering Problems
of the National Academy of Sciences of Ukraine
(Kharkov, e-mail: yaskov@ipmach.kharkov.ua)
PACKING NON-EQUAL HYPERSPHERES INTO
A HYPERSPHERE OF MINIMAL RADIUS
The problem of packing different hyperspheres into a hypersphere of minimal radius is
considered. All hypersphere radii are supposed to be variable. Solving the problem is reduced
to solving a sequence of mathematical programming problems. A special way of construction
of starting pointsis suggested. A smooth transition from one local minimum point to another
providing a decrease of the objective value is realized using the jump algorithm is fulfilled.
Then, solution results are improved due to reduction of the solution space dimension by step-
by-step fixing radii of hyperspheres and rearrangements of hypersphere pairs. Non-linear
mathematical programming problems are solved with the IPOPT (Interior Point Optimizer)
solver and the concept of active inequalities. A number of numerical results are given.
Рассматривается задача упаковки разных гипершаров в гипершаре минимального ради-
уса. Считается, что радиусы всех гипершаров являются переменными. Решение задачи
сводится к решению последовательности задач математического программирования.
Используя jump-алгоритм, выполняется плавный переход от одной точки локального
минимума к другой, в которой уменьшается значение целевой функции. В дальнейшем
результаты решения улучшаются благодаря уменьшению размерности пространства
решений за счет фиксации радиусов гипершаров и перестановки пар гипершаров. При-
ведено несколько численных примеров.
Розглядається задача упаковки різних гіперкуль у гіперкулю мінімального радіуса. Вва-
жається, що радіуси всіх гіперкуль є змінними. Розв’язання задачі зводиться до
розв’язання послідовності задач математичного програмування. Використовуючи jump-
алгоритм, виконується плавний перехід від однієї точки локального мінімуму до іншої, в
якій зменшується значення цільової функції. В подальшому результати розв’язання по-
кращуються завдяки зменшенню розмірності простору розв’язків за рахунок фіксації
радіусів гіперкуль та перестановки пар гіперкуль. Наведені декілька чисельних
прикладів.
Key words: hypersphere, packing, mathematical modeling, jump algorithm
Introduction
Packing hard hyperspheres in two and three dimensions has application in studying proper-
ties of many materials, for example, simple fluids, colloids, glasses, and granular media [1]. In
higher dimensions hard hyperspheres are used to investigate properties such as geometrical frustra-
tion and the geometry of the crystalline state [2]. Packing hyperspheres may be used in the numeri-
cal evaluation of integrals, either on the surface of a sphere or in its interior [3]. The problems arise
in digital communications and storage, including compact disks, cell phones, and the Internet
[3, 4].
Many studies of randomly packed hyperspheres in higher dimensions are performed using
Monte Carlo Method for Molecular Dynamics simulations [2]. In order to reach higher packing
fractions a compression algorithm [5] or a particle scaling algorithm [6] is used.
Skoge et al [1] present a study of disordered jammed hard-sphere packings in four-, five-,
and six-dimensional Euclidean spaces. They use a collision-driven packing generation algorithm
and obtain the first estimates for the packing fractions of the maximally random jammed states.
ПРИКЛАДНАЯ МАТЕМАТИКА
ISSN 0131–2928. Пробл. машиностроения, 2014, Т. 17, № 2 49
Morse et al [7] investigate granocentric model for polydisperse sphere packings polydis-
perse sphere packing in high dimensions.
A method of packing equal hyperspheres into a given hypersphere, based on increasing
problem dimension is considered in [8]. In this paper, we adopt the jump algorithm (JA) developed
for unequal circle packing [9] to solve the problem of packing unequal hypersphere into the hyper-
sphere of minimal radius in space of dimension greater than 3. JA allows to transit from one local
minimum point to another one so that a hypersphere radius decreases.
The paper considers the following problem.
Let there be hyperspheres
( )
⎭
⎬
⎫
⎩
⎨
⎧
≤−−∈,= ∑
=
0)ˆ()(:R,..., 2
1
2
21 i
n
k
kii
n
ni rxxxxxS
where )...,,,( 21 niiii xxxv = is center coordinates, ir̂ is radius of Si, }{1,2,...,= NIi∈ , and a
hypersphere S:
( )
⎭
⎬
⎫
⎩
⎨
⎧
≤ρ−∈,=ρ ∑
=
0:R...,)( 2
1
2
21
n
k
k
n
n xxxxS
of radius ρ where ρ is variable.
A hypersphere Si translated by a vector vi is denoted by Si(vi). A vector
v = (v1, v2, …, vn) ∈ RnN defines a location of ,iS i ∈ I, in the Euclidean n-dimensional space Rn
We without loss of generality suppose that
NN rrrrr ˆˆ,ˆ...ˆˆ 121 <≤≤≤ . (1)
Problem. Find such a vector v ensuring a packing of hyperspheres Si(vi), Ii∈ , without
their mutual overlappings within the hypersphere S(ρ) that radius would be minimal ρ = ρ*.
1. A mathematical model and its characteristics
A mathematical model of the problem can be stated as
ρ* = minρ, s.t. Y = (v, ρ) ∈ W ⊂ Rτ, (2)
where τ = Nn + 1,
} 0,),( ,<<0 0,),(:R{= IivIjivvYW iijiij ∈≥ρΦ∈≥Φ∈ τ . (3)
Inequality 0)ˆˆ()(=),( 2
1
2 ≥+−−Φ ∑ = ji
n
k kjkijiij rrxxvv guarantees non-overlapping
hyperspheres Si and Sj and inequality 0)()ˆ(),(
1
22 ≥−−−ρ=ρΦ ∑ =
n
k kiiiii xxrv provides a
placement of Si(vi) within S(ρ).
The mathematical model (2)–(3) possesses the same characteristics as that of the
mathematical models considered in [9], i. e. local minima are reached at extreme points of W, the
matrix of the inequality system in (3) is strongly sparse, the number of inequalities specifying W is
η ≥ n(n – 1)/2 + n and the problem stated is NP-hard. Thus, a global minimum of the problem can
be in general reached theoretically only.
To tackle the problem (2)–(3) with advantage one needs to construct starting points
belonging to the feasible region W, to compute local minima and to carry out a directed non-
exhaustive search for local minima.
2. Generating starting points and searching for local minima
First of all, we suppose that radii ri of hyperspheres Si, i ∈ I are variables and form
a vector r = (r1, r2, …, rn) ∈ Rn [8]. In this case X = (v, r) ∈ Rτ + N – 1 is the vector of all variables.
Thus, the inequalities in system (3) take the form
.0,),,(,<<00,),,,( IirvIjirrvv iiijijiij ∈≥ρΦ∈≥Φ
ПРИКЛАДНАЯ МАТЕМАТИКА
ISSN 0131–2928. Пробл. машиностроения, 2014, Т. 17, № 2 50
Let 0>= 0ρρ and 0=ir , .Ii∈ We give #v in a random way so that )( 0ρ∈ Svi
# , .Ii∈
Then ,0)(= ## vX .
In order to construct a point Wv ∈ρ ),( 0 on the ground of the point ),( 0ρ#v we solve the
problem
i
N
i
rrr
1=
max=)(max=)( ∑ΨΨ
) , s.t. 1R),(= −+τ⊂∈ NDrvX , (4)
where
}. 0, 0,ˆ=)(
0,),,( ,<<0 0,),,,(,R{= 01
Iirrrr
rvIjirrvvXD
iiiii
iiijijiij
N
∈≥≥−ϕ
≥ρΦ∈≥Φ∈ −+τ
(5)
Whence, problem (4)–(5) ensures an increase of the hypersphere radii limited by their
initial values due to inequalities 0,)( ≥ϕ ii r Ii∈ .
It follows from the construction of #X that .DX ∈# So taking starting point #X we solve
problem (4)–(5) and obtain a local maximal point ),( rvX )))
= .
Note that in addition to the characteristics of problem (2)–(3), problem (4)–(5) possesses
the properties.
1. Inequalities 0,)( ≥ϕ ii r Ii∈ , in (5) imply that if
brrr i
i
N
i
i
N
=ˆ==)(
=1=1
∑∑Ψ
)) (6)
then rr ˆ=) and spheres ,iS ,Ii∈ are packed into )( 0ρS . This means that the point X
)
is a global
maximal point of problem (4)–(5).
2. If br <Ψ )() , and X
)
is a global maximal point of problem (4)–(5), then spheres ,iS
,Ii∈ can not be packed into )( 0ρS .
3. Value 0ρ can be always chosen such that the attainment of a global maximum is
guaranteed.
Let br =)()Ψ . The point ),( 0ρv) is not in the general case a local minimal point of problem
(2)–(3). So, taking starting point ),( 0ρv) , we calculate a local minimal point ),( 00 ρ
((v of problem
(2)–(3).
4. Transition from one local maximum to another one
Let ),( rvX )))
= be a local maximal point of the problem (4)–(5) and brr
N
i i <=)(
1∑ =
Ψ
)) , i.e.
at least one of the inequalities 0ˆ ≥− ii rr ) , ,Ii∈ is not active. We consider the auxiliary problem by
analogy with the 2D case [9]
n
i
i
N
rrV
1=
=)(max ∑ , s.t. ,R 1−+τ⊂∈ NMX (6)
}, 0,=)( 0,=)(
0,),,( ,<<0 0,),,,( ,R{=
min2max1
01
Iirrrrrr
rvIjirrvvXM
iiiiii
iiijijiij
N
∈≥+−ψ≥−ψ
≥ρΦ∈≥Φ∈ −+τ
(7)
where Ni rIirr ˆ} ,ˆ {max=max =∈ and 1min ˆ} ,ˆ {min= rIirr i =∈ . Note that the feasible region M
differs from D in (4)–(5) by the inequalities 0,)(1 ≥ψ ii r 0,)(2 ≥ψ ii r Ii∈ , instead of
0ˆ=)( ≥−ϕ iiii rrr , 0≥ir in (5). This means that radii 0,≥ir Ii∈ take any values from the
segment ],[ maxmin rr .
ПРИКЛАДНАЯ МАТЕМАТИКА
ISSN 0131–2928. Пробл. машиностроения, 2014, Т. 17, № 2 51
It is proved [9] that there exists the steepest ascent vector 0Z at the point X
)
for problem
(7)–(8) that )(>)( 0 XZX
))
Ψ+Ψ .
Let ),( 00 ρ
((v be a local minimal point of problem (2)–(3). We compute
0,1,....=,,
2
11ˆ=ˆ
2
1ˆ=
22
λ∈⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
⎟
⎠
⎞
⎜
⎝
⎛−⎟
⎠
⎞
⎜
⎝
⎛−
+λ+λ
λ Iirrrr iiii
and assume that sphere radii are equal to ,λir .Ii∈ Then problem (2)–(3) takes the form
ρρ min=( s.t. 1R),(= −+τλ ⊂∈ρ NWvY (9)
where
,} 0,),( ,<<0 0,),(:R{= 1 IivIjivvYW iijiij
N ∈≥ρΦ∈≥Φ∈ λλ−+τλ
2
1
2
)(=),( λλ
=
⎟
⎠
⎞
⎜
⎝
⎛λ +−−Φ ∑ ji
n
k
kjkijiij rrxxvv , ∑
=
λλ −−−ρρΦ
n
k
kiiiii xxrv
1
22 )()(=),( .
Since ,ˆ< ii rrλ ,Ii∈ then the point λ∈ρ Wv ),( 00 (( and ),( 00 ρ
((v is not a local minimal point
of problem (9). So, taking starting point ),( 00 ρ
((v , we solve problem (9) and define a local minimal
point ),( 00 ρ
((((v . Since br
n
i i <
1∑=
λ (see (6)), then, tackling problem (4)–(5) for starting point
DrvX ∈λ ),(= 00
(( , we compute a local maximal point ),( λλλ = rvX )))
. Two cases are possible:
br =)( λΨ
) and br <)( λΨ
) .
If br =)( λΨ
) , then ,ˆ= ii rr λ) ,Ii∈ and hence Wv ∈ρλ ),( 0
(() (3). Since the solution spaces of
problems (2)–(3) and (4)–(5) are different, then ),( 0ρλ
(()v in general is not a local minimal point of
problem (2)–(3). So, taking starting point ),( 0ρλ
(()v , we solve problem (2)–(3). As a result, a new
local minimum point ),( 11 ρ
((v is computed. In the case a local minimal point ),( 11 ρ
((((v of problem (9)
for the starting point ),( 11 ρ
((v is defined again and so on until br <)( λΨ
) becomes , i.e. we have
br
n
i
<∑ =
λ
1
) , ),(= λλλ rvX )))
and Wv ∉ρλλ ),( )) after λ iterations.
In this situation ( br <)( λΨ
) ) we compute the steepest ascent vector 0Z at the point λX
)
for problem (6)–(7), calculate points
},...,2,1,0{,)2/1( 0 ∞<=Γ∈γ+= γγ qZXX
)
(10)
define m, for which MX ∈γ . Then, making use of MrvX mmm ∈),(= we compose the ascending
sequence according to (1)
m
i
m
i
m
i n
rrr ≤≤≤ ....
21
. (11)
Since )ˆ(>)( rVrV m may occur, then, on the ground of sequence (11), we compute
},ˆ,{min=0
j
m
i
m
i rrr
jj
.Ij∈ This ensures the inequality )ˆ()( 0 rVrV m ≤ where
),...,,( 00
2
0
1
0 m
n
mmm rrrr = . Based on sequence (11), we construct two points: )
~~,~(
~~ mmm rvX = where
,=~ m
i
m
j j
vv 0~~ m
i
m
j j
rr = , Ij∈ , and a point )~,~(
~ mmm rvX = where ,=~ m
i
m
j j
vv m
i
m
j j
rr =~ , Ij∈ .
If )(>)
~~(>)ˆ( λrVrVrV m ) , then the new steepest ascent vector 0Z at the point mX
~
for
problem (7)–(8) is calculated. Taking mXX
~
=
)
, we build a new point 02)/(1= ZXX mm +
)
(see
ПРИКЛАДНАЯ МАТЕМАТИКА
ISSN 0131–2928. Пробл. машиностроения, 2014, Т. 17, № 2 52
(10)) and derive new points )
~~,~(
~~ mmm rvX = and )~,~(
~ mmm rvX = in accordance with sequence (11)
and so on. The iterative process is continued until either )ˆ(=)
~~( rVrV m or )ˆ(<)()
~~( rVrVrV m λ≤
)
occurs.
If )ˆ(=)
~~( rVrV m , i.e. i
m
i rr ˆ=
~~ , ,Ii∈ then taking starting point ),~( λμ
(m
iv , we tackle problem
(2)–(3) and calculate a new local minimal point ),( 00 ρ
((v . The process is repeated until
)ˆ(<)()
~~( rVrVrV m λ≤
) becomes and next, we go to Subsection 5.3.
Note that JA executes a smooth transition from one local maximum to another one of
problem (4)–(5).
5. Decrease of the problem dimension and rearrangement of hypersphere pairs
Reduction of the solution space dimension is realized by means of sequencial fixing initial
values of sphere radii without fixing their center coordinates in the same manner as in [9].
Rearrangements of pairs of spheres whose radii are slightly distinguished allow to improve
the objective value of problem (2)–(3). An algorithm executing such rearrangements is described in
[10].
In order to obtain a good approximation to a global minimum of problem (2)–(3) we repeat
the step-by-step procedure consisting of the construction of a starting point and the search for a
local minimum of problem (2)–(3) with JA ν times. As a result local minimum points ),*,*( ttv ρ
10}{1,2,...,= ≤ν∈Tt are computed.
Then we single out a local minimal point )*,*( 00 ρv corresponding to
},*{min=*0 Ttt ∈ρρ . The point )*,*( 00 ρv is taken as an approximation to a global minimum of
problem (2)–(3).
6. Numerical examples
We solve a number of instances for different number of hyperspheres in the Euclidean
spaces of dimensions from 4 to 13.
The Interior Point Optimizer (IPOPT) exploiting information on Jacobians and Hessians
[11], and the concept of ε -active inequalities [8,12] are used to solve non-linear programming
problems.
The algorithms were coded in Delphi and performed using an AMD Athlon 64 X2 6000+
(3.1Ghz) processor.
The average runtimes (hours) for the instances are presented in Table 1. Rows of the table
correspond to the space dimensions and columns correspond to the numbers of hyperspheres. In-
stances considered may be downloaded from the webpage: http://f-bit.ru/uploads/295485.zip.
Table 1. The averaged runtimes depending on the space dimension and the number of hyperspheres
Space dimension Number of hyperspheres
n N = 30 N = 40 N = 50 N = 60 N = 70
4 0.5 2 4 10 18
5 0.7 3 6 16 24
6 1 5 9 20 36
7 2 8 15 30 36
8 3.5 12 30 – –
9 6 18 39 – –
10 10 24 48 – –
11 14 30 – – –
12 18 37 – – –
13 24 48 – – –
ПРИКЛАДНАЯ МАТЕМАТИКА
ISSN 0131–2928. Пробл. машиностроения, 2014, Т. 17, № 2 53
Conclusion
Algorithm JA which expoits the assumption that radii of all hyperspheres are variable is
adopted for higher dimensional spaces. Smooth transitions between local maximal points proveding
a growth of the objective values. The algorithm is especially effective if neighbor initial radii of
hyperspheres are slightly distinguished.
A decrease of the problem dimension by means of sequential fixing sphere radius values
and rearrangements of hypersphere pairs allow to improve results.
Numerical results are presented.
Acknowledgement
I acknowledge the support of the Science and Technology Center in Ukraine and the
National Academy of Sciences of Ukraine, grant 5710.
References
1. Skoge, М. Packing hyperspheres in high-dimensional Euclidean spaces / M. Skoge [et al] // Physical Re-
view. – 2006. – Vol. E4. – 041127.
2. Agapie, S. C. Random packing of hyperspheres and Marsaglia's parking lot test // S. C. Agapie,
P. A. Whitlock. – Monte Carlo Methods and Applications. – 2010. – Vol. 16 (3-4). – P. 197–209.
3. Conway, J. H. Sphere Packings, Lattices, and Groups / J. H. Conway, N. J. A. Sloane. – New York:
Springer-Verlag, 2010. – 703 p.
4. Torquato, S. Exactly solvable disordered sphere-packing model in arbitrary-dimensional Euclidean spaces
/ S. Torquato // Physical Review. – 2006. – Vol. E73. – 031106.
5. Jodrey, W. S. Computer simulation of close random packing of equal spheres / W. S. Jodrey, E. M. Tory
// Physical Review. – 1985. – Vol. A32. – P. 2347–2351.
6. Fraser, D. P. Setting up Random Configurations / D. P. Fraser // Information Quarterly for Computer
Simulation of Condensed Phases. – 1985. – Vol. 19. – P. 53–59.
7. Morse, P. Polydisperse sphere packing in high dimensions, a search for an upper critical dimension /
P. Morse, M. Clusel, E. Corwin // Proc. APS March Meeting 2012, February 27–March 2, 2012, Boston,
Massachusetts. – 2012. – Vol. 57(1).
8. Stoyan, Yu. Packing congruent hyperspheres into a hypersphere / Yu. Stoyan, G. Yaskov // Journal of
Global Optimization. – 2012. – Vol. 52(4). – P. 855–868.
9. Stoyan, Yu. Packing unequal circles into a strip of minimal length with a jump algorithm / Yu. Stoyan,
G. Yaskov // Optimization Letters. – 2014. – Vol. 8(3). – P. 949–970.
10. Stoyan, Yu. A mathematical model and a solution method for the problem of placing various-sized circles
into a strip / Yu. Stoyan, G. Yaskov // European Journal of Operational Research. – 2004. – Vol. 156. –
P. 590–600.
11. Wächter, A. On the implementation of a primal-dual interior point filter line search algorithm for large-
scale nonlinear programming / A. Wächter, L. T. Biegler // Mathematical Programming. – 2006. –
Vol. 106(1). – P. 25–57.
12. Zoutendijk, G. Methods of feasible directions. A study in linear and non-linear programming /
G. Zoutendijk. – Amsterdam, London, New York, Princeton: Elsevier Publishing Company, 1960. –
126 p.
Поступила в редакцию
05.01.14
|
| id | nasplib_isofts_kiev_ua-123456789-80974 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0131-2928 |
| language | English |
| last_indexed | 2025-12-07T18:06:48Z |
| publishDate | 2014 |
| publisher | Інстиут проблем машинобудування ім. А.М. Підгорного НАН України |
| record_format | dspace |
| spelling | Yaskov, G.N. 2015-04-29T16:47:01Z 2015-04-29T16:47:01Z 2014 Packing non-equal hyperspheres into a hypersphere of minimal radius / G.N. Yaskov // Проблемы машиностроения. — 2014. — Т. 17, № 1. — С. 48-53. — Бібліогр.: 12 назв. — англ. 0131-2928 https://nasplib.isofts.kiev.ua/handle/123456789/80974 519.85 The problem of packing different hyperspheres into a hypersphere of minimal radius is considered. All hypersphere radii are supposed to be variable. Solving the problem is reduced to solving a sequence of mathematical programming problems. A special way of construction of starting pointsis suggested. A smooth transition from one local minimum point to another providing a decrease of the objective value is realized using the jump algorithm is fulfilled. Then, solution results are improved due to reduction of the solution space dimension by step-by-step fixing radii of hyperspheres and rearrangements of hypersphere pairs. Non-linear mathematical programming problems are solved with the IPOPT (Interior Point Optimizer) solver and the concept of active inequalities. A number of numerical results are given. Рассматривается задача упаковки разных гипершаров в гипершаре минимального радиуса. Считается, что радиусы всех гипершаров являются переменными. Решение задачи сводится к решению последовательности задач математического программирования. Используя jump-алгоритм, выполняется плавный переход от одной точки локального минимума к другой, в которой уменьшается значение целевой функции. В дальнейшем результаты решения улучшаются благодаря уменьшению размерности пространства решений за счет фиксации радиусов гипершаров и перестановки пар гипершаров. Приведено несколько численных примеров. Розглядається задача упаковки різних гіперкуль у гіперкулю мінімального радіуса. Вважається, що радіуси всіх гіперкуль є змінними. Розв’язання задачі зводиться до розв’язання послідовності задач математичного програмування. Використовуючи jumpалгоритм, виконується плавний перехід від однієї точки локального мінімуму до іншої, в якій зменшується значення цільової функції. В подальшому результати розв’язання покращуються завдяки зменшенню розмірності простору розв’язків за рахунок фіксації радіусів гіперкуль та перестановки пар гіперкуль. Наведені декілька чисельних прикладів. I acknowledge the support of the Science and Technology Center in Ukraine and the National Academy of Sciences of Ukraine, grant 5710. en Інстиут проблем машинобудування ім. А.М. Підгорного НАН України Проблемы машиностроения Прикладная математика Packing non-equal hyperspheres into a hypersphere of minimal radius Article published earlier |
| spellingShingle | Packing non-equal hyperspheres into a hypersphere of minimal radius Yaskov, G.N. Прикладная математика |
| title | Packing non-equal hyperspheres into a hypersphere of minimal radius |
| title_full | Packing non-equal hyperspheres into a hypersphere of minimal radius |
| title_fullStr | Packing non-equal hyperspheres into a hypersphere of minimal radius |
| title_full_unstemmed | Packing non-equal hyperspheres into a hypersphere of minimal radius |
| title_short | Packing non-equal hyperspheres into a hypersphere of minimal radius |
| title_sort | packing non-equal hyperspheres into a hypersphere of minimal radius |
| topic | Прикладная математика |
| topic_facet | Прикладная математика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/80974 |
| work_keys_str_mv | AT yaskovgn packingnonequalhyperspheresintoahypersphereofminimalradius |