Bi‐objective Circular‐Hole Based Problem in Additive Manufacturing Topology Optimization

Abstract

   The paper deals with the circle packing problem which arises in topology optimization for additive manufacturing. The problem consists in packing a number of circles of radii within a particular range imposed by technical limitations, the packing factor being maximized. A biobjective formulation for the problem compromising the packing factor and the maximum mechanical stress of parts is suggested. The -constraint method is applied to search for a trade-off solution of the problem. A new packing approach based on a modified Apollonian circle packing and nonlinear optimization is developed. Numerical examples and graphical illustration of results are given.

Keywords

•  1  Additive manufacturing
• topology optimization
• mechanical stress
• bi-objective optimization
• -constraint method
• packing
• circle
• polygon
• Apollonian circle packing
• nonlinear optimization

1. Introduction 

One of the most important topics of modern mechanical engineering is reducing weight while maintaining specific characteristics of structures designed. Such problems with conflicting criteria are related to decision making in a formidable manufacturing process. A key objective of the problems is finding optimal geometric shape and topology of the designed product ensuring minimum weight at specified strength. To this end, topology optimization methods [1] are used to find the best design parameters satisfying the technological and strength constraints and thus providing the objective function extremum. When optimizing topology of a structure, the stress level in a particular part of the structure can be used as an indicator of ineffective material usage. Ideally, the stress level in the structure should be uniform, close to the limiting, but safe value [2].

Applying topology optimization methods in mechanical engineering is a newish development in the design procedure. The methods received the greatest impetus in their development when it became possible to use additive technologies in the manufacturing process [3] instead of classical subtractive methods. Additive technologies enable to expand the range of designs for the same product.

In the last two decades, topology optimization became an active field for scientific research. This led to the use of a multidisciplinary approach in the search for solutions to the problems, which use the methods of solid mechanics, thermodynamics, biology simultaneously [4].

Paper [2] reviews modern topology optimization methods.

Currently, the following main methods of topology optimization can be distinguished: SIMP (solid isotropic material with penalization), ESO (evolutionary structural optimization), Level-Set (level setting method) and their various combinations. One of the most effective applications of these methods is in optimizing the topology of continuous structures, i.e. finding the best placement location and geometry for holes (cavities) within the modeling area.

Circle packing problems (CPP) have a wide range of industrial and engineering applications, for example, facility layout design, cutting stock problems in the glass, metal, paper, textile and wood industries etc.

As a rule, practical optimization problems have several conflicting objectives. Such problems are called multi-objective. Optimization methods for multi-objective optimization problems and its applications are reviewed in [5, 6].

In this paper we first propose a bi-objective formulation for circular-hole based topology optimization which takes into account both the packing factor and the maximum mechanical stress of parts. A new approach for packing circles based on a modified finite Apollonian circle packing (ACP) and optimized homothetic transformations of circles is suggested. Both techniques allow to advantageously arrange circles within polygonal parts minimizing material expenses. The -constraint method [7] is applied to find out a trade-off circular arrangement.

In accordance with ACP (see, for example [8]), starting from three mutually tangent circles, next circles are added to be tangent to the three circles forming four mutually tangent circles (or tangent to the frontier of the container). We modify ACP for taking into account the upper bound of circle radii and the minimal allowed distance between the circles. Some circles are allowed to be moved within the container and located to positions which give a possibility to enlarge radii of next circles being packed.

The main contributions of the paper are as follows:  A bi-objective model of non-standard circular packing problem considering both the maximum packing factor and mechanical stress of parts for a topology optimization  A new approach for constructing starting points based on ACP  New benchmark instances for packing circles with variable radii.

2. Related papers 

The number of papers concerning CPP goes up and up each year. Paper [9] reviews selected works dealing with packing methods and applications for CPP. We make mention of some recent papers [10, 11, 12]. A powerful tool of solving CPP with unequal circles is treating additional variable metric characteristics of circles and/or containers (see, for example, [11, 12, 13, 14]). The best results for a set of benchmark CPP instances are continuously updated in the well known website [15].

Paper [16] proposes a circular packing model and a fast heuristic algorithm to optimize part geometries subject to the DMLS constraints. A feature of the model is that radii of circles are preassigned.

In [9] a model and a numerical solution approach to packing egg-shaped objects with arbitrary size and orientation into optimized convex containers is presented. The area of the container is minimized The solution strategy is based on the analysis of embedded Lagrange multipliers and nonlinear optimization. Within the universal model, circles and ellipses are considered to be special cases of egg.

The ε-constraint method introduced in [7] is often used for solving multi-objective optimization problems. The method optimizes only one objective while the other objectives are imposed by limits. In [5] the Pareto optimality of solutions obtained by the ε-constraint method is investigated.

A bi-objective function for packing in a spacecraft module is proposed in [17]. The dimensions of the module are minimized and other criteria such as desired adjacency between items and packing costs are also taken into account. Paper [18] uses a genetic algorithm for bi-objective topology optimization: minimization mass and maximization effective flexural and torsional rigidities. Methods for analysis of stress state in parts with different geometries are discussed in [16, 19]. Effective methods of nonsmooth optimization for allocation problems are considered in [20].

Containment the circle Сq (vq , rq ) into the domain P

Сq (vq , rq )  P  int Cq (vq , rq ) I P*   ,  q  IN ,  where P*  Ў2 \ int P

 Minimal allowed distance between the circles Сq (vq , rq ) and Сg (vg , rg ) (a, b) is Euclidean distance between points a, b  R 2 , dist(Сq (vq , rq ), Сg (vg , rg ))  ,   (q, g )  l ,  l  I p ,   0   dist(Cq (vq , rq ),Cg (vg , rg )) 

min aCq (vq ,rq ), bCg (vg ,rg )

(a, b) ,  l  {(q, g ) : Сq (vq , rq )  Pl , Сg (vg , rg )  Pl , q  g} . 

3. Problem statement 

Let P0 be a polygon given by its vertices v0i  (x0i , y0i ), i  I0  {1, 2,..., s0}. We define a disconnected polygonal domain of the form

P  U Pl ,  Pl  P0 ,  l  I p ,  Pl I Pj   , l  j  I p  {1, 2,..., nP} ,  lI p

Pl ={(x, y)  R2 : ml (x, y)  0, m  1, 2,..., Ml }   are convex polygons given by vertices vli  (xli , yli ), i  Il  {1, 2,..., sl }; ml (x, y)  aml x+bml y+cml  0 , l  I p , are normal equations of the edges of Pl , l  I p . Let us also define a collection of circles

Cq  Cq (vq , rq )  {( x, y)  R 2 : ( x  xq )2  ( y  yq )2  rq2}   of variable radii rq and translation vectors vq  (xq , yq ) for q  I N  {1, 2,..., N} , 0  r   rq  r   r  , r  , r  are given lower and upper allowed values for rq , r  is the maximal possible radius of the circle which can be inscribed into Pl , l  I p .

Conditions of packing the circles Сq (vq , rq ) , q  IN , into the domain P are determined as where follows.

 where           ( 1 )  ( 2 )  ( 4 ) 

A problem of bi-objective circle topology optimization into the polygonal domain is formulated as follows.

Pack circles Сq (vq , rq ) , q  IN , into the domain P providing containment l circles into the polygon Pl , l  I p , lI p l  n  N and the distance constraints ( 2 ) and maximizing the packing factor while minimizing the maximum mechanical stress.

The packing conditions ( 1 ), ( 2 ) are analytically described using the phi-function technique [21], which makes it possible presenting a mathematical model as the following bi-objective problem: max{(), ()}   ( 3 )  subject to  W ,    where   (v, r) is a vector of variables; v  (v1, v2 ,..., vn ) is a vector of variable packing parameters; r  (r1, r2 ,..., rn ) is a vector of variable radii of circles; function 2 ()    rq  

qIn is the total sum of the circle areas; () is an implicit function which defines the maximum mechanical stress depending on the vector v of center coordinates of circles and the vector r of radii of circles;

W = {  R3n: ) qg (vq , vg , rq , rg )    0, (q, g )  l , l  I p , q (vq , rq )  0, q  In ,   rq  rq  0, q  In ,  rq  rq  0, q  In}     is an adjusted phi-function of the circles Cq and Cg , (q, g )  l ; is a feasible region; ) qg (vq , vg , rq , rg )  ( xq  xg )2  ( yq  yg )2  (rq  rg  )2 ,   q (vq , rq )  max{ min lI p m1,2,...,Ml {ml (vq )  rq }}    is a phi-function of the circle Cq , q  In , and the set P*  R2 \ int P .

)

The inequality qg (vq , vg , rq , rg )  0 ensures the condition ( 2 ) for packing the circles Cq and Cg , (q, g )   , on the minimal allowed distance  and the inequality q (vq , rq )  0 l condition ( 1 ) for packing the circle Cq into the polygon P . provides the

We note that () and () are compromising objectives. Therefore, our aim is to find a tradeoff solution of the bi-objective problem ( 3 )-( 5 ).

4. Solution approach  4.1.

Solution strategy 

We use the multistart strategy [22] for solving the circular problem ( 3 )-( 5 ). ( 5 )      ( 6 )     

On the assumption that an accepted value of the maximum mechanical stress is tolerable we solve the problem by means of the  -constraint method [7] which reduces the problem ( 3 )-( 5 ) to a singleobjective one

max ()    subject to  W    

W  = { W  ( )    0} . 

The main objective is maximizing sum of squares of circles to be packed. Continual review of mechanical stress is a formidable problem. Of importance is the threshold value  of mechanical stress.

Let us temporarily relax the inequality

( )    0   ( 7 )  Then we can evaluate a posteriori the maximum mechanical stress for the obtained topology of the n * domain P0 \ int Ui1Ci (* ) and verify the condition ( 7 ) with respect to the local maximum point  . If the condition ( 7 ) holds true, i.e. (*)    0 , then a feasible point of the problem ( 6 )-( 7 ) is found, otherwise we calculate another local maximum point ** and repeat the procedure until ( 7 ) will be met.

We decompose the problem ( 6 )-( 7 ) into l subproblems separately for each polygon Pl , l  I p . Our multistart strategy involves the following main stages. appropriate polygon P , l  I p

l Stage 1. Define a lower bound l of the number l of circles which can be packed into the with the maximum packing factor, using Algorithm 1 based on packing equal circles [14]. Form a point ul* . 0  (w1* , w2* , ..., wn*p ) using IPOPT [23]. 4.2.

Solution algorithm 

Let us consider our solution strategy in details. Stage 4. Choose the best local maximum point satisfying the inequality (7) found at Stage 3.

Packing results depend heavily on the number of circles packed and starting points. We make use the idea of ACP. According to ACP circles are packed repeatedly touching three other circles [8]. To start ACP we first construct an initial configuration of tangent circles. To this end we realize a preliminary packing of equal circles with radius r  (if possible). The problem is known as IIPP (Identical Item Packing Problem) [24] The circle layout algorithm is based on the models described in [14].

We consider packing circles into the polygon Pl , l  I p . Let nl1  lj11 j be packed into the polygons P , j  1, 2,...,l 1. Now we pack the circle C q , q  n1 1. By condition, rq is bounded j above by r  , that can be, in general, less than the maximal possible radius rl , l  I p , the circle C q (vq , rl ) being inscribed into Pl . In this case the center vq of the circle C q (vq , r  ) is free to move within a polygonal set Pˆ l  Pl (Figure 1) ensuring feasible locations of C q (vq , r  ) in Pl .

Pl

r  ˆ P l r  l Figure 1: Packing the first circle into  Pl  

A random position of the circle center is chosen and then a step-by-step procedure of sequential addition of next circles according to the algorithm [14, 25] is carried out. If a circle with radius r  cannot be packed into Pl , we go to Stage 2 (ACP) starting from the circle with the maximal possible radius rl* , l  I p . If there are several possible locations for the circle, we choose a location for which the circle is tangent to the maximal number of the polygon edges.

To this end we solve consequently the problems.

* max rqk ,  k  0,1, 2,..., kl   

(k ) subject to  ul  W l (k )

  W (k)  { u(k )  R2k 3 l l : ml (xq , yq )  rq  0, m  1, 2,..., M l ,  l  I p ,  2 2 2  xq j1  xqt1   yq j1  yqt1    2r    0,  

* j,t  1, 2,..., k, j  t,   k {2,..., k } , 

2 2 2  xq j1  xqk    yq j1  yqk   rq  rqk  d   0,  

* j  1, 2,..., k, k {1,.2,.., kl } }.  

  * r qkl* С qkl* r 

 rq

Сq r 

 rq Сq2

P l r   rq Сq1

* k  1, 2,..., kl ; * 

A local maximum of the problem ( 8 )-( 9 ) is calculated. If rqk  r , then we continue to solve problem ( 8 )-( 9 ) for the next k , considering u(k )*  (xq* , yq* ,..., xq*k 1, yq*k 1, xqk , yqk , 0) where l *  xqk , yqk are randomly chosen ( ul(k )* W (k) ) as a starting point. If rqk  r , we stop the iterative l process. The point ul*  (vl* , rl* )  (xq* , yq* ,..., xq*k 1, yq*k1, xq*k , yq*k , r1444,.2..4,r443, rq*kl* )  

* is the algorithm output. Then k  kl , the circle Cqkl* touches at least three circles (or edges of Pl ) and can be considered as a first circle packed according to ACP (Figure 2). ( 8 )    ( 9 )       

4.2.2. Algorithm 2. Generating starting feasible points  

* If rqk

is a strict local maximum of the problem ( 6 )-( 7 ), then the circles Cq , Cq1,...,Cqkl* are rigidly fixed forming a “jammed” packing [26]. We pack next circles C qkl*1, Cqkl*2 ,...,Cql 1 according to ACP until the current radius r

 following ACP becomes less than r (Figure 3). A point * qkl*kASP 1

where kASP is the number of additional circles is obtained. The total number of circles packed into Pl is l  kl*  kASP , the radii values being within [r , r ] .

4.2.3. Local optimization 

After having constructed the starting packing for each polygon Pl , l  I p , we have the total number n  lI p l of circles to be packed into P .

We turn to problem ( 6 )-( 7 ), calculate a local maximum point and then construct a starting point 0  (w1* , w2* , ..., wn*p ) . To solve the nonlinear programming problem we make use of IPOPT solver [23] together with the decomposition strategy [15].

* rqkl* Сqkl*2 Сq+kl* +3 rq

Сq Сq2 Сq+l -1 Сqkl*1 Сq1

P l Сqkl*kACP Figure 3: Circle arrangement according to ACP 

Several local maximum points are computed and ordered in decreasing order of () (see problem ( 6 )-( 7 )) and then one can choose a point meeting ( 7 ). The first point in the ordering for which the inequality ( 7 ) holds true is a trade-off solution of the problem ( 3 )-( 5 ). If there is no a point satisfying the threshold value a (see ( 7 )), new local maximum points are computed or a compromise value a   is selected. Calculation of mechanical stress values is not considered in this paper. We refer to paper [10].

As computations show, local maximum points are close to or coincide with the starting points constructed according to ACP.

5. Computational results 

We consider the benchmark geometry presented in [10] and provide new benchmark examples for packing circles with variable radii. The dependence of the number of circles packed and the packing density on the minimal allowed distance between circles is studied. All experiments were running on an Intel Core I5 750 computer. We use the Delphi programming language and the Windows 10 operation system. Software library IPOPT [23, 27] for nonlinear optimization problems exploiting first and second derivative (Hessians) information is utilized.

Example 1. P0 is given by 11 vertices v01  (0,0), v02  ( 0,9 ), v03  ( 18,9 ), v04  ( 5, 28 ), v05  (0,33), v05  (0, 40), v06  (0, 40), v07  (60, 40), v08  (76,34), v09  ( 98,11 ), v0,10  ( 100,6 ), v0,11  (100, 0) . P  UlI p l

P , where IP  {1, 2,...,5} , vertices of Pl , l  I p , are v11  (22,31), v12  (35, 27), v51  (74,37), v52  (95,37), v53  (91, 31), v54  (74,35). The minimal allowed distance between circles is   0; r   0.5; r   5;

The total number of circles packed into P is n  91 ( 1  15, 2  23, 3  14, 4  31, 5  8 ). Value of the objective in the starting point (ACP) is (0 )  361.3287 and one in the local maximum point is *  362.0946 . Illustration of the circles packed is shown in Figure 4. This example is relevant to maximizing the packing factor and meaningless in relation to mechanical stress being infinite at   0 .

Example 2. See Example 1.   0.5. The starting objective value is (0 )  317.9666 and the local maximum point is *  319.3224 . Illustration (1  11, 2  19, 3  10, 4  21, 5  5) .   P0  P0 is shown in

Figure 5. n  66

P 1

P2

P2 Figure 4: Circle arrangement according to Example 1  Figure 5: Circle arrangement according to Example 2  P 3 local maximum point is *  301.7119 . Illustration is shown in Figure 6. n  50 (1  8, 2  12, 3  8, 4  17, 5  5) .

Example 4. See Example 1.   1. The starting objective value is (0 )  288.9095 and the local maximum point is *  289.7335 . Illustration is shown in Figure 7. n  47 (1  8, 2  12, 3  8, 4  14, 5  5) .

The runtime is within 30 seconds for all examples.

As computational results show, with an increase in the minimal allowed distance between circles, the contribution of large circles to the total circle area increases, since it is proportional to the squares of the circle radii. Obviously, this leads to a decrease in the number of circles with small radii and an increase in the radii of other circles.

In this regard, the choice of  is of importance. A compromise value is chosen: a too low value can lead to poor quality printing due to the technical features of the process, while a too large one causes additional material consumption. Furthermore, the secondary objective () can be influenced by varying the values of  , r  and r  . Figure 6: Circle arrangement according to Example 3  Figure 7: Circle arrangement according to Example 4 

6. Conclusions 

Topology optimization is a key point in additive manufacturing. Circular-hole based layout models help to cut down material expenses while meeting strength requirements.

We formulate non-standard packing problem of circles with variable metric characteristics. The proposed bi-objective model takes into account both the maximum packing factor and mechanical stress of parts. An efficient packing algorithm based on Apollonian circle packing, nonlinear programming and the -constraint method has been developed. The approach allows estimating the number of circular perforations needed and search for an approximate solution of the problem maximizing the packing factor and following a threshold value of mechanical stress.

Further research is directed to layout of circular perforations inside a 3D part considering balancing conditions [22, 28]. Therewith a more nuanced approach to multi-objective optimization should be constructed.

7. Acknowledgements 

The investigation is partially supported by the “Program for the State Priority Scientific Research and Technological (Experimental) Development of the Department of Physical and Technical Problems of Energy of the National Academy of Sciences of Ukraine” (#6541230) and National Research Foundation of Ukraine (#02.2020/167). 

8. References 

References

4.2.1. Algorithm  1 .  Searching for a lower bound of the number of circles 

[1] O. Sigmund , K. Maute , Struct topology optimization approaches , Structural and Multidisciplinary Optimization 48 ( 2013 ) 1031 - 1055 . doi: 10 .1007/s00158-013-0978-6.

[2] J. Liu , Y. Ma , A survey of manufacturing oriented topology optimization methods , Advances in Engineering Softwar 100 ( 2016 ) 161 - 175 . doi: 10 .1016/j.advengsoft. 2016 . 07 .017.

[3] A. Ramya , S. I. Vanapalli, 3D printing technologies in various applications , International Journal of Mechanical Engineering and Technology 7 ( 2016 ) 396 - 409 . Available from: http://www.iaeme.com/ currentissue.asp?JType=IJMET& VType=7&IType=3 .

[4] J. D. Deaton , R. V. Grandhi , A survey of structural and multidisciplinary continuum topology optimization: post 2000, Structural and Multidisciplinary Optimization 49 ( 2014 ) 1 - 38 . doi: 10 .1007/s00158-013-0956-z.

[5] K. Miettinen , Nonlinear Multiobjective Optimization, Springer Science & Business Media , 2012 .

[6] N. Gunantara , Q. Ai , A review of multi-objective optimization: Methods and its applications , Cogent Engineering , 5 : 1 ( 2018 ). doi: 10 .1080/23311916. 2018 . 1502242 .

[7] Y. Y. Haimes , L. S. Lasdon , D. A. Wismer , On a bicriterion formulation of the problems of integrated system identification and system optimization, . IEEE Trans. Syst. Man. Cybern . 1 ( 1971 ) 296 - 297 . doi: 10 .1109/TSMC. 1971 . 4308298 .

[8] W. Chen , M. Jiao , C. Kessler , A. Malik , X. Zhang , Spatial Statistics of Apollonian Gaskets, Experimental Mathematics 28 ( 2019 ) 263270 . doi: 10 .1080/10586458. 2017 . 1385037 .

[9] F. J. Kampas , J. D. Pintér , I. Castillo , Packing ovals in optimized regular polygons , J Glob Optim 77 ( 2020 ) 175 - 196 . doi: 10 .1007/s10898-019-00824-8.

[10] S. P. Fekete , S. Morr , C. Scheffer , Split Packing: Algorithms for Packing Circles with Optimal Worst-Case Density , Discrete Comput Geom 61 ( 2019 ) 562 - 594 . doi: 10 .1007/s00454-018-0020- 2.

[11] Y. Stoyan , G. Yaskov, T. Romanova , I. Litvinchev, S. Yakovlev , J. M. Velarde Cantú , Optimized packing multidimensional hyperspheres: a unified approach , Math Biosci Eng. 17 ( 2020 ) 6601 - 6630 . doi: 10 .3934/mbe.2020344.

[12] S. Yakovlev , O. Kartashov , K. Korobchynskyi , B. Skripka , Numerical Results of Variable Radii Method in the Unequal Circles Packing Problem , in: Proceedings of 2019 IEEE 15th International Conference on the Experience of Designing and Application of CAD Systems (CADSM) , Polyana, Ukraine, 2019 , pp. 1 - 4 . doi: 10 .1109/CADSM. 2019 . 8779288 .