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