An optimization problem of packing identical circles into a multiply connected region. Part 2. A solution method and its realisation

The paper deals with an optimization problem of packing identical circles into a multiply connected region whose frontier consists of arcs of circles and line segments. On the ground of the characteristics of a mathematical model a solution method is offered. The method consists of a combination of...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2011
Hauptverfasser:	Stoyan, Yu.G., Chugay, A.M.
Format:	Artikel
Sprache:	English
Veröffentlicht:	Інстиут проблем машинобудування ім. А.М. Підгорного НАН України 2011
Schriftenreihe:	Проблемы машиностроения
Schlagworte:	Прикладная математика
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/103878
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:	An optimization problem of packing identical circles into a multiply connected region. Part 2. A solution method and its realisation / Yu.G. Stoyan, A.M. Chugay // Проблемы машиностроения. — 2011. — Т. 14, № 2. — С. 52-60. — англ.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-103878
record_format	dspace
spelling	irk-123456789-1038782016-06-27T03:02:09Z An optimization problem of packing identical circles into a multiply connected region. Part 2. A solution method and its realisation Stoyan, Yu.G. Chugay, A.M. Прикладная математика The paper deals with an optimization problem of packing identical circles into a multiply connected region whose frontier consists of arcs of circles and line segments. On the ground of the characteristics of a mathematical model a solution method is offered. The method consists of a combination of a method of generating starting points, a modification of the feasible directions method to search for local maxima and a modification of the decremental neighbourhood search method to find an approximation to a global maximum. Numerical examples are given. Рассматривается оптимизационная задача упаковки одинаковых кругов в многосвязную область, граница которой состоит из отрезков дуг окружностей и отрезков прямых. На основании свойств математической модели предлагается метод решения задачи. Метод предполагает комбинацию метода получения начальных точек, модифицированного метода возможных направлений для поиска локальных максимумов и модифицированного метода сужающихся окрестностей для поиска приближения к глобальному максимуму. Приводятся численные примеры. Розглядається оптимізаційна задача пакування однакових кіл у багатозв’язну область, границя якої складається з відрізків дуг околів та відрізків прямих. На підставі властивостей математичної моделі пропонується метод розв'язання задачі. Метод передбачає комбінацію методу одержання початкових точок, модифікованого методу можливих напрямів для пошуку локальних максимумів та модифікованого методу звужувальних околів для пошуку наближення до глобального максимуму. Наводяться числові приклади. 2011 Article An optimization problem of packing identical circles into a multiply connected region. Part 2. A solution method and its realisation / Yu.G. Stoyan, A.M. Chugay // Проблемы машиностроения. — 2011. — Т. 14, № 2. — С. 52-60. — англ. 0131-2928 http://dspace.nbuv.gov.ua/handle/123456789/103878 519.85 en Проблемы машиностроения Інстиут проблем машинобудування ім. А.М. Підгорного НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	English
topic	Прикладная математика Прикладная математика
spellingShingle	Прикладная математика Прикладная математика Stoyan, Yu.G. Chugay, A.M. An optimization problem of packing identical circles into a multiply connected region. Part 2. A solution method and its realisation Проблемы машиностроения
description	The paper deals with an optimization problem of packing identical circles into a multiply connected region whose frontier consists of arcs of circles and line segments. On the ground of the characteristics of a mathematical model a solution method is offered. The method consists of a combination of a method of generating starting points, a modification of the feasible directions method to search for local maxima and a modification of the decremental neighbourhood search method to find an approximation to a global maximum. Numerical examples are given.
format	Article
author	Stoyan, Yu.G. Chugay, A.M.
author_facet	Stoyan, Yu.G. Chugay, A.M.
author_sort	Stoyan, Yu.G.
title	An optimization problem of packing identical circles into a multiply connected region. Part 2. A solution method and its realisation
title_short	An optimization problem of packing identical circles into a multiply connected region. Part 2. A solution method and its realisation
title_full	An optimization problem of packing identical circles into a multiply connected region. Part 2. A solution method and its realisation
title_fullStr	An optimization problem of packing identical circles into a multiply connected region. Part 2. A solution method and its realisation
title_full_unstemmed	An optimization problem of packing identical circles into a multiply connected region. Part 2. A solution method and its realisation
title_sort	optimization problem of packing identical circles into a multiply connected region. part 2. a solution method and its realisation
publisher	Інстиут проблем машинобудування ім. А.М. Підгорного НАН України
publishDate	2011
topic_facet	Прикладная математика
url	http://dspace.nbuv.gov.ua/handle/123456789/103878
citation_txt	An optimization problem of packing identical circles into a multiply connected region. Part 2. A solution method and its realisation / Yu.G. Stoyan, A.M. Chugay // Проблемы машиностроения. — 2011. — Т. 14, № 2. — С. 52-60. — англ.
series	Проблемы машиностроения
work_keys_str_mv	AT stoyanyug anoptimizationproblemofpackingidenticalcirclesintoamultiplyconnectedregionpart2asolutionmethodanditsrealisation AT chugayam anoptimizationproblemofpackingidenticalcirclesintoamultiplyconnectedregionpart2asolutionmethodanditsrealisation AT stoyanyug optimizationproblemofpackingidenticalcirclesintoamultiplyconnectedregionpart2asolutionmethodanditsrealisation AT chugayam optimizationproblemofpackingidenticalcirclesintoamultiplyconnectedregionpart2asolutionmethodanditsrealisation
first_indexed	2025-07-07T14:30:42Z
last_indexed	2025-07-07T14:30:42Z
_version_	1836998871971004416
fulltext	ПРИКЛАДНАЯ МАТЕМАТИКА ISSN 0131–2928. Пробл. машиностроения, 2011, Т. 14, № 2 52 UDC 519.85 Yu. G. Stoyan, Corr. member of NAS of Ukraine A. M. Chugay, PhD Institute for Mechanical Engineering Problems of the National Academy of Sciences of Ukraine (Kharkov, E-mail: stoyan@ipmach.kharkov.ua; chugay@ipmach.kharkov.ua) AN OPTIMIZATION PROBLEM OF PACKING IDENTICAL CIRCLES INTO A MULTIPLY CONNECTED REGION Part 2. A solution method and its realisation Рассматривается оптимизационная задача упаковки одинаковых кругов в многосвязную область, граница которой состоит из отрезков дуг окружностей и отрезков прямых. На основании свойств математической модели предлагается метод решения задачи. Метод предполагает комбинацию метода получения начальных точек, модифициро- ванного метода возможных направлений для поиска локальных максимумов и модифи- цированного метода сужающихся окрестностей для поиска приближения к глобально- му максимуму. Приводятся численные примеры. Розглядається оптимізаційна задача пакування однакових кіл у багатозв’язну область, границя якої складається з відрізків дуг околів та відрізків прямих. На підставі власти- востей математичної моделі пропонується метод розв'язання задачі. Метод передба- чає комбінацію методу одержання початкових точок, модифікованого методу можли- вих напрямів для пошуку локальних максимумів та модифікованого методу звужуваль- них околів для пошуку наближення до глобального максимуму. Наводяться числові при- клади. The paper deals with an optimization problem of packing identical circles into a multiply con- nected region whose frontier consists of arcs of circles and line segments. On the ground of the characteristics of a mathematical model a solution method is offered. The method consists of a combination of a method of generating starting points, a modification of the feasible directions method to search for local maxima and a modification of the decremental neighbourhood search method to find an approximation to a global maximum. Numerical examples are given. The statement of the considered problem and its mathematical model is presented in [1]. In this paper on the basis of characteristics of the mathematical model a solution method is offered. In what follows, problems given in [1] we denote as follows: a) the problem (1)-(2) – the problem A; the problem (3) – the problem B. General solution strategy According to the mathematical model a solving of the problem is reduced to a performance of some stages. At each of ones the problem B of packing n circles of the given radius r is solved. Firstly, a preliminary estimation of the number of circles to be packed is realized. By virtue of item 9 of mathematical characteristics given in [1] we search for an approximation to a global maximum of the problem B using the decremental neighbourhood search method [2, 3] (in what follows DNS). Random vectors which define starting locations of circles into the region are generated by the DNS. On the basis of the vectors starting points from the feasible region are constructed and local maxima of the problem B are computed. At each stage of the DNS the best local maximum is stored. If process obtaining the best local maximum is decelerated then solution process converges quickly to some local maximum. This local maximum is taken as an approximation to a global one. ПРИКЛАДНАЯ МАТЕМАТИКА ISSN 0131–2928. Пробл. машиностроения, 2011, Т. 14, № 2 53 Starting from characteristics above for successfully solving the problem A it needs to fulfil the following steps. Step 1. Define n0 so that a containment of n0 circles into P is guaranteed. Then take n = n0 + 1 and pass to the next step. Step 2. Give ri = r/2, and generate Punl i ∈ , nIi∈ , ),...,2,1( λ=∈ λIl , by a random way utilizing a modification of the DNS so that n n nl n nlnlnl WrrruuuX ∈= ) 2 1,..., 2 1, 2 1,,...,,( 21 4434421 . Step 3. Take the points Xnl as starting points and search for local maxima Xnl, λ∈ Jl , of the problem B. Step 4. Select the best local maximum { }λ∗∗ ∈= J lXFX nl n n ),(maxarg ~ . Step 5. If nrXF n n =∗) ~ ( then a global maximum of the problem B is achieved. In this case take n = n + 1 and solve the problem B again, i.e. return to the step 2. Step 6. If nrXF n n <∗) ~ ( and a stopping criterion of the DNS is not fulfilled then return to the step 2. Step 7. If the stopping criterion of the DNS is fulfilled and nrXF n n <∗) ~ ( , then take )1(~ −∗ = nuu as an approximation to a global maximum of the problem A and the number of circles packed is n – 1. Construction of starting point For obtaining of starting points the rectangular lattice is constructed. The length of lattice cell sides is accepted equal to r/2. This lattice arbitrarily is placed with respect to the region. Cells which completely belong to the region are selected. The number k of the cells is strictly more than n. Centre coordinates of the cells form a vector p of length 2k. These vectors are generated by the DNS. The first 2n coordinates of vectors of kind p define the centers of circles and form vector un. Then vectors vn and un define starting points Xn = (un, vn). A starting point is constructed according to the following algorithm (fig.1). Step 1. Cover the region P by a lattice whose basic parallelogram (cell) is a square ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ ≤≤−≤≤−∈= ryrrxrRyxS 2 1 2 1, 2 1 2 1:),( 2 . Step 2. Define the number k > n of squares such that a) b) Fig. 1. A starting point construction: а) – lattice construction; b) – placing of circles of radius r/2 in lattice cells ПРИКЛАДНАЯ МАТЕМАТИКА ISSN 0131–2928. Пробл. машиностроения, 2011, Т. 14, № 2 54 PrbyrbraxraRyxS iiiii ⊂ ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ +≤≤−+≤≤−∈= 2 1 2 1, 2 1 2 1:),( 2 , where (ai, bi) are centre coordinates of Si, },...,2,1{ kIi k =∈ (fig. 1, a). Step 3. Give randomly a vector k iiii i Rppppp kn 2),...,,...,,( 21 ∈= , where ),( jjj iii bap = . It is evident that the number of the vectors pi is equal k!, i. e. the vectors form a permuta- tion set kR2⊂Π without repetitions. Step 4. Give )2/,...,2/,2/( 44 344 21 n ni rrrv = and form a vector nni n ninini Ruuuu 2 21 ),...,,( ∈= so that ),( jjj iii ni j bapu == , nIj∈ , i. e. uni is obtained as a result of equating sequentially components of uni to the first n components of ),...,,...,,( 21 kn i n iii i ppppp 4434421 = . Hence, the number of uni is equal to )!(! ! nkn k − . Thus, taken ),( jj ii ba as centre coordinates of Cj we obtain a placement of Cj of radius r/2, nIj∈ , into P without overlapping (fig. 1, b). Points of kind nninini RvuX 3),( ∈= are taken as starting points to compute local maxima of the problem B. To the permutation set kR2⊂Π there corresponds a set nR3⊂Τ of starting points and, hence, a set nRL 3⊂ of local maxima of the problem B. Thus, a non-exhaustive search of local maxima of set L can be reduced to a non-exhaustive search of points of kR2⊂Π . Local optimization By virtue of items 6–8 of characteristics of the problem B given in [1] a feasible region can be presented as a finite union of subregions which are described by systems of nonlinear inequali- ties. It allows to reduce a search of a local maximum of the problem B to a computation of se- quence of local maxima on the subregions. To this end we single out one of subregions which con- tains a starting point. On this subregion searching for a local maximum is carried out. A local maximum obtained can belongs to several subregions. If there exist a subregion for which the point is not a local maximum then the point is taken as a starting point for searching for a new local maximum on the subregion. If such subregion is absent then the point is a local maximum of the problem B. A search of a local maximum of the problem B can be reduced to solving the following se- quence of nonlinear programming problems (NLP) )(max)( n n nj n XFXF =∗ , s. t. 0,...,2,1, η<<=∈ mjWX jnt n , (1) }. ,0, ,0 , ,, ,0),,,(, ,0),(:{ 3 nini njijiijnii s i nn nt IirIirr jiIjirruuIiruRXW jj t j ∈≥∈≥− <∈≥Φ∈≥Γ∈= (2) To solve the NLP (1)–(2) the modification of the Zoutendijk method of feasible directions [4] together with the concept of ε-active inequalities [2, 5] are used. The modification realizes the usual iterative process υ=+=+ ,...,2,1 ,)1( ktZXX knkkn , where nk RZ 3∈ is a solution of the following linear programming problem kαmax , s.t. kkk GZ ∈α ),( , (3) ПРИКЛАДНАЯ МАТЕМАТИКА ISSN 0131–2928. Пробл. машиностроения, 2011, Т. 14, № 2 55 ( ) ( ){ },3,...,2,1,11),(,...,2,1 ,),(,),(:),( 13 nizj wZXZXFRZG k ikk k knk k kknk n nkkk jj =≤≤−ες= ≥Ψ∇α≥∇∈α= + (4) ( )knk n ZXF ),(∇ is the scalar product of the gradient of )( n n XF and the vector Zk, ( )knk k ZX j ),(Ψ∇ is the scalar product of the gradient of )( nX jk Ψ that is the left side of an ε-active inequality of a system of kind (4) (given in [1]) and Zk, k k j w α= if )( nkX jk Ψ is a concave function and 0= jkw if otherwise. The problem (3)-(4) is solved by the interior point method [6]. A scheme of local optimization is presented in fig. 2. A transition from one problem of form (1)–(2) to another is carried out as follows. Let n nl WX ∈ be a starting point. We single out an inequality system of kind (4) (given in [1]) which specifies a subregion nni WW ⊂ 1 such that 1ni nl WX ∈ . Taken Xnl as a starting point we solve the problem )(max)( 1 n n n n XFXF =∗ , s.t. 1ni n WX ∈ . The point ∗1nX can be a local maximum with respect to either Wn (fig. 2, a) or 1niW (fig. 2, b). In order to define whether ∗1nX is a local maximum with respect to Wn (i. e. a local maxi- mum of the problem B) we single out ε-active inequalities at the point ∗1nX from the system (2) (given in [1]) and solve the following linear programming problem αmax , s. t. GZ ∈α ),( , ( ) ( ){ }.3,...,2,1,11),(,...,2,1 ,),(,),(:),( 1113 nizj wZXZXFRZG j n j n n n =≤≤−ες= ≥Ψ∇α≥∇∈α= + If 0≤α , then ∗1nX is a local maximum of the problem B. If 0>α , then ∗1nX is not a lo- cal maximum of the problem B (fig. 2, b) and it enables to compute a point n nn WtZXX ∈+= )( 11 at which )()( 11 n n n n XFXF <∗ . After that we form a new inequality system of kind (4) (given in [1]) that specifies a new subregion nni WW ⊂ 2 such that 2 1 ni n WX ∈ . Taken the point 1nX as a starting point we solve the following NLP: a) b) Fig. 2. A scheme of local optimization: а) – ∗1nX is a local maximum with respect to Wn; b) – ∗1nX is a local maximum with respect to 1niW ПРИКЛАДНАЯ МАТЕМАТИКА ISSN 0131–2928. Пробл. машиностроения, 2011, Т. 14, № 2 56 )(max)( 2 n n n n XFXF =∗ , s.t. 2ni n WX ∈ . The process is continued until a local maximum of the problem B is reached. In this case * nmnl XX = (fig.2). Global optimization Let us assume that each starting point is a random event. This means that the local maxi- mum corresponding to the starting point is a random event as well. Numerical experiments show that random sample histograms of objective function values at local maxima corresponding to ran- dom samples of starting points are close to the normal distribution. This assumption enables to use the three sigma rule when looking for an approximation to the global maximum of the problem B. The probabilistic properties allow using the DNS to search for an approximation to a global maxi- mum. This probabilistic method is more effective than the Monte-Carlo method [3]. The basic idea of the DNS can be presented by the following simplified scheme. Firstly, a random sample from the set kR2⊂Π is realized and an appropriate set of local maxima is com- puted. Then a starting point, at which the value of the objective function is greatest, is singled out. The point is taken as a centre of a neighbourhood of radius β (diameter of П), and a random sample from the neighbourhood is performed. After that we compute an appropriate set of local maxima. A starting point corresponding to a local maximum at which the objective function reaches the great- est value is selected. If the value is less than the previous one then the radius decreases and a new random sample from the neighbourhood is realized. If the value is strictly greater than the previous one then a starting point corresponding to the value is taken as a centre of a new neighbourhood of the previous radius and a random sample from the neighbourhood is performed. The computational process is continued until the neighbourhood radius becomes less than given one. A local maxi- mum at which the objective reaches a maximal value is taken as an approximation to a global maximum. A modification of the DNS consists of the following stages. I. Initialization stage of the DNS On this stage we search for promising centres of neighbourhoods for the next stage (a re- current stage of the DNS) as follows. Firstly, a random sample of vectors from the set Π is generated. On the ground of the vec- tors starting points are formed and appropriate local maxima are computed. The vectors to which correspond ω the best local maxima are taken as centres of neighbourhoods. In order to choose promising vectors from the set Π for the subsequent iterative process random samples are gener- ated in the neighbourhoods. An arithmetic average and a mean-square distance of the samples are calculated for each neighbourhood. Step 1. Realize a random sample Π⊂Π0 consisting of λ points, construct a set { } Τ⊂λ=∈=Τ λ ),...,2,1(,0 JjX nj of starting points and form an appropriate set { } LJjXL nj ⊂∈= λ ∗,0 of local maxima. Thus, to each 0Π∈jp there corresponds a local maxi- mum 0 * LX nj ∈ . Step 2. Choose points 0 * LX lnj ∈ , },...,2,1{ ω=∈ ωIl so that { }},{\:)(max)(...)()( * 0 ***** 21 ω∈∈≥>>> ω IlXLXXFXFXFXF lnjnn n nj n nj n nj n . Hence, to each local maximum ∗lnjX there corresponds the point 0Π∈ljp , ω∈ Il . Take the points 0Π∈ljp as centres of neighbourhoods ,00 Π⊂lN ω∈ Il , of radius β<ρ0 . Derive random samples ,00 ll NS ⊂ ω∈ Il , consisting of λ points. The value β=ρ 25,00 allows to estimate "behaviour" of )( n n XF at local maxima close to ∗lnjX , ω∈ Il . Step 3. Form sets Τ⊂Τ l0 and LL l ⊂0 corresponding ,00 ll NS ⊂ ω∈ Il . ПРИКЛАДНАЯ МАТЕМАТИКА ISSN 0131–2928. Пробл. машиностроения, 2011, Т. 14, № 2 57 Step 4. Compute an arithmetic average lm0 and a mean-square distance l0σ , ω∈ Il , of values of )( n n XF for each lL0 . Step 5. Determine the point 0~p , corresponding to the local maximum ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ ∈= ω = ∗∗∗ U 1 0 0 s.t. ),(maxarg ~ l l nn n n LXXFX . II. Recurrent stage of the DNS On the basis of the statistical characteristics of random samples of the previous stage new promising centers are found. The choice of the centers is carried out on the ground of assumption about the normal distribution law of objective function values at local maxima. It allows to use the three sigma rule. If after performance of a given number of iterations of the DNS values of objec- tive function at local maxima are not improved then radii of the neighbourhoods fast decreases. The iterative process begins from k = 1. Let the (k–1)-th iteration have been fulfilled. As a result of the iteration a set L(k–1)i is formed, m(k–1)i, ilk )( −σ , i = 1, 2, 3, are computed and a point 1~ −kp corresponding to the local maxi- mum ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ ∈= = − ∗∗∗− U 3 1 )1( )1( s.t. ),(maxarg ~ i ik nn n kn LXXFX , is obtained. Step 1. Single out centres kic of neighbourhoods Nki, i = 1, 2, 3, the following way: − ⎪⎩ ⎪ ⎨ ⎧ ≤ > = −−− −−− ), ~ () ~ ( if ~ ), ~ () ~ ( if ~ )2()1(2 )2()1(1 1 kn n kn n k kn n kn n k k XFXFp XFXFpc if k = 1, then 01 ~pck = ; − ⎪ ⎩ ⎪ ⎨ ⎧ ∈= =∈= ∈= = − −−− − − −−− − −−− , ~ and ~ if ,~or , ~ and ~either if , ~ and ~ if 3)1( )1(113)1( 21 2)2( )1(112)1( 1)1( )1(111)1( 2 k knkkk kk k knkkk k knkkk k LXpcc pcLXpcc LXpcc c if k = 1, then ljk pc =2 , where ljp is a centre of N0l at which 0~p is obtained; − ikk cc )1(3 −= , where ikc )1( − is the centre of ikN )1( − , at which }3,2,1,max{ )1()1( =θσ+ −− im ikik , 30 ≤θ< (if k = 1, then i = 1, 2, …, ω) is obtained. Step 2. Define radii kiρ of the neighbourhoods kiN , i = 1, 2, 3, as follows: ⎪⎩ ⎪ ⎨ ⎧ >θσ+ρ≤ρ μ ≤θσ+μρ =ρ −−−− −−−− , if 1 , if 1)1()1()1( * 1)1()1()1( kikikkik kikikik ki fm fm where ⎪⎩ ⎪ ⎨ ⎧ ≤ > = −−− −−− − ), ~ () ~ ( if ) ~ ( ), ~ () ~ ( if ) ~ ( )2()1()2( )2()1()1( * 1 kn n kn n kn n kn n kn n kn n k XFXFXF XFXFXFf ⎪⎩ ⎪ ⎨ ⎧ >β≤ρ μ ≤≤ρμ =ρ −− − −−−− − ), ~ () ~ ( if 1 ), ~ () ~ ( and ) ~ () ~ ( if )2()1( 1 1 )3()1()2()1( 11 kn n kn nk kn n kn n kn n kn nk k XFXF XFXFXFXF 8.0=μ is a factor which decreases or increases neighbourhood radii on each stage of the DNS, 6.01 =μ is a factor which guarantees rapid decreasing of neighbourhood radii in the case of absence of an improvement of ∗nkX ~ . If 1=k then β=ρ=ρ=ρ=ρ 321 kkkk . Step 3. Realize random samples kiki NS ⊂ , construct sets Τ⊂Τki and LLki ⊂ , compute ПРИКЛАДНАЯ МАТЕМАТИКА ISSN 0131–2928. Пробл. машиностроения, 2011, Т. 14, № 2 58 kim , kiσ , 3,2,1=i , and obtain a point kp~ . Step 4. Verify a stopping criterion. If the number of identical values of )( n n XF on each of Lki, i = 1, 2, 3 is greater than λ6.0 , then we finish the solution process. It should be noted that if the radius value in the DNS is close to the minimal admissible one ( r2 ), then the number of identical local maxima and local maxima, at which the objective has the same value, increases significantly. Step 5. Set 1+← kk . The input parameter λ must be chosen carefully since an excessive value of λ leads to a high computational burden. On the other hand, a too small λ results in a solution deterioration. It follows from statistical experiments that the value of λ has to be greater than or equal to 50 to pro- vide a reliability of kim and kiσ . In additional, a value of λ independs on the problem if n > 20. Computation experiments All the computational experiments were run on PC with the following main characteristics: Intel Core2Duo E4500 processor and 2 Gb of RAM. The linear programming problems (3)–(4) are calculated by means of HOPDM package (version 2.13) [6]. It should be noted that at present there is a number of modern solvers (for example, Meszaros solver [7], which efficiently solve linear programming problems by the interior point method. The solvers shall allow essentially reducing a runtime. When looking for approximations to global maxima of problems of kind B we take λ = 50, i.e. we compute 50 local maxima into each neighbourhood. Comparison of results Since, all known us researches do not solve packing problems of identical circles into an arbitrary multiply connected region then we compare computational results of packing circles into squares and rectangles with the benchmark results presented in [8]. For testing our approach we solve a number of numerical examples of circle packings in the unit square and rectangles presented in the site www.packomania.com. The computational re- sults obtained show that the approach produces the same high performance solutions when using at most 10–30 starting points. The solution results of the problems 1.1–5.9 in [8] are obtained by our approach as well. Table presents a performance of GENPACK [8] and our approach for first block of problems 1.1– 1.9 given in [8] for which we obtain two improvements. Figure 3 shows improvements of the results of packing problems presented in [8]. Performance of GENPACK and our method for problems given in [8] Results Problem Obtained in [10] obtained by means of GENPACK in [8] obtained by means of our method Name Box dimensional Circle radius Number of packed circles Number of packed circles Time, second Number of packed circles Time, second 1.1 160×80 6 90 91 734.05 92 5351 1.2 100×200 8 84 84 5791.83 84 4461 1.3 120×240 10 73 74 4065.91 74 3879 1.4 100×80 5 86 86 37108.39 86 9785 1.5 120×80 6 68 68 23.35 68 2311 1.6 120×100 6 87 87 2273.14 87 3456 1.7 80×80 5 68 68 12336.67 68 9874 1.8 100×100 6 70 71 225.57 71 2869 1.9 120×120 7 73 74 18.53 75 3985 ПРИКЛАДНАЯ МАТЕМАТИКА ISSN 0131–2928. Пробл. машиностроения, 2011, Т. 14, № 2 59 Figure 3,a illustrates the packing problem of circles of radius 7 in the square 120×120 (the problem 1.9 in [8]). The result in [8] is improved by one circle. Figure 3,b illustrates the packing problem of circles of radius 6 in the rectangle 160×80 (the problem 1.1 in [8]). The result in [8] is improved by one circle. Numerical examples Abilities of the mathematical model offered and solution methods are demonstrated by a choice of test instances. Let there be a set of identical circles and a multiply connected region P presented in fig. 1, a (given in [1]). The frontier of P0 (fig. 1, b) (given in [1]) is given by the sequence of the following line segments and arcs of circles: [ ]2211 ,,, yxyx , [ ]1113322 ,,,,,, ryxyxyx , [ ]4433 ,,, yxyx , [ ]5544 ,,, yxyx , [ ]6655 ,,, yxyx , [ ]2227766 ,,,,,, ryxyxyx , [ ]3338877 ,,,,,, ryxyxyx , [ ]9988 ,,, yxyx , [ ]101099 ,,, yxyx , [ ]111010 ,,, yxyx , where )60 ,10(),( 11 =yx , )19.75 ,6.17(),( 22 =yx , )41.77,15.28(),( 33 =yx , )70,30(),( 44 =yx , )80,60(),( 55 =yx , )70,88.62(),( 66 =yx , )84.39 ,26.80(),( 77 =yx , )95.30 ,34.62(),( 88 =yx , )35 ,45(),( 99 =yx , )25 ,28(),( 1010 =yx , )90 ,20(),( 11 =yx , )50 ,(63),( 22 =yx , )28 ,(75),( 33 =yx , 151 =r , 202 =r , 133 =r . The prohibited areas are represented as follows: U U ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = = 2 1 1 q lqll MCA , }3,2,1{=∈ σIl , (5) where }04)55()45(:),{( 2222 11 ≤−−+−∈= yxRyxC , }04)65()25(:),{( 2222 12 ≤−−+−∈= yxRyxC , }04)50()65(:),{( 2222 13 ≤−−+−∈= yxRyxC , M11, M12, M21, M22, M31 and M32 are the triangles given by their vertex coordinates: (45, 55), (50, 50) and (40, 50); (45, 55), (40, 60) and (50, 60); (25, 58), (30, 53) and (20, 52); (25, 58), (20, 63) and (30, 63); (65, 52), (70, 47) and (60, 47); (65, 52), (60, 57) and (70, 57) respectively. In the paper we present result of packing circle into given region P if r = 2.5 (fig. 4). Fig- ure 4, a illustrates the packing of 90 circles of radius 2.5 corresponding to an approximation to a global maximum of the problem A, and fig. 4, b illustrates the packing of circles corresponding to an approximation to a global maximum Xn* of the problem B when packing n = 91 circles. The ra- a) b) Fig. 3. Improved results: a) – the result of the packing problem of circles of radius 7 in the square 120×120; b) – the result of the packing problem of circles of radius 6 in the rectangle 160×80. ПРИКЛАДНАЯ МАТЕМАТИКА ISSN 0131–2928. Пробл. машиностроения, 2011, Т. 14, № 2 60 dius of the black-out circle in fig. 4, b is equal to 2.45, i. e. 91 circles of radius 2.5 can not be packed into P. Dependences of the runtime on the number of circles being packed are shown in fig. 5. The graphic depicted in fig. 5, a shows the runtime t1 which is expended to pack n circles. It should be noted that the runtime t1 strongly depends on the estimation of n0 of circles that can be packed into P. Figure 5, b shows the runtime t2 which is expended to solve the problem B and to prove that n + 1 circles can not be packed into P. It follows from the graphics shown in fig. 5, b that if n > 60, then the runtime essentially increases. In this case an application of the DNS demands a paralleling of the computational proc- ess. Conclusions This work presents a solution method to solve the problem of packing identical circles into a multiply connected region. The computational results demonstrate that the proposed approach produces high performance solutions. The comparison of obtained results with the world analogues shows that the approach is promising. We offer an efficient methodology to reduce the computational burden when searching for local maxima. It should be noted that the basic part of runtime is expended to prove that no more circle can be packed. The runtime depends strongly on a complexity of the placement region shape (i.e. on the number of prohibited areas and the primary objects of type Qj2 and Qj4 [1]) that form the region P). a) b) Fig. 4. Results of packings if r = 2.5: a) – the result of packing of 90 circles; b) – the result of packing of 91 circles a) b) Fig. 5. Dependences of the runtime on the number of circles: a) – the runtime t1; b) – the runtime t2

An optimization problem of packing identical circles into a multiply connected region. Part 2. A solution method and its realisation

Institution

Ähnliche Einträge