Open AccessArticle

Global Optimization for Mixed–Discrete Structural Design

Jung-Fa Tsai

¹,

Ming-Hua Lin

^2,* and

Duan-Yi Wen

Department of Business Management, National Taipei University of Technology, Taipei 10608, Taiwan

Department of Urban Industrial Management and Marketing, University of Taipei, Taipei 11153, Taiwan

Author to whom correspondence should be addressed.

Symmetry 2020, 12(9), 1529; https://doi.org/10.3390/sym12091529

Submission received: 24 August 2020 / Revised: 10 September 2020 / Accepted: 12 September 2020 / Published: 16 September 2020

Download

Browse Figures

Versions Notes

Abstract

Several structural design problems that involve continuous and discrete variables are very challenging because of the combinatorial and non-convex characteristics of the problems. Although the deterministic optimization approach theoretically guarantees to find the global optimum, it usually leads to a significant burden in computational time. This article studies the deterministic approach for globally solving mixed–discrete structural optimization problems. An improved method that symmetrically reduces the number of constraints for linearly expressing signomial terms with pure discrete variables is applied to significantly enhance the computational efficiency of obtaining the exact global optimum of the mixed–discrete structural design problem. Numerical experiments of solving the stepped cantilever beam design problem and the pressure vessel design problem are conducted to show the efficiency and effectiveness of the presented approach. Compared with existing methods, this study introduces fewer convex terms and constraints for transforming the mixed–discrete structural problem and uses much less computational time for solving the reformulated problem to global optimality.

Keywords:

global optimization; mixed–integer programming; mathematical methods; linearization; mixed–discrete variable; structural design problem

1. Introduction

Various problems that contain continuous and discrete variables arise in practical structural design applications; therefore, the mixed–discrete structural optimization (MDSO) problems have attracted increasing attention from researchers and practitioners in the last few decades. Some of the approaches for solving the MDSO problems belong to metaheuristics. Although the metaheuristic methods, such as tabu search, simulated annealing, evolutionary algorithms, and ant colony optimization, are robust and can successfully solve various types of problems [1], they cannot guarantee the global optimality of the obtained solution.

A signomial geometric function can be expressed as

\sum_{i = 1}^{k} c_{i} (\prod_{j}^{n} x_{j}^{α_{i j}})

, where

c_{i}

α_{i j} \in R

. Signomial geometric functions occur frequently in many engineering optimization problems such as chemical equilibrium problems [2], structural mechanics [3], integrated circuit design [4], stochastic processes [5], and aircraft design [6]. Since many nonlinear programming problems can be constructed or restated as signomial geometric programming problems by a simple change of variables or by an algebraic manipulation of terms [7], developing a global optimization approach for signomial geometric programming problems is useful for treating practical applications. The focus of this article is on the deterministic optimization approach for globally solving the MDSO problems that can be formulated as signomial geometric programming problems with mixed–discrete variables, such as the stepped cantilever beam design problem, the spring design problem, and the pressure vessel design problem.

The engineering optimization problems that contain signomial geometric functions are NP—hard and difficult to be solved due to the combinatorial and non-convex characteristics of the problems. One major deterministic approach for globally solving the MDSO problems with signomial geometric functions is to transform the original problems as convex mixed–integer nonlinear programming (MINLP) problems. Some research [8,9,10,11,12] proposed general methods to treat generalized geometric problems and applied their methods to solve engineering design problems. Tsai and Lin [13], Lundell et al. [14], Li and Lu [15], and Lin et al. [16] solved generalized geometric problems or signomial geometric problems with continuous and discrete variables by using convexification and piecewise linearization techniques. Lin and Tsai [17] provided a complete survey of research on optimization approaches for the MDSO problems with signomial geometric functions, and proposed a deterministic method to solve the MDSO problems with signomial geometric functions by using convex transformations, linearization methods, and range reduction mechanisms. For all non-convex signomial geometric functions, Lin and Tsai [17] employed variable transformations to convexify all non-convex signomial terms, and then linearly approximated the inverse transformations. Experimental results indicated that their approach obtained an approximately globally optimal solution of the MDSO problem with a lower error in constraint compared with heuristic methods.

For treating pure discrete signomial terms in the MDSO problems, Tsai and Lin [18] proposed a linear transformation by using a logarithmic number of extra binary variables and constraints. Lu [19] developed a logarithmic method for globally solving the problems with the product of free-sign discrete functions. Both Tsai and Lin [18] and Lu [19] extended the Vielma and Nemhauser [20] method of dealing with special ordered set of type 1 (SOS1) constraints to linearize pure discrete signomial terms. Recently, Lin et al. [21] proposed a novel method based on the Li et al. [16] method to further decrease the constraints required in linearizing the discrete signomial term and efficiently treated the three-dimensional open-dimension rectangular packing problems. Tsai et al. [22] applied the Li et al. [23] method to solve the engineering design problems with discrete signomial terms. Lu [24] also proposed a similar approach for solving the product of free-sign discrete functions.

Although the deterministic optimization approach provides a theoretical guarantee of finding the global optimum, it usually leads to a significant burden in computational time. This study improves the reformulation method in Lin and Tsai [17] for the MDSO problems to enhance computational efficiency. Compared with the Lin and Tsai [17] method for the MDSO problems, this study has the following merits:

Reduces the number of convex terms generated in reformulating the MDSO problems: Compared with the Lin and Tsai [17] method that converts the pure discrete signomial terms to convex terms and then linearizes the inverse transformation functions, this study directly linearizes the pure discrete signomial terms. Therefore, fewer convex terms are introduced in the transformed model;
Decreases the number of binary variables and constraints required to linearize the inverse transformation functions of discrete variables: Compared with the Lin and Tsai [17] method, this study efficiently linearizes the inverse transformation functions of discrete variables by fewer binary variables and constraints.

The rest of the article is organized as follows. Section 2 describes the transformation techniques for convexifying a signomial term with pure discrete variables in the MDSO problems. Section 3 introduces an improved deterministic global optimization method for the MDSO problems. In Section 4, the stepped cantilever beam design problem and the pressure vessel design problem are efficiently solved to show the efficiency and effectiveness of the proposed method. After that, concluding remarks are made in Section 5.

2. Global Optimization Techniques

The mathematical programming model of an MDSO problem considered in this study, referring to Lin and Tsai [17], is expressed as follows:

MDSO:

\min f (x) = \sum_{p = 1}^{T_{0}} c_{p} x_{1}^{α_{p 1}} x_{2}^{α_{p 2}} \dots x_{n}^{α_{p n}},

(1)

subject to:

g_{k} (x) \leq l_{k}, k = 1, \dots, K,

(2)

g_{k} (x) = \sum_{q = 1}^{T_{k}} h_{k q} x_{1}^{β_{k q 1}} x_{2}^{β_{k q 2}} \dots x_{n}^{β_{k q n}},

(3)

x = (x_{1}, x_{2}, \dots, x_{n}), {\underline{x}}_{i} \leq x_{i} \leq {\bar{x}}_{i},

(4)

where

x_{i} \in R

x_{i} > 0

for

1 \leq i \leq n

x_{i}

(

1 \leq i \leq m

) are integer/discrete variables,

x_{i}

(

m + 1 \leq i \leq n

) are continuous variables,

c_{p}

h_{k q}

l_{k}

α_{p i}

β_{k q i} \in R

T_{k}

k = 1, \dots, K

, represent the numbers of monomial terms in the constraints, and

{\underline{x}}_{i}

and

{\bar{x}}_{i}

are the lower and upper bounds of the discrete variable

x_{i}

, respectively.

f (x)

and

g_{k} (x)

are mixed–discrete signomial functions.

Lin and Tsai [17] converted all non-convex signomial terms to convex terms in an MDSO problem and then linearly expressed the inverse transformation functions. The reformulated program can be solved by the conventional convex MINLP techniques to reach a global optimum. However, their method introduces many convex terms and linearizes many inverse transformation functions. Consider a pure discrete signomial term containing only integer/discrete variables

x_{i}

(

1 \leq i \leq m

) as below:

c \prod_{i = 1}^{m} x_{i}^{α_{i}}, where x_{i} \in {d_{i, 1}, d_{i, 2}, \dots, d_{i, r_{i}}}, i = 1, 2, \dots, m .

(5)

This study uses an efficient variable substitution method to directly linearize the pure discrete signomial term without introducing additional convex terms. Li et al. [23] proposed an expression of binary vectors by fewer constraints compared to the Vielma and Nemhauser [20] method. Li et al. [23] symmetrically reduced the number of constraints by half from examining binary variables in the inequality constraints. This paper applies the Li et al. [23] method to symmetrically reduce the number of constraints in linearizing a pure discrete signomial term. Assume r possible values exist for a discrete variable x,

x_{i} \in {d_{1}, d_{2}, \dots, d_{r}}

. Each

j

1 \leq j \leq r

, can be expressed as:

j = 1 + \sum_{t = 1}^{θ} 2^{t - 1} v_{t}, \forall v_{t} \in {0, 1}, θ = ⌈ \log_{2} r ⌉ .

(6)

Let

B (j) = (v_{1}, v_{2}, \dots, v_{θ})

be a binary vector of

j

where entry

t

B (j)

denotes the value of

v_{t}

in the above expression of

j

\forall j \in {1, \dots, r}

. Some notations are introduced below:

S^{+} (t)

: the set composed of all

j

having

v_{t} = 1

B (j)

, i.e.,

S^{+} (t) = {j | v_{t} = 1 in B (j)} .

S^{-} (t)

: the set composed of all

j

having

v_{t} = 0

B (j)

, i.e.,

S^{-} (t) = {j | v_{t} = 0 in B (j)}

The basis of Li et al.’s [23] logarithmic method is stated below.

Theorem 1.

[23]: For an integer

r > 0

, let h =

⌈ l o g_{2} r ⌉

. A vector

λ = (λ_{1}, \dots, λ_{r})

with

λ_{j} \geq 0

and

\sum_{j = 1}^{r} λ_{j} = 1

is a binary vector, if there is a binary vector

u = (u_{1}, \dots, u_{h})

satisfying the following linear system:

\sum_{j \in S^{+} (t)}^{} λ_{j} = u_{t} for t = 1, 2, \dots, h,

(7)

where

λ_{j} \geq 0

u_{t} \in {0, 1}

and

S^{+} (t)

is defined as before.

In Theorem 1,

λ_{j}

are real numbers, but the equality constraints enforce

λ_{j}

to be 0 or 1. Lin et al. [21] extended the Li et al. [23] method for linearizing a pure discrete signomial term

\sum_{i = 1}^{m} x_{i}^{α_{i}}

where

x_{i} \in {d_{i, 1}, d_{i, 2}, \dots, d_{i, r_{i}}}

i = 1, 2, \dots, m

. The following corollary introduced by Lin et al. [21] linearizes a signomial term with pure discrete variables:

Corollary 1.

[21]: Denote

z_{1} = f_{1} (x_{1})

z_{i} = z_{i - 1} f_{i} (x_{i})

for

i = 2, \dots, m

, and

z_{m} = \prod_{i = 1}^{m} f_{i} (x_{i})

where

f_{i} (x_{i}) > 0

x_{i}

are discrete variables,

x_{i} \in {d_{i, 1}, d_{i, 2}, \dots, d_{i, r_{i}}}

i = 1, 2, \dots, m

. The terms

z_{i}

i = 1, 2, \dots, m

, can be linearly expressed by the following expressions:

z_{1} = \sum_{j = 1}^{r_{1}} f_{1} (d_{1, j}) λ_{1, j},

(8)

z_{2} = \sum_{j = 1}^{r_{2}} f_{2} (d_{2, j}) σ_{2, j}, \sum_{j = 1}^{r_{2}} σ_{2, j} = z_{1},

(9)

z_{3} = \sum_{j = 1}^{r_{3}} f_{3} (d_{3, j}) σ_{3, j}, \sum_{j = 1}^{r_{3}} σ_{3, j} = z_{2},

(10)

z_{m} = \sum_{j = 1}^{r_{m}} f_{m} (d_{m, j}) σ_{m, j}, \sum_{j = 1}^{r_{m}} σ_{m, j} = z_{m - 1},

(11)

z_{i - 1} - {\bar{z}}_{i - 1} (1 - u_{i, t}) \leq \sum_{j \in S^{+} (t)}^{} σ_{i, j} \leq z_{i - 1}, \sum_{j \in S^{+} (t)}^{} σ_{i, j} \leq {\bar{z}}_{i - 1} u_{i, t}, t = 1, …, ⌈ \log_{2} r_{i} ⌉, i = 2, 3, \dots, m,

(12)

x_{i} = \sum_{j = 1}^{r_{i}} d_{i, j} λ_{i, j}, \sum_{j = 1}^{r_{i}} λ_{i, j} = 1, i = 1, 2, \dots, m, \sum_{j \in S^{+} (t)}^{} λ_{i, j} = u_{i, t}, t = 1, …, ⌈ \log_{2} r_{i} ⌉, i = 1, 2, \dots, m,

(13)

where

\forall λ_{i, j}, σ_{i, j} \geq 0

\forall u_{i, t} \in {0, 1}

, and

{\bar{z}}_{i - 1}

are upper bounds of

z_{i - 1}

for

i = 2, 3, \dots, m

According to Corollary 1,

\sum_{j = 1}^{m} {⌈ \log}_{2} r_{i} ⌉

binary variables,

4 m - 1 + \sum_{i = 1}^{m} {⌈ \log}_{2} r_{i} ⌉ + 3 \sum_{i = 2}^{m} {⌈ \log}_{2} r_{i} ⌉

constraints, and

\sum_{i = 1}^{m} (r_{i} + 1) + \sum_{i = 2}^{m} r_{i}

continuous variables are required to linearly express discrete variables

x_{i}

and signomial

\prod_{i = 1}^{m} x_{i}^{α_{i}}

where

x_{i} \in {d_{i, 1}, d_{i, 2}, \dots, d_{i, r_{i}}}

i = 1, 2, \dots, m

[21].

This study linearizes the pure discrete signomial terms by the method of Theorem 1. For the non-convex signomial terms containing at least one continuous variable, the following transformation techniques were used to convexify the non-convex terms. Assume a positive mixed–discrete signomial term expressed as below:

c \prod_{i = 1}^{n} x_{i}^{α_{i}}, where c > 0, x_{i} > 0, x_{i} are continuous or discrete variables .

(14)

This positive non-convex term can be converted into a convex term

c \prod_{i \in I}^{} x_{i}^{α_{i}} e^{\sum_{j \notin I}^{} α_{j} y_{j}}

where

I = {k | α_{p} < 0, p = 1, 2, \dots, n}

y_{j} = L (\ln x_{j})

is a linear function of the inverse transformation

\ln x_{j}

[17]. In this study, if

x_{j}

is a discrete variable,

x_{j} \in {d_{j, 1}, d_{j, 2}, \dots, d_{j, r_{j}}}

, then

L (\ln x_{j})

can be expressed as:

L (\ln x_{j}) = \sum_{k = 1}^{r_{j}} (\ln d_{j, k}) λ_{k}, x_{j} = \sum_{k = 1}^{r_{j}} d_{j, k} λ_{k}, \sum_{k = 1}^{r_{j}} λ_{k} = 1, \sum_{j \in S^{+} (t)}^{} λ_{k} = u_{t}, where λ_{k} \geq 0, u_{t} \in {0, 1}, and S^{+} (t) is defined as before .

(15)

Assume a negative mixed–discrete signomial term expressed as below:

c \prod_{i = 1}^{n} x_{i}^{α_{i}}, where c < 0, x_{i} > 0, x_{i} are continuous or discrete variables .

(16)

This negative non-convex term can be converted into a convex term

c \prod_{i \in I}^{} x_{i}^{α_{i}} \prod_{j \notin I}^{} y_{j}^{β}

β = (1 - \sum_{i = 1}^{w} α_{i}) / (n - w)

, where

0 \leq α_{1} \leq α_{2} \leq \dots \leq α_{p}

0 \geq α_{p + 1} \geq α_{p + 2} \geq \dots \geq α_{n}

, and

\sum_{i = 1}^{r} α_{i} < 1

for some largest integer

w

, such that

w \leq p

I = {k | k = 1, 2, \dots, w}

y_{j} = L (x_{j}^{α_{j} / β})

is a linear function of the inverse transformation

x_{j}^{α_{j} / β}

[17].

Similarly, constraint (15) is used to linearize

x_{j}^{α_{j} / β}

x_{j}

is a discrete variable. Compared to the Lin and Tsai [17] method, this study reduces the convex terms and eliminates the redundant constraints in equivalently reformulating the original MDSO problems into a convex MINLP problem. Since the method of Theorem 1 was sharp and locally ideal [21,23], the constructed model was as tight as the model constructed by Lin and Tsai [17].

3. Global Optimization Approach for the MDSO Problems

Figure 1 indicates the solving process of the proposed deterministic approach. First, the pure discrete signomial terms are directly linearized by the transformation techniques described in Corollary 1. The non-convex signomial terms containing at least one continuous variable were transformed into convex terms by the convexification strategies for the positive or negative mixed–discrete signomial term described in Section 2. Then the inverse transformation functions of discrete variables were linearly expressed by the method described in Corollary 1 and the inverse transformation functions of continuous variables were linearly approximated on the variable bounds with

m

line segments.

After the original problem was transformed into a convex MINLP problem, a convex MINLP solver was used to solve the reformulated problem for obtaining an approximate global solution

x^{*}

and to evaluate the error in constraints

e r r o r_{c o n} = \max_{k} (g_{k} (x^{*}) - l_{k}, 0)

. If

e r r o r_{c o n} \leq ε

, then list the global solution

x^{*}

. Otherwise, update the variable range by the range reduction method [17]. If the new variable bound was tighter than the original variable bound, then remain using

m

line segments to linearly approximate the inverse transformations of continuous variables on the new variable bound. Otherwise, set

m

2 m

to use more line segments in piecewise linearization for reducing the approximation error on the original variable bound.

4. Numerical Examples

The purpose of the numerical experiments described below is to demonstrate the enhancements in computational efficiency of the proposed method for the MDSO problems compared with current methods. All reformulated models were solved on a PC with a 3.2 GHz Intel Core i5-4570 CPU and 8 GB memory (Santa Clara, CA, USA).

Example 1.

This structural design problem minimizes the volume of the beam drawn from Erbatur et al. [25]. Figure 2 illustrates the structure of a five-stepped cantilever beam with a rectangular shape. Ten variables are used in this problem.

H_{i}

and

B_{i}

represent the heights and widths, respectively, in all five steps of the cantilever beam.

x_{1} (B_{4})

x_{2} (H_{4})

x_{3} (B_{5})

, and

x_{4} (H_{5})

are continuous variables,

x_{5} (B_{1})

and

x_{6} (H_{1})

are integers, and

x_{7} (B_{2})

x_{8} (H_{2})

x_{9} (B_{3})

, and

x_{10} (H_{3})

are discrete variables. The mathematical programming model of the structural design problem can be formulated as follows:

\min f (x) =_{} 100 (x_{5} x_{6} + x_{7} x_{8} + x_{9} x_{10} + x_{1} x_{2} + x_{3} x_{4}),

(17)

subject to:

g_{1} (x) = 10.7143 - \frac{x_{5} x_{6}^{2}}{10^{3}} \leq 0,

(18)

g_{2} (x) = 8.5714 - \frac{x_{7} x_{8}^{2}}{10^{3}} \leq 0,

(19)

g_{3} (x) = 6.4286 - \frac{x_{9} x_{10}^{2}}{10^{3}} \leq 0,

(20)

g_{4} (x) = 4.2857 - \frac{x_{1} x_{2}^{2}}{10^{3}} \leq 0,

(21)

g_{5} (x) = 2.1429 - \frac{x_{3} x_{4}^{2}}{10^{3}} \leq 0,

(22)

g_{6} (x) = 10^{4} (\frac{244}{x_{5} x_{6}^{3}} + \frac{148}{x_{7} x_{8}^{3}} + \frac{76}{x_{9} x_{10}^{3}} + \frac{28}{x_{1} x_{2}^{3}} + \frac{4}{x_{3} x_{4}^{3}}) - 1086 \leq 0,

(23)

g_{7} (x) = x_{6} - 20 x_{5} \leq 0,

(24)

g_{8} (x) = x_{8} - 20 x_{7} \leq 0,

(25)

g_{9} (x) = x_{10} - 20 x_{9} \leq 0,

(26)

g_{10} (x) = x_{2} - 20 x_{1} \leq 0,

(27)

g_{11} (x) = x_{4} - 20 x_{3} \leq 0,

(28)

x_{1}, x_{3} \in [1, 5], x_{2}, x_{4} \in [30, 65], x_{5} \in (1, 2, \dots, 5), x_{6} \in (30, 31, \dots, 65),

(29)

x_{7}, x_{9} \in (2.4, 2.6, 2.8, 3.1), and x_{8}, x_{10} \in (45.0, 50.0, 55.0, 60.0) .

(30)

Six pure discrete signomial terms:

x_{5} x_{6}

x_{7} x_{8}

x_{9} x_{10}

- x_{5} x_{6}^{2}

- x_{7} x_{8}^{2}

- x_{9} x_{10}^{2}

exist in Example 1. By the proposed method, these six discrete signomial terms are directly linearized. For the positive signomial terms containing continuous variables,

x_{1} x_{2}

and

x_{3} x_{4}

are convexified as

e^{z_{1} + z_{2}}

and

e^{z_{3} + z_{4}}

, respectively. For the negative signomial terms containing continuous variables,

- x_{1} x_{2}^{2}

and

- x_{3} x_{4}^{2}

are convexified as

- y_{1}^{\frac{1}{3}} y_{2}^{\frac{2}{3}}

and

- y_{3}^{\frac{1}{3}} y_{4}^{\frac{2}{3}}

, respectively. Then the inverse transformation functions are approximately linearized. This problem is equivalently reformulated as:

\min f (x) =_{} 100 (w_{1} + w_{2} + w_{3} + e^{z_{1} + z_{2}} + e^{z_{3} + z_{4}}),

(31)

subject to:

g_{1} (x) = 10.7143 - \frac{w_{4}}{10^{3}} \leq 0,

(32)

g_{2} (x) = 8.5714 - \frac{w_{5}}{10^{3}} \leq 0,

(33)

g_{3} (x) = 6.4286 - \frac{w_{6}}{10^{3}} \leq 0,

(34)

g_{4} (x) = 4.2857 - \frac{y_{1}^{\frac{1}{3}} y_{2}^{\frac{2}{3}}}{10^{3}} \leq 0,

(35)

g_{5} (x) = 2.1429 - \frac{y_{3}^{\frac{1}{3}} y_{4}^{\frac{2}{3}}}{10^{3}} \leq 0,

(36)

g_{6} (x) = 10^{4} (244 x_{5}^{- 1} x_{6}^{- 3} + 148 x_{7}^{- 1} x_{8}^{- 3} + 76 x_{9}^{- 1} x_{10}^{- 3} + 28 x_{1}^{- 1} x_{2}^{- 3} + 4 x_{3}^{- 1} x_{4}^{- 3}) - 1086 \leq 0,

(37)

g_{7} (x) = x_{6} - 20 x_{5} \leq 0,

(38)

g_{8} (x) = x_{8} - 20 x_{7} \leq 0,

(39)

g_{9} (x) = x_{10} - 20 x_{9} \leq 0,

(40)

g_{10} (x) = x_{2} - 20 x_{1} \leq 0,

(41)

g_{11} (x) = x_{4} - 20 x_{3} \leq 0,

(42)

z_{i} = L (\ln x_{i}), i = 1, 2, 3, 4,

(43)

y_{i} = L (x_{i}^{3}), i = 1, 2, 3, 4,

(44)

w_{1} = L (x_{5} x_{6}), w_{2} = L (x_{7} x_{8}), w_{3} = L (x_{9} x_{10}),

(45)

w_{4} = L (x_{5} x_{6}^{2}), w_{5} = L (x_{7} x_{8}^{2}), w_{6} = L (x_{9} x_{10}^{2}),

(46)

x_{1}, x_{3} \in [1, 5], x_{2}, x_{4} \in [30, 65], x_{5} \in (1, 2, \dots, 5), x_{6} \in (30, 31, \dots, 65),

(47)

x_{7}, x_{9} \in (2.4, 2.6, 2.8, 3.1), and x_{8}, x_{10} \in (45.0, 50.0, 55.0, 60.0) .

(48)

L (x_{5} x_{6})

L (x_{7} x_{8})

L (x_{9} x_{10})

L (x_{5} x_{6}^{2})

L (x_{7} x_{8}^{2})

, and

L (x_{9} x_{10}^{2})

are linear functions of

x_{5} x_{6}

x_{7} x_{8}

x_{9} x_{10}

x_{5} x_{6}^{2}

x_{7} x_{8}^{2}

, and

x_{9} x_{10}^{2}

, respectively, and can be directly linearized by the method introduced in Section 2.

L (\ln x_{i})

and

L (x_{i}^{3})

are linear functions of

\ln x_{i}

and

x_{i}^{3}

, respectively. After piecewise linearizing the inverse transformation functions of continuous variables, this program was transformed into a convex MINLP problem and the reformulated problem could be solved on LINGO [26]. Table 1 lists the solution, objective value, CPU time, and error in constraint (

\max_{k} (g_{k} (x^{*}) - l_{k}, 0)

) by Lin and Tsai [17] and the proposed method under 16, 32, 64, and 48 line segments in the linear approximation process on the original variable bounds. The objective value approximated closer to the exact global solution as the number of line segments increased. With the same number of line segments, the global solution obtained by the proposed method was identical to that obtained by the Lin and Tsai [17] method; however, the proposed method spent less CPU time solving the reformulated model. The difference in CPU time became larger as the number of line segments increased. With 128 line segments, the CPU time for solving the reformulated model by the Lin and Tsai [17] method was almost 3 h; however, the proposed method required only 22 min. Table 2 displays the solution, objective value, accumulated CPU time, and error in constraint in each iteration for Example 1 by Lin and Tsai [17] and the proposed method using range reduction techniques. Sixteen line segments were used for linearly approximating the inverse transformation functions of continuous variables in each iteration. The accumulated CPU time included the CPU time of solving the reformulated models and updating variable bounds. An error in constraint below 10⁻⁵ could be reached after two iterations. The Lin and Tsai [17] method and the proposed method also found identical optimal solution that was closer to the exact globally optimal solution than other existing heuristic methods [25,27,28]. Compared with the data in Table 1, the range reduction techniques significantly decreased the CPU time.

Example 2.

The pressure vessel design problem that minimizes the total cost of materials, forming, and welding of the pressure vessel shown in Figure 3 was introduced by Sandgren [29]. Four design variables

T_{s} = x_{1}

T_{h} = x_{2}

R = x_{3}

, and

L = x_{4}

are used to represent the shell thickness, the thickness of the head, the inner radius, and the length of the cylindrical section of the vessel, respectively.

T_{s}

and

T_{h}

are discrete values which are integer multiples of 0.0625 inches,

R

and

L

are continuous. Lu [19] developed a logarithmic method for solving optimization problems containing the product of free-sign discrete functions by converting all variables into discrete variables.

x_{1}

and

x_{2}

are discrete variables with discreteness 0.0625, and

x_{3}

and

x_{4}

are integer variables. Example 2 can be expressed as follows:

\min f (x) = 0.6224 x_{1} x_{3} x_{4} + 1.7781 x_{2} x_{3}^{2} + 3.1661 x_{1}^{2} x_{4} + 19.84 x_{1}^{2} x_{3}_{},

(49)

subject to:

g_{1} (x) = 0.0193 x_{3} - x_{1} \leq 0,

(50)

g_{2} (x) = 0.00954 x_{3} - x_{2} \leq 0,

(51)

g_{3} (x) = 1296000 - π x_{3}^{2} x_{4} - \frac{4}{3} π x_{3}^{3} \leq 0,

(52)

g_{4} (x) = x_{4} - 240 \leq 0,

(53)

x_{1}, x_{2} \in {0.0625, 0.125, 0.1875, \dots, 6.1875},

(54)

10 \leq x_{3} \leq 200, 10 \leq x_{4} \leq 200, x_{3} and x_{4} are integer variables .

(55)

This problem can be linearly reformulated as follows:

\min f (x) = 0.6224 w_{1} + 1.7781 w_{2} + 3.1661 w_{3} + 19.84 w_{4}_{},

(56)

subject to:

g_{1} (x) = 0.0193 x_{3} - x_{1} \leq 0,

(57)

g_{2} (x) = 0.00954 x_{3} - x_{2} \leq 0,

(58)

g_{3} (x) = 1296000 - π w_{5} - \frac{4}{3} π w_{6} \leq 0,

(59)

g_{4} (x) = x_{4} - 240 \leq 0,

(60)

w_{1} = L (x_{1} x_{3} x_{4}), w_{2} = L (x_{2} x_{3}^{2}), w_{3} = L (x_{1}^{2} x_{4}), w_{4} = L (x_{1}^{2} x_{3}),

(61)

w_{5} = L (x_{3}^{2} x_{4}), w_{6} = L (x_{3}^{3}),

(62)

x_{1}, x_{2} \in {0.0625, 0.125, 0.1875, \dots, 6.1875},

(63)

10 \leq x_{3} \leq 200, 10 \leq x_{4} \leq 200, x_{3} and x_{4} are integer variables .

(64)

L (x_{1} x_{3} x_{4})

L (x_{2} x_{3}^{2})

L (x_{1}^{2} x_{4})

L (x_{1}^{2} x_{3})

L (x_{3}^{2} x_{4})

, and

L (x_{3}^{3})

are linear expressions of

x_{1} x_{3} x_{4}

x_{2} x_{3}^{2}

x_{1}^{2} x_{4}

x_{1}^{2} x_{3}

x_{3}^{2} x_{4}

, and

x_{3}^{3}

, respectively, using the linearization techniques described in Section 2. Since all signomial terms involve only discrete variables, the transformed program was a mixed–integer linear programming problem solvable to reach a globally optimal solution. Table 3 displays the solution, objective value, and CPU time by Lin and Tsai [17] and the proposed method. The obtained global solution (0.8125, 0.4375, 42, 178) with objective 6074.99836 was the same by two methods. The proposed method required 10 s; however, the Lin and Tsai [17] required 48 s to solve this problem.

5. Conclusions

This study proposes a deterministic optimization approach for globally solving structural design problems formulated as signomial geometric programming problems with mixed–discrete variables. Efficient linearization techniques were used to directly linearize pure discrete signomial terms and to linearly express the inverse transformation functions of discrete variables, therefore resulting in a convex program with fewer convex terms and constraints. Experimental results indicated the proposed approach enhanced computational efficiency compared with current deterministic methods.

Author Contributions

Conceptualization, J.-F.T. and M.-H.L.; methodology, J.-F.T. and M.-H.L.; software, M.-H.L., and D.-Y.W.; validation, J.-F.T. and M.-H.L.; formal analysis, J.-F.T. and M.-H.L.; investigation, J.-F.T., M.-H.L., and D.-Y.W.; data curation, M.-H.L. and D.-Y.W.; writing—original draft preparation, J.-F.T. and M.-H.L.; writing—review and editing, J.-F.T. and M.-H.L.; visualization, M.-H.L. and D.-Y.W; supervision, J.-F.T and M.-H.L.; project administration, J.-F.T. and M.-H.L.; funding acquisition, J.-F.T. and M.-H.L. All authors have read and agreed to the published version of the manuscript.

Funding

This research was supported in part by the Ministry of Science and Technology in Taiwan under Grants MOST 108-2410-H-027-018, MOST 109-2410-H-027-012 -MY2 and MOST 108-2410-H-845-028.

Conflicts of Interest

The authors declare no conflict of interest.

References

Hedar, A. Studies on Metaheuristics for Continuous Global Optimization Problems Dissertation; Kyoto University: Kyoto, Japan, 2004. [Google Scholar]
Passy, U.; Wilde, D.J. A geometric programming algorithm for solving chemical equilibrium problems. SIAM J. Appl. Math. 1968, 16, 363–373. [Google Scholar] [CrossRef]
Ecker, J.G. Geometric programming: Methods, computations and applications. SIAM Rev. 1980, 22, 338–362. [Google Scholar] [CrossRef]
delM Hershenson, M.; Boyd, S.P.; Lee, T.H. Optimal design of a CMOS op-amp via geometric programming. IEEE 2001, 20, 1–21. [Google Scholar] [CrossRef] [Green Version]
Feigin, P.D.; Passy, U. The geometric programming dual to the extinction probability problem in simple branching processes. Ann. Prob. 1981, 9, 498–503. [Google Scholar] [CrossRef]
Kirschen, P.G.; York, M.A.; Ozturk, B.; Hoburg, W.W. Application of signomial programming to aircraft design. J. Aircr. 2017, 55, 965–987. [Google Scholar] [CrossRef]
Shen, P.P.; Zhang, K.C. Global optimization of signomial geometric programming using linear relaxation. Appl. Math. Comput. 2004, 150, 99–114. [Google Scholar] [CrossRef]
Floudas, C.A.; Pardalos, P.M. State of the Art in Global Optimization: Computational Methods and Applications; Kluwer Academic Publisher: Boston, MA, USA, 1996. [Google Scholar]
Maranas, C.D.; Floudas, C.A. Global optimization in generalized geometric programming. Comput. Chem. Eng. 1997, 21, 351–369. [Google Scholar] [CrossRef]
Floudas, C.A. Global optimization in design and control of chemical process systems. J. Process. Control 1999, 10, 125–134. [Google Scholar] [CrossRef]
Floudas, C.A. Recent advances in global optimization for process synthesis, design and control: Enclosure of all solutions. Comput. Chem. Eng. 1999, 23, 963–974. [Google Scholar] [CrossRef]
Floudas, C.A. Deterministic Global Optimization: Theory, Methods and Application; Kluwer Academic Publishers: Boston, CA, USA, 2000. [Google Scholar]
Tsai, J.F.; Lin, M.H. Global optimization of signomial mixed-integer nonlinear programming problems with free variables. J. Glob. Optim. 2008, 42, 39–49. [Google Scholar] [CrossRef]
Lundell, A.; Westerlund, J.; Westerlund, T. Some transformation techniques with applications in global optimization. J. Glob. Optim. 2009, 43, 391–405. [Google Scholar] [CrossRef]
Li, H.L.; Lu, H.C. Global optimization for generalized geometric programs with mixed free-sign variables. Oper. Res. 2009, 57, 701–713. [Google Scholar] [CrossRef]
Lin, M.H.; Tsai, J.F.; Wang, P.C. Solving engineering optimization problems by a deterministic global approach. Appl. Math. Inf. Sci. 2012, 6, 1101–1107. [Google Scholar]
Lin, M.H.; Tsai, J.F. A deterministic global approach for mixed-discrete structural optimization. Eng. Optim. 2014, 46, 863–879. [Google Scholar] [CrossRef]
Tsai, J.F.; Lin, M.H. An improved framework for solving NLIPs with signomial terms in the objective or constraints to global optimality. Comput. Chem. Eng. 2013, 53, 44–54. [Google Scholar] [CrossRef]
Lu, H.C. A logarithmic method for eliminating binary variables and constraints for the product of free-sign discrete function. Discret. Optim. 2013, 10, 11–24. [Google Scholar] [CrossRef] [Green Version]
Vielma, J.P.; Nemhauser, G. Modeling disjunctive constraints with a logarithmic number of binary variables and constraints. Math. Prog. 2011, 128, 49–72. [Google Scholar] [CrossRef]
Lin, M.H.; Tsai, J.F.; Chang, S.C. A superior linearization method for signomial discrete functions in solving three-dimensional open-dimension rectangular packing problems. Optimization 2017, 49, 746–761. [Google Scholar] [CrossRef]
Tsai, J.F.; Lin, M.H.; Peng, L.Y. Finding all global optima of engineering design problems with discrete signomial terms. Eng. Optim. 2020, 52, 165–184. [Google Scholar] [CrossRef]
Li, H.L.; Huang, Y.H.; Fang, S.C. A logarithmic method for reducing binary variables and inequality constraints in solving task assignment problems. INFORMS J. Comput. 2013, 25, 643–653. [Google Scholar] [CrossRef]
Lu, H.C. Improved logarithmic linearizing method for optimization problems with free-sign pure discrete signomial terms. J. Glob. Optim. 2017, 68, 95–123. [Google Scholar] [CrossRef]
Erbatur, F.; Hasancebi, O.; Tutuncu, I.; Kilic, H. Optimal design of planar and space structures with genetic algorithms. Comput. Struct. 2000, 75, 209–224. [Google Scholar] [CrossRef]
LINGO Release 17.0; LINDO System Inc.: Chicago, IL, USA, 2018.
Cai, J.; Thierauf, G. Evolution strategies for solving discrete optimization problems. Adv. Eng. Softw. 1996, 25, 177–183. [Google Scholar] [CrossRef]
Chen, T.Y.; Chen, H.C. Mixed-discrete structural optimization using a rank-niche evolution strategy. Eng. Optim. 2009, 41, 39–58. [Google Scholar] [CrossRef]
Sandgren, E. Nonlinear integer and discrete programming in mechanical design optimization. J. Mech. Des. 1990, 112, 223–229. [Google Scholar] [CrossRef]

Figure 1. Global optimization approach for the mixed–discrete structural optimization (MDSO) problems.

Figure 2. A stepped cantilever beam.

Figure 3. Pressure vessel design.

Table 1. Comparisons of experimental results of Example 1 by different methods.

$m$	$Solution (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}, x_{7}, x_{8}, x_{9}, x_{10})$	Objective Value	CPU Time (hh:mm:ss)		Error in Constraint
$m$		Objective Value	Lin and Tsai [17]	Proposed Method	Error in Constraint
16	(2.202244, 44.044890, 1.748798, 34.975960, 3.0, 60.0, 3.1, 55.0, 2.6, 50.0)	63,850.641469	00:02:32	00:00:59	0.013452
32	(2.203906, 44.078113, 1.749476, 34.989529, 3.0, 60.0, 3.1, 55.0, 2.6, 50.0)	63,880.915782	00:07:14	00:02:21	0.003775
64	(2.204395, 44.087898, 1.749733, 34.994651, 3.0, 60.0, 3.1, 55.0, 2.6, 50.0)	63,890.838703	00:35:19	00:06:35	0.000923
128	(2.204503, 44.090051, 1.749753, 34.995065, 3.0, 60.0, 3.1, 55.0, 2.6, 50.0)	63,892.602486	02:57:18	00:21:36	0.000295

Table 2. Comparisons of experimental results of Example 1 by different methods with range reduction.

Iteration	$Solution (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}, x_{7}, x_{8}, x_{9}, x_{10})$	Objective Value	Accumulated CPU Time (hh:mm:ss)		Error in Constraint
Iteration		Objective Value	Lin and Tsai [17]	Proposed Method	Error in Constraint
1	(2.202244, 44.044890, 1.748798, 34.975960, 3.0, 60.0, 3.1, 55.0, 2.6, 50.0)	63,850.641953	00:02:42	00:00:42	0.013452
2	(2.204553, 44.091065, 1.749769, 34.995373, 3.0, 60.0, 3.1, 55.0, 2.6, 50.0)	63,893.490593	00:44:43	00:11:36	0.000005

Table 3. Experimental results of Example 2 by different methods.

$Solution (x_{1}, x_{2}, x_{3}, x_{4})$	Objective Value	CPU Time (hh:mm:ss)
$Solution (x_{1}, x_{2}, x_{3}, x_{4})$	Objective Value	Lin and Tsai [17]	Proposed Method
(0.8125, 0.4375, 42, 178)	6074.99836	00:00:48	00:00:10

© 2020 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Tsai, J.-F.; Lin, M.-H.; Wen, D.-Y. Global Optimization for Mixed–Discrete Structural Design. Symmetry 2020, 12, 1529. https://doi.org/10.3390/sym12091529

AMA Style

Tsai J-F, Lin M-H, Wen D-Y. Global Optimization for Mixed–Discrete Structural Design. Symmetry. 2020; 12(9):1529. https://doi.org/10.3390/sym12091529

Chicago/Turabian Style

Tsai, Jung-Fa, Ming-Hua Lin, and Duan-Yi Wen. 2020. "Global Optimization for Mixed–Discrete Structural Design" Symmetry 12, no. 9: 1529. https://doi.org/10.3390/sym12091529

APA Style

Tsai, J. -F., Lin, M. -H., & Wen, D. -Y. (2020). Global Optimization for Mixed–Discrete Structural Design. Symmetry, 12(9), 1529. https://doi.org/10.3390/sym12091529

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

Global Optimization for Mixed–Discrete Structural Design

Abstract

1. Introduction

2. Global Optimization Techniques

3. Global Optimization Approach for the MDSO Problems

4. Numerical Examples

5. Conclusions

Author Contributions

Funding

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI