Irregular layout problem for additive production Andrey Chugay[0000-0002-4079-5632], Aleksandr Pankratov[0000-0002-2958-8923], Tetyana Romanova[0000-0002-8618-4917] A. Pidgorny Institute of Mechanical Engineering Problems of the National Academy of Sciences of Ukraine, 2/10 Pozharsky St., 61046 Kharkiv, Ukraine chugay.andrey80@gmail.com, pankratov2001@yahoo.com, tarom27@yahoo.com Abstract. One of the interesting applications of optimization layout problems is additive production. The problem of layout of 3D objects (parts) inside a container (a working chamber of a 3D printer) to minimize the container height is studied. It is aimed to reduce printing costs by minimizing the number of 3D- printing layers while reducing the number of the printer starts. A mathematical model of the layout problem is provided in the form of nonlinear programming problem using the phi-function technique. A solution algorithm to search for optimized layouts is proposed. Computational results demonstrate the efficiency of our approach. Keywords: additive production, packing, mathematical modeling, phi-function, quasi phi-function, nonlinear optimization. 1 Introduction Optimization 3D layout problems have a wide spectrum of real-word applications, including transportation, logistics, chemical and aerospace engineering, shipbuilding, robotics, additive manufacturing, materials science. In this paper the smart technique to optimize the 3D-printing process for selective laser sintering (SLS) additive manu- facturing [1] is developed. The SLS technology uses high power laser sintering for small particles of plastic, ceramic, glass or metal flour in three-dimensional structure. This technology empowers the fast, flexible, cost-efficient, and easy manufacture of prototypes for various application of required shape and size by using powder based material. A physical prototype is an important for design confirmation and op- erational examination by creating the prototype unswervingly from CAD data. The main feature of this technology is the use of powder, consisting of particles of metal coated polymer. After the sintering process piece is placed in a high tempera- ture kiln to burn plastic and fusible took the bronze. The advantages of the technology include no need for material support. Parts immersed into a powder, which works on as a support [2]. Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). Recently 3D-prototyping technologies are evolving rapidly. The purpose of the re- search is development of smart technology to improve 3D-printing process for ad- vanced additive production. We propose the approach for accelerating printing cycle due to the simultaneous printing of several parts providing dense filling the entire volume of the working chamber 3D printer using SLS technology. One of the important problems arising in the process of creating new prototypes (final products) is reducing the time and cost production. For each start of SLS printer requires time and energy for heating and maintaining temperature. In [3] data on what savings can be achieved by optimizing the layout of objects to be created are pro- vided. Our approach allows optimizing the process of 3D printing for the following fac- tors: - printing of several prototypes (products) providing dense filling the volume of the 3D printer working chamber [4]; - minimizing the time and cost of 3D parts production by reducing printing cycle. In this paper the optimization layout problem of irregular 3D objects into opti- mized cuboid is studied. Our approach is based on the mathematical modelling of relations between irregu- lar geometric objects by means of the phi-function technique. It allows us reducing the layout problem to nonlinear programming model. 2 Literature review The list of publications related to the layout problem of irregular 3D objects, taking into account the minimum allowable distances is very scarce within the field of Pack- ing and Cutting. Arbitrary shaped objects in most cases are approximated by sets of cuboids or spheres. To solve the layout problems heuristic and meta-heuristic algo- rithms are used that resulting in the loss of optimal solutions. 3D object layout problems is NP-hard. In order to find feasible solutions some researchers use different techniques, including heuristics (based on different approximation rules heuristics [5], genetic algorithms [6], simulated annealing algorithms [7], artificial bee colony algorithms [8]), extended pattern search [8], traditional optimization methods [9, 10], nonlinear mathematical programming [11]. In the majority of papers, either orientation of 3D objects is fixed or only discrete rotations (by 45 or 90 degrees) are allowed. In particular, paper [2] uses the parallel translation algorithm for packing convex polytopes. The authors of [12] propose the HAPE3D algorithm which can be applied to arbitrarily shaped polyhedra that can be rotated around each coordinate axis at eight different angles. In [13] the issue is dis- cussed that for 3D packing problems making calculations of 0 to 360 degrees orienta- tions of objects with respect to each axis is impossible. Analysis of irregular three- dimensional packing problems in additive manufacturing is provided in [14]. The paper [15 22] presents an intelligent layout planning for rapid prototyping. Only few works consider continuous rotations of 3D objects (see, e.g. [16- 22]. 3 Problem statement In order to minimize the time of 3D parts production using SLS-technology the num- ber of layers should be minimized. The problem of minimizing layers can be formu- lated as a problem of layout (packing) of parts in the container of minimum height (fig.1). Fig. 1. Minimizing of the height of the occupied part of the 3D printer working chamber Let the set of irregular 3D objects Ti , i  I n = {1,2,..., n}, and container  = {( x, y, z )  R3 , 0  w1  x  w2 , 0  l1  y  l2 , 0  h1  z  h2 } be given. Here h1 and h2 are variable. Denote the container  of variable sizes by (h1 , h2 ) . Each object Ti is presented by a union of convex polyhedra n i Ti =  Tik , i  I n , k =1 where Tik is defined by the collection of vertices { pik } . Layout of Ti in R3 determined by the translation vector vi = ( xi , yi , zi ) and the vector of rotation angles i = ( i , i ,  i ), i  I n Thus, vector ui = (vi , i ) determines placement of Pi in the tree-dimensional space R 3 . Further object Ti , translated on the vector vi and rotated by angles  i , i ,  i is denoted by Ti (ui ) . Optimization layout problem. Find vector u  (u1 ,..., un ) that provides layout of objects Ti (ui ), i  I , inside the container (h1 , h2 ) so that the height H  h2  h1 will reach the minimum value. 4 Mathematical model and its properties Using the phi-function technique [16-22] a mathematical model of the optimization layout problem can be presented as the following nonlinear programming problem: min H , (1) X W W = { X  R m :  ij (ui , u j , uij )  0, i < j  I n ,  i (ui , h1 , h2 )  0, i  I n , h2  h1  0} , (2) where X  (h1 , h2 , u , u ) ,  ij (ui , u j , uij ) is the quasi phi-function for polyhedra Ti and T j [18, 21], u   (uij , i < j  I n ) , uij is the vector auxiliary variables for the quasi phi-function  ij (ui , u j , uij ) ,  i (ui , h1 , h2 ) is the phi-function for objects Ti and *  R3 \ int  . The inequality  ij (ui , u j , uij )  0 provides non-overlapping Ti and T j and inequality  i (ui , h1 , h2 )  0 provides containment of Ti into  . The problem (1)-(2) is an exact formulation of the optimization layout problem of 3D objects. The feasible region W of the problem (1)-(2), in the general case, is a disconnected set, and each of its connected components is a multiply connected. 5 Solution approach Our solution approach is addressed to the placement of non-convex continuously rotated objects. To construct feasible starting points the clustering algorithm is pro- posed. Local optimization is performed using the IPOPT code combined with the decomposition strategy. To search for local extrema, a multistart strategy is used. Firstly we solve the problem of clustering of pairs of 3D objects into optimized containing spheres or cuboids. Then depending on the shape of clusters auxiliary sub- problems of packing cuboids or spheres are solved, employing the clusters homothetic transformations. This allows constructing fast feasible starting points. The reduction of computational costs is also facilitated by the fact that the process of finding a local extremum of the problem is divided into two stages: solving NLP subproblems by fixing the rotation angles and solving NLP subproblems allowing free object rotations. In addition, the strategy of finding an approximation to the global extremum is used. As an approximation to the global minimum of the optimization layout problem (1)-(2) the best local minimum found by our approach is considered. 5.1 Generation of feasible starting points In order to generate a feasible starting point for problem (1) - (2) we use the following algorithm. Firstly, pairs of non-overlapping objects are placed into containing regions (cuboids or spheres) of the minimum volume. Then we solve the problem of packing the set of the obtained clusters into the container (cuboid) of minimum height. This algorithm returns feasible placement parameters for each polyhedron. To compute rotation angles of each of polyhedra the following algorithm is proposed. The set of objects Ti , i  I n , is divided into k groups. Each group involves lk identical polyhedra. Each object Ti is contained into the sphere Si of minimum radius ri* , using the following NLP subproblem: ri* = min ri , i  I n , vi , ri Di  R 4  Di =  vi , ri   R 4 :  ij  ri2  ( xij'  xi )2  ( yij'  yi ) 2  ( zij'  zi ) 2  0, j  J i  . Denote a local minimum point of the subproblem by (vi* , ri* ) . Then each object Ti is translated by the vector vi* . Further Сn2  n subproblems of packing the objects Ti , i  I n , into cuboid ij of minimum volume DijC are solved: ri* = min Dijc (h1 , h2 ), (3) (ui ,u j ,h1 ,h2 )Wij  R18 Wij = {(ui , u j , h1 , h2 )  R18 : ij (ui , u j )  0, i (ui , h1 , h2 )  0, (4)  j (u j , h1 , h2 )  0, F (h1 , h2 )  0} where i  j  I n , Dijc (h1 , h2 ) = (h2  h1 )( w2  w1 )(l2  l1 ) , F (h1 , h2 ) = min{h2  h1 , w2  w1 , l2  l1} . The inequality ij (ui , u j )  0 implies that int Ti  int T j =  , while the inequali- ties i (ui , h1 , h2 )  0 and  j (u j , h1 , h2 )  0 guarantee the arrangement of Ti and T j fully inside containing region ij . Next we solve the layout problem of subset of clusters Qi , i  M , inside the cu- boid  of minimum height. Now the problem (1)-(2) is reduced to the following NLP model: min~ H (h1 , h2 ), (5) (u~ ,h1 ,h2 )W  R 6   6 W = {(u , h1 , h2 )  R 6 6 : ij (ui , u j )  0, i  j  M , i (ui , h1 , h2 )  0, (6) i  M , h2  h1  0}, where H(h1 , h2 )= h2 - h1 . Let the point (u* , h1* , h2* )  R 6 6 be an approximation to the global minimum point of the problem (5) - (6). The point corresponds to packing clusters Qi (ui* ), i  M into cuboid (h1* , h2* ) . Each cluster Qi . contains the pair of polyhedra Tk and Tt i i with placement parameters ukQ and utQ in the local coordinate system of the cluster i i Qi . In order to construct a feasible point (u 0 , h10 , h20 )  W of the problem (1) - (2) re- garding the arrangement of clusters Qi , i  M , we set the arrangement of object Ti using the equation vi0  vi*  viQ for i  I n . To define the rotation angles i0 of polyhedra Ti , i  I n , we solve the sequence of n subproblems of the following form: r13i*  min r13i , (7) Ri Di  R9 Di = {Ri  R9 : V1i R i  V1i , V2i Ri  V2i , V3i Ri  V3i ,  rij rik   jk , i (8)  rji rki   jk , i  1, 2,3} i where V1i , V2i , V3i are vectors of initial coordinates of the first three vertices of the polyhedron Pi , V ji  Ri* ( RiQV ji  viQ ) , j  1, 2,3, Ri is the rotation matrix, i  I n . Let ri* be a solution of the problem (7) - (8). Then the angles of Ti can be derived in the form: i  arcsin r13i*  i* i  arcsin(r23 / cos i ) ,  i  arccos( r12i* / cos i ) . 5.2 Local optimization To find a local extremum of the problem (1)-(2) the following algorithm is used. This algorithm allows reducing CPU. The feasible region of the problem (1)-(2) can be always represented by a union of subregions (see e.g. [21]). It enables to search for a local minimum of the problem (1)-(2) by solving a collection of NLP subproblems with a considerably smaller num- ber of inequalities. The key idea of the proposed algorithm is based on the decomposition strategy (see, e.g. [23]). The large scale problem (1)-(2) is reduced to a sequence of subprob- lems of smaller dimension. The following stages are performed:  generating feasible subregions of the feasible region (2) related to the appro- priate starting points;  forming the system of   active constraints;  searching for local extrema of the subproblems generated at the first step, employing state-of-the-art NLP-solvers;  replacing subregions. Now we consider the algorithm in detail. Let the point X   W be a starting point. Then we select an appropriate subregion W0 , such that X   W0  W and substitute the point X  in the inequality system (2). Each quasi phi-function has the form       ij' ui , u j , u   max  ijs ui , u j , u  , s  1, ,ij .  a   Then we select one of the functions  ijij ui , u j , u  , aij  1, ,ij , i  j  I ,   such that   a    ij' ui , u j , u    ijij ui , u j , u   ij . Similarly we choose  i  ui , u   0, i  I . It results in the system of inequalities 0  X   0 describing the subregion W0 . Then the subproblem   F u0* = min X W0  R  F  u    is solved. The inequality system 0 X 0*  0 distinguishes the active inequality    j 0 0* j  0, j  0  {1,...,  0 }    {1,..., } . Denote the subsystem by  ija (ui , u j )  0, i  I 01  I , j  I 02  I . This allows choosing quasi phi-functions    ij' ui , u j , u  that involve functions  ija (ui , u j ), for i  I 01 , j  I 02 . Then we calculate the values of the functions at the point X 0* . Let    ij' ui0 , u 0j    ijс (ui0 , u 0j  )  0ij , i  I 01 , j  I 02 . If ij0  0, i  I 01 , j  I 02 then replace subsystems  ija (ui , u j )  0 by systems  сij (ui , u j )  0 , i  I 01 , j  I 02 . Thus a new subsystem of inequalities defining a new subregion W1  W is generated. Obviously, X 0  W1. Taking the starting point X 0 , we solve the problem   F u1*  = min X W1  R m F  u  , and search for a local minimum point X 1* .   The computational process is repeated until F u(1)*  F u* .   The search for a local minimum of the problem (1) - (2) can be divided into two stages: optimization of the system with linear constraints and nonlinear optimization. The first stage is realized by fixing the rotation angles i0 of objects Ti , i  I n at the feasible starting point (u 0 , u0 )  W . Fixing rotation angles significantly reduces the dimension of the problem (1) - (2) switching to the linear constraints to describe the feasible region. Figure 3 depicts layout of irregular 3D objects that corresponds to a) a feasible starting point and b) the appropriate local minimum found by our algorithm. a) b) Fig. 1. Example of layouts of irregular objects corresponding: a) a starting point; b) a local minimum point 6 Computation experiments We present some examples to demonstrate the efficiency of our methodology. We have run all experiments on an Intel I5 2320 computer, programming language C++, Windows 10 OS. To solve NLP problems IPOPT [24] is used, which is available at an open access software depository (https://projects.coin-or.org/Ipopt). Figure 2 demonstrates some benchmark examples of irregular layouts obtained by our approach. In order to show the efficiency of our approach a number of benchmarks instances given in [12] are tested. The results are shown in Table 1. Fig. 2. Examples of 3D irregular object layouts Table 1. Comparison of our results with those publised in [12] Approach HAPE3D Our algorithm The result of packing 20 irregular 3D objects Volume 32550 28500 Runtime (sec) 26202 6656 The result of packing 30 irregular 3D objects Volume 12480 10720 Runtime (sec) 9637 4789 The result of packing 36 irregular 3D objects Volume 48300 42450 Runtime (sec) 53741 9543 The result of packing 40 irregular 3D objects Volume 61950 56012 Runtime (sec) 99952 24543 The result of packing 50 irregular 3D objects Volume 77280 71800 Runtime (sec) 125210 36543 7 Conclusions The 3D-printing procedure using SLS technology takes a long time (many hours or even days) and requires a great financial cost associated with: the printer running, the camera heating and the temperature stabilization. Development of the optimization techniques allowing saving time and material is of paramount importance. The optimization problem of layout of irregular 3D objects into cuboid of mini- mum height is formulated. The mathematical model is constructed, using the phi- function technique. The solution strategy is proposed. To demonstrate the efficiency of our methodology some instances are provided. Obtainment of optimized layouts of 3D objects makes possible reducing the printing cost by minimizing the number of layers of 3D printing and therefore reducing the number of the printer starts. Acknowledgments: The authors would like to thank anonymous referees for careful reading the paper and constructive comments. The authors were partially supported by the “Program for the State Priority Scientific Research and Technological (Ex- perimental) Development of the Department of Physical and Technical Problems of Energy of the National Academy of Sciences of Ukraine” (#6541230). References 1. Ramya, A., Sai Vanapalli: 3D printing technologies in various applications. International Journal of Mechanical Engineering and Technology 7(3), 396-409 (2016). 2. Egeblad, J., Nielse, B.K., Brazil, M.: Translational packing of arbitrary polytopes. Computational Geometry 42, 269–288 (2009). 3. Baumers, M., Dickens, P., Tuck, C., Hague, R.M.: The cost of additive manufacturing: machine productivity, economies of scale and technology-push. Technological Forecasting & Social Change, 102, 193-201 (2016). 4. Romanova, T., Stoyan, Y., Pankratov, A., Litvinchev, I., Avramov, K., Chernobryvko, M., Yanchevskyi, I., Mozgova, I., Bennell, J.: Optimal layout of ellipses and its application for additive manufacturing, International Journal of Production Research, 27 pages, (2019). 5. Verkhoturov, M., Petunin, A., Verkhoturova, G., Danilov, K., Kurennov, D.: The 3D Object Packing Problem into a Parallelepiped Container Based on Discrete-Logical Representation. IFAC-PapersOnLine 49(12), 1-5 (2016). 6. Karabulut, K., İnceoğlu, M.: A Hybrid Genetic Algorithm for Packing in 3D with Deepest Bottom Left with Fill Method. Advances in Information Systems 3261, 441-450 (2004). 7. Cao, P., Fan, Z., Gao, R., Tang, J.: Complex Housing: Modeling and Optimization Using an Improved Multi-Objective Simulated Annealing Algorithm. Proceedings of the ASME, 60563, V02BT03A034 (2016). 8. Guangqiang, L., Fengqiang, Z., Rubo, Z., Du, Jialu, Du., Chen, G.,Yiran, Z.: A Parallel Particle Bee Colony Algorithm Approach to Layout Optimization. Journal of Computational and Theoretical Nanoscience 13(7), 4151-4157 (2016). 9. Torczon, V., Trosset, M.: From evolutionary operation to parallel direct search: Pattern search algorithms for numerical optimization. Computing Science and Statistics 29, 396- 401 (1998). 10. Birgin, E.G., Lobato, R.D., Martіnez, J.M.: Packing ellipsoids by nonlinear optimization. Journal of Global Optimization 65, 709-743 (2016). 11. Fasano, G.: A global optimization point of view to handle non-standard object packing problems. Journal of Global Optimization 55(2), 279 –299 (2013). 12. Liu, X., Liu, J., Cao, A., Yao, Z.: HAPE3D - a new constructive algorithm for the 3D irregular packing problem. Frontiers of Information Technology & Electronic Engineering 16(5), 380-390 (2015). 13. Youn-Kyoung, Joung, Sang Do Noh.: Intelligent 3D packing using a grouping algorithm for automotive container engineering. Journal of Computational Design and Engineering 1(2), 140-151 (2014). 14. Araújo, L. J. P., Özcan, E., Atkin, J. A. D., & Baumers, M. (2019). Analysis of irregular three-dimensional packing problems in additive manufacturing: a new taxonomy and dataset. International Journal of Production Research, 57(18), 5920–5934. 15. Gogate, A. S., & Pande, S. S. (2008). Intelligent layout planning for rapid prototyping. International Journal of Production Research, 46(20), 5607–5631. 16. Stoyan, Y.G., Chugay, A.M.: Packing different cuboids with rotations and spheres into a cuboid. Advances in Decision Sciences. Available at https://www.hindawi.com/journals/ads/2014/571743 (2014). 17. Stoyan, Y.G., Semkin, V.V., Chugay, A.M.: Modeling Close Packing of 3D Objects. Cybernetics and Systems Analysis 52 (2), 296-304 (2016). 18. Stoyan, Y.G., Chugay, A.M.: Mathematical modeling of the interaction of non-oriented convex polytopes. Cybernetic and Systems Analysis 48, 837-845 (2012). 19. Grebennik, I.V., Pankratov, A.V., Chugay, A.M., Baranov, A.V.: Packing n-dimensional parallelepipeds with the feasibility of changing their orthogonal orientation in an n- dimensional parallelepiped. Cybernetics and Systems Analysis 46(5), 793-802 (2010). 20. Stoyan, Y., Pankratov, A., Romanova, T., Fasano, G., Pintér, J.D., Stoian, Y.E., Chugay, A.: Optimized Packings in Space Engineering Applications, Springer Optimization and Its Applications, 144, 478 (2019). 21. Romanova, T., Bennell, J., Stoyan, Y., Pankratov, A.: Packing of concave polyhedra with continuous rotations using nonlinear optimisation, European Journal of Operational Research, 268 (1), 37-53, (2018). 22. Kovalenko, A.A., Romanova, T.E., & Stetsyuk, P.I. (2015). Balance Layout Problem for 3D-Objects: Mathematical Model and Solution Methods. Cybernetics and Systems Analysis, 51(4), 556–565. 23. Romanova, T., Stoyan, Y., Pankratov, A., Litvinchev, I., Marmolejo, J.A.: Decomposition Algorithm for Irregular Placement Problems. In: Vasant P., Zelinka I., Weber GW. (eds) Intelligent Computing and Optimization. Advances in Intelligent Systems and Computing, 1072, 214-221 (2019). 24. Wachter, A., Biegler, L.T.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106 (1), 25-57 (2006).