Igmh§fi I“?!‘>2,;“‘."¢‘";‘.;V.JI 3‘ .‘l\'.",",:"v‘.;" 'r'. .V.‘v ‘. ..‘ .- 3 - . J- ,~_ ‘ I...‘ I I . 4 ’fi(' “1.2.13 377"” '.',',‘_ v‘>-"'1"“.','.Z.' A - ., ,. .. . II .' N , _ I . A DISCRETE FORMULATION 0F MINIMUM DOST DESIGN OF FRAMED STRUCTURES I Thesis for the Degree of Ph. D. MICHIGAN STATE UNIVERSITY HYO NAM CHO 1972 ....... LIBRAR Y Michiga n State University [fifiblfi This is to certify that the thesis entitled A DISCRETE FORMULATION OF MINIMUM COST DESIGN OF FRAMED STRUCTURES presented by Hyo Nam Cho has been accepted towards fulfillment of the requirements for Ph.D. demon] Civil Engineering 74/4m44%4/ Date May 15, 1972 0.7639 ABSTRACT A DISCRETE FORMULATION OF MINIMUM COST DESIGN OF FRAMED STRUCTURES By Hyo Nam Cho A discrete formulation of the optimum design of framed structural systems is developed and the methods of solution are presented. The design problem is the alloca- tion of member sizes from a catalog of commercially avail— able sections in such a way as to minimize the cost of a structure within the working stress constraints and/or deflection constraints. Multiple sets of static service loads are considered in the formulation. Instability is not considered. A matrix set of nonlinear working stress constraints is derived by the stiffness method, following the network- topological approach and incorporating the working stress interaction conditions. This nonlinear constraint set is successively linearized using the Taylor series expansion. The linearized set of constraints is transformed into the constraint set of a successive binary programming problem. The formulation is greatly enhanced by evaluating the Jacobian of the constraint vector function and by eliminating formal inversion of the stiffness matrix. Hyo Nam Cho The objective function of the binary programming formulation for minimum cost design is obtained by associa- ting estimated unit costs of sections with binary variables. The implicit enumeration method, developed by Geoffrion, is considered to be one of the most efficient algorithms for binary programming and, therefore, is chosen as the basic algorithm for this study. An improved algo- rithm is deve10ped which utilizes the multiple choice constraints characteristic of discrete structural design. A two-phase formulation consisting of initial continuous design and main discrete design is suggested. Approximate continuous initial design is intended to yield a good starting solution for the main discrete design. An approximate version of the plastic mechanism method which considers only the principal collapse mechanism is preferred for initial design. This is formulated as a linear program- ming problem which minimizes the weight of the structure. A computer program is developed for the implementa- tion of the above formulations and algorithm. Example applications include a one-story, two-bay frame, a two-story, one-bay frame, and a two-story, three-bay frame. A DISCRETE FORMULATION OF MINIMUM COST DESIGN OF FRAMED STRUCTURES By Hyo Nam Cho A THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Civil Engineering 1972 ACKNOWLEDGMENTS The author wishes to express his most sincere gratitude to Dr. Frank J. Hatfield, the author's major professor, for his guidance, encouragement, interest, and painstaking corrections of this thesis. The author is especially indebted to Dr. J. 5. Frame for his valuable suggestions on mathematical derivations, and to Dr. W. A. Bradley for his critical comments on the assumptions of the study. The author also wishes to extend his thanks to Dr. R. K. wen who has been a source of encouragement. The author is particularly grateful to his wife, Bong Soon, for her painstaking help in the preparation of the manuscript and her sacrifice during the author's gradu- ate study in the United States. The author also is grateful to his son, Jin Yun, in Korea, who has suffered many years of deprivation of a father's affection and care. The author wishes to express his gratitude to the Korean government for providing financial support. This was augmented by additional funds from the Department of Civil Engineering and the Division of Engineering Research, Michigan State University. 11 TABLE ACKNOWLEDGEMENTS . e . . LIST OF FIGURE . . . 0 LIST OF TABLES . . . 0 LIST OF NOTATIONS . . . Chapter I. II. III. INTRODUCTION . 1.1 Objective 1.2 Background 1.3 1.4 Assumptions FORMULATION OF DISCRETE STRUCTURAL A BINARY PROGRAMMING PROBLEM and OF CONTENTS Limitations Solution Procedure DES) IG N AS 2.1 Binary Formulation of Structural Design 2.2 Objective Function 2.} Elastic Design Constraints BINARY PROGRAMMING TECHNIQUES Initial Design Linearization of Constraints 3.1 3.2 3-3 3.4 111 Techniques for Reducing Design Space Solution Algorithm Page ii vi vii ChU'lNN 12 13 20 21 22 28 31 Chapter IV. VI. LIST OF EXTENSIONS OF FORMULATION . . . . . h.1 Deflection Constraints . . . . #.2 Multiple Loading Condition . . IMPLEMENTATION AND EXAMPLE PROBLEMS 5.1 Implementation 5.2 Example Problems Example 1: Example 2: Example 3: 6.1 Conclusions 6.2 Suggestions for Further Study REFERENCES iv One-Story, Two-Bay Frame Two-Story, One-Bay Frame Two-Story, Three-Bay Frame CONCLUSIONS AND SUGGESTIONS FOR FURTHER’STUDY Page 38 39 44 41. 45 1+5 49 51 53 53 55 72 LIST OF FIGURES Figure Page 1 Flow Chart of the Medified Enumeration Scheme . 37 2 Computer Program Flow Diagram . . . . . . . . . 57 3-1 One-Story, Two-Bay Frame . . . . . . . . . . . 59 3-2 Structural Topology and Member Groups . . . . . 59 h-T Two-Story, One-Bay Frame . . . . . . . . . . . 6O h—2 Structural Topology and Member Groups . . . . . 60 5-1 Two-Story, Three-Bay Frame . . . . . . . . . . . 61 5-2 Structural Topology and Member Groups . . . . . 61 Table 1-1 2-2 4: \OCXJVQU'I LIST OF TABLES Page Available Sections for One-Story, Two-Bay and T'O-StOry, Three-Bay Frames 0 a o o o o o o o o 62 Available Sections for Two-Story, One-Bay Frame . . 63 Results for Example 1 with Initial Plastic Design: Geoffrion's Algorithm vs. Modified Algorithm; Bending Moment,Mz, vs. Axial Force,P and Bending Moment,M2, for Working Stress Limit Definition . . 64 Results for Example 1 with Initial Guessed Design: Geoffrion's Algorithm vs. Modified Algorithm; Bending Moment,Mz, vs. Axial Force,P and Bending Moment,Mz, for Working Stress Limit Definition . . 65 Results for Example 1 with Starting Point Varied . 66 Results for Example 1 with Bandwidth and Section Table Length varied o o e o o o o o o o o o o o o 67 Results for Example 1 with Member Groups Varied . 68 Results for Example 1 with Load Factor Varied . . . 69 Results for Example 2, Two-Story, One-Bay Frame . . 70 Results for Example 3, Two-Story, Three-Bay Frame . 71 Results for Different Size of Structures (Mbdified Algorithm) 0 o o o o o o a o o o o o o o 7] vi In fie» a4 n> :> U1 01 Q NOTATIONS branch-node incidence matrix A matrix with multiple loading condition a matrix of linear programming constraints member cross-sectional area the inverse matrix of the system stiffness matrix B matrix with multiple loading condition a vector of linear programming constraints limits the constant vector used in evaluating Jacobian matrices the quasi diagonal matrix form of C c and E with multiple loading condition unit cost matrix of available sections the unit cost of section j for member 1 vector of binary variables binary variable associated with section j for member 1 modulus of elasticity extractor matrix unity vector of multiple choice constraints member force vector defining working stress limit discrete cost function the incumbent value of HE) vii degree of kinematic freedom allowable stress working stress constraint vector function deflection constraint vector functions G, Ga, Gb with multiple loading condition the number of member groups the number of members for member group j quasi diagonal constant matrix for working stress constraints H with multiple loading condition identity matrices moment of inertia about z—axes the matrix which is the derivative of Z with respect to Z3 the Jacobian matrix of G the Jacobian matrices of Ga, Cb Jz, J:, J: with multiple loading condition unassembled quasi diagonal stiffness matrix scaled stiffness matrix of K K and E with multiple loading condition length vector actual bending moment of a member allowable bending moment of a member subject to bending moment alone the number of members the number of free joints the half bandwidth of a section table the number of loading combinations viii 1 I “1' uu i! *l *1 the number of independent loadings the number of member forces used in defining working stress limit the number of working stress combinations a vector of applied joint loads in global coordinates P' with multiple loading conditions actual axial force of a member allowable axial force of a member subject to axial force alone the number of available sections the constant matrix used in evaluating the Jacobian matrix Q matrix with multiple loading conditions a vector of member force at the negative end in local coordinates R with multiple loading condition the constant matrix which consists of elements representing the ratio of member capacity to allowable member forces k.th partial solution the ratio of the member capacity to the i th member force translation matrix unity matrix of the multiple choice constraints a vector of joint displacements in global coordinates a vector of lower and upper limits of joint displacement u} ufi and u' with multiple loading condition ix Sgbscripts A,B 1:3 k a vector of member distortions in local coordinates V with multiple loading condition matrix of unit weights of available sections unit weight of section j for member 1 the constant loading combination factor matrix quasi diagonal unity matrix of the working stress constraints Y with multiple loading conditions member capacity vector member capacity for the 1 3h member of the :1 3211. group diagonal member capacity matrix E matrix with multiple loading conditions matrix of section capacities of available sections plastic section modulus capacity of section j for member 1 rotation matrix positive and negative member ends typical member 1, typical joint 1, or typical section j summation index Superscript .1 k k 1’ 2 O 1‘ t3 j th’column a sequence of partial solution initial or zero r‘th iteration a sequence of partial solution CHAPTER I INTRODUCTION Optimum design of structures has been a challenge to engineers since Galileo pioneered the concept of scien- tific design. The current state of the art and science of structural design is, however, far from true optimization. Research interests in structural optimization recently have been encouraged by rapidly developing mathematical program- ming techniques and digital computer capacity. In the decade following publication of the landmark paper by Schmit (1) in 1960, investigators tested and applied various nonlinear programming formulations of structural design and have written papers documenting their research. However, few researchers have investigated Optimum design of framed structures from catalogs of available member sizes. Virtually nothing has been done to develop a general proce- dure for discrete Optimization of framed structures using elastic analysis and minimum cost criteria. This void is due to limited knowledge of integer programming, the mathe- matical complexity of discrete formulations and the diffi- culty of defining realistic cost parameters. 1.1 Objective The main objective of this study is to develop a discrete formulation and a solution method for optimum elastic design of framed structures. The formulation and solution method presented are meant to demonstrate the feasibility of discrete optimiza- tion, and are not guaranteed to be the best conceivable design method. 1.2 Background In the early 1950's, several workers (2, 3, 4, 5) in the field of structural Optimization recognized that the minimum weight design of framed structures can be formulated as a linear programming problem if the constraints are derived from plastic design theory and if the objective function is linear. Throughout the following decade, most research on structural optimization was directed toward plastic design formulation and linear programming. An excellent summary and bibliography documenting this early development of structural optimization has been written by wasiutynSki (6). Since 1960, the rapid development of computer tech- nology and mathematical programming techniques has stimulated work on a variety of approaches to structural optimization. Extensive surveys with bibliographies documenting the devel- opment of structural optimization during the 1960's have been written by Sheu and Prager (7) and Schmit (8). In the following paragraphs, a few of the more prominent developments will be discussed. In 196k, Meses (9) introduced the concept of suc- cessively linearizing the nonlinear constraints of elastic structural design by using the first term of the Taylor series expansion theorem. An interesting line of research has been pursued since 1965 by Cornell, Reinschmidt, Brotchie, and their associates (10, 11, 12, 13, 14). The main part of their works involves evolution of an iterative design method using sensitivity coefficients, which is an extension of Meses' work. They extensively examined limitations of optimization techniques such as local optimality due to nonconvex design constraints, and slow or oscillatory convergence due to linearization errors. Various aids to convergence such as the basic move limit technique, the adaptive and reduced move limit techniques and the accumu- lation of constraints were devised in an attempt to improve convergence. They concluded that the successive lineariza- tion method may be one of the best tools available to tackle nonlinear optimum elastic design, if the convergence aids are used. While an enormous amount of work has been done and significant developments achieved in structural optimization in the last two decades, the bulk of the effort has been directed toward continuous formulation with a linear or nonlinear objective function. The first nonlinear cost function was proposed by Ridha (15) in 1967. He quantified h the connecting costs as well as the material costs for a framed structure as a nonlinear function. His work stimu- lated academic interest in analytic formulation of the cost function. However, his cost function, being limited to connection and material costs, lacks general applicability because many construction costs depend upon construction situations that are difficult to quantify. It was not until Toakley's paper (16) in 1968 that the discrete optimum formulation of framed structures was introduced. Toakley worked directly with commercially available sections rather than assuming a continuous spec- trum of sections, and formulated a mixed integer programming problem using the static theorem of plasticity for the design of framed structures. The use of Gomory's algorithm (17) to solve the mixed integer programming problem was a natural choice but the unpredictable nature of that algorithm forced Toakley to terminate the program and resort to bounding procedures in most cases. Another extensive study on discrete optimization was made by Reinschmidt (18, 19) in 1969. The discrete design of framed structures was formulated as a pure binary program- ming problem. Plastic design theory (mechanism method) was used for direct linear formulation of design constraints. Hewever, for the design of trusses, an elastic method in- volving successive linearization and sensitivity coefficients (12) was used. The computational efficiency of Geoffrion's implicit enumeration method (20) and Balintfy's approximation 5 algorithm (21) were tested extensively with various simple design problems. To improve computational efficiency, a modified multiple choice algorithm based on Geoffrion's enumeration method was developed. Reinschmidt's work inves- tigated the feasibility of integer programming to solve structural design problems. Reinschmidt concluded that currently available discrete programming techniques are unacceptably inefficient for practical problems. No attempt was made to develop a discrete design formulation for rigid framed structures using the elastic working stress method, nor to formulate a minimum cost design. In 1970, MeCutcheon and Fenves (22) developed a generalized approach for formulation of the minimum weight elastic-plastic design of framed structures as an iterative set of linear programming problems. A generalized matrix set of nonlinear stress constraints is developed by system- atic matrix manipulation. This constraint set is obtained by assembling the equilibrium and compatibility relations of the stiffness method with working stress limit inequali- ties. Constant ratios of member properties and linear scaled stiffness coefficients are assumed. Bu using an assumed initial design, the constraints are linearized to form an iterative set of linear programming problem. 1.3 Asgggptions and Limitations The following assumptions and limitations are used in this study. Asgumptions (a) The material is linearly elastic below the elastic limit and perfectly plastic above it. (b) Displacements are small so that changes in the geometry of the structures may be neglected. (c) The members are prismatic. (d) Loads are applied only at joints, so that maximum working stress occurs at the ends of members. If it is necessary to place a load at an intermediate point on a member, a fictitious joint must be inserted at that point. Distributed loads can be transformed to equivalent concen- trated loads up to the desired degree of precision. limitations (a) Deterministic, rather than probabilistic design philosophy is adopted. (b) Dynamic loading is not considered. (c) The basic geometry of a structure is fixed. (d) Instability (buckling) is not considered. (e) The nonconvex local optimality problem is not considered. Therefore, no guarantee can be made that the final design is truly the global optimum design. Hewever, if the final design is not the global optimum design, it will be a local optimum. Several local optima may be obtained for comparison by starting from different initial points. 1.h Solution Procedure This study presents an efficient generalized formu- lation of optimum discrete working stress design and an 7 improved solution algorithm. Structural design in this study is defined to be the proportioning of members from catalogs of commercially available sections in such a way that the cost of the structure is minimized and working stress and/or deflec- tion limits are not violated. Alternative sets of static service loads are considered. In Chapter II, discrete optimum design is formulated as a binary programming problem. A discrete cost function is proposed, and a set of nonlinear working stress constraints is developed by combining the analysis equations of the stiff- ness method with working stress limit conditions. Chapter III consists of several distinct parts. First, several methods are presented for determining an approximate design that can serve as a starting point for optimization. Then, the constraints for the binary programming formulation are obtained by using a Taylor series expansion to linearize the constraints derived in Chapter II. Next, methods for reducing the number of possible solutions are discussed. Finally, a solution algorithm based on Geoffrion's enumera- tion method is presented. In Chapter IV, the basic formulation of Chapter III is extended to include deflection constraints, and a generalized formulation including alternative loading conditions is presented. In Chapter V, the formulation and the solution algo- rithm proposed are implemented as a computer program. Several example problems solved by this program are presented together 8 with a brief discussion of computational results. Finally, Chapter VI presents some conclusions derived from this study, and several suggestions for further study. CHAPTER II FORMULATION OF DISCRETE STRUCTURAL DESIGN AS A BINARY PROGRAMMING PROBLEM Fbr the purpose of this chapter the term "discrete design" is taken to mean selection of members from a catalog of available sections. However, determination of geometrical configuration within the range of several alternatives, and selection of structural material also may be incorporated into the solution algorithm of Chapter III in a straightforward fashion. The general technique for converting a continuous linear programming problem to a discrete binary programming problem is presented in the first section of this chpater. Succeeding sections discuss expression in the binary program- ming format of a least cost design objective function and of nonlinear elastic design constraints. 2.1 Binggy Formulation of Structural Design Consider the familiar (1+, 5, 23) linear programming formulation of minimum weight structural design: minimize LtZ subject to T; + Tz 2 o (2-1) and Z;g.0 9 10 where Z is a vector of unknown member capacities, LP is a vector of member lengths, and “b.and‘i‘are a vector and matrix, respectively, of design constraint parameters. If there are p available sections for each member, the following discrete transformation can be made: Fbr the i th member capacity Z , i P Zi = £31 21k dik (2-2) where g§1 d1k = 1 and (11.1 = 0 or 1, and zij is the capacity of the J th,section for the i‘th_member. Thus, the member capacity vector Z can be expressed in matrix form as: where A I I t d :[d ,d ’OOO’d :, O O O O I d 'd ’OOO’d 11 12 1p . ’1 m1 m2 mP mop x 1 and /\ '- 1 D Z ~ . - 211,212,...,z1pl {f21’222""’22pl O 0 .e r. _________ I Zm1,zm2,eee ,anP L 1 m x mop This transformation requires the inclusion of additional multiple choice constraints to express the relation given by Eq. 2-2 namely 11 U = .5. (24+) where L I ’1’""1- m xm-p and _l t e =[1’1.‘, 0.00.1)!“ x1 An important advantage of discrete formulation is that it is no longer necessary to assume that unit weight is directly proportional to member capacity. The unit weight of each section can be associated directly with the corresponding binary variables. The linear programming problem can now be cast as a binary programming problem by using the substitution of Eq. 2-}, the multiple choice constraints, Eq. Z-u, and direct eXpression of unit weight. The discrete formulation is: minimize 1W? ...s and subject to b + A Z d 30 (2-5) U (1 = 5‘ 6.13: 0’] where 12 3 '11"12"""1p, . Iw ,w ,...,w '1 0 Lineage, 0 '.r ________ w ,1! goes," L | m1 m2 mp4 m x m’P in which w is the unit weight of the 3.32 section for the 13 1 2; member. 2.2 Objective Function The formulation of realiztic cost functions for structures is extremely difficult because of the qualitative nature of such factors as fabrication, connection, transpor- tation and maintenance. Although Fidha (15) formulated an analytical nonlinear cost function he was able to quantify only the costs of material and connections. In the discrete formulation of structural design, however, it is possible to formulate a realistic function if relative estimated unit costs for the sections are available. The estimated costs are derived from the judgement and experience of the designer, and express both quantitative and qualitative factors. Suppose that a cost per unit length, cij’ has been estimated for each section j that may serve as member 1. Then, the cost objective function F(d) for a binary program- ming problem is p p F (d) - 2: L z: c d 1:] i k=1 1k 1k {2-6) 13 where " 1 1 e = c”,c12....,cjpl ———————— r— —— ———— —. L. _______ I, O O. 1;—;———;- L ! “1’ m2’ ' "PJ m x mop Note that the unit weight matrix ,9} may be used in place of [C if the costs of sections are proportional to their weights. 2.3 Elastic Design Constraints In this section equilibrium, compatibility and constitutive relations will be combined with working stress limit inequalities to yield a unified set of nonlinear design constraints in terms of the unknown member capacity vector. The approach derives from the analysis relations of Hall and woodhead (ah). the network topological formulation of Fenves and Branin (25) and the working stress limits of MCCutcheon and Fenves (22). The definitions and notations used in this section follow those of the references, and the reader is referred to them for the details of the coordinate systems, geometric transformations, and the topological incidence matrix. Fbr a framed structure with m members, n free joint and f degrees of kinematic freedom at each joint, the follows ing equations are needed for analysis: Equilibrium conditions At R = p1 (2-7) 14 Compatibility conditions v a A u' (2-8) Constitutive relations R a K V (2-9) where P' a [P{, Pé, ..., P£]t, a vector of applied joint loads in global coordinates; u' a [u{, ué, ..., u£]t, a vector of resultant joint displacements in global coordinates; R‘ = [R1, R2, ..., Rh t, a vector of member forces at the negative ends in local coordinates; and V . [V1, V2, ..., Vth, a vector of member distortions at the negative ends in local coordinates. Each subvector P1, R5, ui and V1 has f components. The A matrix is a branch-node incidence matrix obtained by combining geometric transformation matrices (rotation matrix A and translation matrix T) with the topological incidence matrix. A submatrix A13 is (xi, - TEA; 0) if the i _1_:_l_1_ member is (negatively, positively, not) incident on the j‘th joint. K is an unassembed diagonal stiffness matrix in which each submatrix K1 is a square matrix of order f which defines the stiffness of member 1 at the negative end. Load-displacement equations obtained from the three equations above are P' . (AtKA) u' (2-10) or u' a (.AtKA)“1 P' 15 Once the displacements u' are obtained, the member forces R can be derived from Ens. 2-8 and 2-9 by back substitution: R 2 K A u' (2-11) Elastic design of a framed structure requires that allowable stress limits not be exceeded anywhere in the structure. The 1970 AISC specification (26) limit combined axial and bending stresses by the following inequality: P M Ipl'ifli'; 21 (2-12) where Rx and M.z are the actual axial force and bending moment, respectively, and RxA and MzA are the axial force and bending moment that would be allowed in a member subject to only one force or the other. This inequality, valid in the range P 15333 0.15, is a linear approximation of the stress limit for x a combined forces. If each allowable force is expressed as a linear function of one capacity of the member, Zi, in the following form: P .l—z and M gl—z (2—13) xA s1 1 2A 82 i ’ then Eq. 2-12 can be cast in matrix form by considering all sign combinations of the two forces: 16 1 3‘ s2 1 P ‘ z - 31 '32 . “ >0 (2-111) 1 1 -s s '— 1 2 Hi If all loads occur at joints and the members are prismatic, then the extreme stresses will occur at the ends of members and Eq. 2-1h can be generalized as: s F YZ — 1 o . ‘1 >0 (2-15) 1 1 s F " 0 1 Bi Where Y1 =[1.1’ 000.1 E I, 1’ .00. 1);.n1 x1 1 n1 is the number of combinations of working stresses, Si = 81' 82’ 0... an! 81. 82, a... -8 ‘81g-32’ o a a g -8 L J n1 x nf , n1, is the number of forces considered, and FAi and F21 are vectors of member forces included in the combined working stresses at ends A and B. F31 and F51 can be represented in terms of the member force vector R: EiTiRi EiRi PM 1‘'131 (2-16) 17 where 31 is an extractor matrix which extracts forces to be included in the combined working stresses from all member forces. The order of E1 is nf by f. A great reduction in the number of constraints could be achieved if the signs of member and forces were known a priori so that only the relevant sign combination would need to be considered rather than all possible combinations. That is, the S1 matrix could be reduced to a single row. Unfortunately, the signs of the forces are unknown and are subject to change as the design process iterates through various combination of member capacities. Substitution of Eq. 2-16 into Eq. 2-15 gives 5 E T 22 .. "13.5.1. R > 0 (2-17) 11 1 ‘- SiEi For all the members of a structure Eq. 2-17 becomes: vz- HR 3 0 (2-18) where Y - _Y ‘ H FR 1 " 1 o ’ " 1 0 Y2 Hz 0 .Y 0 OH“ I L n2on1-m x m a Jami-m x f-m , n = $18.11”; 1 s E 18 t Z a Z Z ... Z E 1’ 2’ 9 me x1 9 and RI[R,R,eeegR]t 1 2 m fem x 1 Eq. 2-18 with the substitution of Eq. 2-11 becomes YZ- HKAu' 20 (2-19) By substituting Eq. 2-10 into Eq. 2-19, 112 .. mmutmr‘P' a 0 (2-20) In order to eliminate the unknown stiffness matrix K from the constraints so that capacities Z1 will be the only unknowns, the submatrix K1 for each member will be scaled to the capacities of that member by the linear function: K g z .1? (2-21) where E1 is termed the scaled stiffness matrix. For all the members, Eq. 2-21 is expressed as K a 2 E (2-22) L _f'm x f°m . .f-m x f-m and 11 is an identity matrix of order f. 19 The final form of the constraints is obtained from Eq. 2-20 by substituting Eq. 2-22: vz - H 2 E11092 in"? 3 0 (2-23) It must be noted that the H and E matrices contain proportionality constants derived from linear approximations of the spectrwm of properties of sections. This linear approximation is ,in general, valid for only a local portion of the spectrum of section properties. Therefore the piece- wise linear approximation is to be used if the range of available sections is large. The proportionality constants in the matrices S i to be pre-estimated to approximate the variation of properties , which is incorporated in H, and ii are of sections to be considered for use for member 1. CHAPTER III BINARY PROGRAMMING TECHNIQUES In this chapter, an algorithm is developed for solving the binary programming problem defined in Chapter II. At the current state of development, binary program- ming algorithms are relatively inefficient. Therefore, it is important to define a reasonable initial design which can then be improved by binary programming. The effort involved in the initial design phase is rewarded by a saving in the number of iterations necessary to achieve the optimum design. The best guess of an experienced designer would be a legitimate initial design, but more formal approximate design techniques also may be used. Two methods are discussed, namely, the plastic mechanism method and the elastic equilibrium method. The constraint set given by Eq. 2-23 in nonlinear, whereas binary programming requires linearity. To overcome this difficulty, the constraints are linearized about the preceding design at each iteration of the binary programming process. A Taylor series expansion method is used for linea- rizing the constraints. Evaluation of the linearized con- straints at each iteration is facilitated by successively altering the constraints of the previous iteration, rather than deriving them anew from the nonlinear form. A successive 20 21 alteration scheme also is employed to eliminate inversion of the assembled system stiffness matrix at each iteration. The efficiency of the solution technique is improved further by reducing the number of possible designs. This is accomplished by specifying that certain members all be fabri- cated of the same section, and, at each iteration, by limiting the number of sections that may be used for particular member or group of members. The binary programming algorithm itself is an implicit enumeration method based on Geoffrion's enumeration algorithm (20), which, in turn, is an adaptation of Balas' additive method(27). 3.1 Initial Design Any conventional method can be used to formulate an initial design. However, since the initial design subse- quently will be altered to achieve the optimum design, a high degree of precision is not justified in the initial design phase. Therefore, simple methods of approximation should be used to formulate the initial design. Two such methods are the plastic mechanism method and the elastic equilibrium method. Plastic Mechanism Method Plastic design by the kinematic mechanism method is a classical linear programming problem (A. 5. 23, 28, 29). The virtual work constraints are readily formulated if the collapse mechanisms of a given structure are fairly easy to enumerate. If all possible mechanisms are included in the constraints, then an exact analysis is obtained (39). 22 However, enumeration of all the mechanisms for a complex structure is tedious. Nevertheless, an approximate lower bound solution may be obtained by including only the principlal mechanisms in the constraints. Identification of the princi- pal mechanisms is based on the experience and judgement of the designer. This approximation is sufficient for defining an initial design. Elastic Equilibrium Method An upper bound solution is obtained by considering equilibrium and working stress limit constraints, but omitting compatibility constraints. That is, the equilibrium conditions, Eq. 2-7, and the working stress limits, Eq. 2-18, but not the compatibility relations, Eq. 2-8, are incorporated to give the following linear programming problem: minimize LtZ subject to AtR = P YZ - HR.3 O Z‘g-O (3-1) Since the formulation is continuous, the solution for section properties, Z, must be rounded up to match the proper- ties of available sections. The resulting design can serve as a starting point for exact discrete optimization. 3.2 gineggiggtion of Constraints Let the nonlinear constraints of Eq. 2-23 be represented by a vector function: 23 o(z> .-.- YZ - H 2 EMAt'z' in"? (3-2) where G(Z) 2 o (3-3) Note that Z, the vector of design variables, is a point in Euclidean m space and 6(2) is an expression of 2on1.m hypersurfaces which bound a region of feasible designs in Euclidean m space. By Taylor series expansion, C(Z) can be linearized in the neighborhood of 2°: 6(2) -.- G_ 0 (3-11) where Jz is the Jacobian matrix of C(Z) with respect to z at z°. That is, J2 ‘-‘ [Jig Jig see, J2. see, J2] (3‘5) in which a . it. {3.3. 22:2 9:th J! 623 Z0 (9Z3. Tzd peso. (9Z1 at Zoe Eq. 3-h gives a set of linear constraints of the same form as Eq. 2-1. Suppose that Zr, G(ZF), and J r of the r‘th successive design are obtained. Then, the r+1‘§§ design can be formulated as: 24 minimize Ltz subject to [C(Zr) - J21. Zr]+ er Z a o (3.6) 213.0 The Jacobian, Jz, can be evaluated efficiently by matrix manipulation and implicit differentiation. J31. , the j _t_l_1_ column of the Jacobian at the r 5; design, Is evaluated as follows: Differentiate (3(2) of Eq. 3-2 with respect to Zj'at Zr to give ”email 333 AZ; NA(AtZrRA)'1P' Zr - aim ——_ 0 (3-1?) 2 z U3: 5‘ Explicit analysis is not performed at each successive design. However, for any design, r, the member stresses are available as: Rumor and the joint displacement as: u' = (AtZrEA)-1P' Note that the feasibility of each successive design point will be checked easily by the available results of C(Zr). That is, G(Zr)-3.0 indicates that Zr is a feasible design point. 3.3 Techniques for Reducing Desigg Space The efficiency of the binary programming algorithm is enhanced if the number of possible solutions is reduced. 29 Two ways to do this are: (1) Specifying groups of members to be designed identically. That is, each member of the same group is to be fabricated from the same standard section. Of course, this results in a degree of over-design, but it is consistent with conventional architectural practice and saves fabrication costs by reducing the number of different section sizes that must be handled; and (2) Limiting the range of sections to be considered at any step of the design process to a restricted bandwidth in the section table centered around sections selected in the preceding design. Details of the two techniques for reducing design space are considered in the following paragraphs. Megber Group Specification The reduction in design space due to designing mem- bers by groups expresses itself as a reduction in the dimen- sions of some of the matrices in the formulation. Consider a structure with m members grouped into g sets. The matrices in the formulation are redefined in the following manner: (1) The member capacity vector is replaced by a member group capacity vector; Z = [Z11, Z1 , 000’ Z1 ]t 2 883:1: where Z designates the typical (1 2g) member of the j;§h group; 13 (2) The length vector is compressed by summing the lengths of members within the same group; 3O 81 82 88 L: {L EL ... EL ] 1k' Ice-1“. ' k=1k where gJ is the number of members in the j‘th group; (3) The Jacobian is compressed in a similar manner; 81k 2 k 85 k J = [ZJ J see J J z k=1z' 1E1“ ’ 1E1 2 (h) The matrix of constants is compressed in the same way; Iggited Bandwidth of Section Table The number of binary variables in the binary program- ming formulation is m x p, the product of the number of members and the number of available sections. By using member group specification, m was reduced to g, the number of member groups. The other factor, p, also can be reduced significantly if only a subset of the complete section table is used as the input of available sections at each iteration. Suppose the r‘th design has been completed and is about to be used as the initial point for the r+1 Eh design. The number of sections to be considered for the r+1 Eh design of one of the members may be chosen as 2.nb+1, centered around the r‘th discrete solution for that member with half bandwidth nb. Thus, 20nb+1 is the input bandwidth for sections for the 31 r+1 th'design. The choice of the half bandwidth is flexible and may depend upon the size of table and the type of design. The use of a subtable at each iteration also can be interpreted as a move-limit technique to aid convergence of the solution. 3.# Solution Algorithm Since 1960, various algorithms have been proposed to solve pure and mixed integer programming problems. Although Gomory (17) developed a generalized algorithm in 1960, it has been proved disappointing and the observation remains that the development of an efficient integer programming technique is inherently difficult. Balinski (30) pointed out that various clever methods of enumeration may constitute the best existing means for solving binary programming problems. A series of enumeration algorithms has been published by various workers (20, 27, 31 through 36). Most of their works vary only in enumeration technique and the use of surrogate constraints and dual imbedded linear programs. Gue (37) concluded that most of the algorithms fit within the general framework for implicit enumeration proposed by Geoffrion (20). He also stated that at this time (1968) computational results indicate little hope for solving problems with more than 100 variables, but that Geoffrion's algorithm seems to be the most promising of existing algorithms. In this study, Geoffrion's algorithm (20) with Balas' additive method (27) is chosen as the basic algorithm mainly because an ALGOL program (38) has been published and this 32 algorithm is relatively simple and efficient in comparison to the other algorithms. However, an effort was made to develop an improved algorithm based on Geoffrion's enumeration method but exploiting the characteristic multiple choice constraints of structural optimization problems. Geoffrion's original algorithm will not be presented in this study but is well documented elsewhere (20, 27). The proposed improved algorithm is presented in detail. The multiple choice constraints characteristic of structural design express the relation that only one of the binary section coefficients for each member can have value of one. The modified algorithm, which recognizes this relation, needs to consider only pm solutions; Geoffrion's general algo- rithm must consider 21"m solutions. Furthermore, the number of constraints needed by the modified algorithm is less than the number needed by Geoffrion's general algorithm since the multiple choice constraints are need not be included explicity as constraints but are implicit in the enumeration scheme of the modified algorithm. Presentation of the algorithm is subdivided into three topics; the enumeration scheme, the fathoming technique and the augmentation mechanism. Enumeration Scheme Emplanation of the enumeration scheme requires prede- fining a few terms. The group of binary section coefficients pertaining to the 1 fig member (i.e., d11, dia’ ..., dip) is called the i th class of variables. An assignment of a variable 33 means that variable has been given a value of one. An assigppent of a class means that one of the variables of the class has been assigned, and all others are zero. A partial solution is the assignment of some but not all classes. Any class not assigned is called £323. A partial solution is augpented by assigning a free class. A completion of a partial solution is the assign- ment of every free class. The completion is said to be feasible if no constraint is violated. A best feasible completion is a feasible completion which minimizes the objective function. A partial solution is said to be fathomed if the best feasible completion can be found, or if it can be determined that no completion will be feasible or better than the incumbent one. Once a partial solution is fathomed, the enumeration scheme backtracks to a new partial solution that has not yet been tried. The enumeration scheme examines each of the pn possible solution implicitly, and saves the best solution yet encoun- tered. Suppose enumeration starts with a solution so in which no classes are assigned. If So cannot be fathomed, it is augmented by assigning a free class according to an augmenta- tion rule. Augmentation is continued until a partial solution Sk1 can be fathomed. Next, the unassigned variables of the Sk1 are assigned one by one and each last assigned class in of the resulting partial solution is examined to see if it can be fathomed. If all those partial solutions are success- fully fathomed, then the last assigned class is made free. This indicates that the partial solution SkI'I, which is Sk1 without its last c1ass,_is fathomed. Now the next to the last 3A k1 assigned class of S becomes the last assigned class of SkI'I. Sk1-1 If all the variables of the last assigned class of are assigned one by one and the resulting partial solutions fathomed successfully, the backtracking continues to Skl'z, and so forth. Backtracking may continue until So is fathomed, at which time all solutions have been enumerated. On the other hand, if the partial solution which is obtained from the assignment of the j pp_variable of the last assigned class of sk‘ cannot be fathomed, then the partial solution sk‘*td is augmented by assigning a free class. At the same time, the variables of the last assigned class of SI“ , which are asso- ciated with fathomed partial solutions, are dropped from storage because they need not be considered again. Augmentation is continued until a new partial solution Ska 1s fathomed. The backtracking and augmentation procedure will be repeated for the partial solution Ska. This is continued until back- tracking is extended to So, signalling termination with the optimal solution or with the information that no feasible solution exists. Figure 1 depicts the enumeration scheme. Note that the enumeration of the structural binary programming problem starts with a completion rather than S°, which obviously reduces the number of explicit enumerations. Fathomipg Mechanism Assuming that the section table is sorted into ascend- ing order by cost, the best (but not necessarily feasible) completion of S is the one that assigns the first variable of each free class. If the partial solution S is feasible with 35 some classes remaining free and is better than the incumbent one, this partial solution is fathomed and replaces the in- cumbent one with all free classes corresponding to members that may be omitted. If S is infeasible, then an attempt is made to fathom it. If the best completion is feasible then the best feasible completion has been found, and S has been fathomed. The value of the cost of the design represented by this completion is computed and compared to the cost of the incumbent design. If an improvement has been achieved, the newly found solution displaces the incumbent. Similarly if the best completion is not feasible, a cost comparison is made to the incumbent one. If the cost of the design represented by the completion exceeds the cost of the incumbent, then no completion of S is better than the incumbent, and S has been fathomed. If the best completion is infeasible but better than the incumbent, nothing further is done to find the best completiOn. Instead, an attempt is made to fathom by demon- strating that there is no feasible completion. That is, if the worst completion, which is obtained by assigning the last variable of each free class, is infeasible, then there can be no feasible completion and S has been fathomed. If the worst completion is also feasible, the partial solution S cannot be fathomed and further augmentation is appropriate. Apgpentation Mechanism The free class to be assigned next is selected in such a way as to minimize the degree of infeasibility. That is, the first variable of a free class is assigned tentatively, 36 and the amounts, if any, by which the constraints are ex- ceeded are summed. That sum is compared to similar sums computed by assigning the first variables of other free classes. The free class for which the sum is smallest (algebraically) is the one that will be assigned. "in. r w 3'7 .. Current d is feasiple & F(d)_<_F_ o and Gb(Z) a o (4-3) 38 39 where cam) u; - (flip-‘1» (4-4) and Gb(Z) -11; + (Atmr‘p' (4—5) Eq. 4-3 is linearized in the neighborhood of 2° by Taylor series expansion: 93(2) .-. Ga(Z°) + J20 (2,—2°) 3 o and Gb(Z) .-. Gb(Z°) + Jbo (z-z°) 2. 0 Z By a derivation similar to that of Section 3-2, the Jacobians are computed as: « BrAtCr and Jbr = -BrAtCr (4-6)‘ 2 Ja Zr The binary programming constraints for deflection limits are: [6"(73') - £1?er + JZr’zVi‘ 3; o (4-7) I‘ [6"(2’) + JarZr] .. Ja f7}? _>_;o Z Z These constraints are appended to the formulation given by Eq. 3.17. A.2 Multiple Loading Condition Often a structure is designed by considering the various combinations of several independent loads such as dead load, live load, wind load, earthquake load, and some ho extraordinary loads. For example, the AISC specifications require design for the following combinations of dead, live and wind load; 1.00 (dead + live) (A-B) 0.75 (dead + live + wind) To account for multiple loading. the analysis equations of Section 2-3 are recast as: A'tR' a P" (4'9) v’ e A'u*' (4-10) 12* = K'v' (tr-11) a1 *1: a a -1 *1 u s (A K A ) P (A-12) where P“ s n v " VI’VZ....’vd] t n R” - R‘,R2,...,Rd] A‘~-A12 Gland K*-K‘2 o A . K C n . L° Ad. L0 Kn"- in which a superscript i denotes a quantity pertaining to 1.1 the 1 pp independent load, and nd is the number of independent loads. Suppose a structure is designed with the working stress constraints of Eq. 2-18 and the deflection constraints of Eq. h-Z under the alternative multiple loading combinations of Eq. h-8. Then Eq. 2-18 and Eq. 4-2 are rewritten as: YZ - H (1.00 R‘ + 1.00 R2) _>_ 0 (A-13) YZ - H (0.75 R1 + 0.75 R2 + 0.75 R3) _>_ 0 u' _<_ (1.00 11'1 + 1.00 u'2) g u' R “ (4-14) .. u' _<_ (0.75 111'1 0.75 u'2 + 0.75 u'3) 3 11111 where the superscripts 1,2 and 3 designate dead load, live load and wind load, respectively. In matrix form, Eq. h-13 and Eq. h-14 are expressed as: Y H0 1.01.1.01, 0 R1 z - Ra _>_ 0 (Lt-15) Y o H 0.75 I. 0.75 I. 0.75 I. p3 u’ 1.0 I 1.0 I 0 u" u' l ’ ’ u'2 ‘g_ u (h-16) 1.1; 0075 I, 0075 I, 0.75 I “'3 “If! in general, Eqs. A-15 and 4-16 can be expressed Y*Z - H'X‘R' 2 o (u—17) and uf' 5 Xau" _<_ u: (4—18) 1.2 where * - 1' * - 1 q 1 1 1 1 A Y 2 Y ’ H '-‘- H O . x = a‘1 I ’ .... aln I y"- n3 , G} n 0 ' n I 1 : 1 a! CA L. H c a I so, a I d _ n61 ’ ncnd J and X2 has same form as X1 except that each submatrix is Kid = {513}12 (I1 is of order m-f and I2 is of order nof) The superscripts of Y and H indicate different loading combinations and nc is the number of loading combinations. By substituting Eq. 4-10, 11 and 12 into Eq. h-17 and 18 and making use of Eq. 2-22, two sets of nonlinear constraints are obtained: I’Z — H'X‘E’E'A*(A't2'i*d')"r>" 3 0 (4-19) 11;" 5 X2(A*tE*E*A*)"P" _<_ u;' (AP-20) z‘--2‘ 0 ‘and ICU-E1 o A '22 E2. 0 . 2nd 0 . find L J L . The generalized binary programming formulation of structural design, including deflection limits and multiple loadings, is derived from Eqs. u-19 and 20 by linearizing and converting to binary form. The formulation is: 1+3 minimize Lt 6‘ d‘ subjectto C(Zr)-3rZr + 31.2 54:0 2 2 58(21') .- Jar 21‘ Ear 2 2 z Gb(z’) + Jar zJr .. r 2‘ 2 U 51 5’ where C(Z’) .— Yazr - Hax1-Zari-(aAa(Aat.-Z*IT(§A5)_1PM ’ Eam’) . u: .- x2(A't2"'fi'A')"P" , char) .. .u;' + XP-(n'txm'ib-IP“ , 321. ,—: Y. - q*1fé*r , 3a . xzexm'é'r 3b .. 361 Q" s H‘x‘ [I - B‘Wc‘s'fi't] , C'I'r :-: IK-*A*B*rp" ’ -‘I’r *1- (C is the quasi diagonal matrix form of C ) and B"r .. (A*t-Z.IT(*A*)'1 . Of course, if the modified solution algorithm is used, the multiple choice constraints, U 3 =3, are to be omitted as they are implicit in the algorithm. CHAPTER V IMPLEMENTATION AND EXAMPLE PROBLEMS This chapter describes a computer program written to implement the formulation and the solution algorithm developed in previous chapters. A number of design examples are solved using the program and the results obtained for various problem conditions are discussed in detail. A one-story, two-bay frame is chosen to illustrate the results of many variations in parameters and design conditions. A two-story, one-bay frame that is also an example in reference 22 is solved for purposes of comparison. A two-story, three-bay frame is selected to test the applicability of the formulation and solution algorithm to fairly large structures. 5.1 Implementation A generalized FORTRAN program is written to implement the discrete design formulation and the improved binary pro- gramming algorithm. The program, which consists of a main program and three large subroutines, solves the discrete Optimum design problem for rigid framed structural systems, that is, planar frames, grids, and space frames. #5 The linear programming subroutine used in the initial design phase is adapted from CLIP, an implementation of the simplex method (#0). The general binary programming sub- routine for the main design phase is a FORTRAN translation of the ALGOL implementation (38) of Geoffrion's algorithm. For purposes of comparison, the modified algorithm is imple- mented as an alternative binary programming subroutine. The final subroutine is a standard matrix inversion routine. The program is written to run on the Control Data Corporation 6500 system. One run accomplishes a complete optimum design. All intermediate results are available with various information concerning analysis of the structure. A flow diagram of the program is presented in Figure 2. 5.2 Example Problems Example 1: One-Story. Two-Bax Frame The first structure considered is the one-story, two-bay frame shown in.Figure 3-1. This structure is suffi- ciently complex to illustrate the variation of results with changes in parameters and design conditions, yet sufficiently simple to be repeatedly analyzed within reasonable computer time. The structural topology and the grouping of members for the example are shown in.Figure 3-2. The structure contains five free joints, seven members, and three member groups. The structure is to be made of steel wide flange (W) sections, with the beams 16 inches deep and the columns 1A inches deep. The sections available for this #6 structure are listed in Table 1-1. There are 12 sections of each depth. The single set of loads shown in Figure 2-1 is considered the design service load. The load factor used for most of the runs is 0.75, as suggested in the AISC manual (26), but other load factors (0.8, 0.9, 1.0) are also used in order to observe the effect of varying the load factor. The other criteria and parameters used for this design are: (a) Modulus of elasticity, E = 29 x 106 psi; (b) Allowable stress, fa = 0.6 x 36 ksi; (0) Ultimate load factors for plastic design, 1.h0 for horizontal loads, 1.85 for vertical loads; (d) Average radii of gyration, 6.53 in. for 16W sec- tions, and 5.75 in. for 14W sections; and (e) Cost considered, material only. A series of runs was made to compare the modified algorithm with Geoffrion's algorithm. Results are presented in Table 2, and it may be observed that for structural design the modified algorithm is more efficient than Geoffrion's by about an order of magnitude. It also may be observed that with the guessed initial design, design using Geoffrion's algorithm required three design iterations but design using the modified algorithm required only two. This may indicate the possibility of Geoffrion's algorithm converging to a non- optimal solution. The relative efficiency of the modified algorithm is attributable to its utilization of the multiple choice constraints characteristic of the discrete structural design and to its direct enumeration of class variables #7 rather than individual binary variables. The effect on the run results of considering an axial force,P, also is shown in Table 2. If only bending force,Mz, is considered and the plastic mechanism is used for initial design, then convergence requires only one iteration and consumes less than 2.5 seconds of computing time. With a guessed initial design, two iterations are needed and about 4 seconds of computing time are used. Convergence is to slightly different designs for the two different starting points. When both P and M2 are considered, oscillatory be- havior occurs if the plastic method is used for initial design. With the guessed initial design, two iterations are required and about 6 seconds of computing time are consumed. Conver- gence is to the same design as given for the guessed initial design when only M2 was considered. These results show that if a good starting point is selected then inclusion of an axial force does not significantly affect the final design but does increase computing time significantly. However, even with a good starting point determined by approximate plastic design, oscillatory behavior may result if unfavorable constraint regions are encountered. The oscillatory behavior and the multiplicity of converged solutions possibly may be due to linearization error and nonconvexity of the design constraint space (10, 1A). That is, the solution obtained may be a local Optimum or a near optimum point rather than the true optimum point of the original constraint space. Table 2 also shows that accurate initial design #8 markedly increases the convergence rate. Because of the relative efficiency of linear programming (0.02 sec. in this case), two phase formulation is strongly recommended, with the plastic mechanism method serving as the first phase. A conservative ultimate load factor seems to lead to a better upper bound starting solution. Another series of runs was made to determine the effects of different starting points. The results are shown in Table 3. In most cases the process converged rapidly to a feasible design, although the results obtained from various starting points show significant diversity. The results indicate that selection of a good starting point will reduce greatly the binary programming time and total computing time required. A remote and infeasible starting point will yield a "no solution" signal, possibly because linearization of constraints exclude the entire feasible region. If conver- gence is achieved, it requires few iterations (5 at most for this example). The effect of varying the bandwidth and table length also was studied, as shown in Table A. The use of small bandwidths greatly reduces the binary programming time and the total time. Variation of table length does not affect the binary programming time significantly provided that the bandwidth about a starting point does not range outside the table. Note that when a bandwidth nearly equal to the length of the table is used rather than a bandwidth of 1/4 of the table length, the binary programming time increases by a #9 factor of six. Interesting results were obtained when the number of member groups was varied as shown in Table 5. The use of a small number of member groups significantly increases the weight of the structure, but greatly reduces the binary pro- gramming time and total time. Finally, a series of runs was made with varying load factors. The results are listed in Table 6. The use of higher load factors significantly increased the weight of the structure, whereas computing time decreased unexpectedly. Possibly this is because the higher load factors lead to a starting point close to the final design. Consequently, fewer iterations are required. It turns out that the approximate inversion process takes about the same amount of computing time (0.10 sec. for this example) as would exact inversion. However, it can be reasonably expected that for a larger structure, the approxi- mate method will be more efficient than the exact method. Example 2: Two-Stopy.0ne-Bgy Frame The second problem considered is the two-story, one bay frame shown in Figure h-1, which is taken from reference 22. This example is chosen to provide a basis for comparison of this study and reference 22. This study develops a discrete optimum formulation of elastic design of framed structures as a successive binary programming problem, whereas reference 22 develops a continuous optimum formulation of elastic-plastic design of framed structures as an iterative 50 linear programming problem. The computer program of this study was run on a CDC 6500 system, whereas the computer program of reference 22 was run on an IBM 360 system. One run of the program of this study corresponds to a complete design, whereas one run of the program of reference 22 corresponds to a single iteration of the design process. The topology and grouping of members for the example are shown in Figure 4-2. The structure contains six free joints, eight members, and three member groups. The structure is to be made of steel wide-flange (W) sections, with the beams 10 inches deep and the columns 8 inches deep. The sections available for this design are listed in Table 1-2, with 12 sections given for each depth. A single set of loads is applied and a load factor of 0.75 is used. The following design criteria are different from those of Example 1: (a) Allowable stress, fa s 26 ksi ; and (b) Average radii of gyration, 4.32 in. for 10W 3.#7 in. for 8W. The results for this problem are presented in Table 7. When plastic initial design is used, the solutions obtained for M2 and for the interaction of P and NZ are the same and are reached in four iterations. If a good guessed starting design is used, a slightly different solution is obtained after two iterations for Hz; with both P and M2 considered, yet another slightly different solution is obtained after three iterations at a cost of about twice the computing time. It is interesting to note that for the example problem 51 the designs obtained from this study are significantly better than those given by reference 22. Note that the solution process of this study appears to be more economical than the solution process of reference 22 in terms of number of itera- tions and computing time. The most striking difference between the two studies is that computing time for the binary programming routine is about five percent of the time for a single iteration, whereas in reference 22 the time consumed by the linear programming routine is about one half of the time for one iteration. The low ratio of mathematical programming 'W‘Q. .‘ ‘. .34.? aquarium-M time to iteration time is attributed to the overhead of matrix manipulation procedures. In contrast to the first example, the use of initial plastic design increased the computing time required. Example 3: Two-Stopz, Three-Bay Frame The last structure considered is the two-story three-bay frame shown in Figure 5-1. This example is chosen to demonstrate the applicability of the formulation and the solution algorithm proposed in this thesis to relatively large structures. The example structure contains 14 free joints, 20 members, and 8 member groups. The design con- stants and available sections for the first example are used for this example also. The results for a single run are presented in Table 8. With a good starting point derived intuitively from the optimum design of Example 1, two itera- tions are required to converge to a feasible solution point in less than 24 seconds. 52 From a comparison of the results for the four example structures shown in Table 9, it is observed that the number of binary programming cycles per iteration for the third example (20 members) is about twice as large as for the first example (7 members). The binary programming time per iteration is about nine times greater for the third example than the first. The number of binary programming cycles appears to be nearly proportional to the number of members if only the extreme size structures are used to estimate the relation. However, computing time increases fairly sharply with increasing structure size. More extensive experiments are required to test the applicability of the formulation and solution algorithm to large structures. However, the results for this example are encouraging. a. ‘v s.‘ v CHAPTER VI CONCLUSIONS AND SUGGESTIONS FOR FURTHER’STUDN 6.1 Conclusions This study proposes a generalized formulation and a special solution algorithm for discrete optimum design of framed structures. Working stress limits, deflection limits, and multiple loadings are considered. The formulation and solution algorithms are characterized by the following features: (a) Discrete optimum elastic design formulated as a successive binary programming problem; (b) A solution algorithm for binary programming that utilizes the multiple choice constraints characteristic of discrete structural design and directly enumerates "class" variables associated with each member; (c) A unified set of nonlinear working stress con- straints expressed in terms of unknown member capacities; (d) A two phase design process consisting of approxi- mate initial continuous design, preferably using the plastic mechanism method, and main discrete design using successive binary programming; (e) Efficient evaluation of the Jacobian matrix of the vector constraint function in order to linearize the con- straints; and 53 5h (f) A discrete cost function associating estimated unit costs of available sections with binary variables. The study demonstrates the capabilities of discrete structural optimization in the following ways: (a) The comparison of discrete and continuous optimization presented in Chapter V indicates that discrete optimization is more efficient and gives more economical design; (b) Binary programming is shown to be relatively efficient if multiple choice constraints are exploited by the programming algorithm; and (c) Application of the design process to a relatively large structure (20 members) gives encouraging evidence that it may be possible to design large structures. In the course of the study, the following observations have been made regarding rate of convergence: (a) Correct selection of critical mechanisms for the initial plastic design phase leads to rapid convergence in the main design phase; (b) A feasible upper bound initial design is preferable to an infeasible starting point; (c) A good choice of bandwidth hastens convergence. An unusually small bandwidth sometimes, causes convergence to an infeasible design; a large bandwidth leads to long com- puting times. A bandwidth of 1/3 to 1/2 the table length appears to be best; (d) To cape with the possibility of multiple solutions it is suggested that several final designs be generated from 55 different initial designs. If the final designs are different, the best one may be selected; and (e) Oscillatory behavior can be damped out by de- creasing the bandwidth at each iteration. 6.2 Spggestions for Further Study This study should be viewed as a single step in the evolution of a practical design process. Many problems remain to be solved. The following are possible extensions of this study: (a) The instability of individual members could be considered either by using reduced allowable compression stresses or by developing new constraints; (b) In the current study, the loading of a structure is assumed to be constant. However, the dead load on a struc- ture is actually a function of the member sizes. Therefore, loads could be treated as variables in the formulation by representing them as functions of the member capacity vector; (c) The efficiency of the design process would be enhanced if the correct critical combination of working stresses in each interaction inequality were known a priori. With the correct combination known, the number of constraints would be reduced from 2on1-m to 2cm.. This usually is not possible bacause member forces are generally unknown prior to analysis. However, by using a good approximate initial design technique and analyzing the design obtained, the sign of most member forces may be identified before the main 56 design phase. Then the number of combinations, and therefore the number of constraints, could be reduced. Further inves- tigation and extensive experimentation are necessary to evaluate the feasibility of this technique; (d) A nonlinear relation between member forces and member capacities could be used instead of the piecewise linear relation. However, the nonlinear representation of ‘I am,“ member forces will cause extreme difficulty in the derivation of constraints; and «.‘&.‘\. ‘ ‘ -.. 8.1}J- (e) The successive binary programming method has H . 3.1; ..._ inherent pitfalls due to linearization error. However, these are unavoidable at present since no general direct nonlinear discrete programming algorithm is available. More research effort should be devoted to developing an efficient nonlinear discrete programming method. 57 ( ) j Initial Design ///Structural geometry, Material constants, Member topology ’// ,. Iteration constAnts, Coefficient matrikJA Load factor, Safety Right side vector b factor, Independent ‘ service loads, Section table, and Type indicators , near programmin & routine Allowable stress fa A Design loads P' Transform Member lengths L continuous LP solu- tion into discrete solution vectorLZo Translation matrix T Rotation matrix 7\ . Incidence matrix A Initial member __j _ capacity 20 3.2a A Program flow Iterationso Terminal 53> "i Computation block Read date {—Iter. = Iter.+1 FORTRAN subroutine l Decision Printed o t t " u pu Scaled stiffness K Off page connector Constant matrix H OUOODUW A) Figure 2: Computer Program Flow Diagram 58 AtErHA Iteration=1 B a (AtE’iAr‘ Matrix inversion routine 3’23”" -131“ (ABE’RA)B"" i; Qr matrix Jacobian J r Constraintzfunction Gr FIGr-erzr Section table matrix 9F,‘8r 1 Coefficient matrix and right side vector for binary programming Figure 2: Iteration-1 Js Initial binary vector db and objective function value F(d°) Binary Programming routine Transform binary solution to discrete solution, Z? 1 Results Solution has converged or maximum number of iterations reaghed No (cont'do) 59 77177 7772377 F‘— 30' T 30' . whips #okips . I—u 1%- "_" ‘5 . 16111 16111 ‘5' ‘1 ZOMPB T a '5' .21” i Figure 3-1: One-Story, Two-Bay Frame m (a; @ <3)@ ‘5” (5) 5 6 h 7 e 1 e“ a s 0) Number of free joints 5 KEY: ( ) free joint Number of member groups 3 member group Number of design members 7 1,2,.. member number Figure 3-2: Structural Topology and Member Groups .....1 6O Zokips if ”H 10“” > 10111 T .201mm ‘5 72" \/ 8W a: La whips 10w i811: Q 8 1.— ~——— w 4”? a Figure A-1: Two-Story, One-Bay Frame eP'H’Je 53 e11 2 he) Number of free joints 6 Number of member groups 3 Number of design members 8 Figure u-2: Structural Topology and Member Groups 61 whips ps kips magi—‘5 i 1619 L—‘SL—‘Jl 16w F‘s—11'}, 1 16w T 2 hob-PS 3:? 110m” ~1- hoki :- 151 Figure 5-1: Two-Story, Three-Bay Frame (8) - ( ) 1o (10) 11 (11) 12 (12) 13(13) 1:. (11.) @ e G5 C5 @ 5 G) 6 (1) 1 ( 6 (5) ( ) 8 0 0 0 0 ® 1 ® a. 3l® Number of free joints 1h Number of member groups 8 Number of design members 20 Figure 5-2: Structural Topology and Member Groups 61 whips “claps wkipa kip PW?) 1611 “-15% 16w “—15% 16w :33- M)kips i. hold” .1- hokips :- 15, Figure 5-1: Two-Story, Three-Bay Frame Number of free joints 1h Number of member groups 8 Number of design members 20 Figure 5-2: Structural Topology and Member Groups 62 n... 22211322223532;26.35.23221 ..-... Section 12 Ax Z'x Section Iz Ax ax (in4) (ina) (in3) (in4) (ing) (in3) 14 w 22 198 6.49 55.1 16 w 26 500 7.67 44.0 14 w 26 244 7.67 40.0 16 w 31 574 9.15 54.0 14 w 50 290 8.85 47.2 16 W 56 447 10.6 64.0 14 w 34 540 10.0 54.6 16 w 40 517 11.8 72.8 14 w 58 586 11.2 61.6 16 w 45 584 15.5 82.1 14 w 45 429 12.6 69.7 16 w 50 657 14.7 91.8 14 w 48 485 14.1 78.4 16 w 58 748 17.1 106 14 w 55 542 15.6 87.1 16 w 64 856 18.8 118 14 w 61 641 17.9 102 16 w 71 941 20.9 152 14 w 68 724 20.0 115 16 w 78 1050 25.0 146 1A W 74 797 21.8 126 16 w 88 1220 25.9 169 14 w 78 851 22.9 154 16 w 96 1560 28.2 186 TABLE 1-2: Available Sections for Two-Story, One-Bay Frame 65 Section I” A3 a‘ Section I” Ax 5* (inn) (inz) (in ‘ (inn) (inf)__(in§l 8 w 10 50.8 2.96 8.86 10 w 15 68.9 4.41 16.0 8 W 15 59.6 5.85 11.4 10 w 17 81.9 4.99 18.6 8 w 15 48.1 4.45 15.6 10 w 19 96.5 5.61 21.6 8 w 17 56.6 5.01 15.9 10 W'21 107 6.20 24.1 8 w 20 69.4 5.89 19.1 10 W’25 155 7.56 29.6 8 W 24 82.5 7.06 23.1 10 W 29 158 8.54 34.7 8 w 28 97.8 8.25 27.1 10 w 55 171 9.71 58.8 8 w 51 110 9.12 50.4 10 w’59 210 11.5 46.9 8 w 55 126 10.5 54.7 10 w 45 249 15.2 54.9 8 W'40 146 11.8 59.8 10 W'49 275 14.4 60.5 8 W 48 184 14.1 49.0 10 W 54 306 15.9 67.1 8 w 58 227 17.1 59.7 10 W’60 544 17.7 75.0 64 #m a @— useums . . bsopma an a JP u . S m Jm 3 m— 5H0 H messes . as an a :— mm a m— : mJeN *Omw: NM 2 JP $0.0 MN — vaflMHUOE an a a. m mm s w. 2 uawwum as.~ momma Nm 3 a. mn.o mm . assessors an s a. . messes mass esmaes msoaeeem ease wwswmm msoeeaueeH massacres asses am»: soo . nausea Hopes sowusaom cemsm>soo msussmsmosm humsam no oz soaumaom museum Ammmooomuosfiav measmom mmswp .NNBJP .ensep ”newsman HmdpfisH m unvvfiififldm w «OHDEH dadaoom MO nvwdflfl mam so usoaeaesoo sosessaees eases museum msamsos hoe .sz.eaesoz msaeoom ems .a.eeeoa Hesse .m> .uz.esesoz mosescm assessomaa assesses .ms sasseomsm m.soasaeoem "seamen samurai HaaoasH seas _ massage hoe seasons alum mamas 65 mm a m_ a s_.m .ommm mm s a. mo.o m_ m assesses . mm a a. m mm a o_ . a .a a ms.o_ momma mm a a. mm.o ow m somaeeooe . .11 mm a a. m mm s m_ . a s_.m some: mm a a, 00.0 mm m eeeeseoz mm >4" +2 N can mm s m. : ushers ss.s momma mm s a. os.o an. m moseeeoew mm. b... ...: sesame mess parses msoseeem ease mmawmm csoasmsoeH sseaeomsa eases lapses sopmmwmm soassaom cowsossou weassmsmonm humsflm mo .02 soapmaow mwospm “noncommuoswsv measwom onse— .mma.: .mmaf «nausea mesons m "speasmcmm w "eases soauoem no nausea mam so assessesoo soaessaeea eases mucosa msameos see .n:.esesoz waspsom was .m.oosoh amass .m> .N£.usosoz mswmsem “sneauomam commemo: .m> massacres m.soaseeoem "seamen seemese HmaeasH sees a massage see dresses "mum mamas 66 TABLE 3: Results for Ekample 1 with Starting Point Varied ConditiOns of Fun Initial Design: Guessed Stress Limit: Mz Length of Section Table: 8 Bandwidth : 5 Solution Algorithm: Geoffrion's EEEElEE (Time:seconds) Initial N2. of Binary Prog. ConvergedSolution gotal Design .6133" 3331:: Time Sections | Weight figgut" 14 W 22 14 w 22 1 2.82 No solution 5.80' 16 W 26 14 w 50 14 W 26 1 2.90 No solution 3.91 16 W 31 14 w 58 14 w 58 #41011! *9 14 w 58 1 90 0.48 14 w 58 “Mesh 1.50 .16 W 45 16 w 45 sible) 14 W 58 14 W’58 14 w 26 3 157 0.70 14 w 22 4950’“ 7.74 16 W 50 16 W 58 14 W'54 14 W'54 14 w 22 1 78 0.59 14 w 22 4850# 2.77 16 W 58 16 W 58 14 W 45 14 W 55 # * 14 W 50 5 145 0.69 14 W 22 4920 4.55 16 W 64 16 W 50 14 w 55 14 w 58 14 w 45 5 141 0.75 14 w 22 49507"! 12.78 16 W 64 16 W 58 (*Computer time is shorted because to intermediate results were printed) 67 TABLE 4: Results for Example 1 with Bandwidth and Section Table Length Varied Conditions of Run Initial Design: Guessed -- 14W38, 14W26, 16W50 Stress Limit: Mz Solution Algorithm: Geoffrion's Results (Time:seconds) Length Band- No. of Binary Prog. Converged Solution Total giogec- Itera- No. 08 4 Table Width tions Cycles Time Sections weight Time 14 w 58 1 8 5 1 28 0.10 14 w 26 4550* 2.28 16 W 50 14 w 58 8 5 5 157 0.70 141122 49508f 7.74 16 W 58 14 w 58 8 7 5 559 2.24 141122 4950?“ 15.14 16 w 58 14 w 58 ' 12 5 1 28 0.09 14 w 26 4550# 1.12' 16 W 50 111. W 38 12 5 5 119 0.585 14 w 22 4950# 4.09‘ 16 W 58 14 w 58 , 12 7 5 255 1.59 14 w 22 4950” 7.15' 16 w 58 14 w 58 u * 12 9 5 469 5.65 14 W 22 4950” 15029 16 W 58 __.__ 14 w 58 .. 12 11 5 758 7.00 14 w 22 4950” 25.50* 16 w 58 68 m: 5... @- 0m 3 mp .. .m.e_ seems an s e. mw.e was m on a m. e 4 s mm s a. mm s s. an a s_ mm a a. mm a m. on s m. : £35 4440mm: mm a 4: ~30 mmp m mm a +2 m . mm s s. mm a as tandem a » mm a .2 mm a. i: 0% 9 oh messes seesmmww esmeoe msoaeeem ease mma.om msoaemaoeH mesons memsom Ifimmmm Hence soapsnom comaessoo meassmamosm mamsfim mo .02 HmeHsH mo .02 anemones " oars magnum m.soaseeoeo ”smeauomaa m "samenessm as “eases unease m "eases someone so summed mam so msoaeaeseo messes masons sense: seas F massage see measuem "m mamas 69 . . r111.--;.n .-L so a m— : .~_~._ soaesamm m-.0 . me a a. 0.. mm s i: so a 0, :0 s m— : sOMOe— fihmom M3 3 +2. no.0 Np F “J 3 JP moo mm a +2 mm a 4: mm.a m. :0 a 0. .. .Rm.s .0.85 mm a .: ate 0.: a a. s f To me 3 ..2 mm 3 a: can mm a 0. so a m— ..weea was: some. a... a .: ass a: a 9 s .: axe mm a .2 mm a .: messes ease nausea usoaeeom ease wmame_nsoaeaeeeH eases schema sousasoo . tandem Hence soausaom somaeesoo msassmnmosm bemoan no 02 waspsmum smog Ampsooomuosaav measmmm m.souumuoow usauduomad m "spmfispsmm a: "eases eschew 0 ”cases someone so senses gm mo 0:03.358 sesame assess sacs seas _ seasons see muHsmmm um Hands TABLE 7: 70 Results for Example 2, Two-Story, One-Bay Frame Condition of Run Length of Section Table: Solution Algorithm: 12 Modified Bandwidth: 5 Results with Initial Plastic Design (8W31, 8W13, 10419) No. of Binary Prog. Converged Solution Ligiis 8:65:81 i:g;:'-E;EE§J Time Sections Volume $2681 8 w 51 8 w 51 M2 8 w 15 4 55 0.08 8 w 20 4285 9.82 10 W 19 10 W 25 8 W 31 8 W 31 p, M2 8 11115 4 57 0.16 8 w 20 4285 15.26 10 W 19 10 W 25 Results with Initial Guessed Design (8W28, 8W24. 10w29) 8 W 28 8 W 28 M2 8 W 24 2 33 0.09 8 W 24 4321 5.54 10 W’29 10 W 25 8 W 28 8 W 31 P, Mz 8 W 24 3 36 0.16 8 W 24 4450 10.85 10 W 29 10 W 25 Results of Comparing Continuous and Discrete Designs Discrete (Author's) Continuous (Ref.22) Stress Limit M2 P’ M2 M2 P’ M2 3 5 5 5 NO. or Iterations 2 3 5 4 Time for each Iteration 2'2 3’5 10 12 "3th. Prog. 0008 0.15 5 7 Time for BP sec. for LP sec. Total Computer 5.34 10.83 50 48 Time sec. sec. sec. sec. w .. '5 :a-g' u TABLE 8: 71 Results for Example 3, Two-Story, Three-Bay Frame Conditions of Run Initial Design: Guessed Member Group 1 2 3 4 5 6 7 8 Section 14W43 14W26 1411143 14W26 1611164 1611164 16W64 16W64 Length of Section Table: 8 Bandwidth: 5 working Stress Limit: M Solution Algorithm: Modified Results (Time:seconds) Member Group 1 2 3 4 5 6 7 8 Section 14W43 14W26 14W43 141126 1611164 161145 161158 16W58 No. of Bhgary . Time per Total Iterations .of Time weight Iteration Time Feasibility Cycles t 2 56 0.55 14550 11.50 25.5’ Feasible TABLE 9: Results for Different Sizes of Structures (Modified Algorithm) (Time:seconds) Simple Portal One-Story, Two-Story, Two-Story, Frame Two-Bay One-Bay Three-Bay Frame Frame Frame Number of Members 9 7 8 20 N0. 0! Binary Prog) 9 25 55 56 Cycles B P Tiggry r°5‘ 0.017 0.06 0.09 0.55 er * $423,710, 0.64 1.74 2.25 11.5 LIST OF REFERENCES 1. 2. 3. 4. 5. 6. 7. 9. LIST OF REFERENCES Schmit, L. A., "Structural Design by Systematic Synthesis," Proceedings of the Second National Conference on ElectronicComputatign, StructuralDivision, , ttsburgh, Pa., September 1960, pp. 105-132. Heyman, J., "Plastic Design of Beams and Plane Frames for Minimum Material Consumption," Quarterly of Applied Mathematigs, Vol. 8, No. 4, 1951, pp. 575-5 1. Livesley, R. K., "The Automatic Design of Structural Frames," arterl Journal of Mechanics and Applied Mathematics, VoI. 8, Part 3, september 1956, pp. 257-27 80 Foulkes, J., "Minimum Weight Design and the Theory of Plastic Collapse," Quarterly of Applied Mathematics, Vol. 10, No. 4, 1953, pp. 347-3 . Prager, W., "Minimum-Weight Design of a Portal Frame," Journal of the Eng%neering Meghgpigs Dizigign, ASCE, o . , o. , ctober 195 , paper 1073. wasiutynski, Z. and Brandtpr., "The Present State of Knowledge in the Field of timum Design of Structures," Applied Mechanigs Reviews, May 1963, pp. 541-550. Sheu, C. Y. and Prager, W., "Recent Developments in Optimal Structural Design," Applied Mechanics Regiews, Vol. 21, No. 10, October 196 , pp. 9 5-992. , Schmit, L. A., "Structural Synthesis 1959-1969: A Decade of Progress," Paper Presented at the 0.8. - Japan Seminar held at Tokyo in August 1969, "Recent Advances in Matrix Methods of Structural Analysis and Desi n," edited by Gallagher, R. 3., étc., e niversity of Alabama in Huntsville, 1971, pp. 565-63lFe Moses, F., "Optimum Structural Design Using Linear Programming " J u al of the Structural Division, ASC , Vol. 90580". 8T6; "IF—Toember 19 4'."'p' p. 89"5—104. 72 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 75 Cornell, C. A., Reinschmidt K. F. and Brotchie, J. F., "Structural Optimization," Research Report R65-26, Part 2, Department of Civil Engineering, M.I.T., Cambridge, Mass., September 1965. Cornell, C. A., Reinschmidt, K. F. and Brotchie, J. F., "A Method for the Optimum Design of Structures ' Proceedings of International Symposium on the Use of Computers in Structural Engineering, Newcastle- Upontyne, England, July 1966. Reinschmidt K. F., Cornell, C. A. and Brotchie, J. F., "Iterative Design and Structural Optimization," Journal of the Structural.Division ASCE, Vol. 92, fio.’ST6; December 1966, pp. 281-518. Nakamura, Y., Cornell, C. A. and Reinschmidt, K. F., "Optimum Design of Framed Structures Using Linear Programming," Research Report R66-4, Department of Civil Engineering, M.I.T., Cambridge, Mass., January 1966. Reinschmidt, K. F. and Russell, M. D., "Linear Methods in Structural Optimization," Research Report R70-41, Department of Civil Engineering, M.I.T., Cambridge, Mass., July 1970. Ridha, R. A. and Wright, R. N., "Minimum Cost Design of Frames," Jpprnal of the Structural Division ASCE, Vol. 95. No. 5T4, August 1967, pp.'i652185. Toakley, A. R., "Optimum Design Using Available Sections," Journal of the Structural Dizision, ASCE, vol. 94. No. 5T5, May 1968, pp. 1219-1241. Gomory, R. E. "Outline of an Algorithm for Integer Solutions to near Programs," Bulletin of the American Mathepatigg; Sggjgty, Vol. 64, 195 , pp. 275-27 . Reinschmidt, K. F., "Discrete Programmin Problems in Structural Design," Research Report 9-50, Department of Civil Engineering, M.I.T., Cambridge, Mass., August 1969. Reinschmidt, K. F., "On Discrete Structural Optimiza- tion," Paper Presented at 5 th Conference on Electronic Computation. inurnal_0f_§truciural_Dizi§iQD. 850E. V01. 97’ NO. 5T1, January 1971. Pp. 189-222. 20 21. 22. 23. 24. 25. 26. 27. 28. 29. 31. 7A Geoffrion, A. M. "I e P n b In licit Enumeration and Salas' Method,’ Memo. #7 3- . Rand Corp., Santa Monica, Calif., February 1966. Balintfy, J. L., "Menu Planning by Computer," Communication of the ACM. Vol. 7, No. 4, April 196A, PP. 255'2590 McCutcheon, W. J., "A General Formulation for the Optimum Design of Framed Structures," Ph.D. Thesis, Department of Civil Engineering, university of Illinois, Urbana, 111., July 1970. Bigelow, R. G. and Gaylord, E. H., "Design of Steel Frames for Minimum weight," Jougnal of the Stgggtgzgl Division ASCE,'Vol. 93. No. ST , December 19 7, pp. 109-131. Hall, A. s. and Woodhead, R. W., "Exams Analygis," John Wiley and Sons, 1961. Fenves, S. J. and Branin F. H., "Network-Topological Formulation of Structural Analysis," Journal 9; the Structnrg% ggang, ASCE, Vol. 89, No. 5T4, August 19 3. pp. A 3-51u. Americal Institute of Steel Construction, Manual S eel Construction, 7 th Edition, 1970. Balas, E., "An Additive Al orithm for Solving the Linear Programs with Zero- e variables," Qperations Research, Vol. 13, No. A, July-August 1965, PP. 517-5h6o Gonzales 0., A. and Fenves, S. J., "A Network-Topological Formulation of the Analysis and Design of Rigid- Plastic Framed Structures," Structural Research Series, No. 339. Department of Civil Engineering, University of Illinois at Urbana, 111., September 1968. Remstad K. M. and wang, C. K., "Optimum Design of Framed Structures," Journal of the Stguctural Division, ASCE, Vo1. 94. No. ST12, December 196 , pp. 2 17-2 45. Balinski, M. L., "Integer Programming: Methods, Uses, Computation," Management Science. Vol. 12, 1965, pp. 253-313 , Glass, H., "A_§§:Q=Qng_Alggzithg," Heneywell Aeronaut. Div., St. Petersburg, Fla., December 1965. 32- 33- 3h. 35. 36. 37. 38. 39. 40. 75 Glover, F., "A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem," Operations Besggzgh, Vol. 13, No. 6, November-December 19 5 PP. 79.919- Lawler, E. L. and Bell, M. D., "A Method for Solving Discrete Optimization Problems," Operations Research, Vol. 14 No. 6, November-December 1966, pp. 1093-1112. Lenka. 0. E. and Spielberg. K., "W and Mixed Integer Programming,‘ IBM Scientific Center, New York, June 196 . Balas, E., "Discrete Programming by the Filter Method," ngzagiggs Research, Vol. 15, No. 5, September-October 19 7. PP. 915-957. Geoffrion, A. H., "An Improved Implicit Enumeration u Approach for Integer Programming,Memo. RN35644-PR, Li Rand Corp., Santa Monica, Calf!" June 1968. Gue, R; L., Liggett, J. C. and Cain, K. 0., "Analysis of Algorithms for the Zero-One Programming Problem," Communications of the ACM, Vol. 11, No. 12, December 1968, pp. 837-8AA. Byrne, J. L. and Proll, L. G., "Algorithm 3A1: Solution of Linear Programs in Zero-One Variables by Implicit Enumeration," Communications of the ACM, Vol. 11, No. 11, November 19 , p. 7 2. Beedle, L. 5., "Plastic Design of SteelFrames." John Wiley and Sons, New York, 1958. 1414‘ Conversational Linear Programming, Michigan State University, unpublished, undated. Ilofii‘! ‘fiiflvfifi. F1. 12L—