18 Mathematical Model of Balanced Layout Problem Using Combinatorial Configurations Igor Grebennik1, Тatiana Romanova2, Inna Urniaieva1, Sergey Shekhovtsov1 1. Department of Computer Science, Kharkiv National University of Radioelectronics, UKRAINE, Kharkiv, 14 Nauki ave., email: igorgrebennik@gmail.com 2. Department of Mathematical Modeling and Optimal Design, Institute for Mechanical Engineering Problems of the National Academy of Sciences of Ukraine, UKRAINE, Kharkiv, 2/10 Pozharskogo str., email: tarom7@yahoo.com Abstract: The optimization of the balanced layout of a i ∈ J n , is uniquely defined by sub-container Ω j , j ∈ J m , in set of 3D-objects in a container is considered. We define which object  i will need to be placed. combinatorial configurations describing the combinatorial structure of the problem. A mathematical In contrast to the BLP problems, where a priori the model of the problem is presented. The model takes into requirement for placing objects in specific sub-containers account the placement constraints, the mechanical Ω j , j ∈ J m , is known, in this study the problem of the characteristics and the combinatorial features of the balanced layout of objects is formulated, which involves problem. generation and selection of a partition of the set A into non- Keywords: Balanced Layout, 3D-objects, Combinatorial Configurations, Phi-function Technique. empty subsets A j , j ∈ J m . Here A j is a subset of objects I. INTRODUCTION which have to be placed on rack S j inside Ω j . Balanced layout problems belong to the class of NP-hard On placement of object  i , i ∈ J n , inside subcontainer placement problems [1] and are the subject of the study of Ω j the following constraints are imposed computational geometry, and the methods for their solution j are a new branch of the theory of operations research [2, 3]. =zi ∑ t l −1 + hi , (1) The essence of the problem lays in the search for the optimal l =1 placement of a given set of 3D-objects in a container, taking where j ∈ J m . We consider that t 0 = 0 and ∀ i ∈ J n there into account, so called, behavior constraints, which ensure the exists j ∈ J m : hi ≤ t * . * balance of the system under consideration [4], [5]. j Let J n ⊆ J n be a set of indexes of objects which are II. PROBLEM FORMULATION j Let Ω be a container of height H that can take the form placed in sub-container Ω j , j ∈ J m , of a cuboid, cylinder, paraboloid of rotation, or truncated m cone. The container Ω is defined in the global coordinate  J nj = J n , J n  J n = ∅ , i ≠ j ∈ J m ; i j (2) system Oxyz , where Oz is the longitudinal axis of j =1 symmetry. We assume that container Ω is divided by k j = | A j | is the number of objects which are placed in horizontal racks into sub-containers Ωj, j∈ Jm = {1, ..., m} . We denote distances between racks S j sub-container Ω j , k j > 0 , j ∈ J m , m ∑kj =n. m and S j +1 by t j , j ∈ J m , ∑ t j = H . The center of the (3) j =1 j =1 lower base of container Ω is located in the origin of the In addition, the following placement constraints have to global coordinate system Oxyz . be taken into account: Let= А { i , i ∈ J n } be a set of homogeneous 3D-objects int  i1  int  i 2 = ∅ , i1 < i 2 ∈ J nj , j ∈ J m , (4) given by their metrical characteristics. Each object  i of  i ⊂ Ω j , i ∈ J nj , j ∈ J m , (5) height hi and mass mi , is defined in its local coordinate j system Oi x i y i z i , i ∈ J n . The location of object  i inside h = ≤tj, h j j max{hi , i ∈ J nj } , j ∈ J m . (6) container Ω is defined by vector = u i (v i , z i , θ i ) , where (v i , z i ) is a translation vector in the global coordinate We designate a system, formed as a result of the placement of objects  i of the set А in container Ω by system Oxyz , θ i is a rotation angle of object  i in the Ω A , and a system of coordinates of Ω A by O s XYZ , where plane Oi x i y i , where v i = ( x i , y i ) , and the value of z i , O s = ( x s (v), y s (v), z s (v)) is the mass center of Ω A ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic 19 n n n expected to be placed. We get a tuple consisting of n ∑ mi x i ∑ mi y i ∑ mi z i elements that form a permutation with repetitions from m x s (v) = i =1 , y s (v) = i =1 , z s = i =1 , (7) numbers 1, 2, ..., m, in which the first element is repeated k1 M M M n times, the second element is repeated k 2 times, ..., the last M = ∑ mi is the mass of system Ω A and O s X Ox , element is repeated k m times. i =1 The total number of permutations is equal to O sY Oy , O s Z Oz . n! P(n, k1 , k 2 , ..., k m ) = . (8) We consider the deviation of the center of mass O s of k1 !⋅ k 2 !⋅ ... ⋅ k m ! system Ω A from given point ( x 0 , y 0 , z 0 ) as an objective Then the number of variants of partitions of various function. objects from set A to m sub-containers Ω j , provided that Combinatorial Balanced layout Problem (CBLP). Define each sub-container contains at least one object and the order such variant of the partition of the object set A into of placing objects inside the sub-container is not important, is nonempty subsets A j , j ∈ J m , and the corresponding equal to placement parameters= u i (v i , z i , θ i ) of objects  i , ∑ n! P(n, k1 , k 2 , ..., k m ) = ∑ k !⋅ k !⋅ ... ⋅ k m ! i ∈ J n , taking into account relations (2)–(6), that the k1 + k 2 +...+ k m = n k + k +...+ k = 1 2 n 1m 2 objective function will reach its minimum value. Note that the number of summands in the sum is equal to We assume that the problem has at least one feasible N = C nm−−11 . solution. Note. Restrictions on the axial and centrifugal moments To generate subsets A j , j ∈ J m , we introduce a special of the system and allowable distances between objects may combinatorial configuration [9]. also be given. Rather complex combinatorial configurations can III. MATHEMATICAL MODEL formally be described and generated using tools of Now we define special combinatorial configurations construction of compositional κ -images of combinatorial describing the discrete structure of the CBLP problem. Some sets ( κ -sets) proposed in [10]. A combinatorial set is basic approaches for mathematical modelling of optimization considered as a set of tuples that constructed from a finite set problems on combinatorial configurations are described in of arbitrary elements (so-called generating elements) e.g., [6, 7]. according to certain rules. Permutations, combinations, The variants of partition of the set A into non-empty arrangements, and binary sequences are the examples of classical combinatorial sets. subsets A j , j ∈ J m , are determined by both the number of The basic idea of generation of κ -sets is introduced in elements in each subset and the order of the subsets. [10]. However, the problem of generating κ -sets of more Let us consider the sub-containers and the assumed complicated combinatorial structure remains the open corresponding sets of objects A j , j ∈ J m . Then the tuple of problem. Just one of such special cases is studied in [11]. m The problem of generating κ -sets is based on special natural numbers (k1 , k 2 , ..., k m ) , such that ∑kj =n, techniques of generating base combinatorial sets. The base j =1 sets can be defined as combinatorial sets with the known determines possible number k j of objects in each sub- descriptions: both classical combinatorial sets (permutations, combinations, arrangements, tuples) or non-classical container Ω j . The number of all such tuples is equal to the combinatorial sets (permutations of tuples, compositions of number of compositions of the number n of length m [8], permutations, permutations with a prescribed number of cycles, etc.). Generation algorithms for some of base which is C nm−−11 . combinatorial sets are presented in, e.g., [12-15]. Let us derive in what ways it is possible to decompose n We denote   (n, m) the set of compositions of the various objects from a set A into m sub-containers Ω j , number n of length m (which corresponds to the partition of j ∈ J m , if in sub-containers there are accordingly different objects from set A to m sub-containers Ω j , k1 , k 2 , ..., k m objects, and sets of objects A j , j∈ Jm , j ∈ J m , provided that each sub-container contains at least one object and the order of objects inside the sub-container is inside corresponding sub-containers Ω , j ∈ J m , are not j not important). Wherein,   (n, m)= N= C nm−−11 . ordered. Without loss of generality, we will distinguish the objects m with the same values of metrical characteristics, height hi= Let  (k1 , ..., k m ) ∈   (n, m) , ∑ k j = n , k j ≥ 1 , j ∈ J m . j =1 and mass mi (for example, consider them to be different in We introduce a combinatorial set  () that is a number). We order the elements of set A . To each object we composition image of combinatorial sets ( κ -set) assign the number of the sub-container into which it is   (n, m) ; C nk1 , C nk 2 , C nk 3 , …, C nk m , generated by sets 1 2 m −1 ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic 20 I n0 , I n1 , I n 2 , …, I n m −1 , where ni = n − k1 − ... − k i , 1, if i ≤ k1 ,  i ∈ J m −1 , I n0 = J n ,  2, if k1 < i ≤ k1 + k 2 , s= n n n n n I n1 = I n0 \ { j1 0 , j 2 0 , ..., j k 0 } , ( j1 0 , j 2 0 , ..., j k 0 ) ∈ C nk1 , n ... 1 1  m, if k1 + k 2 +...+ k m −1 < i ≤ k1 + k 2 +...+ k m , n n n n n n k I n 2 = I n1 \ { j1 1 , j 2 1 , ..., j k 1 } , ( j1 1 , j 2 1 , ..., j k 1 ) ∈ C n 2 , i = 1, 2, .., n, q i ∈ {1, 2, .., n}, q () ∈  (). 2 2 1 … Let us formalize placement constraints (4)-(6), using phi- n n n function technique. I n m −1 = I n m − 2 \ { j1 m − 2 , j 2 m − 2 , ..., j k m − 2 } , m −1 We consider two objects 1 and  2 with variable n n n k ( j1 m − 2 , j 2 m − 2 , ..., j k m − 2 ) ∈ C n m −1 , = parameters u1 (v1 , z1 , θ1 ) ∈ R 3 , = u 2 (v 2 , z 2 , θ 2 ) ∈ R 3 , m −1 m−2 where v1 = ( x1 , y1 ), v 2 = ( x 2 , y 2 ), x1 , y1 , θ1 x 2 , y 2 , θ 2 are n n n continuous variables and z1 , z 2 are discrete variables. I n m −1 = { j1 m −1 , j 2 m −1 , ..., j k m −1 } , m By definition [2, 3] a phi-function is a continuous n n n k ( j1 m −1 , j 2 m −1 , ..., j k m −1 ) ∈ C n m . function, therefore we extend the concept to discrete m m −1 variables z1 , z 2 . Note that Definition 1. Function ϒ12 (u1 , u 2 ) is called a D-phi- function of 3D-objects 1 and  2 if function I n0 ∪ I n1 ∪ ... ∪ I n m −1 = J n = {1, 2, ..., n}, ϒ12 (v1 , z10 , θ1 , v 2 , z 20 , θ 2 ) is a phi-function I n s ∩ I nt = ∅, s ≠ t= ∈ Jm 0 −1 {0,1, ..., m − 1} . Φ 12 (v1 , z10 , θ1 , v 2 , z 20 , θ 2 ) of objects 1 and  2 for fixed values z1 = z10 and z 2 = z 20 . Each element q () ∈  () can be described in the form Definition 2. Function ϒ12 ′ (u1 , u 2 , u12 ) is called a quasi q () = (q1 , ..., q k1 q k1 +1 , ..., q k1 + k 2 , ..., D-phi-function of 3D-objects, 1 and  2 if function q k1 +...+ k m −1 , ..., q k m −1 + k m ), ′ (v1 , z10 , θ1 , v 2 , z 20 , θ 2 , u12 ) ϒ12 is a quasi-phi-function = where (q1 , ..., q k ) n n n ( j1 0 , j 2 0 , ..., j k 0 ) ∈ C nk1 , ′ (v1 , z10 , θ1 , v 2 , z 20 , θ 2 , u12 ) of objects 1 Φ 12 and  2 for 1 1 (q= n n n k fixed values z1 = z10 and z 2 = z 20 . k1 +1 , ..., q k1 + k 2 ) ( j1 , j 2 , ..., j k ) ∈ C n , 1 1 1 2 2 1 Here u12 is the vector of auxiliary continuous variables … that is used to constructs a quasi phi-function of two objects n m −1 n m −1 n k (q k1= +...+ k m −1 , ..., q k m −1 + k m ) ( j1 , j 2 , ..., j k m −1 ) ∈ C n m . 1 and  2 . m m −1 The cardinality of set  () is derived by (9). The placement constraints (4)-(6) are described by the An element q() of the set  () is said to be a tuple of system of inequalities ϒ1 (u , τ) ≥ 0, ϒ 2 (u ) ≥ 0 , where the * inequality ϒ1 (u , τ) ≥ 0 describes the non-overlapping partition of the set А into subsets A j , j ∈ J m . Now we define the vector of the basic variables of the constraints and the inequality ϒ 2 (u ) ≥ 0 describes the * containment constraints problem СBLP:= u (v, z , θ), = where v (v1 , ..., v n ) ∈ R 2n , θ = (θ1 , ..., θ n ) ∈ R n= , vi ( xi , y i ) ∈ R 2 , xi , y i , θ i are τ) min{ϒ1j (u, τ), j ∈ J m }, ϒ1 (u,= = continuous variables, z ( z1 , ..., z n ) ∈ R , z i , i ∈ J n , are n ϒ1j (u ,= τ) min{ϒ qj q (u q , u q , u q q ), q1 < q 2 ∈ J nj }, (11) discrete variables defined by (1). 1 2 1 2 1 2 The values of variables z i , i ∈ J n , are determined in the = *j τ (u q q , q1 < q 2 ∈ J nj ), ϒ 2 (u ) = min{ϒ 2 (u ), j ∈ J m }, * order given by elements q() of combinatorial set  () : 1 2 ϒ *2 j (u ) = min{ϒ *q i (u q i ), q i ∈ J nj } , (12) s = z qi ∑ t l −1 + hqi , (10) ϒ qj q (u q , u q , u q q ) is the function that describes l =1 1 2 1 2 1 2 where non-overlapping of objects  q1 and  q2 , =uq ( x q , y q , z q= , θ q ), u q ( x q , y q , z q , θ q ), 1 1 1 1 1 2 2 2 2 2 ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic 21 ϒ *q i (u q i ) is the function that describes non-overlapping of associated with the construction of partitions of the set of placed objects into sub-containers. objects  q i and Ω = *j R 3 / int Ω j . REFERENCES Thus, in relations (11), (12) for fixed values z q and [1] B. Chazelle, H. Edelsbrunner, L. Guibas, “The 1 complexity of cutting complexes”. Discrete & Comp. z q , we have: ϒ qj q (u q , u q ) is a phi-function [16] Geom. 4(2), pp. 139–181, 1989 2 1 2 1 2 [2] N. Chernov, Stoyan, Y., Romanova, T. “Mathematical Φ q q (u q , u q ) for objects  q1 and  q 2 or a quasi-phi- model and efficient algorithms for object packing 1 2 1 2 problem”. Comput. Geom.: Theory and Appl., 43(5), pp. function [17] Φ ′qq (u q , u q , u q q ) for objects  q1 and 535–553 2010 1 2 1 2 1 2 [3] Yu. Stoyan, Т. Romanova “Mathematical Models of Placement Optimisation: Two- and Three-Dimensional  q 2 ; ϒ *q (u q ) is a phi-function Φq Ω (u q ) for objects *j Problems and Applications”. In: Fasano G., Pinter J. i i i i (eds.) “Modeling and Optimization in Space  qi and Ω *j . Engineering”, 73, pp.363-388. Springer Optimization and its Applications, New York, 2012 If the minimum allowable distances between objects are [4] A. Kovalenko, T. Romanova, P. Stetsyuk “Balance layout given, adjusted phi-functions (quasi-phi-functions) are used problem for 3D-objects: mathematical model and for the corresponding pairs of objects [16, 17]. solution methods”. Cyb.and Syst. Anal., 51(4), pp. 556- Mathematical model of the CBLP problem can be 565, 2015 [5] Yu. Stoyan, Т. Romanova, A. Pankratov, A. Kovalenko, P. defined as follows: Stetsyuk “Modeling and Optimization of Balance Layout Problems”. In: Fasano G., Pinter J. (eds.) F (u=, τ ) min F (u , τ) s.t. (u , τ) ∈ W , * * (13) “Space Engineering. Modeling and Optimization with Case Studies”, 114, pp. 369-400. Springer Optimization and its Applications, New York, 2016 = {(u , τ) ∈ R σ : ϒ1 (u , τ) ≥ 0, ϒ *2 (u ) ≥ 0, µ(u ) ≥ 0} , (14) W [6] S. Butenko, P. Pardalos, V. Shylo “Optimization Methods and Applications”. In: Springer Optimization and Its Applications Series, 130, 2017 where [7]. C. Papadimitriou, K. Steiglitz “Combinatorial Optimization: Algorithms and Complexity”. Courier Corporation, 1998 F (u ) =d =( x s (v, z ) − x 0 ) 2 + ( y s (v, z ) − y 0 ) 2 + ( z s − z 0 ) 2 [8] E. Reingold, J. Nievergelt, N. Deo “Combinatorial Algorithms: Theory and Practice”. Pearson Education, =u (v, z , θ), v = (v1 , ..., v n ) , θ = (θ1 , ..., θ n ) , Canada, 1977 [9] V. Sachkov “Combinatorial Methods in Discrete Mathematics”. Cambridge University Press, Edition 1, v i = ( x i , y i ) , i ∈ J n , z = ( z1 , ..., z n ) , 1996. m [10] Yu. Stoyan, I. Grebennik “Description and Generation of function ϒ1 (u , τ) is described by (11) with Ξ =  Ξj, Combinatorial Sets Having Special Characteristics”. j=1 Inter. Jour. of Biomed. Soft Comp. and Hum. Scien., Spec. vol. Bilevel Programming, Optimization Methods, =Ξ j {(q1 , q 2 ) : q1 < q 2 ∈ J nj } , and Applications to Economics, 18 (1), pp. 83-88, τ = (τ1 , ..., τ s ) = (u q q , q1 < q 2 ∈ J nj ) is a vector of 2013 1 2 [11] I. Grebennik “Description and generation of auxiliary variables for quasi phi-functions, s = Ξ , function permutations containing cycles”. Cybern. Syst. Analysis, 46(6), pp. 945-952, 2010 ϒ *2 (u ) is defined by (12), elements of vector z are given by [12] D. Knuth “The Art of Computer Programming, 4(2): (10), µ(u ) ≥ 0 describes behavior constraints. Generating All Tuples and Permutations”. Addison- Wesley, Boston, 2005 CBLP problem can be represented as a mixed integer [13] D. Kreher, D. Stinson “Combinatorial Algorithms: programming (MIP) problem, using approach with boolean Generation, Enumeration and Search”. CRC Press, 1999 variables. [14] F. Ruskey “Combinatorial Generation”, Dept. of However, unlike (13)-(14), this approach leads to Comput. Sci. Univ. of Victoria, Canada, 1j-CSC 425/20, increasing the number of discrete variables of the model and 2003 therefore increases the dimension of the CBLP problem in [15] W. Lipski “Combinatorics for Programmers” [in Polish], Polish Sci. Publ. (PWN), Warsaw, 1982 MIP form. [16] Yu. Stoyan, A. Pankratov, T. Romanova, A. Chugay IV. CONCLUSION “Optimized object packings using quasi-phi-functions”. In: Fasano G., Pinter J. (eds.) Optimized Packings and We study the problem of the balanced layout of 3D-objects Their Applications, 105, pp. 265-291. Springer within a container divided by horizontal racks onto sub- Optimization and its Applications, New York, 2015 containers. [17] Yu. Stoyan, A. Pankratov, T. Romanova “Quasi phi- A mathematical model has been constructed that takes functions and optimal packing of ellipses”. J. of Glob. into account not only the geometrical and behavior Optim. 65 (2), pp. 283-307, 2016. constraints, but also combinatorial features of the problem ACIT 2018, June 1-3, 2018, Ceske Budejovice, Czech Republic