HIERARCHICAL DECOMPOSmON SYNTHESIS IN OPTIMAL SYSTEMS DESIGN Ramprasad S. Krishnamachari Graduate Student and Panos Y. Papalambros Professor Technical Report 95-16 August, 1995

HIERARCHICAL DECOMPOSITION SYNTHESIS IN OPTIMAL SYSTEMS DESIGN Ramprasad S. Krishnamachari Graduate Student and Panos Y. Papalambros Professor Design Laboratory Department of Mechanical Engineering and Applied Mechanics The University of Michigan Ann Arbor, Michigan ABSTRACT Optimal design of large systems is easier if the optimization model can be decomposed and solved as a set of smaller, coordinated subproblems. Casting a given design problem into a particular optimization model by selecting objectives and constraints is generally a subjective task. This article describes how such a subjective selection can be made so that the resulting optimal design model can be directly partitioned into an appropriate decomposed form. This process is termed decomposition synthesis. A particular methodology for synthesizing hierarchically decomposed optimal design models is presented together with examples. August, 1995 1

INTRODUCTION Solving an optimal design problem by decomposition methods involves partitioning a given optimal design problem (ODP) into several smaller problems and coordinating their solutions to obtain the solution to the original problem. The process of identifying and executing appropriate partitioning of a given ODP is referred to as Decomposition Analysis (Wagner 1993, Wagner and Papalambros 1993a, 1993b). Decomposition of a design problem that has been cast in an optimization model form is linked to the mathematical structure of the already selected objective and constraint functions. For example, if the objective is expressed as a sum of terms, then the solution to the problem using a decomposed form is enhanced. In general, casting a given design problem as an optimization model is subjective. Therefore, one may seek to synthesize an ODP by defining the appropriate model functions so that the resulting model can be directly partitioned and solved in a decomposed form. Decomposition Synthesis is defined as the process of synthesizing a decomposable ODP from a general design problem. Successful decomposition synthesis will allow an ODP of identified decomposition to be composed and solved by a desired decomposition method. This is especially useful in the optimal design of large systems (Papalambros 1995). A general design problem (GDP) is modeled as Find x E F subject to h(x, p) = 0 (1) g(x, p) < 0 where h, g are vectors of design criteria represented by equalities and inequalities that are functions of the design variables x and parameters p, and F is the set constraint on the design variables. The GDP is transformed to an ODP by selecting one or more design criteria from above and composing a scalar objective, namely, Minimize f (x, p') subject to h(x, p) = 0 (2) g(x, p) < 0 andxe F 2

where p' is a vector of parameters that includes any weights used in composing the scalar substitute objectivef. In general, the objective is a vector function which must be scalarized into a scalar substitute form so that the methods of mathematical programming can be used. For q example, if there are q objectivesfi(xi, p'), i = 1,..., q, then fx, p')= ~ fi (xi, p') with xi being a i=l 1 subvector (any vector defined from the components of a given vector) of the design vector x. See Athan (1994) for further details on scalar substitute functions. The functional representations in Eq. (1) and (2) can be converted to equivalent matrix and graph representations: the functional dependence table (FDT) and a bipartite graph or a hypergraph (Wagner and Papalambros 1993a, Michelena and Papalambros 1995a). Functional, matrix, and bipartite graph representations for an example GDP are shown in Fig. 1. Note that a graph G is bipartite if its vertex set V can be divided into two disjoint subsets VI and V2 such that every edge in G joins a vertex in V1 with a vertex in V2 (Deo 1990). Representation of an ODP is similar, with each termfi in a scalar objective represented by a vertex in the graph or a row in the FDT. All graphs are assumed to be connected. (A graph G is connected if a path exists between every pair of vertices.) g;hxI x2x3g gl 1 1 0 X g2(x1,x2) <~0 g2 1 1 0 g3(X2'x3)-<O g3 0 1 1 hi(x3)=0 hi 0 0 1 (a) (b) (c) Fig. 1 Alternate Representations of a General Design Problem Decomposition methods for solving ODPs can be classified into hierarchical and nonhierarchical, and further into primal and dual methods. A given problem may be decomposed and/or solved in more than one way. A recent review and analysis of the decomposability of optimal design problems is given in Wagner (op. cit.). Rigorous partitioning techniques for decomposition analysis have been presented by Michelena and Papalambros (1994, 1995a, b). 3

The decomposition synthesis methodology proposed below makes use of the partitioning tools of decomposition analysis. The methodology consists of two main steps. First, a "block-angular" or a "dual-angular" structure in the GDP is found using a graph partitioning method. Next, an ODP is composed with an identified hierarchical decomposition based on the structure found for the GDP. The next section formalizes some basic concepts for hierarchical and nonhierarchical decomposition. A methodology for hierarchical decomposition synthesis is then presented followed by examples illustrating its application. HIERARCHICAL AND NONHIERARCHICAL DECOMPOSITION A decomposition method is characterized by the mathematical structure that defines the subproblems and by the coordination strategy that connects them in the solution process. Before describing a synthesis methodology it is necessary to define rigorously what we mean by hierarchical or nonhierarchical decomposition of an ODP. In this section we present definitions that can be applied to both primal and dual formulations. Primal Decomposition The primal formulation of the ODP is the functional representation in Eq.(2). Assuming a summation objective (expressed as sum of terms) as in Eq. (2) we have q minimize f(x, p)= A fi(xi, p') (3) xeF i=l subject to: gi(x, p) < 0 j = 1,..., J hm(x, p) = 0 m =,..., M. Consider the two sets C, X defined as C = {(C1, C2,..., ct,..., CT), X = {X1, X2,..., Xi,..., XN} (4) 4

where each gji, h., and each fi term in the objective is represented by a member ct in the set C. The set C is composed of T functions where T = (q + J + M). Each design variable is represented by an xi in the set X. Definiaion 1: A decomposition of an optimal design problem into K subproblems is the ordered triple Pi = (Zi, Vi, Wi), V i = 1,..., K, where Zi is the set of design variables to be optimized in problem i, Vi is the set of functions in problem i, Wi is the set of variables that the functions in the set Vi depend on, and Zi, Vi, Wi satisfy the following: Zi (: 0) X, VicC, Wi C X (5) u Zi = X, uVi=C i i Zi nZj =0, Vi r Vj =0, V i:j, and i, j= 1,...,K with each function in the set Vi dependent on one or more of the design variables that are elements of the set Zi. Definition 2: The input to problem i from problem j is defined by the set iij, where Iij = Wi n Zj, j i. (6) Definition 3: The linking variables of two subproblems i and j are defined by the set Lij = Lji where Lij = ij U ji j i. (7) Definfion 4: The linking variables in a decomposition are defined by the set L,, where Lv= u Lij. (8) i J;i * In a directed graph representation of an ODP (Deo 1990, Wagner 1993) the decomposed problems are the nodes and the inputs are the directed edges. 5s

Definition 5: A directed graph G is said to be an out-tree or an arborescence (Deo op.cit.) if (a) G contains no directed circuit or semicircuit, (b) there is precisely one vertex of zero in-degree, the root of the out-tree. Definition 6: A decomposition of an optimal design problem is hierarchical (nonhierarchical) if its directed graph representation is (not) an out-tree (Figs. 2, 3). Fig. 2 Hierarchical decomposition graph Fig. 3 Nonhierarchical decomposition graph As an example, consider the ODP minimize X1 + X1X2 + X2X3 + X3 (XlIx2.X3) (9) fl = x1 f2 = XlX2,f3 = X2x3, f4 = X3 subject to: gl = X1X2X3 - 8 < O g2 = - (Xl + x2 + X3 - 2) < O g3 = - (Xl) g4 =x1- 4 g5 = -(x2) < 0 g6 = x2 - 4 g7 = -(x3)<0 g8 = x3 - 4 < 0. In a hierarchical decomposition, Fig. 4(a), input flow is unidirectional (from the master problem to the subproblems) and linking variables are (xl, x3); in a nonhierarchical one, Fig. 4(b) inputs are bi-directional and (xl, x2, x3) link the decomposed problems. Dual Decomposition The Lagrangian dual problem of the primal ODP in Eq.(2) is defined as (e.g., Bazaraa et al. 1993) maximize {min L =f(x, p') + jT h(x, p) + T g(x, p)} (10) (p; XO0) x 6

Master Problem Problem 1 Functions: Functions: f =xl, f4=x3 f =xl, f4=x3 3 = - Xl, g4 = Xl - 4 g2 = - (Xl + X2 + x3- 2) g7 = - X3, g8 = x3 - 4 g3 = - X1, g4 = X1 - 4 g7 = - x3, g8 = x3 - 4 Variables: x1, x3 Variables: x1, x3 X1,X3 X xl, x3 X2 Subproblem Problem 2 Functions: Functions: f2=X1X2, f3=x2x3 f2=X1X2, f3=x2x3 g1 =X1X2X3 8 g1 =x1x2x3 -8 g2 = - (X + X2 + X3- 2) g5 = - X2, g6 = X2 - 4 Variables: x2 Variables: X2 (a) (b) Fig. 4 (a) Hierarchical, and (b) nonhierarchical decomposition of the example formulation where l, X (vectors) are the Lagrangian multipliers or dual variables. Under convexity assumptions and suitable constraint qualifications, the primal and dual problems have the same optimal objective values. In such cases it may be advantageous to apply decomposition methods on the dual problem instead of the primal. Definitions of hierarchical and nonhierarchical decomposition remain the same in the dual space, except that the set X will include both primal and dual variables, and ct in general will be a function of both primal design and dual variables. In the definitions for the dual, the primal objectivef is replaced by the Lagrangian L, andfi by Li. A simple two-level hierarchical decomposition of the dual is shown in Fig. 5. Problem A is the master problem defined in the dual space, linking variables are the dual ones, and Problem B is the subproblem defined in the primal space. If Problem A is not "pure," i.e., primal variables must be included in it, then the dual decomposition will become nonhierarchical. 7

Problem A variables: (k, At) I, t - linking variables Problem B f(x, p') T h(x, p) XTg(x, p) variables: x Fig. 5 Hierarchy in dual decomposition Note that instead of including all constraints in the Lagrangian, some of them may be left out and treated separately in the primal. Then the dual variables will correspond to linking constraints that are relaxed when solving the problem (Lootsma 1990). Also, a Lagrangian separable in the primal will allow partition into several subproblems. These cases are illustrated further in the example section. METHODOLOGY FOR HIERARCHICAL DECOMPOSITION SYNTHESIS A method for hierarchical decomposition, primal or dual, can be applied when the ODP model has the exact form required by the relevant coordination strategy. A methodology for decomposition synthesis aims at transforming a GDP into the desired form of a decomposable ODP. Primal Decomposition Synthesis Here we consider ODPs that can be solved by primal hierarchical decomposition methods. Assume the decomposed model has a master problem and q subproblems. Then the original GDP must be cast into the block-angular structure shown in Fig. 6 and Eq. (11). go(Xo) < 0 ho(xo) = 0 (1 la) gi(xo, xi) < 0 h,(xo, xi) = 0 i = 1,..., q (1 lb)

g, h Fig. 6 Block-angular structure in the GDP Identifying Structure The required structural form is sought using graph partitioning methods applied to the bipartite graph representation of the GDP. As linking variables (vertices) xO are removed, the functions that depend exclusively on these variables correspond to go, ho in Eq. (1 la). The corresponding function vertices will be isolated after removal of linking variable vertices from the graph. (A vertex is isolated if it is not connected to any other vertex by an edge.) In Fig. 7(a) the FDT of a general design problem is shown. In the bipartite graph, Fig. 7(b), the set (X4, X5) is selected as linking variables. Removing the corresponding vertices leaves g3 and gs5 isolated. Each connected component in the remaining portion of the graph that excludes the vertices already identified with Eq. (1 la) must have the structure of Eq. (1 lb). (A graph is a connected component if a path exists between every pair of vertices in that graph. An isolated vertex is also a connected component but with just one vertex.) Fig. 7(c) shows the resulting partitions A = (gl, g4, xl, x2), B = (92, g6, X3, X6). The new FDT shown in Fig. 7(d) is blockangular. - i-. _- - 0Eq._(lla) X2 X3X?IX:~-..]( g h xll x21x3lx gWWiooioW gAA)~~~~~ | I 0 1...... g.0............. go1W ae 3 air 1813 1X gl0o)iooo0 101 I 10 Eq. (llb) g1 1 0 0 (a) (b) (c) (d) Fig. 7 Steps in identifying block-angular structure in the GDP Identifying Structure~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~.......

Algorithms for identifying connected components in a graph can be used to find partitions as in Fig. 7(c) for a particular choice of linking variables. Correct choice of linking variables is a key decision as studied in Decomposition Analysis (Wagner 1993, Michelena and Papalambros 1995a, b). Also, partitions such as A and B in Fig. 7(c) need not be the only way the graph can be partitioned to fit the particular structural form. For example, one could combine A and B into a larger single cluster and still produce the required structure. The resulting clusters, however, may not be internally connected and hence not always acceptable (Wagner op.cit.). Identifying a suitable structure for synthesis must include acceptability criteria determined by the user. Composing the ODP After identifying the block-angular structure in the GDP, an ODP can be synthesized by creating a summation objective function as follows: (i) select a function from the block { go, xO ), Eq.(l la); (ii) select a function from each block i, i =,..., q, Eq.(llb); (iii) add all selected functions with appropriate weights w,, i = 0,..., q; this is the objective function; (iv) append all constraints to the objective to complete the model. The resulting structure will have the form of Eq. (12) and Fig. 8. q minimize f =fo(xo,Wo)+ fi(xo,xiwi) (12) X0, Xi i=l subject to: go(xo) < 0, ho(xo) = 0 gi(xo, xi) < 0, hi(xo, xi)= == 1,.., q. This ODP can be decomposed into a master problem in the linking variables xo and q subproblems in the local variables xi. A hierarchical coordination method such as those proposed by Kirsch (1981) or Azarm (1988) can be used to solve it. The functions selected need not be weighted linearly; exponential or other nonlinear weighting forms can be used (Athan 1994). 10

XO XI X2 ~ ~ Xq Fig. 8 Hierarchically Decomposed ODP Not all terms need be present in Eq. (12). For a given choice of linking variables, no functions may exist in the set corresponding to Eq. 11 (a). Also, objective function terms for composing the ODP may be selectable only from the set corresponding to Eq. 11 (a) as required in the formulations used by Sobieski (1982), and Haftka (1984). The objective composed in the above two cases will not include all terms inf of Eq. (12). Dual Decomposition Synthesis To apply dual hierarchical decomposition methods we must identify a dual-angular structure in the GDP, as in Eq. (13) and Fig. 9. q Zgji(xi) < 0 j = (J- Cg)... J (a) i= q i=l gj(xj) 0= 1,..., q (c) (13) hm(xm)= 0 m= 1,..., q (d) Here Cg and Ch are the number of coupling inequality and equality functions identified in the GDP, respectively. Identification of structure in the GDP is similar to the primal case. The graph is partitioned by removing vertices that correspond to functions.

X1 X2 x3 ~ ~ Xq x_ X2 X3 x._ L —-------- I - g, h g, h Fig. 9 Dual-angular structure in the GDP Fig. 10 Hierarchically decomposed ODP However, it is necessary that these linking functions be separable in the variables xi of the independent connected components to ensure separability in the dual objective. Thus, a particular partitioning of the GDP is acceptable only if the above separability criterion is met. Given a dual-angular partitioning, a hierarchically decomposed ODP solvable by dual methods can be created by constructing an appropriate objective, as in the primal case, namely, q minimize f= I fi (xi,wi) (14) i=l 1 subject to the constraints in Eq. (13). The resulting FDT will have a structure as in Fig. 10. The Lagrangian of this formulation is additively separable in xi and the problem can be solved with dual decomposition methods, e.g., Lasdon (1968). For a linear model the Dantzig-Wolfe (1960) method can be used. EXAMPLES The methodology for primal or dual decomposition synthesis is demonstrated below with some simple examples. Example 1: Pressure Vessel Design A GDP for pressure vessel design based on a model in Wilde (1978) is given in Table 1. The vessel is made of a cylindrical body and is welded on both sides by hemispherical heads. 12

Table 1 Pressure vessel problem [Example 1] Functional Description of the Design Matrix Representation Requirements Resentation Xi X2 X3 X4 gl(xl, X2, X3)< O Cylinder mass limits 1 1 1 O 82(X1, X4) ~ 0 Hemisphere mass limits 1 0 0 1 g3(X1, X2) O Stress limits in cylinder walls 1 1 O O g4(x1, x4) 0 Stress limits in head walls 1 0 0 1 g5(X1, X3) ~0 Volume requirement 1 O 1 O 86(x3) ~. O Limit on cylinder length 0 1 0 The variables xl,..., X4 are cylinder and head radii, cylinder thickness, cylinder length, and head thickness, respectively. Decomposition into a master problem and two subproblems is sought. If xl is chosen as the linking variable and removed, the bipartite graph of the GDP partitions into two connected components, partitions I and II, Fig. 11(a). A block-angular structure is identified, Fig. 1 l(b), with no function terms identified with Eq. 1 1l(a), and xo = xl, xl = (X2, X3), and x2 = X4. Functions gl, g2 are selected for a linearly weighted objective, i.e., minimize the volume of the cylinder and heads. The synthesized ODP, Fig. 12, is now ready to be decomposed into a master problem in the linking variables xl, and two subproblems in the local variables (x2, X3) and X4. Instead of gl, g2 one can use the stresses in the cylinder and heads to compose the objective. X-> XI X2 X3 X4 1 1 0 93 0... 82~~~ ~~ 0 0~~~~~5~, ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~~~~........ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~~~...... partition - partition-, - II 9 0 0 (a) (b) Fig. 11(a) Partitioning of the GDP4, (b) Block-anguar GDP [Example 1 13

minimize f=f[=wl g]+f2[=w g] X2 Xg2] 3 X4 ~~~~~(xi~~21.. i.......... subject to: f2 0 0 gl(Xl, x2, x3) < 0 g2(xl, x4) < 0 gS g3(xl,x2) ~0 g4(Xl,x4) <0 g5(x, x3)<0 g6(x3)<0 g2 |',!!i g4i:!i 0 0..3.i.'1........... (a) (b) Fig. 12 Synthesized ODP: (a) Functional form, (b) Matrix form [Example 1] Example 2: Resource Management Consider the GDP developed based on a problem in the area of resource management of an economic system (Wong 1970, appearing as test problem #113, in Hock and Schittkowski 1982), Eq. (15). gl(Xl, X2) < 0 g2(X3, X4) < 0 g3(X5, X6) < 0 g4(X7, X8) < O gS(X9, Xlo) O0 g6(X1, X2, X7, X8) 0 g7(Xl,X2, X9, XlO) 0 g8(Xl,X2, X3,X4) <0 (15) g9(xl, x2, x3,x4) glo(x1, X2, X56) <0 gll(Xl, X2. X9, Xlo) < 0 hl (x, X2, X7, 8) = h2(x1, X2, Xs ) = 0 We seek a decomposition with a master problem and four subproblems. Repeating the steps of previous example we obtain the ODP in Fig. 13. The set of linking variables is (x, x2 ) and (g1, gg, go, 8g, 87) is the set of functions chosen to compose the objective. The synthesized ODP is decomposable into a master problem in the linking variables {xl, x2}, and four subproblems in the local variables (x3,X4}, {xs5,x6}, (X7, X8}s, {x, x9lo}. 14

1. 0 0 0 0 00 Ag2.10Ot010l 0l 0 0 0......................... go2 0.i. 0 O 0 0 iiiiiiiiiii 0 0 0 0 O 0 E am l...........o...... the tank is releasedo o aicntrlld fshon o te oombfreo o o o pio o so o o Ois O s gi o o......... O O. O.................0 Fig. 13 Synthesized ODP - Matrix Form [Example 2] Examaple 3: Solar House Heating System This GDP is based ction a model Descproposed by Wildthe (1978) and is presenrited in Table 2.3 456 g2xSolar energy collected by a s0 heet inpucollector is used to heat water stored in a tank. The heat from (the tank is released in a controlled fashion to the rooms by 0 0 0 0 0 g4(x4) 0 li mits on wall insulation 0thickness X, and weather stripping 0 ngth x1, so0 0 gs(xs) < 0 limits on roofinsulation 0 0 0 0 1 0 g6(x2, X3) < wall area of the water tank 0 1 1 0 0 0 g7(xl, x2, x3) < 0 heat storage capacity of water tank 1 1 1 0 O 0 g8(X6) ~0| limits on weather stripping length 0 0 0 0 0 We seek an ODP that can be decomposed hierarchically into a master problem and four subproblems in the dual space. We must first find coupling or linking functions. Selecting ({gl, 15

g2 as the coupling functions and removing them partitions the bipartite graph of the GDP as in Fig. 14(a). This partition would be acceptable if (g, g 2 are additively separable in the partitioned variables xi, namely, [ {xl, x2, X3), {X4), {xs5), and (x6)]. From the original model in Wilde (op. cit.), gl is additively separable in the functions (g1l(xl), g12(x2, x3), g13(x4), g14(X6)), and g2 is additively separable in the functions (g21(xl), g22(X4), g23(X5), g24(X6)). The current partitioning is therefore acceptable. The dual-angular structure in the GDP identified is shown in Fig. 14(b). One could choose {g3, g4, gS, g8) from the partitions and compose an ODP as shown in Fig. 15, to minimize the weighted sum of collector area, wall insulation, roof insulation, and weather stripping length. IV 1e II > xl X2 X3 X4 X5 X6 Ig3 iiiiiiil iii. iii iiiii. 0 0. Xi. _: ______ _ III --. g7 0 0 0 0 0 0 0 0 0 0 1.... III 8 O O O O O (a) (b) Fig. 14 (a) Partitioning of the GDP, (b) Dual-angular GDP [Example 3] minimize f = f1[= w1 g3]+ f2[= w2 g4] + f3[= W3 g5] + f4[= W4 g8] f O O...'................ 0 0. o...............,,,. g~(xi, X2, X3, X4, X5, X6)0 ~ 0 f4' - -.8., 0 - 0.....al g2(x1, X0, X50 X6)0 ~ 0 0 0o............ g3(X1) < 0 g4(X4) < 0I gs5(x5) < 0 g6(X2, X3) < 0 ~g4 0 0 0 0. - g7(1l, X2, X3) 0 g8(x6) O - 0 ~ 0 ~1 (a) (b) Fig. 15 Synthesized ODP: (a) Functional form, (b) Matrix form [Example 3] 16

Example 4: Management of Water Resources Consider the GDP developed based on a problem in the area of water resource management proposed by Sung (1978) (cited in an example problem by Haimes et al., 1990, exercise.# 1, section 9.5), Eq. (16). We seek an ODP that is decomposable into a master problem and three subproblems in the dual. gl(xl, x2) < 0 g2(x3, X4) <0 g3(X5, x6, X7) 0< g4(x2)< 0 g5(x3, X4) < 0 g6(x4, X7) < 0 g7(xl) < 0 g8(X2)< g9(x3) 0< glo(x4) < 0 gll(xs) < 0 g12(X6) < 0 (16) g13(X7) < 0 hi (xl, x2, x3) = 0 h2(x65, X6, 7) =0 All equality and inequality functions are linear and so additively separable in each variable. A hierarchically decomposed ODP obtained after going through steps as in the previous example is shown in Fig. 16. Coupling functions are {h1, g9}, and (gl..., g3} is the set of functions chosen to compose the objective. X-> Xl X2 X3 X4 X5 X6 X7 f2 0.1.?!!0 0 0 g l:~',','~i o o. o::':j!'',',ii,.' o o o o o.. Fg 1 Synthe.sizediODP:iMatrix form [Example4...................1 g 0 0 0 1 0 0 0 97.:.:: O O O O...O.O.t........., O O O h2 0 0 0 0 o 0o 0 0,,1 h~2 o o o o....'......:, 812 0 0 0 0 > Fig. 16 Synthesized ODP - Matrix form [Example 4]

CONCLUDING REMARKS In the methodology for hierarchical decomposition synthesis presented here the GDP partitioning to achieve a specific decomposition goal is not unique. There may also be several decomposition goals that need be explored and compared. Studying these alternatives is itself an optimization problem. Methods for "optimal" decomposition synthesis are currently under investigation. The selection of a particular decomposition method depends on number of factors, and the following guidelines may be useful. Primal (dual) methods would be preferable if (a) the GDP can be partitioned with a small number of linking variables (functions), (b) constraint feasibility need (not) be maintained throughout the iterations, and (c) the GDP has a small (large) number of variables and a large (small) number of constraints. A hierarchically decomposed ODP for solution by both primal and dual methods can be synthesized from a GDP by introducing new variables, especially for highly coupled GDPs (Wismer and Chattergy 1978). The disadvantage is increase in the size of the problem. Such cases can be handled also by the methods presented here. As the GDP becomes more coupled, nonhierarchical decomposition may be the only way to partition the problem without increasing its size. It is not clear what should be the basis for synthesis in such a case. Synthesizing an ODP that can be decomposed into a specified number of q subproblems may not be always possible. Also, a q value may not be determinable a priori. In such cases GDP partitions for different values of q must be studied and a suitable q value selected. Only a two-level hierarchical decomposition synthesis was discussed here but the methodology can be extended to multi-level synthesis. Also, instead of a scalar substitute objective, one could treat the individual objectives as components of a vector and solve the vector minimization problem with a variety of techniques. In conclusion, the proposed synthesis approach is an attractive, more systematic way to formulate and solve large optimal system design problems. The resulting optimization model need not be solved necessarily by decomposition methods. 18

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. REFERENCES Athan, T., 1994, A Quasi-Random Methodfor Multicriteria Optimization, Doctoral Dissertation, Department of Mechanical Engineering and Applied Mechanics, University of Michigan, Ann Arbor. Azarm, S., Li, W., 1988, "A Two-Level Decomposition Method For Design Optimization," Engineering Optimization, Vol. 13, pp. 211-224. Bazaraa, M., Sherali, H., Shetty., C., 1993, Nonlinear Programming: Theory and Algorithms, Second edition, Wiley, New York. Dantzig, G., and Wolfe, P., 1960, "Decomposition Principles for Linear Programming," Operations Research, Vol. 8, pp. 101-111. Deo, N., 1990, Graph Theory With Applications to Engineering and Computer Science, PrenticeHall of India, New Delhi. Haftka, R., 1984, "An Improved Computational Approach for Multilevel Optimum Design," Journal of Structural Mechanics, Vol. 12, No. 2, pp. 245-261. Haimes, Y., Tarvainen, K., Shima, T., Thadathil, J., 1990, Hierarchical Multiobjective Analysis of Large-Scale Systems, Hemisphere Publishing, New York. Hock, W., and Schittkowski, K., 1981, Test Examples for Nonlinear Programming Codes, Lecture Notes in Economics and Mathematical Systems, No. 187, (ed.) Beckman, M., and Kunzi, H., Springer-Verlag, Berlin. Kirsch, U., 1981, Optimal Structural Design, McGraw-Hill, New York. Lasdon, L., 1968, "Duality and Decomposition in Mathematical Programming," IEEE, Trans. of Systems Science and Cybernetics, Vol. SSC-4, No. 2, pp. 86-100. Lootsma, F., 1990, "Exploitation of Structure in Nonlinear Optimization," Parallel Computing, Vol. 6, pp. 31-45. 19

Michelena, N., Papalambros, P., 1994, "A Network Reliability Approach to Optimal Decomposition of Design Problems," Advances in Design Automation, ASME, Vol. 2, pp. 195-204. Michelena, N. and Papalambros, P., 1995a, "A Hypergraph Framework to Optimal ModelBased Decomposition of Design Problems," Technical Report UM-MEAM 95-02, Department of Mechanical Engineering and Applied Mechanics, University of Michigan, Ann Arbor, Michigan. Michelena, N. and Papalambros, P., 1995b, "Optimal Model-Based Decomposition of Powertrain System Design," J. of Mechanical Design, ASME, to appear. Papalambros, P., 1995, "Optimal Design of Mechanical Engineering Systems," J. of Mechanical Design, and the J. of Vibration and Acoustics, ASME, Vol. 117, pp. 55-62. Sobieszczanski-Sobieski, J., 1982, A Linear Decomposition Method For Large Optimization Problems - Blueprintfor Development, NASA TM 83248, Langley, Hampton, VA. Sung, K., 1978, Coordination of Overlapping Hierarchical Water Resources Systems, Ph.D. Dissertation, Case Western Reserve University, Cleveland, Ohio. Wagner, T., 1993, A General Decomposition Methodology for Optimal Systems Design, Ph.D. Dissertation, Department of Mechanical Engineering and Applied Mechanics, University of Michigan, Ann Arbor, MI. Wagner, T., Papalambros, P., 1993a, "A General Framework for Decomposition Analysis in Optimal Design," Advances in Design Automation, ASME, DE-Vol. 65-2, pp. 315-325. Wagner, T., Papalambros, P., 1993b, "Implementation of Decomposition Analysis in Optimal Design," Advances in Design Automation, ASME, DE-Vol. 65-2, pp. 327-335. Wilde, D. J., 1978, Globally Optimal Design, Wiley, New York. Wismer, D., Chattergy, R., 1978, Introduction to Nonlinear Optimization: A Problem Solving Approach, North-Holland, New York. Wong, 1970, Decentralization Planning by Vertical Decomposition of an Economic System: A Nonlinear Approach, Ph.D. Dissertation, National Energy Planning, University of Birmingham, Birmingham, UK. 20