## efficient optimization algorithms – Global Homework Experts

Layout optimization of

large-scale pin-jointed frames

Matthew Gilbert and Andrew Tyas

Department of Civil and Structural Engineering, University of Sheffield,

Sheffield, UK

Keywords Structural analysis, Linear programming, Optimum design

Abstract Computerized layout (or “topology”) optimization was pioneered almost four decades

back. However, despite dramatic increases in available computer power and the application of

increasingly efficient optimization algorithms, even now only relatively modest sized problems can

be tackled using the traditional “ground structure” approach. This is because of the need, in

general, for the latter to contain every conceivable member connecting together the nodes in a

problem. A simple, but effective solution method capable of tackling problems with large numbers

of potential members (e.g. .100,000,000) is presented. Though the method draws on the linear

programming technique of “column generation”, since layout optimization specific heuristics are

employed it is presented as an iterative “member adding” method. The method requires a ground

structure with minimal connectivity to be used in the first iteration; members are then added as

required in subsequent iterations until the (provably) optimal solution is found.

Introduction

Computer-based discrete layout optimization methods for frameworks were

first developed almost four decades back by Dorn et al. (1964), who proposed a

formulation based on plastic design principles. They found that linear

programming (LP) algorithms, which had then only recently been developed,

could be used to select the subset of members that should be present in the

optimal structure.

For plastic layout optimization, the original method was soon extended to

allow multiple load cases and self-weight to be included. A comprehensive

account of this work has been presented by Hemp (1973). Subsequently, in

order to avoid the optimization process leading to impractical Michell type

structures (which contain large numbers of joints and very short members),

Parkes (1975) proposed a means of including joint costs in the formulation. In

fact this method penalises short members rather than the number of joints per

se. It is important to note that, for plastic design, inclusion of these additional

features does not change the linear nature of the problem.

In contrast, for elastic layout optimization with limiting stress criteria it is

well known that computational difficulties arise when multiple load cases are

involved. This is largely due to the likely existence of singular topologies

(Rozvany, 2001; Rozvany and Birker, 1994). In such cases both the

mathematical programming and the so-called “optimality criteria” methods

(Zhou and Rozvany, 1991) will often fail to identify the true optimal frame

The Emerald Research Register for this journal is available at The current issue and full text archive of this journal is available at

http://www.emeraldinsight.com/researchregister http://www.emeraldinsight.com/0264-4401.htm

EC

20,8

1044

Received November 2002

Revised July 2003

Accepted July 2003

Engineering Computations

Vol. 20 No. 8, 2003

pp. 1044-1064

q MCB UP Limited

0264-4401

DOI 10.1108/02644400310503017

layout. However, it is also known that for elastic design with multiple load

cases, by using the layout from a plastic optimization as the basis for an

optimal elastic frame only a relatively small error (e.g. a few per cent) will often

ensue (Kirsch, 1990). This might mean that a practical optimization tool might

well be based on the plastic method even if limiting (elastic) stress design was

the ultimate goal of the optimization process.

In fact one of the main problems with both types of layout optimization,

elastic and plastic, lies in the fact that a large network of potential

members interconnecting specified discrete points, or nodes, in the design

domain is required. Such a network of potential members is referred to as

a “ground structure” (or “structural universe”), and should, if possible,

contain many members since the optimal structure can only be formed

from members present initially. Assuming that each node is connected to

every other node, for a general 2D or 3D design domain, it can be shown

that a total of ðn 2 1Þ þ ðn 2 2Þ þ · · · þ 2 þ 1 [i.e. nðn 2 1Þ=2] members

must initially be present, where n is the number of nodes in the problem.

This is an upper limit on the number of members present as some workers

choose to omit the overlapping members from the ground structure. It

should be noted that the latter simplification will, in general, prevent

optimal solutions from being obtained, should features such as structural

self-weight or joint costs be included in the problem definition (this will

invariably be the case for real-world problems). Figure 1 shows a sample

design domain and loading and support conditions, together with minimal

and full connectivity ground structures.

Though using a fully connected ground structure is desirable, unfortunately

the number of members present in the problem clearly becomes unmanageably

large (because nðn 2 1Þ=2 members are required). Thus, for example, an

apparently modest 40 £ 40 node, single load case problem with a fully

Figure 1.

(a) Design domain

(2 units £ 1 unit),

loading and support

conditions; (b) minimal

connectivity ground

structure containing

11 bars; and (c) full

connectivity ground

structure containing

15 bars (includes

overlapping bars)

Layout

optimization

1045

connected ground structure generates several thousand LP constraints and

well over 2 million LP problem variables (using the lower bound plastic

analysis problem formulation for each physical member a total of 2m LP

problem variables are generally required). Such a problem generally requires

large amounts of CPU time and memory to solve. Additionally, the fact that the

number of members (and LP variables) increases as a function of the square of

the number of nodes means that practically large 3D problems are unlikely to

be solvable in the foreseeable future using the existing methods.

Though it would seem sensible to start with a smaller structure and to add

members to this as and when required, the most recent comprehensive review

of the available literature (Rozvany et al., 1995) indicates that “no simple

methods are available at present for finding the optimal position of additional

members”. More recently, Kirsch (1996) has considered expansion processes,

but concluded that the “development of a systematic method for adding

members. . .is still a challenge”.

For plastic optimization problems the method described in this paper

appears to overcome this difficulty. Additionally, when only a single load case

is involved, the procedure will also provide the optimal structure for the elastic

design with stress constraints problem.

The proposed member adding scheme described in this paper requires that

an initial, minimal connectivity, ground structure is present. The number of

members in the ground structure is increased at each step in an iterative

process to permit the selection of increasingly efficient structural layouts.

Thus, conceptually it may be considered that the method makes use of an

“adaptive ground structure” which grows according to the particular design

constraints present. Alternatively, since it will be found that the initial ground

structure does not influence the optimal structure obtained, as far as the user is

concerned the whole notion of a ground structure may be disregarded since it is

actually only the extent of the design domain, the specified nodal density and

the loading/support conditions which will have any influence on the optimal

design.

It is shown that by using the method very significant reductions in CPU time

and memory requirements can be realised. Although only 2D structures are

considered in this paper, the technique is applicable to 3D structures and

treatment of quite large, practical, 3D problems should be possible using the

method.

Classical plastic layout optimization

The whole field of plastic layout optimization appears to have been largely

ignored for many years. This is despite the fact that many structures are

currently designed to meet the requirements of limit state design codes (i.e.

codes of practice based on plastic design principles). Additionally, new and

increasingly effective LP solution algorithms are becoming available (e.g. the

EC

20,8

1046

so-called “interior-point” or “barrier” methods, based on the work by

Karmarker (1984)). For these reasons, and with a view to enhance the existing

procedures, it was felt that the classical plastic method warranted further

study. A brief description of the two classical plastic layout optimization

formulations are given in the following sections.

The lower bound (primal) formulation

The lower bound LP plastic design formulation for the minimum volume

problem for a ground structure subjected to a single load case and containing m

members and n nodes are stated as follows:

min V ¼ qTc ð1Þ

subject to

Bq ¼ f ð2Þ

qþ i ; q2 i $ 0; i ¼ 1; . . .; m

where V is the total volume of the structure, qT ¼ {qþ 1 ; 2q2 1 ; qþ 2 ; 2q2 2 ; . . .

2q2 m}; cT ¼ {l1=sþ 1 ; 2l1=s2 1 ; l2=sþ 2 ; 2l2=s2 2 ; . . . 2 lm=sþ m}; B is a suitable

ð2n £ 2mÞ equilibrium matrix and fT ¼ { f x 1; f 1y; f x 2; f 2y; . . .f ny}; and

li

; qþ i ; q2 i ; sþ i ; s2 i represent, respectively, the length and tensile and

compressive member forces and stresses in member i. Finally, f x j ; f y j are x

and y direction live load components applied to node j. Using this formulation

the LP problem variables are clearly the member forces, qþ i ; q2 i :

The upper bound (dual) formulation – obtained using duality principles

The upper bound LP plastic design formulation for the same problem may be

derived using duality principles from the lower bound formulation (Hemp,

1973), and are possibly stated as follows:

max W ¼ fTu ð3Þ

subject to:

BTu # c ð4Þ

where uT ¼ {ux 1; u1y; ux 2; u2y; . . .uny}; and ux j ; ujy are the x and y direction virtual

nodal displacement components, i.e. the objective is to maximise the virtual

work of the given forces taken over the virtual nodal displacements, subject to

limits on the virtual member strains. Note that in the dual LP formulation the

problem variables are the nodal displacements uj.

Layout

optimization

1047

The upper bound (dual) formulation – obtained from Michell’s optimality

criteria

Alternatively, the constraints required in the dual formulation may be obtained

from Michell’s optimality criteria. In a Michell structure, the ground structure

effectively comprises an infinite number of members. Michell’s optimality

criteria (Michell, 1904) states that in an optimal structure the magnitude of the

virtual member strain 1i in each member i with non-zero force is given by:

1i ¼

1 þsi

or 1i ¼ 2

1 2si

ð5Þ

and also, when (5) does not hold, that:

2

1 2si

, 1i ,

1 þsi

ð6Þ

i.e. for all members:

2

1 2si

# 1i #

1 þsi

ð7Þ

Expressed alternatively in terms of member displacement ui we have:

2

1 2si

#

ui

li #

1 þsi

ð8Þ

If member i connects two nodes j and k, and also assuming that displacements

are small, the member displacement can be written in full as:

ui ¼

1 li

h i xk 2 xj ux k 2 ux j þ yk 2 yj uky 2 ujy ð9Þ

where the original co-ordinates of nodes j and k are denoted, respectively, as

ðxj; yjÞ and ðxk; ykÞ; and their x and y direction infinitesimal displacements are,

respectively, ux j ; ujy and ux k; uky : Substituting equation (9) into equation (8)

gives:

2

1 2si

#

1 2li

h i ðxk 2 xjÞ ux k 2 ux j þ ð yk 2 yjÞ uky 2 ujy # s1þ

i

ð10Þ

Now, imposing constraint (10) for all m members in the discretized layout

opimization problem is exactly equivalent to imposing condition (4), obtained

alternatively using duality principles. Thus, for a given ground structure, the

dual LP problem constraints are equivalent to Michell’s constraints, and hence

are sufficient to enable an optimal solution to be obtained.

EC

20,8

1048

Plastic layout optimization: development of a member adding

approach

The main objective of the present investigation has been to develop an

alternative plastic layout optimization procedure in which problem size

increases much less rapidly with the number of nodes in the design domain

than when using current methods. The subsequent section describes the

background to such a method.

Solution of large-scale LP problems

Over the past few decades, many techniques have been developed for solving

the large-scale LP problems. Typically, problems can be so large that it is

impractical to store all variables and constraints at any given time. Hence, the

so-called “decomposition” procedures are typically employed. “Column

generation” describes the process used in decomposition procedures whereby

additional variables (or “columns”) are added to a reduced LP problem, the

latter usually being termed the “restricted master problem” (RMP). The column

generation technique follows on from the analogous technique of “cut

generation” applied to the dual problem (Kelley, 1960). In this case, violated

constraints (or “cuts”) not present in the reduced LP problem are added.

Though originally used in conjunction with simplex based LP algorithms,

column generation techniques have been recently considered in the context of

interior point methods (Gondzio and Sarkissian, 1997). In order to be effective,

column generation techniques are typically used in conjunction with the

problem specific heuristics, said to be implemented by a so-called “oracle”.

Often the oracle will add just one column (or cut) to the restricted master

problem at each iteration though in the method described here typically many

columns are added simultaneously.

Perhaps surprisingly, decomposition techniques appear to have been rarely

applied to structural layout optimization problems. Woo and Schmit (1981)

describe a method involving the use of the revised simplex method to solve the

restricted master problems of Dantzig Wolfe decomposition, primarily to

generate extreme points in the case of problems involving smooth (i.e.

non-polyhedral) convex sets (for example, rigid-plastic design using constant

stress elements).

For the plastic frame layout optimization problem described in this paper

the LP variables correspond to the members (i.e. member forces or member

forces and areas in an expanded multiple load case formulation). Since

the plastic layout optimization specific heuristics are used, the expansion

process developed can alternatively be usefully described in structural terms,

i.e. as involving “member adding”. Member adding can be viewed as one

technique which may be used as part of “expansion”, or “adaptive ground

structure”, procedures used in the efficient solution of layout optimization

problems.

Layout

optimization

1049

Initial connectivity heuristic

Central to the success of any member adding method is the choice of initial

frame. Once chosen this then allows the formulation of the initial RMP. Ideally,

the number of members in the initial structure should be as small as possible, to

save computational effort. However, the initial frame should be structurally

stable (i.e. not a mechanism) to allow a structurally stable optimal structure to

be formed from a subset of its members. Furthermore, to reduce the

computations required, the initial frame should ideally be as near optimal as

possible.

The simplest approach is to initially only connect adjacent nodes together

(i.e. as in the case of Figure 1(b)).

Suitable optimality criteria – checking the virtual member strains

The virtual member strain constraints (10) correspond to the member force

variables in the dual LP problem. Unless a given member is present in the

RMP, these values are not available directly. However, following an initial

optimization the virtual member strains for each potential member may readily

be calculated and checked using constraint (10). This is straightforward

because nodal displacements are included in the dual LP problem formulation;

hence the data are available following an optimization and it is trivial, and

computationally inexpensive, task to calculate the implied virtual strain in each

potential bar linking every pair of unconnected nodes.

Additionally, because the data from the dual LP problem are generally

available (either throughout or once an optimal solution has been found) it is

not necessary to pose the problem in upper bound form. The dual variables

corresponding to the lower bound nodal equilibrium constraints represent the

nodal displacements required in the calculations above.

It is also worth noting that adding a member which initially has zero

force/area to the lower bound problem formulation does not lead to violation of

any of the lower bound constraints. Thus, the optimal solution from a given

iteration will also represent a basic feasible solution for the next iteration;

making use of this advanced basis in a computer program can reduce CPU

times, particularly when simplex based LP solvers are used.

If constraint (10) is not satisfied for any potential member, it follows that the

solution is likely to be non-optimal. Hence, in this case one or more new

members should be added.

Simple example

A simple example serves to illustrate how a member adding procedure might

work. Suppose the ground structure, loading and support conditions given in

Figure 1(b) are used initially (also shown in Figure 2(a)) and that all members

are formed from material with a limiting compressive and tensile stress of

unity. Following the initial LP optimization process, a minimum volume of

3.36603 is calculated (optimal structure shown in Figure 2(b)).

EC

20,8

1050

The virtual nodal displacements associated with the initial optimal solution

are required by the member adding method and are presented in Table I.

Using the proposed procedure, which is designed to tackle general cases, the

virtual strains in all potential members not present in the current ground

structure (i.e. AE, AF, BE and BF) would need to be checked to see whether

condition (10) is satisfied. However, as potential members AE and BF overlap

the existing members and since this particular problem does not include for

example, joint costs and/or self-weight, it is clear by inspection that the strains

in these particular potential members need not be checked.

Then, consider the implied virtual strain in potential member, AF:

1AF ¼

1

L2

AF

ðxF 2 xAÞ ux F 2 ux A þ ð yF 2 yAÞ uy F 2 uy A

¼

1 5

½ð1Þð5Þ þ ð22Þð21Þ ¼ 7

5

Figure 2.

(a) Initial minimal

connectivity ground

structure, containing 11

bars; (b) initial optimal

structure

(volume ¼ 3.36603); and

(c) final optimal structure

obtained using the

member adding

procedure

(volume ¼ 2.63397)

Node x displacement y displacement

C 3 21

D 2 0

E* 4* 0*

F 5 21

Note: *Because E is not connected by any members in the optimal structure, various

displacement values are possible

Table I.

Example: virtual nodal

displacements taken

from initial optimal

solution

Layout

optimization

1051

Since 7=5 . 1, condition (10) is violated. Hence, member AF should be

considered as a candidate for admission to the ground structure at the next

iteration.

Additionally, it is evident that prior to the next iteration that if all

displacements were scaled down by a factor of 1=ð7=5Þ ¼ 5=7 then all dual

constraints would be satisfied. This means that a lower bound on the volume

can be calculated to be 3:36603 £ 5=7 ¼ 2:40431:

In this example, once member AF is added to the ground structure the form

of the final optimal structure may be determined following the next LP

iteration. This latter structure has a much reduced weight of 2.63397 and is

shown in Figure 2(c).

Heuristic criteria for adding a new member

It is clear that only those potential members which violate constraint (10) need

to be considered as candidates to be added to the ground structure at the next

iteration. However, though for a trivial problem a strategy which involves

adding to the ground structure all members which fall into this “candidate”

category may work well, in the case of larger problems a different approach is

required. This is because unless the structure found following the first LP

iteration is near optimal, a prohibitively high number of members would fall

into the candidate category at this stage and would then have to be added. To

counter this, a simple but effective heuristic procedure has been developed.

(1) Set iteration count k¼0 and select initial ground structure containing mk

members (forms initial RMP).

(2) Solve RMP (and its dual).

(3) Select value for filter parameter b and set counter of number of candidate

members, madd k ¼ 0.

(4) For each potential member ði ¼ mk þ 1 . . . mallÞ; compute ki ¼

max 1isþ i ; 21is2 i ; if ðki $ bÞ then madd k ¼ madd k þ 1.

(5) If (b ¼ bmin or madd k ¼ am0) then add all madd k members to RMP; else if

madd

k . am0 sort the madd k candidate members in descending order

according to ki and add top am0 members in list to RMP; else k¼k+1

and repeat from step 3.

(6) k ¼ k+1.

(7) If madd k – 0 then repeat from step 2.

The algorithm works by employing a two stage high pass filter. The first stage

of the filter, controlled by parameter b, limits the number of candidate

members that need to be subsequently sorted into priority order for admission

into the frame. In most cases b, which must always be greater than unity, is

best set at some fixed proportion of the maximum observed value of ki, denoted

k

max. The second stage of the filter, controlled by parameter a, governs the

EC

20,8

1052

maximum number of members which can be admitted at each iteration (the

latter being taken here to be am0, where m0 is the number of members present

initially).

Sometimes the first stage of the filter will block out too many candidate

members, leaving less than am0 members to be added. In such cases, rather

than adding only a few members and then solving a RMP which is only slightly

different to the previous one, provided b is greater than b min then k is

incremented and a new (lower) value of b is tried. Thus, the number of

algorithm iterations k may often be greater than the number of LP iterations.

As stated earlier, selection of b in step 3 normally requires prior knowledge

of k max. To obviate the need to initially loop through potential members to find

this maximum value prior to step 3, for the purposes of the work described in

this paper, for iterations 1-13, respectively, b has been taken as 1.4142, 1.4,

1.325, 1.2, 1.15, 1.1, 1.075, 1.05, 1.04, 1.03, 1.02, 1.01, 1.005 (subsequently b ¼

bmin ¼ 1:0001Þ: Note that this particular sequence of values is only appropriate

for the special case of frames with equal x and y nodal densities and equal

compressive and tensile strengths.

Finally, whilst for sake of clarity the algorithm shown does not include

calculations to bound from below the true optimal volume, this can easily be

carried out in step 3 or 4 by dividing the current (upper bound) volume by

k

max. Additionally, the stopping criteria given in step 7 can readily be modified

to alternatively allow termination if the percentage gap between the upper and

lower bound volumes is within a specified tolerance.

Formal status of the method

It is useful to clarify the formal status of both the solutions obtained and the

convergence characteristics of the method.

Suppose, at the end of a given iteration, it is found that the virtual strain in

one or more of the potential members linking nodes in the design domain is

greater than the computed strain limit, and that the maximum ratio of virtual to

limiting strains is k max. This indicates that the current solution to the

restricted upper bound (dual) problem does not represent a feasible solution to

the fully connected ground structure problem. Duality theory indicates that the

computed volume must represent an upper bound on the optimal volume of the

equivalent fully connected ground structure. However, multiplying all virtual

displacements by 1/k max both ensures feasibility and reduces the virtual work

and hence the computed structural volume by a factor of 1/k max. In this case,

duality theory indicates that the scaled down volume must represent a lower

bound on the optimal volume of the equivalent fully connected ground structure.

Alternatively suppose that, at the end of a given iteration, it is found that the

virtual strain in each of the potential members linking nodes in the design

domain is less than or equal to the computed strain limit (i.e. k max¼1, or, in

practice k max <1). This indicates that the current solution to the restricted

Layout

optimization

1053

upper bound (dual) problem is a feasible solution to the fully connected ground

structure problem. Furthermore, since the current solution is optimal for the

reduced structure, it follows that the present solution must also be optimal for

the equivalent fully connected ground structure.

Finally, since even a fully connected ground structure contains only a finite

number of members, any procedure that involves adding (though not

removing) members successively, such as the one described here, must only

require a finite number of iterations before an optimal solution is obtained (i.e.

cycling will not, in general, prevent a solution from being obtained). Though

formal proof that the procedure must always find the optimal solution in

significantly fewer iterations than mall – m0 has not been established, empirical

evidence indicates that a relatively small number of iterations will generally be

required (where mall is the number of members in the fully connected ground

structure and m0 is the number of members in the initial, minimal connectivity,

ground structure used at the start of the member adding scheme).

Numerical examples

Purpose written software was programmed using an object-oriented approach

and the language C++ to initially set up and then modify the LP problem at

successive iterations using the member adding procedure described previously.

A highly efficient C++ standard template library (STL) sort routine was used

in the program to obtain a priority ordered list of members to be added to the

frame at a given iteration.

The MOSEK (version 2.0) interior point LP solver which uses a

homogeneous and self-dual algorithm (www.mosek.com) was used for the

numerical studies. The pre-solve feature was switched off and the problem was

initially passed to the solver in memory using the supplied subroutine library.

Subsequently, it was only necessary to pass changes to the current problem to

the solver (rather than the entire revised problem). Problems were run on AMD

Athlon XP1900 based PC (running at 1.6 GHz) with 1.5 Gb of RAM, running

under Microsoft Windows XP Professional.

Test problems

Three simple demonstration problems are described here. Problem A is a

relatively small problem which can also be solved using the traditional fully

connected ground structure approach. Problems B and C are considerably

larger, having structural universes containing 13,263,825 and 116,288,875

potential members, respectively. Note that this latter problem is several orders

of magnitude larger in size than the “large” truss examples described by

Rozvany et al. (1995).

In all cases, a unit applied load and equal compressive and tensile strengths

of unity were used. Design domains, loading and support conditions are shown

in Figure 3.

EC

20,8

1054

Figure 3.

Numerical test problems:

A (353,220 potential

members), B (13, 263, 825

potential members) and

C (116, 288, 875 potential

members)

Layout

optimization

1055

Influence of initial connectivity

For problem A, five alternative initial connection strategies were investigated:

(1) connect members to adjacent nodes, omitting all diagonals except

backward facing diagonals on the bottom row;

(2) connect members to adjacent nodes, omitting forward facing diagonals;

(3) connect to adjacent nodes;

(4) connect to adjacent nodes and also connect each loaded node to each

support node; and

(5) fully connected ground structure including overlapping bars.

For clarity the five strategies are also illustrated diagrammatically in Figure 4.

Figure 4 presents results from the runs. Note that when member adding

was employed the number of members added at each iteration was limited to

5 per cent of the number of members present initially. The influence of this

parameter will be considered in more detail in the next section.

From Figure 4, a number of observations can be made. First, as expected, the

computed optimal volume of the frame was found not to be influenced by the

initial ground structure used. Secondly, it is clear that all member adding CPU

times are significantly shorter than when a fully connected ground structure

was used from the outset.

Figure 4.

Comparative CPU times

and LP problem sizes for

test problem A (353,220

potential members):

influence of initial nodal

connectivity

EC

20,8

1056

The shortest run time was observed when each node was connected only

to immediate adjacent nodes, including diagonals [i.e. (3)]. In this case, the run

time was only 8 per cent of that required when the conventional ground

structure was used. Perhaps most significantly of all, only a little more than

1 per cent of the number of LP variables were required, reducing memory usage

dramatically.

Comparing cases (1) and (2) with (3), it is clear that it is counter-productive in

terms of CPU time to reduce the level of initial connectivity too much. However,

because the peak number of LP variables, and hence memory requirements, are

reduced slightly when using reduced connectivity, this may sometimes be a

useful strategy.

Figure 5 shows all the intermediate optimal structures for case (3). The line

thickness on these and other plots presented in the paper were taken to be

proportional to the square root of the cross sectional area (for clarity, assuming

a circular member cross-section, bars with radius ,0.001 were not plotted.

Note that the use of any cut-off would sometime lead to apparently anomalous

details on the plots, e.g. a member apparently ending abruptly in space).

It is notable from Figure 5 that the near optimal forms (and volumes) are

obtained after only a few iterations.

It is also useful to examine the performance of the methods with larger

problems. Figure 6 shows plots of CPU time against the number of potential

members (for clarity a log-log scale is used). To obtain the figure the number of

nodes, and hence potential members, in problem A was varied.

Figure 6 shows that the member adding procedure is consistently

computationally less expensive than the traditional ground structure method.

Additionally, the high memory requirements of the latter method meant that

the largest initial fully solvable connected ground structure problem contained

just 1,225 nodes (749,700 potential members). This compares unfavourably

with the size of the largest problem which could be solved when using the

member adding method, which in this case contained 18,769 nodes (176,128,296

potential members). It is also noteworthy that the computed volume obtained

from the largest problem solvable (i.e. containing 176,128,296 potential

members) was just 1.6 per cent lower than the computed volume obtained when

using the standard level of nodal density indicated in Figure 3 (i.e. containing

353,220 potential members).

Figure 7 shows a plot of the peak number of LP variables in the

problem plotted against the number of potential members, for clarity using

a log-log scale. The figure indicates that as problem size increases, the ratio

of the peak number LP variables required using the initially fully connected

ground structure method to those required using the member adding method

increases markedly, e.g. with 100,000 potential members the ratio is

approximately 18:1 whereas with 100,000,000 potential members the ratio

increases to 1080:1.

Layout

optimization

1057

Influence of member adding selection criteria

For problem A, two alternative member adding selection strategies were

investigated. The first strategy was to use condition (10) alone to govern

whether, at the end of a given iteration, one or more members should be added

prior to the next iteration.

The second strategy was to limit the total number of members added at any

given iteration to fixed proportions of the number of members present in the

initial ground structure (i.e. according to the member adding algorithm). For all

runs, an initial ground structure which included only connections between the

adjacent nodes was used. Results are shown in Table II.

Figure 5.

Intermediate optimal

frames following each LP

iteration for test problem

A (adjacent nodes

initially connected)

EC

20,8

1058

It is evident from Table II that the total CPU time expended is not especially

sensitive to the percentage of additional members added, provided the latter is

not either very small or very large. Of those tried the 5 per cent m0 run was

solved most quickly (10.8 s).

It is also evident from Table II that in all cases the vast majority of the total

CPU time consumed was spent in the LP solution phase, rather than whilst

implementing the member adding heuristics (i.e. in the “oracle” phase).

Figure 6.

CPU times vs no. of

potential members:

comparison between

“ground structure”

and “member adding”

(5 per cent m0) methods

Figure 7.

Peak no. of LP variables

vs no. of potential

members: comparison

between “ground

structure” and “member

adding” (5 per cent m0)

methods

Layout

optimization

1059

Larger test problems B and C

Figure 8 shows the output for problem B.

The computed optimal volume for problem B was 3.14534. This is 0.12 per

cent greater than p, the optimal volume for this type of problem. The CPU time

for this problem was 42 min 10 s whilst the peak number of LP variables was

76,847. This is less than 1 per cent of the number of variables which would have

been required had an initial fully connected ground structure been used.

Figure 9 shows the output for problem C.

“Member adding” method: no. of members added at each iteration

1 per cent

m0

3 per cent

m0

5 per cent

m0

10 per cent

m0

100 per cent

m0

No

limit

Volume, V 2.43206 2.43206 2.43206 2.43206 2.43206 2.43206

No. of

LP iterations 40 18 13 12 6 4

Initial no. of

LP variables 6,384 6,384 6,384 6,384 6,384 6,384

Peak no. of

LP variables 7,610 7,876 8,092 8,892 16,261 139,556

CPU time to

#1.001 £ V(s) 22.7 6.1 5.8 5.8 6.3 53.2

CPU time for

LP phase

only (s) 28.8 13.0 9.6 10.4 11.2 80.8

Total CPU

time (s) 31.7 14.4 10.9 11.7 12.4 82.4

Table II.

Comparative CPU times

and LP problem sizes

for test problem A

(353,220 potential

members): influence of

admission criteria for

new members

Figure 8.

Optimal form for

problem B (13,263,825

potential members)

EC

20,8

1060

The computed optimal volume for problem C was 4.499827. This is just 0.038

per cent greater than the corresponding Michell structure volume of 4.498115

(obtained for this design problem by Zhou and Rozvany (1991)).

The CPU time for this problem was 6 h and 50 min. Following the analysis, it

was noted that a computed volume which was within ^15 per cent of the

optimal had been obtained in just 20 s and that a computed volume which was

within ^5 per cent of the optimal had been obtained in only 9 min. However,

during the solution process itself (when the optimal volume was unknown)

it took 17 min to obtain a computed volume which was provably within

^15 per cent of the optimal, and 3 h and 40 min to obtain a computed volume

which was provably within ^5 per cent of the optimal.

The peak number of LP variables for problem C was 215,103. This is less

than 0.1 per cent of the number of variables which would have been required

had an initial fully connected ground structure been used.

Discussion

Rather than attempting to solve the design problems with complex design

constraints, this paper has focused on solving the simple classical plastic

layout optimization problem for large problems (containing up to many

millions of potential members). Effective use is made of modern LP algorithms,

which are at present extremely well developed.

The proposed member adding method uses optimality criteria in conjunction

with the heuristic member admission rules. Though the current rules appear

very effective, the development of alternative rules may lead to even better

Figure 9.

Optimal form for

problem C (116, 288, 875

potential members)

Layout

optimization

1061

performance. For example, currently only the addition of members is allowed.

However, it is possible to modify the method so that a specified number of

non-optimal members can be deleted during a given iteration. This has the

advantage that problem size can be more carefully managed and could, for

example, allow the analysis of large problems even if the computer memory

available is limited (if a limit was placed on the total number of members

present during any iteration). Further investigations are required.

The proposed method provides major benefits compared with the standard

fully-connected ground structure approach (in terms of both analysis time and

the size of problem which is tractable). Although, even with the new method,

CPU time has been found to rise steeply as the number of nodes increases, it

should be borne in mind that real-life design domains are likely to be much

more constrained than those considered here, reducing dramatically the

number of potential members for a given number of nodes. Additional practical

constraints, such as stipulating the maximum length of compression members

will also dramatically reduce the number of potential members. Thus, the

application of this method raises the possibility of LP-based optimization being

used to tackle problems of a size which would be of interest to practicing

designers. The use of a dense grid of nodes in the design domain might in many

cases obviate the need for more complex optimization methods to be applied

(for example, procedures which use flexible though computationally expensive

genetic algorithms to add nodes to an initially sparse grid, or move nodes to

optimal locations (Kawamura et al., 2002)).

Though not considered here, real-world problems will almost always involve

the application of several independent load cases. Though efficient procedures

which involve solving in succession a series of specially defined single load

case problems have been proposed (e.g. for two load cases by several workers,

including the work of Hemp (1973)), such methods appear only to apply in the

special case of equal compressive and tensile material strengths, ultimately

they may not be useful in practice. Alternatively, the lower and upper bound

plastic LP formulations can be expanded to tackle multiple load cases (Hemp,

1973). Dual constraints relating to the expanded problem may then be used to

determine which members should be added as part of the member adding

procedure. This will be demonstrated elsewhere in due course.

Though only 2D problems have been considered in the current paper, the

extension of the member adding technique to 3D should be relatively

straightforward. However, because initially connecting each node to all

adjacent nodes, as for 2D problems, may lead to excessive number of members,

it is likely that various different initial nodal connectivity strategies will need to

be tried before an efficient scheme is found. Additionally, including joint costs

in the manner suggested by Parkes (1975) only requires slight modification of

constraint (10) in order to be used in conjunction with the member adding

technique.

EC

20,8

1062

The work described here is an initial step in a larger programme of work

concerned with the development of computationally efficient and practically

applicable layout optimization tools for use in practice. The significant

reduction in computational effort and memory requirements for the

optimization of large frameworks should allow the incorporation of more

complex constraints, which will enable LP-based optimization methods to be

used to design more realistic structural frameworks. Currently, the two areas of

investigation by the authors are system stability and member buckling.

System stability is an issue because often it is found that the optimal layouts

obtained using traditional methods are in unstable equilibrium with the

specified applied loads (e.g. as in the case of the optimal solution for problem B

– refer to Figure 8). Clearly this is unacceptable. Various methods of

overcoming the problem have been suggested. For example, Rozvany (1996)

noted the possibility of adding nominal imperfections to the problem

formulation. He concluded that the computer time required to solve the

expanded problem would be prohibitive. However, because of the availability

of the member adding method, this conclusion may no longer be justified. Work

is now proceeding in this area.

In addition to the system stability problem mentioned above, the problem of

individual compression member stability (i.e. buckling) needs to be addressed.

In essence the problem is that as the ultimate compressive strength of a

member is effectively a function of the geometry of its cross-section (rather

than being constant for a member of given length), the optimization problem

becomes non-linear. This may be tackled by adopting an iterative LP solution

procedure which involves updating member compressive strengths at each

iteration (Reinschmidt and Russell, 1974). However, the successive application

of LP already used as part of the member adding procedure means that in

principle non-linear behaviour may readily be incorporated (though as with all

non-linear optimization schemes there is a possibility of arriving at local rather

than global optima). This will be discussed elsewhere in due course.

Conclusions

A conceptually simple, but very effective member adding method has been

described. Using the method, layout optimization problems can be tackled

which involve far greater number of potential members than has hitherto been

possible (e.g. .100,000,000 potential member problems are tractable at

present). Though the method requires selection of an initial ground structure,

the precise form of the initial connectivity has been shown not to influence the

optimal design. Furthermore, bounds on the optimality of intermediate

solutions obtained using the method can be computed, with the final solution

being provably optimal. Additionally, though the “plastic” design formulation

has been used, the solutions are also optimal for the “elastic” with stress

constraints design problem provided only a single load case is present.

Layout

optimization

1063

In the future the method will be applied to large 3D problems and

additionally features such as stability, joint costs and member self-weight will

be added to the problem formulation, to increase the practical applicability of

the output.

References

Dorn, W.S., Gomory, R.E. and Greenberg, H.J. (1964), “Automatic design of optimal structures”,

J. de Mechanique, Vol. 3, pp. 25-52.

Gondzio, J. and Sarkissian, R. (1997), “Column generation with a primal-dual method”, in, Logilab

Technical Report 96.6, University of Geneva.

Hemp, W.S. (1973), Optimum Structures, Clarendon press, Oxford.

Karmarker, N.K. (1984), “A new polynomial-time algorithm for linear programming”,

Combinatorica, Vol. 4, pp. 373-95.

Kawamura, H., Ohmori, H. and Kito, N. (2002), “Truss topology optimization by a modified

genetic algorithm”, Struct. Multidisc. Optim., Vol. 23 No. 6, pp. 467-72.

Kelley, J.E. (1960), “The cutting-plane method for solving convex programs”, J. S.I.A.M., Vol. 8

No. 4, pp. 703-12.

Kirsch, U. (1990), “On singular topologies in optimum structural design”, Struct. Optimization,

Vol. 2, pp. 133-42.

Kirsch, U. (1996), “Integration of reduction and expansion processes in layout optimization”,

Struct. Optimization, Vol. 11, pp. 13-18.

Michell, A.G.M. (1904), “The limits of economy of material in frame-structures”, Phil. Mag., Vol. 8,

pp. 589-97.

Parkes, E.W. (1975), “Joints in optimum frameworks”, Int. J. Solids and Structures, Vol. 11,

pp. 1017-22.

Reinschmidt, K.F. and Russell, A.D. (1974), “Applications of linear programming in structural

layout and optimisation”, Computers and Structures, Vol. 4, pp. 855-69.

Rozvany, G.I.N. (1996), “Difficulties in truss topology optimization with stress, local buckling and

system stability constraints”, Struct Optimization, Vol. 11 No. 3/4, pp. 213-7.

Rozvany, G.I.N. (2001), “On design dependent constraints and singular topologies”, Struct.

Multidisc. Optim., Vol. 21 No. 2, pp. 164-72.

Rozvany, G.I.N. and Birker, T. (1994), “On singular topologies in exact layout optimization”,

Struct. Optimization, Vol. 8, pp. 228-35.

Rozvany, G.I.N., Bendsoe, M.P. and Kirsch, U. (1995), “Layout optimization of structures”, Appl.

Mech. Review, Vol. 48 No. 2, pp. 41-119.

Woo, T.H. and Schmit, L.A. (1981), “Decomposition in optimal plastic design of structures”, Int.

J. Solids Structs, Vol. 17 No. 1, pp. 39-56.

Zhou, M. and Rozvany, G.I.N. (1991), “The COC algorithm, Part II: topological, geometrical and

generalized shape optimizaion”, Comput. Method Appl. Mech. Eng., Vol. 89 No. 1-3,

pp. 309-36.

Further reading

Rozvany, G.I.N. and Zhou, M. (1991), “The COC algorithm, Part I: cross-section optimization or

sizing”, Comput. Method Appl. Mech. Eng., Vol. 89 No. 1-3, pp. 281-308.

EC

20,8

1064