OPTIMAL HIERARCHICAL DECOMPOSITION SYNTHESIS USING INTEGER PROGRAMMING Ramprasad S. Krishnamachari Graduate Student and Panos Y. Papalambros Professor Technical Report 95-17 November, 1995

OPTIMAL HIERARCHICAL DECOMPOSITION SYNTHESIS USING INTEGER PROGRAMMING Ramprasad S. Krishnamachari Graduate Student and Panos Y. Papalambros t Professor Design Laboratory Department of Mechanical Engineering and Applied Mechanics The University of Michigan Ann Arbor, Michigan ABSTRACT Decomposition synthesis in optimal design is the process of creating an optimal design model by selecting objectives and constraints so that it can be directly partitioned into an appropriate decomposed form. Such synthesis results are not unique since there may be many partitions that satisfy the decomposition requirements. Introducing suitable criteria an optimal decomposition synthesis process can be defined in a manner analogous to optimal partitioning formulations. The article presents an integer programming formulation and solution techniques for synthesizing hierarchically decomposed optimal design problems. Examples for designing a pressure vessel, an automotive caliper disc brake and a speed reducer are also presented. November, 1995 Corresponding author

INTRODUCTION The general design problem (GDP) is defined formally as GDP: find x E X subject to h(x, p) =0 (1) g(x, p) < 0 where h, g represent vectors of design criteria generally assumed to be nonlinear functions of the design variables x and parameters p, and X is the set constraint on the design variables, imposing additional restrictions on x, such as discreteness. The GDP is transformed to an optimal design problem (ODP) by selecting one or more design criteria from Eq. (1) and composing a scalar objective as follows: K ODP: minimize f (x, p') = 1 fi(xi, p') subject to h(x, p) = 0 (2) g(x, p) < 0 and x E X where p' is a vector of parameters that may include weights used in composing the scalar objective f (x, p') to be minimized, xi is a subvector (any vector defined from the components of a given vector) of x, andfi(xi, p') are independent criteria selected from h and g to define the objective. Synthesis of the ODP is based on a variety of subjective considerations, generally regarding (i) the type of knowledge available and/or desirable for the underlying design problem and (ii) expedience in solving the resulting mathematical optimization problem. Design of large complex engineering systems modeled as nonlinear programming problems can benefit from the use of decomposition strategies; see Papalambros (1995) for a review. Synthesizing ODP's that can be decomposed and solved in a systematic way is then desirable. A "hierarchical decomposition synthesis" methodology where a hierarchically decomposed ODP is obtained starting from a GDP was proposed by Krishnamachari and Papalambros (1995) - abbreviated as 2

K&P (1995) in the sequel. The ODP thus obtained can be partitioned and solved with a prescribed decomposition method. Synthesis of a decomposable ODP is a natural extension of the decomposition analysis methodology developed for partitioning already formulated ODP's into appropriate decomposed forms (Wagner 1993, Papalambros 1995). Given an undecomposed GDP (or ODP for that matter) there are many ways of obtaining a decomposed ODP. It is then natural to attempt to formalize a process for selecting the "best" such ODP relative to some formal criteria. This process is termed optimal decomposition synthesis and it is analogous to the optimal partitioning methods developed for decomposition analysis (Michelena and Papalambros 1994, 1995). The methodology proposed in K&P (1995) mainly focuses on synthesizing ODP's that can be solved by a primal hierarchical decomposition method (Wagner 1993). A block-angular structure is first identified in the GDP. An ODP is then created that can be hierarchically decomposed based on this structure. Formally, a GDP is first cast into the form go(xo) < 0 ho(xo) = 0 (3) gi(xo, xi) < 0 i= 1..., K hi(xo, xi) = 0 i =1,..., K (4) that has a master problem and K subproblems with the block-angular structure of Fig. 1. A hierarchically decomposed ODP is synthesized by composing a weighted additive objective selecting criteria from Eq. (3) and (4) as shown in Eq. (5) and Fig. 2. As noted in K&P (1995) the synthesized objective may include components only from Eq. (3) or Eq. (4). K minimize f =fo(xo, wo) + I fi(xo, xi, wi) x-,x i = 1 subject to: go(xo) < 0 (5) ho(xo) = 0 gi(x,xi) <0 i=....,K hi(xo, xi) = 0 i = l...,K 3

X0 xI X2 x x XK l_ X ^' * I_ g, h gh Fig. 1 GDP with block-angular structure Fig. 2 Synthesized ODP Identification of the block-angular structure in the GDP is performed using graph partitioning. This procedure proposed in K&P (1995) can be illustrated using the following example. Consider a GDP with a functional dependence table (FDT) as in Fig. 3(a). Linking variables {4, x5 } are selected using the graph representation of the FDT, Fig. 3(b). The vertices corresponding to these variables are removed and the graph splits into pieces. The partitions corresponding to Eq. (3-4) are shown in Fig. 3(c). The partitioned GDP now has the FDT shown in Fig. 3(d). i^IA - ~ ix4I (: ~ eq'(3) XlX ~iX2 4 X5 X6 X Xeq1(3) X X3 X _1 0 0 g3I::i 93 O' 0 0 0 0 2 0 0 1 1 10 0 X g5 ( i- 0 0 0 0 J_ _ _ XK< X3 1 g2 l _ol t ~ t I Xlg 000100 g~ 9gOOJj 0 I g g 1 0110 01g (a) (b) (c) (d) Fig. 3 Steps in identifying block-angular structure in the GDP 4

Partitions I and II in Fig. 3(c) represented as the connected components (blocks) of the system in Fig. 3(d) is not the only way of creating a model structure in the form of Eq. (4). For example, a single larger cluster resulting from combining these two partitions would still satisfy Eq. (4). In general, selection of linking variables and block composition is not unique for a given desirable structure. If this selection can be guided by a formal objective criterion, a combinatorial optimization problem can be posed to find the "most suitable" structure, a process we termed optimal decomposition synthesis. The next section describes an integer programming model for this problem and a solution strategy when connectivity within each cluster is not strictly required. Direct graph partitioning methods that do account for connectivity are briefly discussed in the subsequent section. The methods are then demonstrated and compared in some small but illustrative design examples. INTEGER PROGRAMMING FORMULATION Considering the GDP in Eqs. (3) and (4), we refer to the linking variables xo and associated functions ho, go as the master cluster, and the local variables xi and functions hi, gi as the subclusters (for i = 1,..., K). Note that these clusters will correspond to the master problem and subproblems, respectively, in the hierarchically decomposed ODP to be synthesized. To proceed with the formulation we assume that there are two desirable characteristics of the final ODP. The model blocks should be (i) relatively small in size to facilitate comprehension and computation, (ii) of approximately the same size to facilitate validation, parametric studies, and load balancing in case of parallel solution. The first characteristic leads to an objective function that attempts to minimize both the size of the master cluster and the average size of the subclusters: minimize it,,, (size of the master cluster) + ws (average size of the subclusters), where wvm, \vs are weights. The second characteristic imposes the constraint Ks (size of the smallest subcluster) ~> (size of the largest subcluster), where Ks > 1 is a size factor. The size of a cluster is defined as equal to the sum of the number of variables and the number of design criteria (functions) that it contains. 5

Note that this formulation does not account for changes in the cluster sizes resulting from the composition of the system objective. Also recall that block-angular structures such as that of Fig. 3 may include a subcluster (block) that is not a (single) connected component. This issue will be addressed in the next section. In the formulation, each cluster is designated by its variables and functions. All variables and functions in the GDP must be assigned. The master cluster contains all design criteria that are functions exclusively of the linking variables. A local variable belongs to a subcluster if the function that depends on that variable is in the subcluster. Each function can belong to only one subcluster. Functions belonging to two different subclusters cannot have any common variables other than the linking ones. An integer linear programming (ILP) model is created whose zeroone variables indicate what cluster the design variables and functions are assigned to. The model is kept linear by assuming that the number of subclusters K is fixed during optimization. A postoptimal parametric study on K can be then conducted. It is assumed throughout Wm = Ws = 1.0. The ILP model is advantageous since it represents a difficult but well-studied optimization problem. The global optimum may be found using branch and bound or cutting plane methods, and a lower bound on the ILP solution can be always obtained by solving the relaxed continuous LP (see. e.g., Papadimitriou and Steiglitz 1982). To proceed with the ILP model define the following: i cluster index, i = 0,..., K (zero corresponding to the master cluster) j function (criterion) index in the GDP, j= 1...., T v variable index in the GDP, v = 1,..., N dj number of variables in function j fl if function j contains variable v =J, 0 otherwise fl if cluster i contains variable v e= otherwise sv =[ 0 otherwise 6

Ks cluster relative size constant, usually 3 > Ks > 1 Si size of cluster i The mathematical model for the optimal synthesis problem is now stated as follows: N T K minimize X eov+ soj + (1/K) X Si (6) eivsij v=l j=1 i=1 subject to: T N hl Si = Sij+ ~ eiv =,....,K j=l v=l K 1h2: X sij1=l j T i=O K h3': eiV=1 v= 1....,N i=0 gl: KsSi >Sq, q:i, i,q= 1,2,..., K N g2: ajv eov > djsoj j= 1,...,T v = 1 N K g3: ajv eov < dj - sij = -,...,T v=1 1i=1 g4: eiv> ( ajvsij / I a,,) -eov'= 1,..., N and i 1,..... K J J g5: ei < E avsij = IN... and i= 1,....K J N g6': 6 eiv> 1 i= 1,...K v= 1 Constraint hi defines the size of a subcluster, while h2 and h3 enforce the requirement that each function and variable belong to one and only one cluster, respectively. Constraint gl restricts the relative sizes of subclusters; g2 states that a function belonging to the master cluster must be 7

depend only the linking variables, and g3 precludes such functions from being in any subcluster. Constraint g4 says that if a function j depending on a variable v is in subcluster i then variable v is also in i, unless v is a linking variable; g5 says that if the functions depending on variable v are not in a subcluster i then v does not belong to subcluster i. Finally, g6 says that each subcluster must have at least one design variable that is a local variable. The ILP model in Eq. (6) is NP-hard. Cutting plane methods and enumeration methods such as branch and bound will guarantee a global optimum for the ILP model in Eq. (6), if a solution is found. Other methods relying mostly on heuristics can provide solutions at various levels of confidence (Papadimitriou and Steiglitz, op. cit., Murty 1994). Here we use a branch and bound approach. Specifically, the model is first represented using AMPL (A Mathematical Programming Language, see Fourer 1993), and then solved using standard software from OSL (Optimization System Library, see IBM 1990). Use of standard software is of particular influence in selecting the solution method. SYNTHESIS WITH CONNECTED SUBCLUSTERS As mentioned already, the model in Eq. (6) does not guarantee solutions that have all subclusters corresponding to connected components. Such connectedness may be a design requirement for the synthesis process. In the ILP formulation connectivity can be enforced by adding constraints. There is a difficulty, however, since the number of constraints needed to impose the connectivity requirement (keeping the formulation linear) increases exponentially with the number of design criteria and variables in the GDP. Imposing connectivity in a cluster requires that any partition into two parts of the graph representing the cluster must have at least one edge common to both partitions. For a cluster with n vertices there are 2n - 1 possible partitions, and this must be repeated for all vertices of all subclusters. In addition, new intermediate discrete variables would be needed to keep the formulation linear. This approach is considered unprofitable as we would haevery large number of constraints in the ILP model for even medium size problems. 8

An alternative is to use a two phase approach for solving the graph partitioning problem directly using a greedy recursive graph partitioning technique followed by local search. In the first phase we try to achieve a'good' feasible solution and in the second to improve on it. One could stop at the end of the first phase, if desired. Following the process exemplified in Fig. (3), the main task is to identify the "best" set of linking variables. This identifies the master and subclusters while all constraints in Eq. (6), except for the relative size constraints gl, are automatically satisfied. The goal then is to identify the linking variables that provide the lowest objective value without violating the relative size constraint in Eq. (6) - without exhaustive enumeration. Recursive Partitioning The starting point for the partitioning process is the GDP with N variables and T functions. The graph is assumed to be connected and it is partitioned recursively. Each recursion is called a stage and has the following steps Step 1: Select cluster for partitioning. At each stage the largest subcluster (the one with the maximum number of vertices) is identified. A tie is broken by choosing the cluster containing the variable with the lowest index. The first such subcluster is the original graph. Step 2: Selecting the best linking variable. Partitioning is effected by removing from the graph the vertices that correspond to each subcluster variable, one at a time, to test if the particular variable could serve as a linking variable. Each variable tested from the list of candidate linking variables is temporarily added to the list of best linking variables, bl. The master cluster and subclusters are identified, and the model, Eq. (6) is evaluated. After collecting model values for each variable in the current largest subcluster, the best linking variable (the one whose feasible solution has the lowest objective value) is added to bl permanently. A tie is broken by choosing the variable with the lowest index. If no feasible solution is obtained, the best variable is chosen as the one with the least violation of the relative size constraint. Ties are broken by choosing the 9

variable whose vertex has the maximum degree in the graph corresponding to the subcluster under consideration. Step 3: Updating. The list bl is updated until all variables in the GDP have been chosen as linking variables or some other termination criterion is met. Each updated solution can be further improved by a local search technique; otherwise, the solution chosen is the best feasible solution (if it exists) available at termination. To illustrate consider the example GDP gl(x, X2,x3) < 0 g2(xl, 4) < 0 (7) g3(xl,x2)< 0 g4(l,4)< 0 g5(X, X3) < 0 g6(x3) < 0 Assuming Ks = 2 the master cluster and the subclusters identified by Phase 1 is as follows: Update 1: MC - {x1}; SC1 - {gl,g3, gs5, g6; 2,x3}, SC2 - {g2,g4,x4}: Objective value = 5.5 Update 2: MC - {X,x2;g3 }; SC1 - {g2,g4,x4}, SC2 - {g, g5, g6,x3}: Objective value = 6.5 (8) Update 3: MC - {xl, x2, x3; gl, g3, g5, g6}; SC1 - {g2, g4, x4}: Objective value = 10.0 Update 4: MC - {x, x2, x3, x4;g l,g g 3, g 4, gs5, g6}: Objective value = 10.0 The best solution is obtained when a single linking variable xl is chosen, terminating Phase 1 after all variables have been considered. Approximate complexity analysis of Phase 1 when T is of the same order as N indicates a worst case in the order of N4 operations. if all operations are done sequentially. Of course. Phase 1 can be also implemented using a connected component identification algorithm commonly used in the area of graph theory (see, e.g., Deo 1990). 10

Local Search Local search techniques are based on single or multiple exchanges of nodes between clusters (Kemighan and Lin 1970). The number of linking variables is assumed fixed during the search. Two ordinary local search and one variable depth search methods are used here based on standard approaches. The methods mainly differ in how a local neighborhood is defined and searched (see, Papadimitriou and Steiglitz, and Murty, op. cit). At each stage the local search goes through cycles that consist of one or more node exchanges. In the ordinary local search only exchanges that lead to an improvement are accepted during a cycle, a restriction not used in the variable depth search. In the present implementation, a feasible solution is always preferred over an infeasible one. In case of a tie for the best feasible solution, the partition that contains the exchanged variable of the lowest index is chosen. If all solutions are infeasible then the best solution is selected as the one with the least relative size constraint violation. The variable depth search is more expensive than ordinary local search but tends to lead to better solutions. DEMONSTRATION EXAMPLES Application to three well-known optimal design examples are presented in this section: a pressure vessel, a caliper disc brake, and a speed reducer. Since we start from a GDP, the models used here are not exactly the same as those in the literature. Synthesis of ODP's from the GDP's is performed using (i) the integer programming model Eq. (6) and its branch and bound solution (ILP) - with no subcluster connectivity requirement, (ii) recursive graph partitioning without local search (RP), with local search (RPLS), and by complete enumeration or exhaustive search (ES) - where all combinations of linking variables, and subclusters are considered. Results for the different solution techniques are tabulated for three different values of the relative size constraint parameter Ks: 2, 1.5, and 1; It is assumed v,, = Ws = 1.0 throughout. The solution to the relaxed LP is also reported as it provides a global lower bound. 11

Design of a Pressure Vessel several authors, including Papalambros and Wilde (1988) and Sandgren (1990). The pressure vessel is made of a cylindrical body with hemispherical heads welded at the two ends. The design variables xl,..., X4 correspond to cylinder and head radius, cylinder thickness, cylinder length, and head thickness, respectively. Table 1 Pressure vessel general design problem GDP - Functional Description of the Design FDT Matrix Representation Criteria Representation xl I X2 X3 X4 gl (X, x2, x3) < 0 Cylinder mass limits 1 1 1i 0 g2(xl, X4) < 0 Hemisphere mass limits 1 0 0 1 g3(xl, x2) < 0 Stress limits in cylinder 1 1 0 0 walls g4(XI, x4) < 0 Stress limits in 1 0 1 hemispherical walls _ g5(xl, x3) < 0 Volume requirement 1 0 1 0 g6(x3) _ 0 Limit on cylinder length 0 0 1 [0 Table 1 summarizes the functional dependence table (FDT) assumed here. Note that detailed knowledge of the exact functional form is not required. The value of the objective function for the optimal synthesis model for different solution techniques and parameters are shown in Table 2. The numbers in parentheses indicate the optimal number of subclusters in each case. The best GDP structure identified for Ks = 2 is shown in Fig. 4. No functions exclusively depending on xl exist in this case. The sub-clusters obtained using the ILP formulation were connected components even though no such requirement was explicitly imposed. The objective function values and the best linking variables (not shown in the table) were the same for all cases except for Ks = 1 with RP. That solution has only one subcluster, because no feasible one with two or more subclusters could be found using only the RP technique. In contrast, two subclusters are identifiable when the RP technique is combined with any of the local search techniques (RPLS). The best block-angular structures for Ks = 1.0 and Ks = 1.5 are given in Eq. (9) and (10) below. The two sub-clusters SC1 and SC2 12

correspond to subproblems related to hemispherical head and cylinder body, respectively. This is the case for Ks = 2 as well. Ks = 1.0, objective value = 7.0: MC - {xl, x3; gs, g6}; (9) SC1 - {g2, g4; x4}, SC2 - {gl, g3; x2}: Ks = 1.5, objective value = 6.5: MC- {Ix, x2; g3}; (10) SC1 - {g2, g4; x4}, SC2 - {gl, g5, g6; X3}: Table 2 Pressure Vessel Problem Results Solution Techniques Ks = 2 K = 1.5 K = 1.0 RP 1 5.5 (2) 6.5 (2) 10.0 (1) RPLS 5.5 (2) 6.5 (2) 7.0 (2) ES 5.5 (2) 6.5 (2) 7.0 (2) ILP (B & B) 5.5 (2) 6.5 (2) 7.0(2) LP0 (2) 5.0 (2) 5.0 (2),, - " N X -> X X2 x3 \ X4 / 9 N- g l i i..................... ------- g3 1 100 — - - i —— ^ —---— i'....... -- -- X) gX j@ g X X g4 1^__^''-^ — ^ -'i. *'**^*g::::::4:0::::::::::::::::::: /00 0 1::::i:::::::::::::::::::::: i___________ _ 1______I 0 04 1 U par. I par. II(b) (a) Fig. 4 Pressure vessel: optimal GDP partitioning for Ks = 2 To compose the ODP several ways are possible. For example, for Ks = 2, one can choose {g1, g9} as the objective of each subcluster and compose an additive separable objective as discussed in K&P (1995). A hierarchically decomposed ODP can be similarly synthesized from Eq. (9, 10) for the cases of Ks = 1, KS = 1.5. 13

Design of a Caliper Disk Brake A disc brake for a passenger car based on the model proposed by Siddall (1982) is considered here. The brake has a caliper that holds a hydraulic cylinder and piston assembly. The GDP is shown in Table 3. The variables xl, x2,..., x6 correspond to lining center line radius, lining diameter, piston diameter, disc thickness, oil pressure, and outside disk diameter, respectively. Optimal solutions are shown in Table 4. Again the ILP formulation generated connected components. The objective function value increases as the Ks value decreases, since the problem is being more severely restricted. Table 3 General design problem for designing a caliper disc brake _________________________Design Criteria I gl (X3, x5, x1, x2) < 0 limit on stopping time g2(x3. X5, Xl, x2) < 0 limit on the braking force g3(X6, x4) ~< 0 volume of the disk g4(X5) - 0 j oil pressure limits g5(x3, X5, Xl, x2) <~ 0 lining pressure limit 6(x6, x4) < 0 limit on maximum temperature g7(x6, l, x2) < 0 i lining must not overhang disc g8(Xl x2) ~ 0 | lining must not interfere with the hub g9(xl, X3) _ 0 I cylinder must not interfere with the hub The best block-angular structure in the GDP is shown in Fig. 5 and described as follows: Ks = 2 and 1.5, objective value = 9: MC - {xi, x2; g8}; (11) SC1 - {g3, g6, g7; x4, x6}, SC2 - {gl, g2, g4, g5, g9; 3, X5}: Note that the criteria in SC1 relate to disc design, and in SC2 to the requirements for stopping the vehicle. From the clusters identified one could choose gl (stopping time) and g3 (volume of the disc) and compose an additively separable objective in the ODP. Criterion g8 that limits how close the lining can get to the hub may also be added to the objective with a suitable weight, if this is important for packaging. 14

Table 4 Caliper Disc Brake Problem Results Solution Method Ks = 2 Ks = 1.5 Ks = 1.0 All Techniques 9 (2) 9 (2) 10 (2) LP 7.5 (2) 7.5 (2) 7.5 (2) X-> x1 X2 X3 X5 X4 x6 g8 71 0 0 0 0 g ~ 1 1,.. 1 0;;. 1 1: 0. g4 l 0:1:,:00":":::1.;....... 1.......== 0 0 g32 0 0 0 0 0 g6 0 -0 0 0 1 1 g7? 1:...1 0 0 0......... Fig. 5 Optimal block-angular structure in the GDP For Ks = 1 the solution is as follows: Ks = 1, objective value = 10: MC - {xl, x2, x3; gs, g9}; (12) SC1 - {g3,g6,g7;X4,X6},SC2 - {gl,g2,g4,gs;X5}: The structure resembles closely those with the other values of Ks. In all cases then the engineering interpretation for a meaningful ODP is that the assembly or packaging requirements are specified by the master problem and two subproblems deal with design requirements for the disc and for stopping the vehicle. Design of a Speed Reducer Design of a speed reducer based on a model originally proposed by Golinski (1970) and later modified by Lee (1977) and Azarm et al. (1989) is considered here. The reducer consists of a gear-pinion pair mounted on shafts 1 and 2 respectively. Each shaft is supported by one bearing at each end. The system includes gear, pinion, shafts, and bearings enclosed in a housing. 15

Table 5 General design problem for speed reducer ___________ T'____________Design Criteria gl (X1, x2, X3) ~0 _ bending stress on the gear tooth g2(x1, X2, x3) ~ 0 compressive stress on the gear tooth g3(Xl, X2, X3, X6) ~ 0 weight of the pinion g4(xl, X2, X3, X7) -< 0 weight of the gear g5(x2, x3, x4, x6) -< 0 deflection of shaft 1I g6(x2, X3, X5, X7) ~ 0 deflection of shaft 2 g7(X2, x3, x4, x6) < 0 stress in shaft 1 g8(x2, X3, x5, x7) <0 stress in shaft 2 g9(x6, x4) <: 0 limit on the diameter of the shaft 1 gl1(X7, X5) < 0 limit on the diameter of the shaft 2 gl 1(X4, x6) <0 weight of shaft 1 g12(X5, x7) -< 0 weight of shaft 2 g13(X2, x3) --- 0 sum of the diameters of the gear and pinion g14(Xl, x2) - 0 upper bound on face width gI5(Xl, x2) <- 0 lower bound on face width g16(Xl) - 0; g17(Xl) < 0; bounds glg(X2) < 0; g19(x2) < 0; bounds g20(x3) <0; g21(x3) 0; bounds g22(x4) < 0; g23(x4) 0; bounds g24(x5) < 0; g25 (x5) < 0; bounds g26(x6) < 0; g27(x6) - 0; bounds g28(x7) ~- 0; g29(x7) <- 0; bounds The GDP shown in Table 5 follows the model version by Lee (1977). The variables xI, x2,..x7 are gear face width, gear tooth module, number of teeth on the pinion, distance between gear shaft bearings, distance between pinion shaft bearings, and shaft 1 and 2 diameters. Table 6 Speed Reducer Problem Results Solution Techniques Ks = 2 Ks = 1.5 Ks = 1.0 RP 25.0 (2) 25.0 (2) 25.0 (2) RPLS | 25.0 (2) 25.0 (2) 25.0 (2) ES 20.66 (3) 20.66 (3) 25.0 (2) ILP (B & B) 20.66 (3) 20.66 (3) 25.0 (2) LP 12.0 (3) 12.0 (3) 18.0 (2) Partitioning results are shown in Table 6. For Ks = 2 the best structure obtained by RP and RPLS are shown in Fig. 6(a) and by ES and ILP in Fig. 6(b). 16

_ Xl X2, X3 X5 X7 X4 X6 _ X X3 X6 X X4 X1 X Yg2 ___ 1 11 1 O I0 0 I0 i 0 0 _ O 0 0 g2 1 110 0110 0 0 00000 gi3 0 1 1 0 0 _ O O g9 1 0 0 0 0 0 91g4 1ll:0020.0 g21 o..'! 0 0 0100o _gl...110^^::.11...... 0.000........... 2l 0100000 gl6 10 0 0 0 0 0 g26 0 0 1 0 0 0 0 gl7 1 000 0000 g27 0O O O gl8 1 __0 0 1 O 0 g F28 0 0 0 1 0 0 0 [gi9 0 _10 01 g0 00 1.- g29 0O' O 0-I:: 1I: 0 0 0 g20 0.10: f0 0 90 g5 l1l1 0l 10 g21 0 1 0 0 0 0, g7.:::'0):,:: ~:i1i ~ii 0 1 10 1...........................::...::.................0... g4 11:-:1- 0 10 0 g92 001;oW? 1 Q01if; A-02 I So 0 0 M8 0111 i:10000;1:i O0010,: I 0 [0!i 0l 0 0 1 1 00 0 S0 ~ g22 o! o o00 0l~tifti\^':im 0o g1 O 0!2 0 0 0 1 1 0 0 O 0 0 0 0__:1 0ii^^ 0 i 0 g248 0 |01 0 0 0' 0g21 0 1 00:::^ ^ 0 7g 1. l 0 oI I 0 28 0 1 0 _____ g4 l 0;Nr~ 0 1 _g529 0;0: t0000 0 1 l000 0 li + g4_5 l _.:_.Ri- OV0:;::0::g i,:..: g3 L 10I: 0 | 0 10 0 I~_ 16 0 gg59 [1: ~i! [ g1.... L........0 o.. 1 1....0.E_ 0 I2g9 O 6:0 0:.0: 0 ] 0 1 07 g23 0 ~__ 100_1|| 01|| O gl2 0 0O;.:0 0::0 0 926 000 i~ 0 ~ 0 go2 1. 24 O 0 0'000~1 0 g207 O0 0 0 0 0'/: O; g25 O O ~: *........... Ii (a) (b) Fig. 6 Optimal block-angular structure in the speed reducer GDP: (a) RP result (b) ES result The subclusters obtained using ILP were again connected components. No feasible solution could be found for a number of subclusters higher than shown in Table 6. The block-angular structure in Fig. 6ta) represents the partition Ks = 2, objectivevalue = 25.0: MC - {x, x2x3; g, g2 g3.. g2l}; (13) SC1 - {g3, g5, g7, g9, gl,g22, g23, g26, g27; x4, x6} SC2 - {g4, g6, g8, glo, g12, g24, g25, g28, g29; X5, x7}: One may choose g3 (pinion weight), g4 (gear weight), and gi3 (gear box width) to compose the objective. The criteria in SC1 and SC2 relate to pinion and sub-assemblies, respectively. Since 17

it is not necessary to pick only one criterion from each cluster, one could compose an additively separable objective using {g3, gl } from SC 1, {g4, g12} from SC2, and g13 from MC. The structure in Fig. 6(b) obtained using ILP represents the partition: Ks = 2, objective value = 20.66: MC - {x2, x3, X6, x7; g13, g18, -*, g21, g26.**-, g29}; SC1 - {g5, g7, g9, gll, g22, g23; x4} SC2 - {gl,..., g4, g14,..., g17; x1 }, (14j SC3 - {g6, g8, glo, g12, g24, g25; x5}: Subclusters SC1, SC2, and SC3 correspond to design of shafts 1, the gear-pinion pair, and shaft 2, respectively. A meaningful additively separable objective can be composed choosing gl I from SC1, gl12 from SC3, {g3, g4} from SC2, and gl3 from MC. This is the same objective as one of those constructed from Eq. (13) above, but the decomposed ODP has one additional subproblem. The ILP branch and bound method found a better solution than RP or RPLS, but a meaningful synthesis of a decomposed ODP can be achieved with all methods. From the results obtained so far one might wonder whether the ILP formulation does result in subproblem clusters that are not connected. That is indeed the case. The ILP solution obtained when two subclusters were sought with Ks = 2 is Ks = 2, objective value = 24.5: MC - {x2, x3, x6, x7; gl3, g18.-, g21, g26.-., g29}; SC1 - {g5,..., gl2, g22,., g25; X4, X5 }, SC2 - {gl..., g4, g14..., g17; X }: (15) The graph representing SC1 consists of two connected components. As expected, the objective value in this case is lower than the best solution obtained (with two subclusters) when the subclusters were required to be connected (see Table 6). DISCUSSION Given the combinatorial nature of the optimal synthesis formulation, the techniques presented seek the best possible solution with a reasonable amount of computation. The nature of the clustering procedure requirements makes it difficult to use partitioning methods, such as those in 18

VLSI circuit design (Bryan et al. 1988). Seeking a "good" rather than an optimal solution is an appropriate goal. Indeed, the optimization model in Eq. (6) has limitations and subjective judgment is still needed. In this context, the following discussion points are in order. Synthesis of a decomposed ODP for a large system would in general require evaluation of the optimally decomposed ODPs generated for different values of Ks and of the weights wh, We. Multicriteria optimizatmization may prove useful, particularly if the designer does not have a good grasp of how to rank relative importance of the criteria. Weights could be assigned to different criteria and/or variables in situations where the design functions have to be evaluated using extensive simulations. Extensions to the present formulation and solution techniques will be required. The model presented cannot account for changes in the size of the clusters when composing the objective. Also, the best structure identified for synthesis from a given GDP is based on the associated functional dependence table (FDT) representing the system. The FDT is not unique, as manipulations and/or functional rearrangements of the GDP model can modify the FDT. The procedure is then sensitive to changes in te to changes in the FDT. However, several FDT's for the same design problem could be "averaged" to a single one using weights. The FDT need be stable rather than precise, since the synthesis process ultimately aims at organizing the design activity rather than at a computational advantage on the margin. In solving the ILP the number of subclusters K must be specified. The maximum value of K for which a feasible solution to the ILP exists is not known a priori. If the continuous LP is infeasible for a particular value of K then the associated ILP is infeasible. The Branch and Bound method used for solving the ILP can also discover infeasibility but the number of nodes in the branch and bound tree could become large. A good starting guess for the maximum value of K can be easier to obtain using the RP or RPLS techniques. The branch and bound solution provides a lower bound for RP and RPLS. and the continuous LP solution provides a lower bound for the ILP. Finally, the integer programming formulation may not be always solved using branch and bound in a reasonable time. Branch and cut methods (Papadimitriou and Steiglitz 1982) may be 19

proven more effective in larger problems. A discussion of alternate methods that may not guarantee a global optimum is available in Murty (1994). CONCLUSION A formulation for optimal decomposition synthesis and some general solution techniques have been presented. The designer can use the proposed methods to synthesize a suitable decomposed ODP. The integer programming formulation can be readily adapted to different user needs. Only two level primal decomposition synthesis has been discussed in this paper. In many problems it may be preferable to obtain a multi-level decomposed ODP instead of a two-level one or to use dual methods instead of primal ones. Developing formulations and solution techniques to address these requires further study. The ideas proposed here have been tested using small to medium size design problems. Their true value will be ascertained only after treating problems of a size sufficiently large to defy obvious intuitive problem partitions, and to test their relative merits. Coordinated solution of the decomposed problems will pose its own challenges. ACKNOWLEDGMENT This research has been partially supported by the Automotive Research Center at the University of Michigan, a US Army Center of Excellence in Modeling and Simulation of Ground Vehicles, under Contract No. DAAE07-94-C-R094. This support is gratefully acknowledged. The second author is also grateful to the Universities of Michigan and Patras for supporting his sabbatical leave for this research. REFERENCES Azarm, S., and Li. W., 1989, "Multi-level Design Optimization Using Global Monotonicity Analysis," ASME Journal of Mechanisms, Transmission, and Automation in Design, Vol. 113. No. 111, pp. 211-224. 20

Bryan, T.. and Lorenzetti, M., (eds.), 1988, Physical Design Automation of VLSI Systems, Benjamin/Cummings, San Francisco. Deo, N., 1990, Graph Theory With Applications to Engineering and Computer Science, PrenticeHall of India, New Delhi. Fourer, R., Gay, D., and Kemrnighan, B., 1993, AMPL: A Modeling Language for Mathematical Programming, The Scientific Press, South San Fransisco. Golinski, J., 1970, "Optimal Synthesis Problems Solved by Means of Nonlinear Programming and Random Methods," Journal of Mechanisms, Vol. 5, pp. 287-309. IBM, 1990, "Optimization Subroutine Library Guide and Reference," IBM Corporation, N.Y. Kernighan, B., and Lin, S., 1970, "An Efficient Heuristic Procedure for Partitioning Graphs," Bell Systems Journal, Vol. 29, pp. 291-307. Krishnamachari, R., and Papalambros, P., 1995, "Hierarchical Decomposition Synthesis in Optimal Systems Design," ASME Journal of Mechanical Design, (in review). Lee, T., 1977, "Weight Minimization of a Speed Reducer," ASME Paper No. 77- DET 163. Michelena, N., and Papalambros, P., 1994. "A Network Reliability Approach to Optimal Decomposition of Design Problems," ASME Journal of Mechanical Design, Vol. 117, No. 3, pp. 433-440. Michelena, N., and Papalambros, P., 1995. "Optimal Model-Based Partitioning of Powertrain System Design," S. Azarm et al. (eds.), Advances in Design Automation, Boston, Vol. 1, pp. 165-192. Murty, K., 1994, Operations Research: Deterministic Models, Prentice-Hall, Inc., Englewood Cliffs, New Jersey. Papadimitriou, C., and Steiglitz, K., 1982, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Inc., Englewood Cliffs, New Jersey. Papalambros, P., 1995, "Optimal Design of Mechanical Components and Systems," ASME Journal of Mechanical Design, 50th Anniversary of the Design Eng.Aeering Division Issue, Vol. 117, pp. 5562. Papalambros, P., and Wilde, D., 1988. Principles of Optimal Design: Modeling and Computation, Cambridge U. Press, New York. 21

Sandgren, E., 1990, "Nonlinear Integer and Discrete Programming in Mechanical Design Optimization," ASME Journal of Mechanical Design, Vol. 112, pp. 223-229. Siddall, 1982, Optimal Engineering Design, Marcel Dekker, Inc., New York. Wagner, T., 1993, A General Decomposition Methodology for Optimal Systems Design, Doctoral Dissertation, Department of Mechanical Engineering and Applied Mechanics, The University of Michigan, Ann Arbor, MI. Wilde, D., 1978, Globally Optimal Design, Wiley, New York. 22