Sage Journals: Discover world-class research

Abstract

The main issue in the present article is to investigate how to solve a mixed integer fractional signomial geometric programing problem (MIFSGP). In the first step to achieving this idea, we must convert a fractional signomial programing problem into a non-fractional problem via a simple conversion technique. Then, a convex relaxation with a new modified piecewise linear approximation with integer break points as a pre-solve method is used to reach an integer global optimum solution. A few numerical examples are included to illustrate the advantages of the proposed method

Keywords

Global optimization geometric programing signomial fractional programing mixed integer programing and piecewise linear approximation

Introduction

A mixed integer signomial geometric fractional programing problem (MISFP) arises from the minimization of a quotient function which consists of several signomial terms appearing in the objective function subject to given signomial constraints with some integer decision variables.¹ In the optimization literature, geometric fractional programing problems play a very important role in engineering designs and management problems.

Fractional programing problems occur in many decision programs such as industrial economics, Information theory.^2–4 In addition, fractional programing problems are identified to optimize power distribution systems.⁵ Even though fractional programing has received intensive attention in the last four decades because of its importance in modeling many optimization problems, the discussion on methods of solving signomial fractional problems (SFP) has received less attention. Since these problems often occur in Complex industrial designs with a large number of variables and require a lot of accuracy, the main challenge of such problems is to reach the global optimal solution for integer or real variables within the shortest time and the least amount of computer memory space usage. For this reason our effort has been made to reach a more efficient and faster method than the previous methods.

In 1967, Dinkelbach⁶ proposed an algorithm to solve continuous nonlinear fractional programing problems that were also used to solve many issues involving geometric fractional objectives. Several specialized methods have been proposed to obtain the global optimum for mixed integer geometric programing problems (MIGPP).⁷

Chang⁸ worked on a problem to reach a solution as close as a global solution for the mixed integer fractional posynomial programing problems. Tsai⁹ proposes a new treat by using a convex and linearization method for solving nonlinear fractional programing problems, with multiple fractional signomial functions.

M. Saraj et al. (2018) solved posynomial fractional programing problems (PFP) via the linearization approach, in addition, they have also considered the problem of linear multi objective geometric programing problem via reference point approach in (2014).^10,11 In a recent researches, Mishra et al¹² solved nonlinear fractional programing problems by signomial geometric programing approach. Shirinnejad et al.¹³ proposed a technique to solve a signomial fractional programing problems globally with as small as distance from the solution of the original problem. In a valuable work by Westerlund,¹⁴ a few helpful transformation techniques are considered in deterministic global optimization for signomial programing problems. In addition, he applied the most effortless power transformations to convexify posynomial and signomial geometric terms. Although the GGPECP algorithm used by Westerlund in 2003 was used to solve the convexified and underestimated problems to reach a globally optimal solution, in his method, he used too many constraints in expressing a piecewise linear function, which may cause heavy computational burdens. Therefore we have presented an efficient technique by combining power transformations tool to convexify the non-convex signomial terms and a more accurate modified linearization technique which can give mixed integer solution as close as possible to the original problem. By applying our propose, we observed not only less number of iterations but also got the integer solution as well.

There are two ways to convex a positive signomial term (posynomial) with power transformation, so-called Negative power transformation (NPT) and positive power transformation (PPT).

Although using NPT is more accessible than PPT, the PPT technique makes a convex form of signomial function tighter than NPT to original non-convex functions, as explained in Westerlund et al.¹⁴ Tsai (2005) proposed a new approach to solve a general signomial fractional programing problem to reach a global optimum. He used NPT to convexify posynomial terms and superior piecewise linearization techniques. We now use the PPT technique to convexify the non-convex posynomial term along with piecewise linear approximations.

In this work, we have applied a modified model for piecewise linear functions of one and two variables which perform significantly better than the standard binary models that Vilma and Nemhauser¹⁵ proved the efficiency of this superior piecewise linearization technique. Therefore, this work discusses a mixed integer global optimal solution to convexify every non-convex signomial term. Univariate transformations are applied in such a way to convexify and underestimate with this piecewise linear approximation of the inverse transformation of f(x), where x lies in the interval [a₀, a_m] such that a₀, a_m∈ Z with m + 1 integer breakpoints. In this article, applying integer breakpoints for integer variables is studied in detail as a pre-solution method to reach the integer solution for those variables.

This issue develops a global optimization method with fewer iteration numbers and CPU time than other methods to obtain a mixed integer solution in solving a Signomial Fractional Programing problem (SFP).

Problem formulation

A mixed integer signomial fractional programing problem (MISFP) seeks an approximate global optimum solution denoted as $C (x) = \sum_{j = 1}^{J} c_{j} Π_{i = 1}^{n} x_{j}^{α_{ji}}$ where c_j and α_ji $\in R \ {0}$ .

The variables in a signomial function must be Positive.

This study considers a MISFP problem with the following form:

Minimize f (x) = \frac{P (x)}{Q (x)}

S . t Ax \leq b

B_{k} (x) + C_{k} (x) \leq 0, k = 1, 2, \dots, K

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

Where P(x) and Q(x) represent twice–differentiable signomial functions and $Q (x) > 0$ .

The matrix A and vector b are constants, and B_k and C_k represent convex and non–convex signomial functions, respectively. ${\underline{x}}_{i}$ and ${\bar{x}}_{i}$ indicate the lower and upper bounds of a real and bounded variable x_i.

Since the transformation approach is valid for signomial constraints, therefore the signomial fractional expression $\frac{P (x)}{Q (x)}$ in objective function can be rewritten in the constraint form as below:

Minimize x_{n + 1}

S . t \frac{P (x)}{Q (x)} - x_{n + 1} \leq 0, Q (x) > 0 \forall x

S . t Ax \leq b

B_{k} (x) + C_{k} (x) \leq 0, k = 1, 2, \dots, K

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

The problem is further converted to:

P (x) - x_{n + 1} . Q (x) \leq 0

Where $x_{n + 1}$ is a new real and bounded variable.

(2.2) is a signomial function and may be non–convex.

Convexification strategies

The problem of convexification a non-convex signomial term, such as inverse and exponential transformations, is discussed in detail in Shen and Yu^2,7 Lundell et al.¹⁶, Chang¹ In this study, we use a particular case of the inverse transformation technique suggested by Westerlund. Convexity requirements for negative and positive signomial terms are given in the following propositions.⁹

Proposition 1. A twice differentiable function $f (x) = c Π_{i = 1}^{n} x_{i}^{α_{i}}$ is convex if $c < 0, x_{i}, α_{i} > 0,$

$(i = 1, \dots, n) and \sum_{i = 1}^{n} α_{i} \leq 1$ .

Proposition 2. A twice differentiable function, $f (x) = c Π_{i = 1}^{n} x_{i}^{α_{i}}$ is convex if $\forall c > 0, x_{i} > 0, α_{i} \leq 0, (i = 1, \dots, n)$

Proposition 2 in the literature is called (NPT). The technique of NPT is used to convexify and underestimate the posynomial terms because it seems simpler than positive power transformation (PPT). Westerlund indicated that PPT is a tighter underestimate than (NPT).

Therefore, we apply PPT to convexify posynomial terms. PPT can be expressed and proved in Proposition 3.

Consider the following Lemma and Hints from Tsai⁹:

Lemma. Due to differentiability of $X$ , we have $f (X) = c Π_{i = 1}^{n} x_{i}^{α_{i}}$ where $X = (x_{1}, x_{2}, \dots, x_{n})$ for $i = 1, \dots, n$ , $\forall i x_{i}, α_{i},$

c \in R, detH (X) = (- c)^{n} (Π_{i = 1}^{n} α_{i} x_{i}^{n α_{i} - 2}) (1 - \sum_{i = 1}^{n} α_{i}) .

Hint 1: If c, $x_{i} > 0$ and $α_{i} \leq 0$ (for all i), det $H (x) \geq 0 .$

Hint 2: If $c < 0$ and $x_{i}, α_{i} \geq 0$ (for all i), and $1 - \sum_{i = 1}^{n} α_{i} \geq 0,$ det $H (x) \geq 0 .$

Proposition 3. A differentiable function, $f (X) = c Π_{i = 1}^{n} x_{i}^{α_{i}}$ is said to be convex if $\forall c, x_{i} > 0, \exists k \neq i, α_{k} > 0,$

$α_{i} \leq 0 (i = 1, \dots, n), \sum_{i = 1}^{n} α_{i} \geq 1$ .

Proposition 3 is called PPT technique in the literature.

We demonstrate an alternative proof for this proposition:

Proof. Through the Hessian matrix H(X) of f (X), for $i = 1, \dots, n, α_{i} \leq 0, \exists k \neq i, α_{k} > 0$ , by lemma 3.1 and

Hint 1, we have

\begin{matrix} \det H_{i} (X) = (- c)^{i} (Π_{j = 1}^{i} α_{j} x_{j}^{i α_{j} - 2}) (1 - \sum_{j = 1}^{i} α_{j}) > 0, \\ for i = 1, \dots, n, i \neq k \end{matrix}

(1)

\det H_{k} (X) = (- c)^{k} (Π_{j = 1}^{k} α_{j} x_{j}^{k α_{j} - 2}) (1 - \sum_{j = 1}^{k} α_{j})

(2)

Now, concerning k, there are two modes:

(1) If k is even, then:

since $c > 0$ , so $(- c)^{k} > 0, α_{k} > 0$ and for $1 \leq j < k$ ,

The number of $α_{j} < 0$ , is odd, then $(Π_{j = 1}^{k} α_{j} x_{j}^{k α_{j} - 2}) < 0$

Therefore:

$H_{k} (X) > 0$ , if and only if $(1 - \sum_{j = 1}^{k} α_{j}) \leq 0$ or $(\sum_{j = 1}^{k} α_{j} \geq 1)$ .

(2) If k is odd, then:

Since $c > 0$ , so $(- c)^{k} < 0, α_{k} > 0$ and for $1 \leq j < k$ ,

The number of $α_{j} < 0$ , is even, then $(Π_{j = 1}^{k} α_{j} x_{j}^{k α_{j} - 2}) < 0$

Therefore:

$H_{k} (X) > 0$ , if and only if $(1 - \sum_{j = 1}^{k} α_{j}) \leq 0$ or $(\sum_{j = 1}^{k} α_{j} \geq 1)$ .

Since $\det H_{i} (X) \geq 0$ , for all i, then H(X) is positive definite, and consequently, f(X) is convex.

Transformation and underestimation approach

Convexification a non-convex function is a very essential concept in determining global optimization techniques. A good convex under-estimator should be as tight as possible and contains a minimum number of additional variables and constraints. By approximating the inverse power transformations, $x = X^{α}$ or $x^{\frac{1}{α}} = X$ , with piecewise linear functions, the whole problem can be convexified. Now we prove the transformation theorem for negative signomial terms.

Consider the following remark from Tsai and Lin,¹⁷ which expresses the conditions to convexify a power function:

Remark 1. A function $f (x) = x^{α}$ , $x > 0$ , is convex when $α \leq 0$ or $α \geq 1$ , and f(x) is concave if $0 < α < 1$ .

Remark 3. A negative signomial term, $z = {cx}_{1}^{p_{1}} x_{2}^{p_{2}} \dots x_{n}^{p_{n}}$ , where $x_{i} > 0$ , (for $i = 1, \dots, n, c < 0, p_{i} \geq 0)$ , $(for i = 1, 2, \dots, k, k < n, p_{i} < 0)$ and $(for i = k + 1, \dots, n)$ , can be convexified and underestimated as follows:

(i) $z = c Π_{i = 1}^{k} {({(x_{i}^{\frac{1}{α}})}^{α})}^{p_{i}} . Π_{i = k + 1}^{n} {({(x_{i}^{- \frac{1}{β}})}^{- β})}^{p_{i}}$

(ii) $α \sum_{i = 1}^{k} p_{i} - β \sum_{i = k + 1}^{n} p_{i} \leq 1$ , where $0 < α \leq 1, β > 0$

(iii) $c \prod_{i = 1}^{k} L {(X_{i})}^{α P_{i}} . \prod_{i = k + 1}^{n} L {(X_{i})}^{- β P_{i}} \leq c \prod_{i = 1}^{k} X_{i}^{α p_{i}} . \prod_{i = k + 1}^{n} {X_{i}}^{- β P_{i}}$

Where L(X_i) is a piecewise linearization approximation of

X_{i} = x_{i}^{\frac{1}{α}} i = 1, \dots, k

(3)

And L(X_i) is a piecewise linearization approximation of

X_{i} = x_{i}^{\frac{- 1}{β}} i = k + 1, \dots, n

(4)

Hint: Without losing generality, the signomial terms can be rewritten by (i), inverse transformations (3), and (4) for $α, β > 0$ . Now, with assumptions (ii) and (iii), we want to prove that $Z$ can be convexified and underestimated.

Proof. Since all powers in (iii) are positive with $α, β > 0$ , the inequality (iii) will be valid if

L (X_{i}) \geq X_{i} i = 1, \dots, n

(5)

We find that (5) and thus (iii) will be valid if (3) and (4) are convex functions; it is fulfilled if $α$ is chosen in $0 < α \leq 1$ and $β > 0$ , so they are satisfied by conditions of (ii) and remark 1.

Thus, $Z$ in (i) is a convex term referring to proposition 3.

Theorem 1: A positive signomial term (posynomial) $z = {cx}_{1}^{p_{1}} x_{2}^{p_{2}} \dots x_{n}^{p_{n}}$ . Where $p_{i} \geq 0$ (for $i = 1, \dots, k$ ),

$P_{i} < 0$ (for $i = k + 1, \dots, n)$ , and $p_{1} \geq p_{2} \geq \dots \geq p_{n}$ can be convexified and underestimated as follows:

i) $z = c {({(x_{1}^{\frac{1}{α}})}^{α})}^{p_{1}} . Π_{i = 2}^{k} {({(x_{i}^{\frac{- 1}{β}})}^{- β})}^{p_{i}} . Π_{i = k + 1}^{n} x_{i}^{p_{i}}$ .

ii) $α p_{1} - β \sum_{i = 2}^{k} p_{i} + \sum_{i = k + 1}^{n} p_{i} \geq 1$ , where $α \geq 1, β > 0$ .

iii) $c {(L (X_{1}))}^{α p_{1}} . Π_{i = 2}^{k} (L (X_{i}))^{- β P_{i}} . Π_{i = k + 1}^{n} x_{i}^{p_{i}} \leq {cX}_{1}^{α p_{1}} . Π_{i = 2}^{k} X_{i}^{- β p_{i}} . Π_{i = k + 1}^{n} x_{i}^{p_{i}}$

Where L(X_i) represents piecewise linear approximations of

X_{1} = x_{1}^{\frac{1}{α}}

(6)

and

X_{i} = x_{i}^{\frac{- 1}{β}}, for i = 2, \dots, k .

(7)

Proof. Without losing generality, z can be rewritten by (i) by choosing $X_{1} = x_{1}^{\frac{1}{α}}$ , $X_{i} = x_{i}^{\frac{- 1}{β}}$ , $i = 2, \dots, k α, β > 0$ , so we have $z = {cX}_{1}^{α p_{1}} . Π_{i = 2}^{k} X_{i}^{- β p_{i}} . Π_{i = k + 1}^{n} x_{i}^{p_{i}}$ .

Inequality (iii) should be valid if

L (X_{1}) \leq X_{1}

(8)

And L (X_{i}) \geq X_{i} For i = 2, \dots, k

(9)

Since the first transformation variable in the left-hand inequality of (iii) is an increasing function where the next k−1 variables in the transformed signomial term have negative powers, it corresponds to decreasing functions. Hence, it was found that (8) and (9) are valid if the inverse transformation (6) is provided a concave function and the inverse transformations (7) are offered by convex functions too. Thus, (iii) is fully satisfied parameter $α$ is chosen, such as the $α \geq 1$ for (6) to be a concave function and $β > 0$ for (7) to be a convex function.

Since $α \geq 1$ and $β > 0$ , in the expression (ii), $α p_{1} - β \sum_{i = 2}^{k} p_{i} + \sum_{i = k + 1}^{n} p_{i} \geq 1$

The first term is positive and the second and third are negative. It is also valid for any sufficiently large α and small $β$ .

Hence, according to conditions (ii) and (iii), z is a convex w.r.t.

Piecewise linear approximation

A custom way to Solve piecewise linear approximation is to apply the special order sets (SOS). However, this study used a much better approach in fractional programing, which is more efficient than ordinary methods. Therefore, this work uses a tight relaxation method of approximating piecewise linear functions.¹⁵

Remark¹⁷: An injective function $B : {1, 2, \dots, m} \to {0, 1}^{θ}, θ = lo g_{2} m$ , where the vectors $B (p)$ and $B (p + 1)$ differ in at most one component for all $p \in {1, 2, \dots, m - 1}$ .

Let $B (p) = (u_{1}, u_{2}, \dots, u_{θ}), \forall u_{h} \in {0, 1}, k = 1, 2, \dots θ$ . and $B (0) = B (1)$ .

$S^{+} (k) = {p ∣ \forall B (p)$ and $B (p + 1), u_{k} = 1, p = 1, 2, \dots, m - 1} \cup$ ${p ∣ \forall B (p), u_{i} = 1, p \in {0, m}}$

$S^{-} (k) = {p ∣ \forall B (p)$ and $B (p + 1), u_{Y} = 0, p = 1, 2, \dots, m - 1} \cup$ ${p ∣ \forall B (p), u_{k} = 0, p \in {0, m}}$ .

Theorem 2¹⁷: The Given a univariate function $f (x)$ , $a_{0} \leq x \leq a_{m}$ , denote $L (f (x))$ as the piecewise linear function of $f (x)$ , where

$a_{0} < a_{1} < a_{2} < \dots < a_{m}$ be the $m + 1$ integer break points of $L (f (x))$ can be expressed as

L (f (x)) = \sum_{p = 0}^{m} f (a_{p}) w_{p}, x = \sum_{p = 0}^{m} a_{p} w_{p}, \sum_{p = 0}^{m} w_{p} = 1,

\sum_{p \in S^{+} (k)} w_{p} \leq u_{k}, \sum_{p \in S^{-} (k)} w_{p} \leq 1 - u_{k}, \forall w_{p} \in R_{+},

\forall u_{k} \in {0, 1} and \forall x \in Z, a_{p} \in Z c

Since we are looking for a global integer solution for a class of mixed integer nonlinear programing problems, we use in this study integer breakpoints in the piecewise linearization technique to approximate the inverse transformation functions for every integer decision variable. This strategy can solve the mixed integer convexified signomial programing problems faster than the custom (SOS). Thus, the integer results were achieved for integer variables with no greater dominations.

Illustrative examples

Example 1. Consider the following non-convex MISFP problem. The tolerable error is specified as ε = 0.02 from Chang¹:

\begin{matrix} Min \frac{x_{1} x_{2}^{0.5} x_{3}^{1.2}}{2 x_{2} x_{3} + x_{2}^{2.1} x_{3}^{1.3}} \\ S . t \\ 2 x_{1} + 3 x_{2} + x_{3} \geq 8 \end{matrix}

(10)

3 x_{1} + x_{2} \geq 5

(11)

x_{2} + 2 x_{3} \geq 10

(12)

2 x_{1} + x_{3} \leq 4

(13)

0.2 \leq x_{1} \leq 5, 1 \leq x_{2} \leq 5, 1 \leq x_{3} \leq 5

(14)

x_{1} \in R, x_{2}, x_{3} \in Z

We introduce a new and small variable $(0.01 < x_{4} \leq 1.9)$ for the above problem and use proposition 1 and proposition 3 as a transforming strategy and theorem1 from Tsai and Lin¹⁷ as a linear approximation strategy to treat this problem, respectively.

This problem then becomes a convex MISP problem below:

\begin{matrix} Minimize x_{4} \\ S . t x_{1} x_{2}^{0.5} x_{3}^{1.2} - 2 x_{2} x_{3} x_{4} - x_{2}^{2.1} x_{3}^{1.3} x_{4} \leq 0 \\ S . t (1) - (5) \\ 0.01 \leq x_{4} \leq 1.9 \\ x_{1}, x_{4} \in R, x_{2}, x_{3} \in Z \end{matrix}

There are three non-convex terms in the constraints. To convexify the positive term $x_{1} x_{2}^{0.5} x_{3}^{1.2}$ , Based on proposition 3:

Let K = 3, $α_{1}, α_{2} < 0, α_{3} > 0, such that α_{1} + α_{2} + α_{3} \geq 1$

Let $α_{1} = - 0.5$ , $α_{2} = - 0.5, α_{3} = 2.4$ so it needs to power transformations as: $X_{1} = x_{1}^{- 2}$ , $X_{2} = x_{2}^{- 1} and X_{3} = x_{3}^{0.5}$ therefore $x_{1} x_{2}^{0.5} x_{3}^{1.2} = X_{1}^{- 0.5} X_{2}^{- 0.5} X_{3}^{2.4}$

To convexify the non-convex negative signomial term $- 2 x_{2} x_{3} x_{4}$ by referring to proposition 1, we have:

$α (1 + 1 + 1) \leq 1$ with $0 \leq α \leq 1$ so we have $α \leq \frac{1}{3}$ , and the inverse transformation variables $y_{i} = x_{i}^{3}$ and for the non-convex signomial term $- 2 x_{2} x_{3} x_{4}$ yields to $- 2 Y_{2}^{\frac{1}{3}} Y_{3}^{\frac{1}{3}} Y_{4}^{\frac{1}{3}}$ , and for another signomial term:

$- x_{2}^{2.1} x_{3}^{1.3} x_{4}$ We have: $4.4 α \leq 1 \Rightarrow α \leq \frac{10}{34}, Z_{i} = {(x_{i})}^{\frac{44}{10}}$ so $- x_{2}^{2.1} x_{3}^{1.3} x_{4}$ is convexified as $- Z_{2}^{\frac{21}{44}} Z_{3}^{\frac{13}{44}} Z_{4}^{\frac{10}{44}}$ .

The original MISFP problem is reformulated as follows:

\begin{matrix} Minimize x_{4} \\ S . t {\hat{X}}_{1}^{- 0.5} {\hat{X}}_{2}^{- 0.5} {\hat{X}}_{3}^{2.4} - 2 {\hat{Y}}_{2}^{\frac{1}{3}} {\hat{Y}}_{3}^{\frac{1}{3}} {\hat{Y}}_{4}^{\frac{1}{3}} - {\hat{Z}}_{2}^{\frac{21}{44}} {\hat{Z}}_{3}^{\frac{13}{44}} {\hat{Z}}_{4}^{\frac{10}{44}} \leq 0 \\ {\hat{X}}_{1} = L (x_{1}^{- 2}), {\hat{X}}_{2} = L (x_{2}^{- 1}), {\hat{X}}_{3} = L (x_{3}^{0.5}) \\ {\hat{Y}}_{i} = L (x_{i}^{3}), i = 2, 3, 4, {\hat{Z}}_{4} = L (x_{4}^{\frac{44}{10}}), {\hat{Z}}_{3} = L (x_{3}^{\frac{44}{13}}), \\ {\hat{Z}}_{2} = L (x_{2}^{\frac{44}{21}}) \\ (1) - (5) \\ x_{1}, x_{4} \in R, x_{2}, x_{3} \in Z \end{matrix}

Where $L (x_{i}^{α}), i = 1, 2, 3, 4$ represent the piecewise linearized expressions. By considering theorem 1 and utilizing only four integer breakpoints, to achieve piecewise linearization, as you can see in table 1, we can solve that problem. The convex problem is solved by LINGO software 18.0 (2014),⁷ and the global mixed-integer result is $(x_{1}, x_{2}, x_{3}) = (0.33, 4, 3)$ . The objective value for the relaxed problem x₄ is 0.01, and $ε = 0.00009$ by 14 iterations without using any additional integer programing algorithm. Although, if the original non-convex problem is solved using the branch and bound algorithm, it will have the mixed integer solution with fewer iterations, the value of the objective function will be worse. In addition, compared to the previous solution method in Chang,¹ which by considering four breakpoints, the value of the objective function was 0.07361 and the approximation error was 0.062737 without reaching the integer solution for x₃. so, to reach an acceptable approximation error, the author had to choose more break points. It is obvious that the proposed method has reached the desired solution by devoting less time and CPU memory, and this difference will be more visible in problems with more variables.

Example 2. The actual optimization problem of a shock absorber design presented minimizing the weight of a stress shock absorber subject to some constraints on the minimum deflection. The variables x₁, x₂, and x₃ are the mean coil diameter, the wire diameter, and the number of active coils, respectively.⁹

\begin{matrix} Minimize (x_{3} + 2) x_{1} x_{2}^{2} \\ Subject to 1 - \frac{x_{1}^{3} x_{3}}{71785 x_{2}^{4}} \leq 0 \\ \frac{3 x_{1}^{2} - x_{1} x_{2}}{12566 (x_{1} x_{2}^{3} - x_{2}^{4})} + \frac{1}{5108 x_{2}^{2}} - 1 \leq 0 \\ 1 - \frac{140.45 x^{2}}{x_{2} x_{3}} \leq 0 \\ \frac{x_{1} + x_{2}}{1.5} - 1 \leq 0 \\ 0.25 \leq x_{1} \leq 1.3, 0.05 \leq x_{2} \leq 2.0, 2 \leq x_{3} \leq 15 \end{matrix}

Table 1.

Chosen integer breakpoints for integer variables.

Variables	Breakpoints
$x_{1}$	(0.2,1.4,2.6,3.8,5)
$x_{2}$	(1,2,3,4,5)
$x_{3}$	(1,2,3,4,5)
$x_{4}$	(0.01,0.49,0.97,1.45,1.91)

The above problem can be reformulated as follows:

\begin{matrix} Minimize {\hat{Y}}_{1}^{- 1} {\hat{Y}}_{2}^{4} {\hat{Y}}_{3}^{- 1} + 2 {\hat{Y}}_{1}^{- 1} x_{2}^{2} \\ Subject to - 1 + 71785 + {\hat{Z}}_{1}^{0.75} x_{2}^{4} x_{3}^{- 1} \leq 0 \\ \frac{3 {\hat{Y}}_{1}^{- 2} {\hat{X}}_{2}^{- 3} {\hat{u}}^{- 1}}{12566} + \frac{{\hat{Y}}_{1}^{- 1}}{12566} + \frac{{\hat{X}}_{2}^{- 2}}{5108} - 1 \leq 0 \\ x_{3} - 140.45 \leq 0 \\ x_{1} + x_{2} - 1.5 \leq 0 \\ where Y_{1} = x_{1}^{- 1}, Y_{2} = x_{2}^{- 0.5}, Y_{3} = x_{3}^{- 1}, Z_{1} = x_{1}^{4} \\ u = x_{1} - x_{2}, {\hat{Y}}_{i} = L (Y_{i}), {\hat{Z}}_{1} = L (Z_{1}) \\ 0.25 \leq x_{1} \leq 1.3, 0.05 \leq x_{1} \leq 2.0, 2 \leq x_{3} \leq 15 \\ x_{1}, x_{2} \in R, x_{3} \in Z \end{matrix}

By previous theorems

{\hat{Y}}_{1} \geq Y_{1}, {\hat{Y}}_{3} \geq Y_{3}, {\hat{Z}}_{1} \geq Z_{1} and {\hat{Y}}_{2} \geq Y_{2}

L(Y_i) represents the piecewise linearization expressions of the terms Y_i = 1,2,3 by Theorem 2.

Without utilizing any integer algorithm, to reach a global optimum solution for four breakpoints, we have:

\begin{matrix} x_{1} = \sum_{P = 0}^{4} a_{P} w_{P}, {\hat{Y}}_{1} = \sum_{P = 0}^{4} (a_{P})^{- 1} w_{P}, \\ {\hat{Z}}_{1} = \sum_{P = 0}^{4} (a_{P})^{4} w_{P}, a_{P} \in [0.25, 1.3] \\ \sum_{P = 0}^{4} w_{P} = 1, w_{0} + w_{1} \leq u_{1}, w_{3} + w_{4} \leq 1 - u_{1}, \\ w_{2} \leq u_{2}, w_{0} + w_{4} \leq 1 - u_{2}, \\ \forall w_{j} \in R_{+}, j = 0, 1, 2, 3, 4 \\ u_{1}, u_{2} \in {0, 1} \end{matrix}

\begin{matrix} x_{2} = \sum_{P = 0}^{4} a_{P} w_{P + 5}, {\hat{Y}}_{2} = \sum_{P = 0}^{4} (a_{P})^{- 0.5} w_{P + 5}, \\ {\hat{Z}}_{1} = \sum_{P = 0}^{4} (a_{P})^{4} w_{P}, a_{P} \in [0.05, 2] \end{matrix}

\begin{matrix} \sum_{P = 0}^{4} w_{P + 5} = 1, w_{5} + w_{6} \leq u_{3}, w_{8} + w_{9} \leq 1 - u_{3}, \\ w_{7} \leq u_{4}, w_{5} + w_{9} \leq 1 - u_{4}, \end{matrix}

\forall w_{j} \in R_{+}, j = 5, 6, 7, 8, 9

\begin{matrix} x_{3} = \sum_{P = 0}^{4} a_{P} w_{P + 10}, {\hat{Y}}_{3} = \sum_{P = 0}^{4} (a_{P})^{- 1} w_{P + 10}, \\ {\hat{Z}}_{1} = \sum_{P = 0}^{4} (a_{P})^{4} w_{P}, a_{P} \in [2, \dots, 15] \end{matrix}

\begin{matrix} \sum_{P = 0}^{4} w_{P + 10} = 1, w_{10} + w_{11} \leq u_{5}, w_{13} + w_{14} \leq 1 - u_{5}, \\ w_{12} \leq u_{6}, w_{10} + w_{14} \leq 1 - u_{6}, \end{matrix}

\forall w_{j} \in R_{+}, j = 10, \dots, 14

x_{1} = \sum_{P = 0}^{4} a_{P} w_{P}, {\hat{Z}}_{1} = \sum_{P = 0}^{4} (a_{P})^{4} w_{P + 15}, a_{P} \in [0.25, 1.3]

\begin{matrix} \sum_{P = 0}^{4} w_{P + 15} = 1, w_{15} + w_{16} \leq u_{7}, w_{18} + w_{19} \leq 1 - u_{7}, \\ w_{17} \leq u_{8}, w_{15} + w_{19} \leq 1 - u_{8}, \end{matrix}

\forall w_{j} \in R_{+}, j = 15, \dots, 19

This program is solved by LINGO 18.0 (2014), where the tolerable error is specified as 0.001. The obtained mixed integer solution with the comparison of solutions of previous methods is listed in Table 2.

Table 2.

The comparison of results for the shock absorber design problem.

Variable	Arora (1989)¹⁸	Coello (1999)¹⁹	Ray and Saini (2001)²⁰	J-F Tsai (2005)⁹	Proposed method
x ₁	0.39918	0.351661	0.321532	0.3567178	0.3509423
x ₂	0.053396	0.05148	0.050417	0.05168906	0.051396512
x ₃	9.1854	11.632201	13.979915	11.28896	11.00000
O.V.	0.012730273	0.012704783	0.01306	0.01266523	0.011684151

This table indicates the advantage of our method compared with the other solution obtained by the other authors, as Table 2. shows the results of the proposed method is global optimum within the tolerable error of 0.001.

Conclusion

In this study, we applied a convenient non-fractionalization technique and a tight power transformation method (PPT) with a novel modified piecewise linear approximation to convert a non-convex MIFSP problem into a convex MISP problem that yields global optimality. It is essential to be noted the mentioned piecewise linear approximation underestimates convexified functions, and we could obtain an integer solution without using any integer algorithm. Since this proposed method works only for a class of non-convex signomial fractional programing problems with integer variables where the integer variables have no large domains, we can introduce this technique as a pre-solve reduction method to reduce the calculation of problem-solving and reach a better solution. After comparing the results of this study with the previous works (see example in Tsai⁹), we found that using the proposed algorithm is more efficient and tighter to obtain a mixed integer signomial fractional global solution.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

ORCID iD

Mansour Saraj

References

Chang

CT.

On the posynomial fractional programming problems. Eur J Oper Res 2002; 143(1): 42–52.

Shen

Fractional programming for communication systems—part I: power control and beamforming. IEEE Trans Signal Process 2018; 66(10): 2616–2630.

Meister

Oettli

On the capacity of a discrete constant channel. Inf Control 1967; 11: 341–351.

Bradley

Frey

CS.

Fractional programming with homogeneous fractions. Eur J Oper Res 1974; 22(2): 350–357.

Ota

Pati

Ojha

AK.

Geometric programming technique to optimize power distribution system. Opsearch 2019; 56: 282–299.

Dinkelbach

On nonlinear fractional programming. Manage Sci 1967; 13: 492–498.

Mixed integer nonlinear programming Convexification techniques and algorithm development. PhD Thesis, Academic University, 2000.

Chang

CT.

Formulating the mixed integer fractional posynomial programming. Eur J Oper Res 2006; 173: 370–386.

Tsai

J-F.

Global optimization of nonlinear fractional programming problems in engineering design. Eng Optim 2005; 37: 399–409.

10.

Bazikar

Saraj

Solving linear multi-objective geometric programming problems via reference point approach. Sains Malaysia. 2014; 43(8): 1271–1274.

11.

Bazikar

Saraj

. Solving fractional geometric programming problems via relaxation approach. MatLAB J 2018; 1(3): 1–14.

12.

Mishra

Ota

RR.

Signomial geometric programming approach to solve Non-Linear fractional programming problems. Int J Appl Comput Math 2022; 8(1): 38. DOI: 10.1007/s40819-022-01248-x

13.

Shirinnejad

Saraj

Shokrolahi

, et al. Fuzzy approach to solve a global mixed integer multi-objective fractional signomial geometric programming problem. Int J Ind Math 2023; 15(2): 127–136.

14.

Westerlund

Liberti

Maculan

(eds). Some transformation techniques in global optimization. Global optimization from theory to implementation. Boston, MA: Springer, 2007, pp.45–74.

15.

Vielma

Nemhauser

GL.

Modeling disjunctive constraints with a logarithmic number of binary variables and constraints. Math Program 2011; 128(1–2): 49–72.

16.

Lundell

Westerlund

Some transformation techniques with applications in global optimization. J Glob Optim 2009; 43(2-3): 391–405.

17.

Tsai

J-F

Lin

M-H.

An efficient global approach for posynomial geometric programming problems. informs J Comput 2011; 23: 483–492.

18.

Arora

JS.

Introduction to optimum design. New York: Elsevier, 2004.

19.

Coello

Self-adaptive penalties for GA based optimization. In: Proceeding of the congress on evolutionary computation, vol. 1. Washington, DC: IEEE Service Center, 1999, pp.573–580.

20.

Ray

Saini

. Engineering design optimization using a swarm with intelligent information sharing among individuals. Eng Optimiz 2001; 33: 735–748.

Global optimization of mixed integer signomial fractional programing problems

Abstract

Keywords

Introduction

Problem formulation

Convexification strategies

Transformation and underestimation approach

Piecewise linear approximation

Illustrative examples

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References