• a assuming that profile j is selected.

  • b assuming that non-nodal loads are replaced with equivalent nodal loads.

  • c these matrices and vectors refer to displacements or stresses at a limited number of prescribed output locations along member i.

1 Introduction

In structural optimization, the problem formulation plays a fundamental role. The mathematical structure of the optimization problem determines which solution methods can be applied, and how difficult it is to find the optimal solution. From the designer’s perspective, the problem should include the necessary requirements of design, manufacture and economy (Farkas 2005) such that the results of optimization are applicable in practice. In general, the problem formulation is a compromise between meeting the needs of the designer and the capabilities of contemporary solution procedures.

In practical optimization of frame structures, the member profiles must be chosen from a catalog of commercially available sections. When this feature is coupled with conventional formulations based on elastic structural analysis, the problem is not only nonlinear (Wang and Arora 2006), but it also contains discrete design variables. The resulting mixed-integer nonlinear programming (MINLP) problem can be treated by several optimization methods that have been proposed in the literature on discrete structural design of frames (for reviews, see Thanedar and Vanderplaats (1995), Arora and Huang (1996), Huang and Arora (1997), and Arora (2002)). However, these methods have in common that they cannot guarantee that the global optimum is found.

In a detailed review, Arora (2002) discusses various methods for structural optimization with discrete variables. These include branch-and-bound for nonlinear problems, sequential linearization, dynamic rounding-off, penalty approach and various stochastic methods, among others. Some of the more recent approaches include the discrete Lagrangian-based algorithm (Juang and Chang 2006), and a scheme based on the optimality criteria method (Schevenels et al. 2014).

Currently, stochastic algorithms are widely used for solving discrete frame optimization problems. These methods include genetic algorithms (Camp et al. 1998; Rajeev and Krishnamoorthy 1992; Gero et al. 2006; Kripakaran et al. 2010), ant colony optimization (Camp et al. 2005; Kaveh and Talatahari 2010), firefly algorithm (Gandomi et al. 2011; Carbas 2016), harmony search algorithm (Saka 2009), particle swarm optimization (Venter and Sobieszczanski-Sobieski 2003), guided stochastic search heuristic (Kazemzadeh Azad and Hasancebi 2015), eagle strategy with differential evolution (Talatahari et al. 2015), and teaching-learning based optimization (Togan 2012). The general idea is to explore the design space in a random fashion, thereby using information collected from previous analyses to gradually improve the design. These algorithms owe their popularity to the fact that they are easy to understand and to implement. They can cope with discrete parameters and are able to take into account complex constraints. However, stochastic algorithms converge slowly, involve algorithmic parameters that require careful tuning, and global optimality cannot be guaranteed since no conclusive convergence checks can be made.

In this paper, global discrete sizing optimization of frame structures is considered. The weight of the structure is minimized, taking into account stress and displacement constraints. The optimization problem is reformulated into a mixed-integer linear programming (MILP) problem. In the classical approach for structural optimization the nested analysis and design (NAND) approach is employed (Arora and Wang 2005): in every iteration a finite element analysis is performed in order to obtain the state variables (the structural nodal displacements and the member end forces). In order to facilitate the reformulation of the optimization problem as an MILP, the simultaneous analysis and design (SAND) approach (Arora and Wang 2005) is adopted in this study: the state variables are considered as additional design variables and the state equations (the equilibrium equations and member stiffness relations) are enforced by means of additional constraints. In addition, a set of binary decision variables is introduced for each member of the structure to select a profile from the catalog given by the designer. The obtained MILP can be solved for global optimality with well-established algorithms such as branch-and-bound methods (Wolsey 1998; Nemhauser and Wolsey 1999).

The MILP formulation approach has originally been proposed by Ghattas and Grossmann (1991) and Grossmann et al. (1992) for discrete topology optimization of trusses, later studied by Rasmussen and Stolpe (2008), Faustino et al. (2006), and Kanno and Guo (2010). Mela (2014) included member strength and buckling constraints specified by the Eurocode in the truss topology design problem. Van Mellaert and Schevenels (2015) included both the member and the joint constraints for sizing optimization of statically determinate trusses. Stolpe (2007) proposed a mixed-integer linear programming reformulation approach to solve continuum topology optimization problems. Kureta and Kanno (2014) developed a mixed integer programming approach for topology optimization of periodic frame structures with negative Poisson’s ratio, and Hirota and Kanno (2015) developed a mixed integer programming approach for the optimal design of periodic frame structures with negative thermal expansion.

The main differences in the mixed-integer linear programming problem between frames and trusses are related to structural analysis and member resistance constraints. In truss analysis, the only stress resultant is the normal force, which is constant in the member. Thus, for each member, a single state variable is required. For frames modeled with beam elements, shear forces and bending moments in addition to normal forces must be included in the analysis. Moreover, nodal rotations need to be considered in addition to displacements. Consequently, the number of state variables and constraints related to structural analysis increases when the mixed-integer formulation is extended from trusses to frames.

The member resistance and deflection constraints for trusses are imposed by simply limiting the normal force and nodal displacement variables, respectively. For members of frames, the stress resultants typically vary along the member, which implies that resistance constraints must be considered at several locations and not only at member ends. This applies also for deflection constraints. Furthermore, the interaction of stress resultants should be taken into account, which means that the resistance constraints become more complicated than simple bounds on the state variables.

This study focuses on the computational efficiency of the mixed-integer linear programming approach for the discrete sizing optimization of frames. The MILP formulation for topology optimization presented in Stolpe (2007), Kureta and Kanno (2014), and Hirota and Kanno (2015) is adopted for sizing optimization. However, the formulation is extended to take into account non-nodal loads. In addition, catalogs consisting of 9 to 24 available profiles are adopted, instead of the smaller catalogs consisting of 3 profiles adopted for the MILP frame problems presented in the literature.

The paper is organized as follows. In Section 2, the mixed-integer linear programming problem for frame optimization is presented: the design variables as well as the constraints are described in detail. In Section 3, the formulation is applied to three example problems: a simple portal frame with an inclined roof, a two-story frame with three load cases, and a three-bay three-story frame. In addition, the performance of the MILP reformulation method is compared with the performance of a genetic algorithm by solving several multiple-bay multiple-story frame problems. Section 4 summarizes the main findings of this study.

2 Mixed-integer linear programming formulation

This section describes the mixed-integer linear programming formulation for the discrete sizing optimization of frame structures. The formulation is written for plane frames with prismatic members analyzed by the theory of linear elasticity. For simplicity, it is assumed that all members are made of the same material. Moreover, only a single load case is considered, but the formulation can easily be extended to multiple load cases. Non-nodal loads are replaced with equivalent nodal loads in the formulation of the problem. The joints are assumed to be rigid, although hinged connections can be incorporated into the formulation.

Consider a frame structure defined by n m members and n n nodes with n dof degrees of freedom. The number of profile alternatives is n s. Denote by \(\mathcal {M} = \{1,2,\ldots ,{n_{\text {m}}}\}\) and \(\mathcal {C} = \{1,2,\ldots ,{n_{\text {s}}}\}\) the index sets for members and profiles. Each member may have its own set of profile alternatives. The index set of profiles of member i is denoted by \(\mathcal {C}_{i} \subseteq \mathcal {C}\).

2.1 Design variables

The design variables include a vector of binary decision variables y, a vector of continuous nodal displacement variables u (including translations and rotations), and a vector of continuous member end forces q (caused by the equivalent nodal loads). The binary variables are employed to select member profiles from the set of available alternatives. For member i, profile j is selected when the corresponding variable y ij = 1. Profile j is not selected for member i when the corresponding variable y ij = 0. For each member i and for each section j a set of three independent member end forces is defined, including the normal end force N 1, ij , and the bending moment end forces M 1, ij and M 2, ij as shown in Fig. 1. The member end forces for each member i and for each section j are collected in the vector q ij :

$$ \mathbf{q}_{ij}=\left[\begin{array}{lll} N_{1,ij} & M_{1,ij} & M_{2,ij} \end{array}\right]^{\mathrm{T}} $$
(1)
Fig. 1
figure 1

Member end forces

Full size image

The vector with the design variables x is given by:

$$ \mathbf{x}=\left[\begin{array}{lll} \mathbf{y}^{\mathrm{T}} & \mathbf{u}^{\mathrm{T}} &\mathbf{q}^{\mathrm{T}}\end{array}\right]^{\mathrm{T}},\hphantom{10}\mathbf{y}\in\mathbb{B}^{n_{\mathrm{b}}},\mathbf{u}\in\mathbb{R}^{n_{\text{dof}}},\mathbf{q}\in\mathbb{R}^{3n_{\mathrm{b}}} $$
(2)

The total number of binary decision variables is denoted by \(n_{\mathrm {b}}={\sum }_{i=1}^{n_{\mathrm {m}}}n_{\mathrm {s}i}\), where n m is the total number of members in the structure, and n si is the total number of available sections for member i. The total number of degrees of freedom is denoted by n dof. The total number of force variables is 3n b. The total number of design variables is calculated as n dv = n dof + 4n b.

2.2 Problem statement

The mixed-integer linear programming problem for a frame structure is given by (4) through (9):

$$\begin{array}{@{}rcl@{}}\underset{\mathbf{x}}{\min}\sum\limits_{i\in\mathcal{M}}\sum\limits_{j\in\mathcal{C}_{i}}c_{ij}y_{ij}&& \end{array} $$
(3)
$$\begin{array}{@{}rcl@{}} \text{such that} ~~~~~~~~\sum\limits_{j\in\mathcal{C}_{i}}y_{ij}&=&1 \qquad\qquad\qquad~~~~\forall\;i\in\mathcal{M} \end{array} $$
(4)
$$\begin{array}{@{}rcl@{}} \sum\limits_{i\in\mathcal{M}}\sum\limits_{j\in\mathcal{C}_{i}}\mathbf{B}_{i}^{\mathrm{T}}\mathbf{T}_{i}^{\mathrm{T}}\mathbf{R}_{i}\mathbf{q}_{ij} &=&\mathbf{f} \end{array} $$
(5)
$$\begin{array}{@{}rcl@{}} (1-y_{ij}){\mathbf{\underline{q}}^{\prime}_{ij}}\leqslant\mathbf{K}_{ij}\mathbf{T}_{i}\mathbf{B}_{i}\mathbf{u}-\mathbf{q}_{ij}&\leqslant&(1-y_{ij})\bar{\mathbf{q}}^{\prime}_{ij} \qquad\qquad~ \forall\;i\in\mathcal{M},\:\forall\;j\in\mathcal{C}_{i} \end{array} $$
(6)
$$\begin{array}{@{}rcl@{}} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~y_{ij}{\mathbf{\underline{q}}^{\prime}_{ij}}\leqslant\mathbf{q}_{ij} &\leqslant& y_{ij}\bar{\mathbf{q}}^{\prime}_{ij} \qquad\qquad\qquad~~~ \forall\;i\in\mathcal{M},\:\forall\;j\in\mathcal{C}_{i} \end{array} $$
(7)
$$\begin{array}{@{}rcl@{}} {\mathbf{\underline{d}}^{\prime}_{ij}}+ y_{ij}({\mathbf{\underline{d}}_{ij}}-{\mathbf{\underline{d}}^{\prime}_{ij}}) \leqslant\mathbf{D}_{i}\mathbf{T}_{i}\mathbf{B}_{i}\mathbf{u}+\tilde{\mathbf{d}}_{ij} &\leqslant&\bar{\mathbf{d}}^{\prime}_{ij}+ y_{ij}(\bar{\mathbf{d}}_{ij}-\bar{\mathbf{d}}^{\prime}_{ij}) \quad~ \forall\;i\in\mathcal{M},\:\forall\;j\in\mathcal{C}_{i} \end{array} $$
(8)
$$\begin{array}{@{}rcl@{}} {\mathbf{\underline{s}}^{\prime}_{ij}}+ y_{ij}({\mathbf{\underline{s}}_{ij}}-{\mathbf{\underline{s}}^{\prime}_{ij}}) \leqslant\mathbf{S}_{ij}\mathbf{T}_{i}\mathbf{B}_{i}\mathbf{u}+\tilde{\mathbf{s}}_{ij} &\leqslant&\bar{\mathbf{s}}^{\prime}_{ij}+ y_{ij}(\bar{\mathbf{s}}_{ij}-\bar{\mathbf{s}}^{\prime}_{ij}) \quad~~~ \forall\;i\in\mathcal{M},\:\forall\;j\in\mathcal{C}_{i} \end{array} $$
(9)

The objective function is given by (4), where c ij is the cost of profile j for member i. When the structural weight is taken as the objective function, c ij is the weight of member i with profile j, and it can be written as c ij = ρL i A ij , where ρ is the density of the material, L i is the length of member i, and A ij is the section area of profile j for member i. Alternatively, c ij can be written as c ij = L i w ij , where w ij = ρ ij A ij is the weight per unit length of profile j for member i. This expression can be used, if multiple materials are included in the problem.

The subsequent equations are the constraints of the optimization problem. Equation (4) ensures that a single profile j is chosen from the catalog \(\mathcal {C}_{i}\) for member i. The equilibrium equations and the member stiffness relations are given by (5) and (6), respectively. Equation (7) ensures that if profile j is not selected for member i, the corresponding force variables become zero, i.e. q ij = 0. The derivation of (3–7) is given in Appendix A. The displacements and stresses at predefined locations of member i are limited by the constraints of (8) and (9), respectively. The derivation of these constraints is given in the subsequent sections. A list of symbols is provided at the beginning of the paper.

It is possible to take into account multiple load cases by introducing additional nodal displacement and force variables and constraints of (5) to (9) for each load case (Mela 2014).

2.3 Displacements along elements

Constraints on deflections along the members are expressed in terms of nodal values using interpolation with shape functions. The idea is that the designer defines a priori the locations where chosen displacement components are restricted.

The displacement along the local x-axis as defined in Fig. 2 at location x ∈ [0, L i ] of member i for profile j is calculated as:

$$ u_{ij}(x) =\mathbf{D}_{i}^{u}(x)\mathbf{T}_{i}\mathbf{B}_{i}\mathbf{u}+\tilde{u}_{ij}(x) $$
(10)

where \(\tilde {u}_{ij}(x)\) is the displacement at location x of member i due to the element loads, assuming that profile j is selected and that the member ends are clamped. This term compensates for the fact that non-nodal loads are replaced by equivalent nodal loads in the formulation of the problem. The displacements along the local y-axis v ij (x), and the rotation φ ij (x) are calculated in the same way. The shape function vectors Diu(x), Div(x) and Diφ(x) are given by (44) to (46) in Section A.3.

Fig. 2
figure 2

Local displacements

Full size image

The constrained displacement components of element i with profile j at the locations x k of interest are collected in the vector d ij . For example, if the transverse displacement v i of element i is to be constrained at the locations x 1, x 2, and x 3, the vector d ij is given by:

$$ \mathbf{d}_{ij}=\left[\begin{array}{l} v_{ij}(x_{1})\\ v_{ij}(x_{2})\\ v_{ij}(x_{3}) \end{array}\right] $$
(11)

This vector is obtained as follows:

$$ \mathbf{d}_{ij}=\mathbf{D}_{i}\mathbf{T}_{i}\mathbf{B}_{i}\mathbf{u}+\tilde{\mathbf{d}}_{ij} $$
(12)

where the matrix D i and the vector \(\tilde {\mathbf {d}}_{ij}\) are (in this case):

$$ \mathbf{D}_{i} =\left[\begin{array}{l} \mathbf{D}_{i}^{v}(x_{1})\\ \mathbf{D}_{i}^{v}(x_{2})\\ \mathbf{D}_{i}^{v}(x_{3}) \end{array}\right] \qquad\quad \tilde{\mathbf{d}}_{ij} =\left[\begin{array}{l} \tilde{v}_{ij}(x_{1})\\ \tilde{v}_{ij}(x_{2})\\ \tilde{v}_{ij}(x_{3}) \end{array}\right] $$
(13)

In order to limit the relevant displacement components at all predefined locations of member i, the constraints given by (8) are introduced, where \(\mathbf {\underline {d}}_{ij}\) and \(\bar {\mathbf {d}}_{ij}\) are the prescribed minimum and maximum allowed value of displacements, respectively. The artificial bounds \(\mathbf {\underline {d}}^{\prime }_{ij}\) and \(\bar {\mathbf {d}}^{\prime }_{ij}\) ensure that when profile j is not selected for member i, the constraints (8) do not impose any limits on the nodal displacements u. When profile j is selected for member i (y ij = 1), (8) becomes \(\mathbf {\underline {d}}_{ij}\leqslant \mathbf {D}_{i}\mathbf {T}_{i}\mathbf {B}_{i}\mathbf {u}+\tilde {\mathbf {d}}_{ij}\leqslant \bar {\mathbf {d}}_{ij}\) and the appropriate displacement components are constrained. When profile j is not selected for member i (y ij = 0), (8) reduces to \(\mathbf {\underline {d}}^{\prime }_{ij}\leqslant \mathbf {D}_{i}\mathbf {T}_{i}\mathbf {B}_{i}\mathbf {u}+\tilde {\mathbf {d}}_{ij}\leqslant \bar {\mathbf {d}}^{\prime }_{ij}\). The bounds \(\mathbf {\underline {d}}^{\prime }_{ij}\) and \(\bar {\mathbf {d}}^{\prime }_{ij}\) are calculated similarly to \(\mathbf {\underline {q}}^{\prime }_{ij}\) and \(\bar {\mathbf {q}}^{\prime }_{ij}\) (42 and 43) for each row k of matrix D i and vector \(\tilde {\mathbf {d}}_{ij}\) as:

$$\begin{array}{@{}rcl@{}} &&{\underline{d}}^{\prime}_{k,ij}=\underset{\mathbf{u}}{\min} ~\mathbf{D}_{k,i}\mathbf{T}_{i}\mathbf{B}_{i}\mathbf{u}+\tilde{\mathbf{d}}_{k,ij}\\ &&~~~~~~~~~~~~~~~\textrm{s.t.} \mathbf{\underline{\mathbf{u}}} \leqslant\mathbf{u}\leqslant\mathbf{\overline{\mathbf{u}}} \end{array} $$
(14)
$$\begin{array}{@{}rcl@{}} &&\bar{d}^{\prime}_{k,ij}=\underset{\mathbf{u}}{\max}~\mathbf{D}_{k,i}\mathbf{T}_{i}\mathbf{B}_{i}\mathbf{u}+\tilde{\mathbf{d}}_{k,ij}\\ &&~~~~~~~~~~~~~~~\textrm{s.t.} \mathbf{\underline{\mathbf{u}}} \leqslant\mathbf{u}\leqslant\mathbf{\overline{\mathbf{u}}} \end{array} $$
(15)

where \(\mathbf {\underline {\mathbf {u}}}\) and \(\mathbf {\overline {\mathbf {u}}}\) are the minimum and maximum allowed nodal displacements, respectively.

When only nodal displacements are limited, the constraints given by (8) can be substituted by the following constraints:

$$ \mathbf{\underline{\mathbf{u}}}\leqslant\mathbf{u}\leqslant\mathbf{\overline{\mathbf{u}}} $$
(16)

2.4 Stresses

The resistance of cross-sections subjected to shear forces, normal forces, and bending moments is checked at predefined locations along the members. For elastic design, the resistance constraints can be written in terms of stresses as:

$$ \sigma_{\min}\leqslant\sigma_{\mathrm{t},ij}\left( x\right)\leqslant\sigma_{\max} $$
(17)

where \(\sigma _{\mathrm {t},ij}\left (x\right )\) is the normal stress at the top fiber of the cross-section of member i for profile j at location x. The normal stress at the bottom fiber of the cross-section \(\sigma _{\mathrm {b},ij}\left (x\right )\), and the maximum shear stress τ ij (x) of member i for profile j at location x are limited in the same way. These stresses are calculated as

$$\begin{array}{@{}rcl@{}} \sigma_{\mathrm{t},ij}(x) & =&\frac{N_{ij}(x)}{A_{ij}}+\frac{M_{ij}(x)}{W_{\mathrm{t},ij}} \end{array} $$
(18)
$$\begin{array}{@{}rcl@{}} \sigma_{\mathrm{b},ij}(x) & =&\frac{N_{ij}(x)}{A_{ij}}-\frac{M_{ij}(x)}{W_{\mathrm{b},ij}} \end{array} $$
(19)
$$\begin{array}{@{}rcl@{}} \tau_{ij}(x) & =&\frac{V_{ij}(x)S_{ij}}{I_{ij}b_{ij}} \end{array} $$
(20)

where W t, ij and W b, ij are the section moduli with respect to the top and bottom fibers of the cross-section, respectively, I ij is the second moment of area, S ij is the first moment of area, and b ij is the width of the profile at the point where the maximum shear stress occurs. N ij (x), V ij (x), and M ij (x) are, respectively, the normal force, shear force, and bending moment at location x as given by Fig. 3. For plastic design, similar constraints related to the stress resultants can be formulated.

Fig. 3
figure 3

Internal forces of member i for profile j at location x

Full size image

The stress σ t, ij (x) at location x of member i for profile j is calculated as:

$$ \sigma_{\mathrm{t},ij}(x) =\mathbf{S}_{ij}^{\sigma_{\mathrm{t}}}(x)\mathbf{T}_{i}\mathbf{B}_{i}\mathbf{u}+\tilde{\sigma}_{\mathrm{t},ij}(x) $$
(21)

where \(\tilde {\sigma }_{\mathrm {t},ij}(x)\) is the stress of the beam at location x due to the element loads, assuming that profile j is selected and that the member ends are clamped, calculated in a similar way as given by (18). The stresses σ b, ij (x) and τ ij (x) are calculated in the same was as in (21).

The stresses can be calculated from the nodal displacements u using the vectors Siσ t(x), Siσ b(x) and Siτ(x), which are given by (47) to (49) in Section A.4. Stress constraints have been treated similarly in the literature (Kureta and Kanno 2014; Hirota and Kanno 2015), but only for point loads located at the element nodes. The proposed formulation of (21) takes into account distributed loads and point loads not located at the nodes.

The constrained stress components σ t, ij , σ b, ij and/or τ ij of element i with profile j at locations x k are collected in the vector s ij . For example, if the normal stress at the top of element i is to be constrained at locations x 1, x 2, and x 3, the vector s ij is given by:

$$ \mathbf{s}_{ij}=\left[\begin{array}{c} \sigma_{\mathrm{t},ij}(x_{1})\\ \sigma_{\mathrm{t},ij}(x_{2})\\ \sigma_{\mathrm{t},ij}(x_{3}) \end{array}\right] $$
(22)

This vector is obtained as follows:

$$ \mathbf{s}_{ij}=\mathbf{S}_{ij}\mathbf{T}_{i}\mathbf{B}_{i}\mathbf{u}+\tilde{\mathbf{s}}_{ij} $$
(23)

where S ij and \(\tilde {\mathbf {s}}_{ij}\) are in this case

$$ \mathbf{S}_{ij}=\left[\begin{array}{c} \mathbf{S}_{ij}^{\sigma_{\mathrm{t}}}(x_{1})\\ \mathbf{S}_{ij}^{\sigma_{\mathrm{t}}}(x_{2})\\ \mathbf{S}_{ij}^{\sigma_{\mathrm{t}}}(x_{3}) \end{array}\right] \qquad \tilde{\mathbf{s}}_{ij}=\left[\begin{array}{c} \tilde{\sigma}_{\mathrm{t},ij}(x_{1})\\ \tilde{\sigma}_{\mathrm{t},ij}(x_{2})\\ \tilde{\sigma}_{\mathrm{t},ij}(x_{3}) \end{array}\right] $$
(24)

In general, the stress constraints at predefined locations along the members are written in the form of (9), where \(\tilde {\mathbf {s}}_{ij}\) is a vector containing the selected stress components at the predefined locations of the beam with clamped-clamped boundary conditions subjected to the element loads of member i for profile j, and \(\mathbf {\underline {\mathbf {s}}_{ij}}\) and \(\bar {\mathbf {s}}_{ij}\) are the prescribed minimum and maximum allowed stresses. The artificial bounds \(\mathbf {\underline {\mathbf {s}}^{\prime }_{ij}}\) and \(\bar {\mathbf {s}}^{\prime }_{ij}\) serve the same purpose as the bounds \(\mathbf {\underline {\mathbf {d}}^{\prime }_{ij}}\) and \(\mathbf {\underline {\mathbf {d}}^{\prime }_{ij}}\), i.e. they ensure that if profile j is not selected for member i, the nodal displacements are not constrained by (9). They are computed analogously to (14) and (15), using \(\tilde {\mathbf {s}}_{ij}\) instead of \(\tilde {\mathbf {d}}_{ij}\).

3 Test problems and optimization results

In this Section, the mixed-integer linear programming formulation presented above is applied to three test problems. Firstly, a simple portal frame with an inclined roof subjected to a distributed load is considered. This problem is employed to verify the method because it can also be solved by complete enumeration. Secondly, a two-story frame benchmark problem reported in the literature is treated. Finally, a three-bay three-story frame is considered. This problem represents a case where the optimum design is not easy to find by enumeration.

All test problems are solved by the commercial software Gurobi (Gurobi Optimization Inc 2015). The software employs the branch-and-cut method (Wolsey 1998), where cutting planes and other enhancements are incorporated in the general branch-and-bound framework in order to reduce the computational time. Several parameters for controlling the details of the algorithm are available. In this study, the default values of these parameters are used, except for feasibility and integer tolerances, respectively, which are set to values given below. Thus, the crucial decisions of the branch-and-cut algorithm, e.g. branching strategy and cutting plane selection, are governed by the software.

According to the principle of branch-and-bound, in each iteration, a lower bound of the objective function, f LB , is computed by solving a linear programming relaxation of the problem, where integer variables are treated as continuous. This lower bound increases over the iterations, whereas the upper bound of the optimum, f UB , decreases as better feasible solutions are found. At any time, the optimality gap, defined by

$$ \text{Gap} = \frac{f_{UB}-f_{LB}}{f_{UB}} $$
(25)

can be calculated to measure the quality of the solution. When the optimality gap becomes 0, the global optimality of the solution is verified. For numerical purposes, a small positive value is employed.

3.1 Portal frame

Figure 4 shows a portal frame structure with four members. The height of the frame is h 1 = 4 m and h 2 = 2 m, the span of the frame is w = 10 m, the value of the distributed load is \(p=25{~\text {kN}\left /\mathrm {m}\right .}\).

Fig. 4
figure 4

Schematic of the portal frame. The displacements are constrained at the locations indicated by a triangle (△), the stresses are constrained at the locations indicated by a cross (×)

Full size image

The objective of the optimization problem is to minimize the weight of the structure. The members are made of steel, and the profiles are chosen from a catalog with 24 HEA alternatives (Table 1). The Young’s modulus is 210 GPa, the density is 7850 kg/m3, and the yield strength is f y = 235 MPa. The allowable normal stress is f y, while the allowable shear stress is \(f_{\mathrm {y}}/\sqrt {3}=136\:\textrm {MPa}\). For members 1 and 4 all stress components are limited at three equidistant locations including the end points of the members. For members 2 and 3 all stress components are limited at five equidistant locations including the end points of the members (see Fig. 4). The stress constraints are given by (9). For determining the components of the vector \(\tilde {\mathbf {s}}_{ij}\) included in this equation, the normal force \(\tilde {N}_{i}(x)\), shear force \(\tilde {V}_{i}(x)\) and bending moment \(\tilde {M}_{i}(x)\) of a beam representing member i with clamped-clamped boundary conditions subjected to the element loads are required.

Table 1 HEA profile catalog
Full size table

For member 2 they are calculated as:

$$\begin{array}{@{}rcl@{}} \tilde{N}_{2}(x) & =&\sin(\alpha_{2})\cos(\alpha_{2})px-\sin(\alpha_{2})\frac{pw}{4} \end{array} $$
(26)
$$\begin{array}{@{}rcl@{}} \tilde{V}_{2}(x) & =&\cos^{2}(\alpha_{2})px-\cos(\alpha_{2})\frac{pw}{4} \end{array} $$
(27)
$$\begin{array}{@{}rcl@{}} \tilde{M}_{2}(x) &=&\cos^{2}(\alpha_{2})\frac{px^{2}}{2}-\cos(\alpha_{2})\frac{pw}{4}x+\frac{p}{12}\left( \frac{w}{2}\right)^{2} \end{array} $$
(28)

where \(\alpha _{2}=\tan ^{-1}\left (h_{2}/(w/2)\right )\) is the angle of inclination of member 2. The normal stresses \(\tilde {\sigma }_{\mathrm {t},2j}(x)\) and \(\tilde {\sigma }_{\mathrm {b},2j}(x)\) at the top and bottom of member 2 for profile j at location x, respectively, and the shear stresses \(\tilde {\tau }_{2j}(x)\) at the neutral axis of member 2 for profile j at location x are then obtained by substituting \(\tilde {N}_{2}(x)\), \(\tilde {V}_{2}(x)\), and \(\tilde {M}_{2}(x)\) in (18) to (20).

For member 3, the normal force \(\tilde {N}_{3}(x)\), shear force \(\tilde {V}_{3}(x)\) and bending moment \(\tilde {M}_{3}(x)\) are calculated as:

$$\begin{array}{@{}rcl@{}} \tilde{N}_{3}(x) & =&-\sin(\alpha_{3})\cos(\alpha_{3})px+\sin(\alpha_{3})\frac{pw}{4} \end{array} $$
(29)
$$\begin{array}{@{}rcl@{}} \tilde{V}_{3}(x) & =&\cos^{2}(\alpha_{3})px-\cos(\alpha_{3})\frac{pw}{4} \end{array} $$
(30)
$$\begin{array}{@{}rcl@{}} \tilde{M}_{3}(x) &=&-\cos^{2}(\alpha_{3})\frac{px^{2}}{2}+\cos(\alpha_{3})\frac{pw}{4}x+\frac{p}{12}\left( \frac{w}{2}\right)^{2} \end{array} $$
(31)

The stresses of the beam with clamped-clamped boundary conditions subjected to the element loads at location x of member 3 for profile j are calculated similarly as for member 2.

The maximum allowed displacement is \(u_{\max }=0.05\:\mathrm {m}\). For member 2, the vertical displacement component is limited at x 1 = L 2/2 and x 2 = L 2, and for member 3 the vertical displacement component is limited at x 1 = L 3/2. The displacement constraints are given by (8). The vector containing the vertical displacements of member 2 at the predefined locations x 1 and x 2 is in this case given by:

$$ \mathbf{d}_{2j}=\left[\begin{array}{c} u_{2j}(x_{1})\sin\alpha_{2}+v_{2j}(x_{1})\cos\alpha_{2}\\ u_{2j}(x_{2})\sin\alpha_{2}+v_{2j}(x_{2})\cos\alpha_{2} \end{array}\right] $$
(32)

where u 2j (x k ) and v 2j (x k ) are the displacements along the local x- and y-axes, respectively, of member 2 at location x k for profile j. The matrix D 2 is:

$$ \mathbf{D}_{2}=\left[\begin{array}{c} \mathbf{D}_{2}^{u}(x_{1})\sin\alpha_{2}+\mathbf{D}_{2}^{v}(x_{1})\cos\alpha_{2}\\ \mathbf{D}_{2}^{u}(x_{2})\sin\alpha_{2}+\mathbf{D}_{2}^{v}(x_{2})\cos\alpha_{2} \end{array}\right] $$
(33)

and the vector \(\tilde {\mathbf {d}}_{2j}\) is:

$$ \tilde{\mathbf{d}}_{2j}=\left[\begin{array}{c} \tilde{u}_{2j}(x_{1})\sin\alpha_{2}+\tilde{v}_{2j}(x_{1})\cos\alpha_{2}\\ \tilde{u}_{2j}(x_{2})\sin\alpha_{2}+\tilde{v}_{2j}(x_{2})\cos\alpha_{2} \end{array}\right] $$
(34)

where \(\tilde {u}_{2j}(x)\) and \(\tilde {v}_{2j}(x)\) are derived from the constitutive relations between stress and strain according to the Euler-Bernoulli beam theory:

$$\begin{array}{@{}rcl@{}} \tilde{u}_{2j}(x) & =&\frac{\sin\left( \alpha_{2}\right)\cos\left( \alpha_{2}\right)p}{2EA_{2j}}x^{2}-\frac{\sin\left( \alpha_{2}\right)pw}{4EA_{2j}}x \end{array} $$
(35)
$$\begin{array}{@{}rcl@{}} \tilde{v}_{2j}(x) &=&-\frac{\cos^{2}\left( \alpha_{2}\right)p}{24EI_{2j}}x^{4}+\frac{\cos\left( \alpha_{2}\right)pw}{24EI_{2j}}x^{3}-\frac{pw^{2}}{96EI_{2j}}x^{2} \end{array} $$
(36)

The vector containing the vertical displacements of member 3 at the predefined location x 1 is:

$$ \mathbf{d}_{3j}=\left[\begin{array}{c} u_{3j}(x_{1})\sin\alpha_{3}+v_{3j}(x_{1})\cos\alpha_{3}\end{array}\right] $$
(37)

where u 3j (x 1) and v 3j (x 1) are the displacements along the local x- and y-axes, respectively, of member 3 at x 1 for profile j, and \(\alpha _{3}=-\tan ^{-1}\left (h_{2}/(w/2)\right )\) is the angle of inclination of member 3. The matrix D 3, the vector \(\tilde {\mathbf {d}}_{3j}\), and the displacement components \(\tilde {u}_{3j}(x)\) and \(\tilde {v}_{3j}(x)\) are composed in the same way as for member 2.

The sizing optimization problem is defined by (4) to (9). The total number of members is n m = 4, and for each member the number of available profiles is n s = 24. Thus there are altogether n b = 96 binary decision variables, and 3n b = 288 force variables, whereas the number of degrees of freedom is n dof = 9. Consequently, the problem consists of 393 design variables and 4765 constraints, and the constraint coefficient matrix contains 24000 nonzero elements. There are 4 equality constraints to ensure that only one profile is selected for each member (4), 9 nodal equilibrium equality constraints (5), 1152 member stiffness relation inequality constraints (6), 1152 force inequality constraints (7), 144 displacement inequality constraints (8), and 2304 stress inequality constraints (9). The number of profile combinations is 244 = 331776. The problem is solved by Gurobi (version 6.0.2) on a computer with an Intel Core i7-5600U processor (2.6 GHz clock frequency) and 8 GB RAM. The feasibility tolerance is set to 10−9, the integer feasibility tolerance is set to 10−9, and the optimality gap (defined as the relative difference between the lower and upper objective bound) is set to 5 × 10−3. The optimization problem is solved in 26 seconds, and 10510 nodes of the branch-and-bound tree are explored.

The optimum design is obtained by assigning the profile HEA 240 for all members. This can be explained by inspecting the force diagrams (Fig. 11). The critical cross-sections of all members have approximately equal normal forces and bending moments. This suggests that the same profile for all members produces approximately equal normal stresses at all critical cross-sections, which implies that a single profile for the entire frame should yield the minimum weight design as long as the normal stress constraints are decisive. In this case, the shear stress constraints and the displacement constraints are not critical. The total weight of the structure is 1131.63 kg. It is verified by full enumeration of all possible designs that this is indeed the global optimum.

Detailed results for this test problem are given in Appendix B, where the deformed shape of the frame, internal force diagrams and constraint margins evaluated at the optimum design are presented.

3.2 Two-story frame

Figure 5 shows a two-story frame under three load cases. Sizing optimization of this structure has been considered in the literature by Chai and Sun (1996), Jivotovski (2000), and Juang and Chang (2006). The horizontal displacements of nodes 2 and 3 are limited to 2.54 cm, whereas the allowable normal stress in all members is 163860 kN/cm2. The Young’s modulus of the material is 206.88 GPa, and the density is 76999.34 N/cm3. The members are divided in 4 groups: the columns of the same story must have the same profile, the beams are designed independently. The catalog of available sections is given in Table 2.

Fig. 5
figure 5

Schematic of the two-story frame. The three load cases are indicated by (1), (2), and (3)

Full size image
Table 2 Profile catalog for the two-story frame
Full size table

The mixed-integer linear programming formulation is adopted for multiple load cases by including nodal displacement and member force variables for each load case. Moreover, the constraints of (5) through (9) are written for each load case. Altogether, the sizing optimization problem of (4) through (9) contains 576 variables (54 binary, 522 continuous) and 5268 constraints.

The MILP problem is solved by Gurobi (version 6.5) on a computer with an Intel Core i5-3470 processor (3.2 GHz clock frequency) and 16 GB RAM. The optimality gap is set to 5 × 10−3, and default values are used for the other parameters. The runtime of the algorithm is 7 seconds, and 1461 nodes of the branch-and-bound tree are explored. At termination, the global optimality of the solution is verified. The weight of the solution is 42.53 kN. Profile number 5 is assigned to members 1 and 5, profile number 2 is assigned to members 2, 3, and 4, and profile number 7 is assigned to member 6 (see Table 1). This solution is the same as the solution reported by Juang and Chang (2006), who have carried out a complete enumeration to verify that 42.53 kN is indeed the global optimum.

3.3 Three-bay three-story frame

Figure 6 shows a three-bay three-story frame with 21 members. The height of each story is h = 3.5 m, the width of each bay is w = 6 m, the value of the horizontal load is F = 22.05 kN, and the value of the distributed vertical load is p = 50.1 kN/m. The members are divided in seven groups, and in each group, all members must have the same profile. The beams (members 13 to 21) form one group, whereas, the columns are organized in six groups such that for each story, two groups are generated: the outer columns (members 1 and 4, 5 and 8, and 9 and 12) and inner columns (members 2 and 3, 6 and 7, and 10 and 11). Among group members, identical profiles are enforced by introducing additional linear constraints in terms of the profile selection variables, y ij . For example, the profiles of columns 1 and 4 are set to be identical by the following constraints:

$$ y_{1j} = y_{4j} \quad \forall\;j\in\mathcal{C} $$
(38)
Fig. 6
figure 6

Schematic of the three-bay three-story frame

Full size image

The objective of the optimization problem is to minimize the structural weight. In order to reduce the computation time, a limited set of available profiles is used: 15 profile alternatives ranging from HEA 100 to HEA 400 (Table 1) are included in the catalog. The material properties and allowed stresses are as in the previous example. For each member, all stress components are limited at three equidistant locations x 1 = 0, x 2 = L i /2, and x 3 = L i . For each column, the interstory drift, △u, is limited by h/300 = 0.0117 m. For example, the interstory drift constraint of column 5 is

$$ -\triangle u\leqslant u_{9}-u_{5} \leqslant \triangle u $$
(39)

where u 9, and u 5 are the horizontal displacements of nodes 9 and 5, respectively. The other interstory drift constraints are composed similarly. For each beam, the vertical deflection is limited at location x 1 = L i /2 by w/200 = 0.03 m.

The minimum weight problem is given by (4) through (9). The total number of members is n m = 21, and for each member the number of available profiles is n s = 15, resulting in n b = 315 binary decision variables. The number of force variables is 3n b = 945, and the number of degrees of freedom is n dof = 36. The MILP consists of 1296 design variables, 13791 constraints, and the constraint coefficient matrix has 64195 nonzero elements. The number of design combinations is 157 = 171 × 106. There are 21 equality constraints to ensure that only one profile is selected for each member (4), 36 nodal equilibrium equality constraints (5), 3780 member stiffness relation inequality constraints (6), 3780 force inequality constraints (7), 270 deflection constraints (8), 5670 stress inequality constraints (9), and 210 grouping constraints. The interstory drift constraints are imposed by limiting the difference of the horizontal nodal displacements at the top and bottom of each column. Consequently, there are 24 interstory drift constraints.

The MILP is solved by Gurobi (version 6.5) on the same computer as the first example problem. The optimality gap is set to 5 × 10−3, the feasibility tolerance is set to 10−6, and default values are used for the other parameters. The runtime of the algorithm is 19249 seconds (5.3 hours), and 140066 nodes of the branch-and-bound tree are explored. At termination, the global optimality of the solution (Fig. 7) is verified.

Fig. 7
figure 7

Optimal design of the three-bay three-story frame

Full size image

The convergence of the algorithm is illustrated in Fig. 8. The progress of the upper and lower bound, respectively, are shown by the two curves. It can be seen that feasible solutions close to the global optimum are found quickly.

Fig. 8
figure 8

Convergence curves of the optimization. After exploring 140066 nodes of the branch-and-bound tree, an optimality gap of 0.5 % is reached in point A and the optimization is terminated

Full size image

The optimum design is shown in Fig. 7. The weight of the frame is 6131.87 kg. Detailed results for this test problem are given in Appendix C, where the deformed shape of the frame, internal force diagrams and constraint margins evaluated at the optimum design are presented.

The deflections of the beams (Table 5) are small and not decisive for the optimal design. As can be seen from Table 6, the utilization ratio of the interstory drift constraints ranges from 0.90 to 1.00 for the bottom two rows of columns. This means that the interstory drift is decisive for the optimal design.

Stresses in the members vary significantly throughout the frame (Table 7). The utilization ratios of the stress constraints range from 0.65 to 0.96 for the beams, and from 0.38 to 0.96 for the columns. Highest utilization ratios appear in the members of the first story. As interstory drift and profile grouping constraints are enforced, a fully stressed design is not obtained.

3.4 Comparison with a genetic algorithm

It is interesting to compare the performance of the mixed-integer linear programming approach with metaheuristic methods in order to assess the computational cost that comes with the ability of the MILP formulation to find and verify the global optimum.

In this paper, the genetic algorithm (GA) function from the Matlab 2015 Global Optimization Toolbox is chosen as the metaheuristic solution method. Now the problem formulation follows the conventional nested analysis and design approach, where only member cross-sections are taken as design variables, and the values of the internal forces and displacements used in constraint evaluation are computed by the finite element method for given cross-sections. Default stopping criteria and parameter values are used, except for the constraint tolerance, which is set to 10−6 instead of the using the default value of 10−3 to make a fair comparison.

The three-bay three-story frame problem is solved by performing 100 different runs of the genetic algorithm with a population size of 70 for each generation. The results are shown in Fig. 9. The mean objective function value of all runs in each generation is represented by the solid black curve. The mean value of all solutions is 6210.5 kg, which is 1.3 % greater than the global optimum. The gray region delimits the highest and lowest obtained objective function value in each generation. The global optimum is indicated by the dotted line. For 32% of the runs, the global optimum is reached. 54% of all runs reach a solution which is heavier than the mean objective function value. The weight of the heaviest solution is 6335.7 kg (3.3% greater than the global optimum). The computation time to perform 100 runs is 9.7 hours, giving an average of 350 seconds for 1 run.

Fig. 9
figure 9

Performance of the genetic algorithm. The mean objective function value of 100 runs in each generation is represented by the black curve. The gray region delimits the highest and lowest obtained objective function value in each generation. The global optimum is indicated by the dotted line

Full size image

This analysis depicts the typical stochastic nature of the genetic algorithm. For the majority of the runs, the global optimum is not obtained, although the solution deviates by only few percents, and the results of the genetic algorithm are satisfactory. On the other hand, during the computations, the quality of the solution cannot be assessed with the genetic algorithm, and eventually, the algorithm is simply stopped when no better solution is found, or when the maximum number of iterations has been reached. On the contrary, the solution process of the MILP ends precisely when the global optimality of the solution is verified. If global optimality of the solution is not required, the branch-and-cut method can be terminated when the optimality gap has become sufficiently small.

Therefore, in addition, a comparison of the performance obtained by setting a limit on the computation time is made. The performance measured for the objective function value is illustrated by optimizing a two-bay two-story, three-bay three-story, and four-bay four-story frame imposing the same dimensions, loads, and constraints of the three-bay three-story frame example problem discussed in the previous section. For each case, multiple optimization problems are solved using a different subset of 5 available profiles. The different subsets are composed by dividing the catalog consisting of 15 profile alternatives ranging from HEA 100 to HEA 400 (Table 1) in five equidistant intervals, and randomly selecting a section from each interval.

For the two-bay two-story, three-bay three-story, and four-bay four-story frame a time limit of respectively 5, 50, and 500 seconds is set for each optimization. For each example case, 100 different optimization problems are solved. The performance profiles (Rojas-Labanda and Stolpe 2015; Dolan and Moré 2002) of the MILP reformulation method and the genetic algorithm are shown in Fig. 10. In this figure, the x-axis represents the parameter τ which is the relative ratio of the objective function value and the best obtained objective function value using the same subset of sections. The y-axis represents the percentage of optimization problems reaching an objective function value that is at most τ-times higher than the best obtained objective function value. The intersection of the plotted curves with the y-axis indicates the percentage of winning solutions. It can be seen that the MILP reformulation method performs better for the two-bay two-story (Fig. 10a) and three-bay three-story frame (Fig. 10b). In these cases, the winning solution is obtained with the MILP approach for respectively 96 and 80% of the optimization problems. For 80% of the problems, the genetic algorithm yields solutions with an objective function value that is at most respectively 10 and 5% higher than the solution obtained with the MILP approach. In the case of the four-bay four-story frame (Fig. 10c), the winning solution is obtained with the genetic algorithm for 75% of the optimization problems, and for 80% of the problems the MILP method yields solutions with an objective function value that is at most 6% higher than the solution obtained with the genetic algorithm. In this case, the genetic algorithm performs better. Due to the simplicity of implementing the genetic algorithm, adopting this approach might be preferable for practitioners. However, the quality of the solution can only be assessed by means of the optimality gap provided by the MILP approach. Therefore, the computation time can be reduced when adopting the MILP approach by terminating the optimization when the optimality gap is sufficiently small, say 5 to 10%. In addition, the method can be used to benchmark the efficiency of other methods.

Fig. 10
figure 10

Performance measured for the objective function value of the MILP reformulation approach (solid line) and genetic algorithm (dotted line) solving the two-bay two-story, three-bay three-story, and four-bay four-story frame problems

Full size image

4 Conclusion

This paper addresses a mixed-integer linear programming approach for discrete sizing optimization of frame structures using commercial profile catalogs. The performance of the method is compared with the performance of a genetic algorithm. The main benefit of the MILP formulation is that it allows for finding the global optimum of frames using well-established deterministic solution methods such as branch-and-bound. The formulation can be adopted for various materials and applications. In order to make the approach more relevant for practical applications, constraints derived from design codes can be included. In extending the formulation presented in this paper, the linearity of the problem should be preserved, because otherwise a large-scale nonlinear mixed-integer problem needs to be solved, which implies a substantial increase of computational burden.

The critical point of the mixed-integer formulation is the problem size. The problem includes hundreds of variables and thousands of constraints even for modest design tasks. The problem size increases rapidly as more members and profiles as well as additional load cases are introduced, which, due to the nature of MILP problems, implies that the computational time will grow significantly. The multiple-bay multiple-story frame gives some indication of this. In some cases the genetic algorithm appears to be more efficient than the MILP approach. However, even if the computational time for finding and verifying the global optimum becomes prohibitively large, the MILP formulation can still be used for finding good designs. Moreover, the branch-and-bound method provides the optimality gap throughout the iterations. This information can be used to reduce the computational time by terminating the algorithm when the optimality gap becomes sufficiently small.

In order to draw definitive conclusions on the applicability of the MILP approach to practical design problems, the capabilities of the branch-and-cut method should be thoroughly studied in order to reduce the computational times. The convergence behavior depicted in Fig. 8 shows that while contemporary branch-and-cut algorithms are able to find feasible solutions (including the global optimum) relatively quickly, the improvement of the lower bound is rather slow. Consequently, further research efforts should be targeted at producing tighter relaxations of the MILP problem in order to obtain greater lower bounds more quickly. For this task, special-purpose cutting planes that efficiently exploit the specific mathematical structure of the MILP problem should be considered. Additionally, various case studies of actual design tasks should be treated. For a given design problem, engineering judgment and problem-specific additional constraints can often be employed to improve the solution process.