# A Global Optimization Algorithm for Signomial Geometric Programming Problem

Authors: Xue-Ping Hou; Pei-Ping Shen; Yong-Qiang Chen
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

This paper presents a global optimization algorithm for solving the signomial geometric programming (SGP) problem. In the algorithm, by the straight forward algebraic manipulation of terms and by utilizing a transformation of variables, the initial nonconvex programming problem (SGP) is first converted into an equivalent monotonic optimization problem and then is reduced to a sequence of linear programming problems, based on the linearizing technique. To improve the computational efficiency of the algorithm, two range reduction operations are combined in the branch and bound procedure. The proposed algorithm is convergent to the global minimum of the (SGP) by means of the subsequent solutions of a series of relaxation linear programming problems. And finally, the numerical results are reported to vindicate the feasibility and effectiveness of the proposed method.


---

## Body

## 1. Introduction

The signomial geometric programming (SGP) problem can be formulated as the following nonlinear optimization problem:(1)
(
SGP
)
:
{
min
⁡
Φ
0
(
y
)
s
.
t
.
Φ
m
(
y
)
≤
0
,
m
=
1
,
…
,
M
0
,
y
∈
Ω
0
,
where
(2)
Φ
m
(
y
)
=
∑
t
=
1
T
m
‍
δ
m
t
∏
i
=
1
n
0
‍
y
i
η
m
t
i
,
m
=
0,1
,
…
,
M
0
,
Ω
0
=
{
y
∈
R
+
n
0
∣
0
<
y
i
l
≤
y
i
≤
y
i
u
<
∞
,
i
=
1
,
…
,
n
0
}
.
T
m are positive integers and δ
m
t and η
m
t
i are all arbitrary real constant coefficients and exponents, respectively. In general, the problem (SGP) corresponds to a nonlinear optimization problem with nonconvex objective function and constraint set. As noted by [1, 2], many nonlinear programming problems may be restated as geometric programming with little additional effort by simple techniques such as change of variables or by straightforward algebraic manipulation of terms. Additionally, (SGP) problem has found a wide range of applications in production planning, location, distribution contexts in risk management problems, various chemical process design and engineering design situations, and so on [3–10]. Hence, it is necessary to present good algorithms for solving (SGP).The theory of (SGP) was initially developed over three decades ago by Duffin et al. [11–13]. Subsequently, it had been studied by a number of researchers. In general, local optimization approaches for solving (SGP) problem include three kinds of methods as follows. First, successive approximation by posynomials has received the most popularity [14]. Second, Passy and Wilde [15] developed a weaker type of duality to accommodate this class of nonlinear optimization. Third, general nonlinear programming methods [16]. Though local optimization methods for solving SGP problem are ubiquitous, the global optimization algorithm based on the characteristics of (SGP) problem is scarce. When η
m
t
i in Φ
m
(
y
) is positive integer or rational number, some authors in [8, 17–19] developed the corresponding global solution methods for (SGP). In this case that each η
m
t
i is real, Maranas et al. [20] proposed a global optimization branch and bound algorithm, by using the exponential variable transformation of (SGP) and the convex relaxation. Shen and Zhang [21] also proposed a global optimization algorithm based on the exponential variable transformation of (SGP) and the linear relaxation. Recently, Shen et al. [22] presented a robust algorithm for (SGP) problem by seeking an essential optimal solution. Wang et al. [23] developed a general algorithm for solving (SGP) problem with nonpositive degree of difficulty. Qu et al. [24] proposed a global optimization algorithm using linear relaxation for (SGP) problem.In this paper we present a new global optimization algorithm for (SGP) problem by using several reduction operations and by solving a sequence of linear programming problems over partitioned subsets. The proposed method uses a convenient transformation based on the characteristics of (SGP) problem; thus, the original problem (SGP) is equivalently reformulated as a monotonic optimization problem (P), that is, the objective function is increasing and all the constrained functions can be denoted by the difference of two increasing functions in problem (P). A comparison of this method with other methods reviewed above is given below. First, the proposed linear relaxation is based on the monotonic optimization problem (P), which applies more information of the functions of (SGP). And what is more important is that the proposed reduction operations which are adopted in our global optimization algorithm can cut away a large part of the region in which the global optimal solution of (SGP) does not exist. This solution procedure will be more efficient than the methods in [21, 25, 26]. Second, the problem investigated in this paper generalizes those of [8, 17–19]. Furthermore, our method is more convenient in computation than the convex relaxation [19] because the main work is to solve the linear programs and the zeros of strictly monotonic functions of one variable over the interval [0,1), which can be solved very efficiently by the existing methods, for example, by the simplex method and the bisection search method. Third, numerical results and comparison with other methods are conducted to show the potential advantage of the proposed algorithm.The remainder of this paper is organized as follows. The next section converts the (SGP) problem into a monotonic optimization problem. We discuss the rectangular branching operation, the lower bounding operation, and the reducing operations needed in our algorithm in Section3. Section 4 incorporates this approach into an algorithm for solving (SGP) and shows the convergence property of the algorithm. In Section 5, we report the results of solving some numerical examples with the algorithm. A summary is presented in the last section.


## 2. Equivalent Problem

In order to convert (SGP) problem into an equivalent optimization problem (P), for each m
=
1
,
…
,
M
0, i
=
1
,
…
,
n
0, let us denote
(3)
η
m
i
=
min
⁡
{
η
m
t
i
∣
t
=
1
,
…
,
T
m
}
,
γ
0
t
i
=
η
0
t
i
,
γ
m
t
i
=
η
m
t
i
-
η
m
i
.
By multiplying both sides of each constraint inequality of (SGP) with ∏
i
=
1
n
0
y
i
(
-
η
m
i
) and by applying the exponent transformation
(4)
y
i
=
exp
⁡
(
x
i
)
,
i
=
1
,
…
,
n
0
,
to the formulation (SGP), we can obtain the following equivalent problem:
(5)
(
SGP
1
)
:
{
min
⁡
∑
t
=
1
T
0
‍
δ
0
t
exp
⁡
(
∑
i
=
1
n
0
‍
γ
0
t
i
x
i
)
s
.
t
.
∑
t
=
1
T
m
‍
δ
m
t
exp
⁡
(
∑
i
=
1
n
0
‍
γ
m
t
i
x
i
)
≤
0
,
m
=
1
,
…
,
M
0
,
x
∈
Ω
=
{
x
∈
R
n
0
∣
ln
⁡
y
i
l
=
x
i
l
≤
x
i
≤
x
i
u
LLLLLllllllllll
=
ln
⁡
y
i
u
,
i
=
1
,
…
,
n
0
x
i
l
}
.Next, for convenience, for eachm
=
0,1
,
…
,
M
0, we assume, without loss of generality, that δ
m
t
>
0 for t
=
1
,
…
,
J
m and δ
m
t
<
0 for t
=
J
m
+
1
,
…
,
T
m, and some notation is introduced as follows:
(6)
I
t
+
=
{
i
∣
γ
0
t
i
>
0
,
i
=
1
,
…
,
n
0
}
,
I
t
-
=
{
i
∣
γ
0
t
i
<
0
,
i
=
1
,
…
,
n
0
}
.
Thus, by using I
t
+, I
t
-, let us calculate
(7)
L
t
=
∑
i
∈
I
t
-
‍
γ
0
t
i
ln
⁡
y
i
u
for
each
t
=
1
,
…
,
J
0
,
U
t
=
∑
i
∈
I
t
-
‍
γ
0
t
i
ln
⁡
y
i
l
for
each
t
=
1
,
…
,
J
0
,
l
t
=
∑
i
∈
I
t
+
‍
γ
0
t
i
ln
⁡
y
i
l
for
each
t
=
J
0
+
1
,
…
,
T
0
,
u
t
=
∑
i
∈
I
t
+
γ
0
t
i
ln
⁡
y
i
u
for
each
t
=
J
0
+
1
,
…
,
T
0
.
Then, by introducing some additional variables x
i, i
=
n
0
+
1
,
…
,
n, with n
=
n
0
+
T
0, we can convert the problem (SGP1) into(8)
(
P
)
:
{
min
⁡
F
0
(
x
)
=
∑
t
=
1
J
0
‍
δ
0
t
exp
⁡
(
∑
i
∈
I
t
+
‍
γ
0
t
i
x
i
+
x
n
0
+
t
)
+
∑
t
=
J
0
+
1
T
0
‍
δ
0
t
exp
⁡
(
∑
i
∈
I
t
-
‍
γ
0
t
i
x
i
-
x
n
0
+
t
)
s
.
t
.
∑
t
=
1
J
m
‍
δ
m
t
exp
⁡
(
∑
i
=
1
n
0
‍
γ
m
t
i
x
i
)
+
∑
t
=
J
m
+
1
T
m
‍
δ
m
t
exp
⁡
(
∑
i
=
1
n
0
‍
γ
m
t
i
x
i
)
≤
0
,
m
=
1
,
…
,
M
0
,
x
n
0
+
t
-
∑
i
∈
I
t
-
‍
γ
0
t
i
x
i
≥
0
,
t
=
1
,
…
,
J
0
,
x
n
0
+
t
+
∑
i
∈
I
t
+
‍
γ
0
t
i
x
i
≥
0
,
t
=
J
0
+
1
,
…
,
T
0
,
x
∈
X
0
,where
(9)
X
0
=
{
x
∈
R
n
∣
x
i
l
≤
x
i
≤
x
i
u
,
i
=
1
,
…
,
n
}
=
{
x
∈
R
n
|
x
i
l
≤
x
i
≤
x
i
u
,
i
=
1
,
…
,
n
0
,
L
i
-
n
0
≤
x
i
≤
U
i
-
n
0
,
i
=
n
0

+

1
,
…
,
n
0

+

J
0
,
-
u
i
-
n
0
≤
x
i
≤
-
l
i
-
n
0
,
i
=
n
0

+

J
0

+

1
,
…
,
n
,
}
.
Additionally, for the sake of simplicity, let M
=
M
0
+
T
0; the problem (P) can be rewritten as the following form:
(10)
(
P
)
:
min
⁡
{
F
0
(
x
)
∣
F
m
+
(
x
)
-
F
m
-
(
x
)
≤
0
,
m
=
1
,
…
,
M
,
x
∈
X
0
}
,
where
(11)
F
m
+
(
x
)
=
{
∑
t
=
1
J
m
‍
δ
m
t
exp
⁡
(
∑
i
=
1
n
0
‍
γ
m
t
i
x
i
)
,
m
=
1
,
…
,
M
0
,
0
,
m
=
M
0
+
1
,
…
,
M
,
(12)
F
m
-
(
x
)
=
{
-
∑
t
=
J
m
+
1
T
m
‍
δ
m
t
exp
⁡
(
∑
i
=
1
n
0
‍
γ
m
t
i
x
i
)
,
m
=
1
,
…
,
M
0
,
x
m
+
n
0
-
M
0
-
∑
i
∈
I
m
-
M
0
-
‍
γ
0
(
m
-
M
0
)
i
x
i
,
m
=

M
0

+

1
,
…
,

M
0

+
J
0
,
x
m
+
n
0
-
M
0
+
∑
i
∈
I
m
-
M
0
+
‍
γ
0
(
m
-
M
0
)
i
x
i
,
m
=

M
0

+

J
0

+

1
,
…
,
M
.Note that each functionF
0
(
x
)
,
F
m
+
(
x
)
,
F
m
-
(
x
) of problem (P) is increasing (i.e., a function f
:
R
n
→
R is said to be increasing if f
(
x
)
≤
f
(
y
) for all x
,
y
∈
R
n satisfying x
i
≤
y
i, i
=
1
,
…
,
n). Thus problem (P) is a monotonic optimization problem, and the key equivalent result for problems (SGP) and (P) is given by Theorem 1.Theorem 1.
y
*
∈
R
n
0 is a global optimal solution for problem (SGP) if and only if x
*
∈
R
n is a global optimal solution for problem (P), where
(13)
x
i
*
=
{
ln
⁡
y
i
*
,
i
=
1
,
…
,
n
0
,
∑
i
∈
I
t
-
‍
γ
0
t
i
ln
⁡
y
i
*
,
i
=
n
0
+
1
,
…
,
n
0
+
J
0
,
-
∑
i
∈
I
t
+
‍
γ
0
t
i
ln
⁡
y
i
*
,
i
=
n
0
+
J
0
+
1
,
…
,
n
.Proof.
The proof of this theorem follows easily from the definitions of problems (SGP) and (P); therefore, it is omitted here.From Theorem1, notice that, in order to solve problem (SGP), we may solve problem (P) instead. In addition, it is easy to see that the global optimal values of problems (SGP) and (P) are equal. Based on the above discussion, here, from now on we assume that the original problem (SGP) has been converted into the problem (P); then a general approach will be considered for solving problem (P).


## 3. Key Algorithm Processes

To globally solve the problem (P), a branch-reduce-bound (BRB) algorithm will be proposed. This algorithm proceeds according to the standard branch and bound scheme with three key processes: branching, reducing, and bounding.The branching process consists in a successive rectangular partition of the initial boxX
0
=
[
x
l
,
x
u
] following in an exhaustive subdivision rule, that is, such that any infinite nested sequence of partition sets generated through the algorithm shrinks to a singleton. A commonly used exhaustive subdivision rule is the standard bisection.The reducing process consists in applying reduction operations to reduce the size of the current partition setX
=
[
a
,
b
]
⊂
X
0
=
[
x
l
,
x
u
]. The process aims at tightening the box containing the feasible portion currently still of interest.The bounding process consists in using the linearization method to give a better lower bound.Next, we begin to establish the approaches processes.


### 3.1. Lower Bound

At a given stage of the BRB algorithm for (P), let X
=
[
a
,
b
]
⊂
X
0 be a rectangle during the partitioning procedure and still of interest; we intend to compute a lower bound LB
(
X
) of the optimal value of (P) over X. Restrict the problem (P) to X:
(14)
P
(
X
)
:
min
⁡
{
F
0
(
x
)
∣
F
m
(
x
)
≤
0
,
m
=
1
,
…
,
M
,
x
∈
X
}
.
Denote the optimal objective function value of problem P
(
X
) by V
[
P
(
X
)
].SinceF
0
(
x
) is increasing, an obvious bound is LB
(
X
)
=
F
0
(
a
); although very simple, this bound suffices to ensure convergence of the algorithm. However, the following procedure may give a better bound.Our main method for computing a lower bound ofV
[
P
(
X
)
] over X is to solve the relaxation linear programming of P
(
X
). The linear relaxation of the problem P
(
X
) can be realized by underestimating every function F
0
(
x
) and F
m
+
(
x
) and by overestimating every function F
m
-
(
x
), for each m
=
1
,
…
,
M
0. All the details for generating the linear relaxation will be given in the following.Denote(15)
X
0
t
=
{
∑
i
∈
I
t
+
‍
γ
0
t
i
x
i
+
x
n
0
+
t
,
t
=
1
,
…
,
J
0
,
∑
i
∈
I
t
-
‍
γ
0
t
i
x
i
-
x
n
0
+
t
,
t
=
J
0
+
1
,
…
,
T
0
,
X
0
t
l
=
{
∑
i
∈
I
t
+
‍
γ
0
t
i
a
i
+
a
n
0
+
t
,
t
=
1
,
…
,
J
0
,
∑
i
∈
I
t
-
‍
γ
0
t
i
b
i
-
b
n
0
+
t
,
t
=
J
0
+
1
,
…
,
T
0
,
X
0
t
u
=
{
∑
i
∈
I
t
+
‍
γ
0
t
i
b
i
+
b
n
0
+
t
,
t
=
1
,
…
,
J
0
,
∑
i
∈
I
t
-
‍
γ
0
t
i
a
i
-
a
n
0
+
t
,
t
=
J
0
+
1
,
…
,
T
0
,
X
m
t
=
∑
i
=
1
n
0
‍
γ
m
t
i
x
i
,
t
=
1
,
…
,
T
m
,
X
m
t
l
=
∑
i
=
1
n
0
‍
γ
m
t
i
a
i
,
t
=
1
,
…
,
T
m
,
X
m
t
u
=
∑
i
=
1
n
0
‍
γ
m
t
i
b
i
,
t
=
1
,
…
,
T
m
,
where m
=
1
,
…
,
M
0. In addition, let
(16)
A
m
t
=
exp
⁡
(
X
m
t
u
)
-
exp
⁡
(
X
m
t
l
)
X
m
t
u
-
X
m
t
l
,
θ
m
t
(
x
)
=
exp
⁡
(
X
m
t
)
,
θ
¯
m
t
(
x
)
=
A
m
t
(
X
m
t
-
X
m
t
l
)
+
exp
⁡
(
X
m
t
l
)
,
θ
_
m
t
(
x
)
=
A
m
t
(
X
m
t
-
ln
⁡
A
m
t
+
1
)
,
where m
=
0,1
,
…
,
M
0, t
=
1
,
…
,
T
m.Theorem 2.
Consider the functionsθ
m
t
(
x
), θ
_
m
t
(
x
), and θ
¯
m
t
(
x
), for any x
∈
X, where m
=
0
,
…
,
M
0 and t
=
1
,
…
,
T
m. Then the following two statements are valid.(i)
The functionθ
¯
m
t
(
x
) is the concave envelope of the function θ
m
t
(
x
) over X, and the function θ
_
m
t
(
x
) is a supporting hyperplane of θ
m
t
(
x
), which is parallel with θ
¯
m
t
(
x
). Moreover, the functions θ
m
t
(
x
), θ
_
m
t
(
x
), and θ
¯
m
t
(
x
) satisfy
(17)
θ
_
m
t
(
x
)
≤
θ
m
t
(
x
)
≤
θ
¯
m
t
(
x
)
,
∀
x
∈
X
.
(ii)
The differencesΔ
m
t
1
(
x
)
=
θ
¯
m
t
(
x
)
-
θ
m
t
(
x
) and Δ
m
t
2
(
x
)
=
θ
m
t
(
x
)
-
θ
_
m
t
(
x
) satisfy max
⁡
x
∈
X
Δ
m
t
1
(
x
)
=
max
⁡
x
∈
X
Δ
m
t
2
(
x
)
=
exp
⁡
(
X
m
t
l
)
(
1
-
Z
m
t
+
Z
m
t
ln
⁡
Z
m
t
)
→
0
a
s
ω
m
t
→
0, where
(18)
ω
m
t
=
X
m
t
u
-
X
m
t
l
,
Z
m
t
=
exp
⁡
(
ω
m
t
)
-
1
ω
m
t
.Proof.
The proof is similar to Theorem 1 in [21]; therefore, it is omitted here.Remark 3.
From Theorem2, we can follow that the functions θ
_
m
t
(
x
) and θ
¯
m
t
(
x
) enough approximate the function θ
m
t
(
x
) as ω
m
t
→
0, respectively.From Theorem2, it is obvious that for all x
∈
X we have
(19)
F
0
(
x
)
≥
L
F
0
(
x
)
=
∑
t
=
1
J
0
‍
δ
0
t
θ
_
0
t
(
x
)
+
∑
t
=
J
0
+
1
T
0
‍
δ
0
t
θ
¯
0
t
(
x
)
,
F
m
+
(
x
)
≥
L
F
m
+
(
x
)
=
∑
t
=
1
J
m
‍
δ
m
t
θ
_
m
t
(
x
)
,
F
m
-
(
x
)
≤
U
F
m
-
(
x
)
=
-
∑
t
=
J
m
+
1
T
m
‍
δ
m
t
θ
¯
m
t
(
x
)
,
where m
=
1
,
…
,
M
0.Consequently, we obtain the following linear programmingRLP
(
X
) as a linear relaxation of P
(
X
) over the partition set X:
(20)
RLP
(
X
)
:
{
min
⁡
L
F
0
(
x
)
s
.
t
.
L
F
m
+
(
x
)
-
U
F
m
-
(
x
)
≤
0
,
m
=
1
,
…
,
M
0
,
F
m
+
(
x
)
-
F
m
-
(
x
)
≤
0
,
m
=
M
0
+
1
,
…
,
M
,
x
∈
X
.An important property ofRLP
(
X
) is that its optimal value V
[
RLP
(
X
)
] satisfies
(21)
V
[
RLP
(
X
)
]
≤
V
[
P
(
X
)
]
,
and thus, from (21), the optimal value V
[
RLP
(
X
)
] of RLP
(
X
) provides a valid lower bound for the optimal value V
[
P
(
X
)
] of P
(
X
) over X.Based on the above discussion, for any rectangleX, in order to obtain a lower bound LB
(
X
) of the optimal value V
[
P
(
X
)
] of the problem P
(
X
), we may compute LB
(
X
) such that
(22)
LB
(
X
)
=
max
⁡
{
V
[
RLP
(
X
)
]
,
F
0
(
a
)
}
.
Clearly, LB
(
X
) defined in (22) satisfies
(23)
F
0
(
a
)
≤
LB
(
X
)
≤
V
[
P
(
X
)
]
and is consistent. It can provide a valid lower bound and guarantee convergence.


### 3.2. Reduction Operations

Clearly, the smaller the rectangleX is, the tighter the lower bound LB
(
X
) of P
(
X
) will be, and therefore the closer the feasible solution of (
P
) will be to the optimal solution of (
P
). To show this, the next results give two reduction operations (i.e., reduction rules A and B) to reduce the size of this partitioned rectangle without losing any feasible solution currently still of interest.


#### 3.2.1. Reduction Rule A

Rule A is based on the monotonic structure of the problem(
P
). At a given stage of the BRB algorithm for (
P
), for a rectangle X
=
[
a
,
b
] generated during the partitioning procedure and still of interest, let UB be the object function value of the best so far feasible solution to problem (
P
). Given an ε
>
0, we want to find a feasible solution x
∈
X of (
P
) such that F
0
(
x
)
≤
UB
-
ε or else establish that no such x exists. So the search for such x can then be restricted to the set H
∩
[
a
,
b
], where
(24)
H
:
=
{
x
∣
F
0
(
x
)
≤
UB
-
ε
,
F
m
(
x
)
≤
0
,
m
=
1
,
…
,
M
}
.The reduction rule aims at replacing the rectangle[
a
,
b
] with a smaller rectangle [
a
′
,
b
′
]
⊂
[
a
,
b
] without losing any point x
∈
H
∩
[
a
,
b
], that is, such that H
∩
[
a
′
,
b
′
]
=
H
∩
[
a
,
b
]. The rectangle [
a
′
,
b
′
] satisfying this condition is denoted by re
d
ν
[
a
,
b
] with
(25)
ν
=
UB
-
ε
.
To illustrate how re
d
ν
[
a
,
b
]
=
[
a
′
,
b
′
] is deduced by this rule, we first define the following functions.Definition 4.
Given two boxes[
a
,
b
] and [
a
′
,
b
′
] with [
a
′
,
b
′
]
⊆
[
a
,
b
], for i
=
1
,
…
,
n, m
=
1
,
…
,
M, the functions φ
m
i
(
α
), ψ
m
i
(
α
), and ψ
0
i
(
α
)
:
[
0,1
]
→
R are defined by
(26)
φ
m
i
(
α
)
=
F
m
-
(
b
-
α
(
b
i
-
a
i
)
e
i
)
-
F
m
+
(
a
)
,
ψ
m
i
(
α
)
=
F
m
+
(
a
′
+
α
(
b
i
-
a
i
′
)
e
i
)
-
F
m
-
(
b
)
,
ψ
0
i
(
α
)
=
F
0
(
a
′
+
α
(
b
i
-
a
i
′
)
e
i
)
-
ν
,
where e
i denotes the ith unit vector of R
n, that is, a vector such that e
i
i
=
1
,
e
j
i
=
0, ∀
j
≠
i, and the functions F
0
(
x
), F
m
+
(
x
), and F
m
-
(
x
) are given in problem (P), respectively.
Clearly, the functionsφ
m
i
(
α
), ψ
m
i
(
α
), and ψ
0
i
(
α
) are either constant or strictly monotonic over the interval [0,1) from the properties of F
m
-
(
x
), F
m
+
(
x
), and F
0
(
x
). By using these functions, re
d
ν
[
a
,
b
] can be given as follows.Theorem 5.
(
i
) If F
0
(
a
)
>
ν or F
m
+
(
a
)
-
F
m
-
(
b
)
>
0 for some m
=
1
,
…
,
M, then r
e
d
ν
[
a
,
b
]
=
[
a
′
,
b
′
]
=
∅.
(
i
i
) If F
0
(
a
)
≤
ν and F
m
+
(
a
)
-
F
m
-
(
b
)
≤
0 for each m
=
1
,
…
,
M, then r
e
d
ν
[
a
,
b
]
=
[
a
′
,
b
′
], where
(27)
a
′
=
b
-
∑
i
=
1
n
‍
min
⁡
m
=
1
,
…
,
M
{
α
m
i
}
(
b
i
-
a
i
)
e
i
,
b
′
=
a
′
+
∑
i
=
1
n
‍
min
⁡
m
=
0,1
,
…
,
M
{
β
m
i
}
(
b
i
-
a
i
′
)
e
i
are given by
(28)
α
m
i
=
{
1
,
i
f
φ
m
i
(
1
)
≥
0
α
w
i
t
h
φ
m
i
(
α
)
=
0
,
o
t
h
e
r
w
i
s
e
,
β
m
i
=
{
1
,
i
f
ψ
m
i
(
1
)
≤
0
α
w
i
t
h
ψ
m
i
(
α
)
=
0
,
o
t
h
e
r
w
i
s
e
.Proof.
(i) By the increasing property ofF
0
(
x
), F
m
+
(
x
), and F
m
-
(
x
), if F
0
(
a
)
>
ν, then F
0
(
x
)
≥
F
0
(
a
)
>
ν for every x
∈
[
a
,
b
]. If there exists m
∈
{
1
,
…
,
M
} such that F
m
+
(
a
)
-
F
m
-
(
b
)
>
0, then F
m
(
x
)
=
F
m
+
(
x
)
-
F
m
-
(
x
)
≥
F
m
+
(
a
)
-
F
m
-
(
b
)
>
0 for every x
∈
[
a
,
b
]. In both cases, H
∩
[
a
,
b
]
=
∅.
(ii) Given any pointx
∈
[
a
,
b
] satisfying
(29)
F
0
(
x
)
≤
ν
,
F
m
+
(
x
)
-
F
m
-
(
x
)
≤
0
,
m
=
1
,
…
,
M
,
we will show that x
∈
[
a
′
,
b
′
]. Let
(30)
α
m
′
i
=
min
⁡
{
α
m
i
∣
m
=
1
,
…
,
M
}
,
β
m
′
′
i
=
min
⁡
{
β
m
i
∣
m
=
0,1
,
…
,
M
}
.
Firstly, we will show thatx
≥
a
′. If x
≱
a
′, then there exists index i such that
(31)
x
i
<
a
i
′
=
b
i
-
α
m
′
i
(
b
i
-
a
i
)
,
i
.
e
.
,
x
i
=
b
i
-
α
(
b
i
-
a
i
)
with
α
m
′
i
<
α
≤
1
.
We consider the following two cases.
Case  1. If α
m
′
i
=
1, then from (31) we have x
i
<
a
i
′
=
b
i
-
α
m
′
i
(
b
i
-
a
i
)
=
a
i, conflicting with x
∈
[
a
,
b
]; that is, x
i
≥
a
i.
Case  2. If 0
≤
α
m
′
i
<
1, the function φ
m
′
i
(
α
) must be strictly decreasing in single variable α over the interval [0,1). If the function φ
m
′
i
(
α
) is not strictly decreasing in single variable α, we get φ
m
′
i
(
α
) must be a constant over the interval [0,1). In this case, we have
(32)
φ
m
′
i
(
1
)
=
φ
m
′
i
(
0
)
=
F
m
′
-
(
b
)
-
F
m
′
+
(
a
)
≥
0
.
It follows from the definition of α
m
′
i that α
m
′
i
=
1, contradicting with 0
≤
α
m
′
i
<
1.
Since the functionφ
m
′
i
(
α
) is strictly decreasing, it follows from (31) and the definition of α
m
′
i that
(33)
F
m
′
-
(
b
-
(
b
i
-
x
i
)
e
i
)
-
F
m
′
+
(
a
)
=
F
m
′
-
(
b
-
α
(
b
i
-
a
i
)
e
i
)
-
F
m
′
+
(
a
)
=
φ
m
′
i
(
α
)
<
φ
m
′
i
(
α
m
′
i
)
=
0
;
hence,
(34)
F
m
′
-
(
b
-
(
b
i
-
x
i
)
e
i
)
<
F
m
′
+
(
a
)
.
In addition, since F
m
′
-
(
x
) is an increasing function in n-dimension variable x and x
≤
b
-
(
b
i
-
x
i
)
e
i, we have
(35)
F
m
′
-
(
x
)
≤
F
m
′
-
(
b
-
(
b
i
-
x
i
)
e
i
)
<
F
m
′
+
(
a
)
,
conflicting with F
m
′
-
(
x
)
≥
F
m
′
+
(
x
)
≥
F
m
′
+
(
a
).
Based on the above discussion, we havex
≥
a
′; that is, x
∈
[
a
′
,
b
] in either case.
Secondly, we also can show fromx
∈
[
a
′
,
b
] that
(36)
x
≤
b
′
,
i
.
e
.
,
x
∈
[
a
′
,
b
′
]
.
Supposed that x
≰
b
′, then there exists some i such that
(37)
x
i
>
b
i
′
=
a
i
′
+
β
m
′′
i
(
b
i
-
a
i
′
)
;
that is, there exists α such that
(38)
x
i
=
a
i
′
+
α
(
b
i
-
a
i
′
)
,
β
m
′′
i
<
α
≤
1
.
By the definition of β
m
′′
i, there are the following two cases to consider.
Case  1. If β
m
′′
i
=
1, then from (38) we have x
i
>
b
i
′
=
a
i
′
+
(
b
i
-
a
i
′
)
=
b
i, conflicting with x
∈
[
a
′
,
b
]; that is, x
i
≤
b
i.
Case  2. If 0
≤
β
m
′′
i
<
1, the function ψ
m
′′
i
(
α
) is strictly increasing in single variable α. If the function ψ
m
′′
i
(
α
) is not strictly increasing in single variable α, we get ψ
m
′′
i
(
α
) must be a constant over the interval [0,1). In this case, we have
(39)
ψ
0
i
(
1
)
=
ψ
0
i
(
0
)
=
F
0
(
a
′
)
-
ν
≤
0
,
or
(40)
ψ
m
′′
i
(
1
)
=
ψ
m
′′
i
(
0
)
=
F
m
′
′
+
(
a
′
)
-
F
m
′′
-
(
b
)
≤
0
.
It follows from the definition of β
m
′′
i that β
m
′′
i
=
1, which is a contradiction with 0
≤
β
m
′′
i
<
1.
Since the functionψ
m
′′
i
(
α
) is strictly increasing, from (31) and the definition of β
m
′′
i, it implies that
(41)
F
0
(
a
′
+
α
(
b
i
-
a
i
′
)
e
i
)
-
ν
=
ψ
0
i
(
α
)
>
ψ
0
i
(
β
0
i
)
=
0
,
or
(42)
F
m
′′
+
(
a
′
+
α
(
b
i
-
a
i
′
)
e
i
)
-
F
m
′′
-
(
b
)
=
ψ
m
′′
i
(
α
)
>
ψ
m
′′
i
(
β
m
′′
i
)
=
0
.
Assume that (41) holds; we can derive from (38) that
(43)
F
0
(
a
′
+
(
x
i
-
a
i
′
)
e
i
)
=
F
0
(
a
′
+
α
(
b
i
-
a
i
′
)
e
i
)
>
ν
.
It follows from x
≥
a
′
+
(
x
i
-
a
i
′
)
e
i and F
0
(
x
) increasing that
(44)
F
0
(
x
)
≥
F
0
(
a
′
+
(
x
i
-
a
i
′
)
e
i
)
>
ν
,
conflicting with F
0
(
x
)
≤
ν.
If (42) holds, we obtain from (38) that
(45)
F
m
′′
+
(
a
′
+
(
x
i
-
a
i
′
)
e
i
)
=
F
m
′′
+
(
a
′
+
α
(
b
i
-
a
i
′
)
e
i
)
>
F
m
′′
-
(
b
)
;
since x
≥
a
′
+
(
x
i
-
a
i
′
)
e
i and F
m
′′
+
(
x
) is increasing, we have
(46)
F
m
′′
+
(
x
)
≥
F
m
′′
+
(
a
′
+
(
x
i
-
a
i
′
)
e
i
)
>
F
m
′′
-
(
b
)
.
It is a contradiction with F
m
′′
+
(
x
)
≤
F
m
′′
-
(
x
)
≤
F
m
′′
-
(
b
).
From the above results, we must havex
≤
b
′
;
that
is
,
x
∈
[
a
′
,
b
′
] in both cases, and this ends the proof.Remark 6.
Clearly, for anyi
=
1
,
…
,
n, α
m
i
(
m
=
1
,
…
,
M
) and β
m
i
(
m
=
0,1
,
…
,
M
) defined in Theorem 5 must exist and be unique, since the functions F
0
(
x
), F
m
+
(
x
), and F
m
-
(
x
) are all continuous and increasing.


#### 3.2.2. Reduction Rule B

For anyx
∈
X
=
(
X
i
)
n
×
1 with X
i
=
[
a
i
,
b
i
]
(
i
=
1
,
…
,
n
), without loss of generality, we assume the above relaxation linear problem RLP
(
X
) can be rewritten as
(47)
RLP
(
X
)
:
{
min
⁡
∑
i
=
1
n
‍
λ
0
i
x
i
+
t
0
s
.
t
.
∑
i
=
1
n
‍
λ
j
i
x
i
+
t
j
≤
0
,
j
=
1
,
…
,
M
,
x
∈
X
⊆
X
0
.Let(48)
R
L
j
=
∑
i
=
1
n
‍
min
⁡
{
λ
j
i
a
i
,
λ
j
i
b
i
}
+
t
j
,
j
=
0,1
,
…
,
M
,
(49)
ρ
i
=
UB
-
R
L
0
+
min
⁡
{
λ
0
i
a
i
,
λ
0
i
b
i
}
λ
0
i
with
λ
0
i
≠
0
,
(50)
τ
j
i
=
-
R
L
j
+
min
⁡
{
λ
j
i
a
i
,
λ
j
i
b
i
}
λ
j
i
with
λ
j
i
≠
0
,
where j
=
1
,
…
,
M, i
=
1
,
…
,
n.Theorem 7.
For any rectangleX
=
(
X
i
)
n
×
1
⊆
X
0, if R
L
0
>
U
B, then there exists no optimal solution of R
L
P
(
X
0
) over X; otherwise, consider the following two cases: if there exists some h
∈
{
1
,
…
,
n
} satisfying λ
0
h
>
0 and ρ
h
<
b
h, then there is no optimal solution of R
L
P
(
X
0
) over X
a; conversely, if λ
0
h
<
0 and ρ
h
>
a
h for some h
∈
{
1
,
…
,
n
}, then there does not exist optimal solution of RLP
(
X
0
) over X
b, where
(51)
X
a
=
(
X
a
i
)
n
×
1
⊆
X
0
w
i
t
h
X
a
i
=
{
X
i
,
i
f
i
≠
h
,
(
ρ
h
,
b
h
]
⋂
‍
X
h
,
i
f
i
=
h
,
X
b
=
(
X
b
i
)
n
×
1
⊆
X
0
w
i
t
h
X
b
i
=
{
X
i
,
i
f
i
≠
h
,
[
a
h
,
ρ
h
)
⋂
‍
X
h
,
i
f
i
=
h
.Theorem 8.
For any rectangleX
=
(
X
i
)
n
×
1
⊆
X
0, if R
L
j
(
x
)
>
0 for some j
∈
{
1
,
…
,
M
}, then there exists no feasible solution of problem R
L
P
(
X
0
) over X, otherwise, consider the following two cases: if there exists some index h
∈
{
1
,
…
,
n
} and j
∈
{
1
,
…
,
M
} satisfying λ
j
h
>
0 and τ
j
h
<
b
h, then there is no feasible solution of the problem R
L
P
(
X
0
) over X
c; conversely, if λ
j
h
<
0 and τ
j
h
>
a
h for some j
∈
{
1
,
…
,
M
} and h
∈
{
1
,
…
,
n
}, then there exists no feasible solution of the problem R
L
P
(
X
0
) over X
d, where
(52)
X
c
=
(
X
c
i
)
n
×
1
⊆
X
0
w
i
t
h
X
c
i
=
{
X
i
,
i
f
i
≠
h
,
(
τ
j
h
,
b
h
]
⋂
‍
X
h
,
i
f
i
=
h
,
X
d
=
(
X
d
i
)
n
×
1
⊆
X
0
w
i
t
h
X
d
i
=
{
X
i
,
i
f
i
≠
h
,
[
a
h
,
τ
j
h
)
⋂
‍
X
h
,
i
f
i
=
h
.Proof.
The proof of the Theorems7 and 8 is similar to Theorems 2 and 3 in [27], respectively; therefore, it is omitted here.By Theorems7 and 8, we can give a new reduction rule B to reject some regions in which the globally optimal solution of RLP
(
X
0
) does not exist. The computation procedure of this rule is summarized as follows.Step 1.
ComputeR
L
0 in (48). If R
L
0
>
UB, let X
=
∅; otherwise, compute ρ
i
(
i
=
1
,
…
,
n
) in (49). If λ
0
h
>
0 and ρ
h
<
b
h for some h
∈
{
1
,
…
,
n
}, then let b
h
=
ρ
h and X
=
(
X
i
)
n
×
1 with X
i
=
[
a
i
,
b
i
]
(
i
=
1
,
…
,
n
). If λ
0
h
<
0 and ρ
h
>
a
h for some h
∈
{
1
,
…
,
n
}, then let a
h
=
ρ
h and X
=
(
X
i
)
n
×
1 with X
i
=
[
a
i
,
b
i
]
(
i
=
1
,
…
,
n
).Step 2.
For anyj
=
1
,
…
,
M, compute R
L
j in (48). If R
L
j
>
0 for some j
∈
{
1
,
…
,
M
}, then let X
=
∅; otherwise, compute τ
j
i in (50) (
j
=
1
,
…
,
M
,
i
=
1
,
…
,
n
). If λ
j
h
>
0 and τ
j
h
<
b
h for some j
∈
{
1
,
…
,
M
} and h
∈
{
1
,
…
,
n
}, then let b
h
=
τ
j
h and X
=
(
X
i
)
n
×
1 with X
i
=
[
a
i
,
b
i
]
(
i
=
1
,
…
,
n
). If λ
j
h
<
0 and τ
j
h
>
a
h for some j
∈
{
1
,
…
,
M
} and h
∈
{
1
,
…
,
n
}, then let a
h
=
τ
j
h and X
=
(
X
i
)
n
×
1 with X
i
=
[
a
i
,
b
i
]
(
i
=
1
,
…
,
n
).Rule B provides a possibility to cut away all or a large part of the rectangleX which is currently investigated by the algorithm procedure.


## 3.1. Lower Bound

At a given stage of the BRB algorithm for (P), let X
=
[
a
,
b
]
⊂
X
0 be a rectangle during the partitioning procedure and still of interest; we intend to compute a lower bound LB
(
X
) of the optimal value of (P) over X. Restrict the problem (P) to X:
(14)
P
(
X
)
:
min
⁡
{
F
0
(
x
)
∣
F
m
(
x
)
≤
0
,
m
=
1
,
…
,
M
,
x
∈
X
}
.
Denote the optimal objective function value of problem P
(
X
) by V
[
P
(
X
)
].SinceF
0
(
x
) is increasing, an obvious bound is LB
(
X
)
=
F
0
(
a
); although very simple, this bound suffices to ensure convergence of the algorithm. However, the following procedure may give a better bound.Our main method for computing a lower bound ofV
[
P
(
X
)
] over X is to solve the relaxation linear programming of P
(
X
). The linear relaxation of the problem P
(
X
) can be realized by underestimating every function F
0
(
x
) and F
m
+
(
x
) and by overestimating every function F
m
-
(
x
), for each m
=
1
,
…
,
M
0. All the details for generating the linear relaxation will be given in the following.Denote(15)
X
0
t
=
{
∑
i
∈
I
t
+
‍
γ
0
t
i
x
i
+
x
n
0
+
t
,
t
=
1
,
…
,
J
0
,
∑
i
∈
I
t
-
‍
γ
0
t
i
x
i
-
x
n
0
+
t
,
t
=
J
0
+
1
,
…
,
T
0
,
X
0
t
l
=
{
∑
i
∈
I
t
+
‍
γ
0
t
i
a
i
+
a
n
0
+
t
,
t
=
1
,
…
,
J
0
,
∑
i
∈
I
t
-
‍
γ
0
t
i
b
i
-
b
n
0
+
t
,
t
=
J
0
+
1
,
…
,
T
0
,
X
0
t
u
=
{
∑
i
∈
I
t
+
‍
γ
0
t
i
b
i
+
b
n
0
+
t
,
t
=
1
,
…
,
J
0
,
∑
i
∈
I
t
-
‍
γ
0
t
i
a
i
-
a
n
0
+
t
,
t
=
J
0
+
1
,
…
,
T
0
,
X
m
t
=
∑
i
=
1
n
0
‍
γ
m
t
i
x
i
,
t
=
1
,
…
,
T
m
,
X
m
t
l
=
∑
i
=
1
n
0
‍
γ
m
t
i
a
i
,
t
=
1
,
…
,
T
m
,
X
m
t
u
=
∑
i
=
1
n
0
‍
γ
m
t
i
b
i
,
t
=
1
,
…
,
T
m
,
where m
=
1
,
…
,
M
0. In addition, let
(16)
A
m
t
=
exp
⁡
(
X
m
t
u
)
-
exp
⁡
(
X
m
t
l
)
X
m
t
u
-
X
m
t
l
,
θ
m
t
(
x
)
=
exp
⁡
(
X
m
t
)
,
θ
¯
m
t
(
x
)
=
A
m
t
(
X
m
t
-
X
m
t
l
)
+
exp
⁡
(
X
m
t
l
)
,
θ
_
m
t
(
x
)
=
A
m
t
(
X
m
t
-
ln
⁡
A
m
t
+
1
)
,
where m
=
0,1
,
…
,
M
0, t
=
1
,
…
,
T
m.Theorem 2.
Consider the functionsθ
m
t
(
x
), θ
_
m
t
(
x
), and θ
¯
m
t
(
x
), for any x
∈
X, where m
=
0
,
…
,
M
0 and t
=
1
,
…
,
T
m. Then the following two statements are valid.(i)
The functionθ
¯
m
t
(
x
) is the concave envelope of the function θ
m
t
(
x
) over X, and the function θ
_
m
t
(
x
) is a supporting hyperplane of θ
m
t
(
x
), which is parallel with θ
¯
m
t
(
x
). Moreover, the functions θ
m
t
(
x
), θ
_
m
t
(
x
), and θ
¯
m
t
(
x
) satisfy
(17)
θ
_
m
t
(
x
)
≤
θ
m
t
(
x
)
≤
θ
¯
m
t
(
x
)
,
∀
x
∈
X
.
(ii)
The differencesΔ
m
t
1
(
x
)
=
θ
¯
m
t
(
x
)
-
θ
m
t
(
x
) and Δ
m
t
2
(
x
)
=
θ
m
t
(
x
)
-
θ
_
m
t
(
x
) satisfy max
⁡
x
∈
X
Δ
m
t
1
(
x
)
=
max
⁡
x
∈
X
Δ
m
t
2
(
x
)
=
exp
⁡
(
X
m
t
l
)
(
1
-
Z
m
t
+
Z
m
t
ln
⁡
Z
m
t
)
→
0
a
s
ω
m
t
→
0, where
(18)
ω
m
t
=
X
m
t
u
-
X
m
t
l
,
Z
m
t
=
exp
⁡
(
ω
m
t
)
-
1
ω
m
t
.Proof.
The proof is similar to Theorem 1 in [21]; therefore, it is omitted here.Remark 3.
From Theorem2, we can follow that the functions θ
_
m
t
(
x
) and θ
¯
m
t
(
x
) enough approximate the function θ
m
t
(
x
) as ω
m
t
→
0, respectively.From Theorem2, it is obvious that for all x
∈
X we have
(19)
F
0
(
x
)
≥
L
F
0
(
x
)
=
∑
t
=
1
J
0
‍
δ
0
t
θ
_
0
t
(
x
)
+
∑
t
=
J
0
+
1
T
0
‍
δ
0
t
θ
¯
0
t
(
x
)
,
F
m
+
(
x
)
≥
L
F
m
+
(
x
)
=
∑
t
=
1
J
m
‍
δ
m
t
θ
_
m
t
(
x
)
,
F
m
-
(
x
)
≤
U
F
m
-
(
x
)
=
-
∑
t
=
J
m
+
1
T
m
‍
δ
m
t
θ
¯
m
t
(
x
)
,
where m
=
1
,
…
,
M
0.Consequently, we obtain the following linear programmingRLP
(
X
) as a linear relaxation of P
(
X
) over the partition set X:
(20)
RLP
(
X
)
:
{
min
⁡
L
F
0
(
x
)
s
.
t
.
L
F
m
+
(
x
)
-
U
F
m
-
(
x
)
≤
0
,
m
=
1
,
…
,
M
0
,
F
m
+
(
x
)
-
F
m
-
(
x
)
≤
0
,
m
=
M
0
+
1
,
…
,
M
,
x
∈
X
.An important property ofRLP
(
X
) is that its optimal value V
[
RLP
(
X
)
] satisfies
(21)
V
[
RLP
(
X
)
]
≤
V
[
P
(
X
)
]
,
and thus, from (21), the optimal value V
[
RLP
(
X
)
] of RLP
(
X
) provides a valid lower bound for the optimal value V
[
P
(
X
)
] of P
(
X
) over X.Based on the above discussion, for any rectangleX, in order to obtain a lower bound LB
(
X
) of the optimal value V
[
P
(
X
)
] of the problem P
(
X
), we may compute LB
(
X
) such that
(22)
LB
(
X
)
=
max
⁡
{
V
[
RLP
(
X
)
]
,
F
0
(
a
)
}
.
Clearly, LB
(
X
) defined in (22) satisfies
(23)
F
0
(
a
)
≤
LB
(
X
)
≤
V
[
P
(
X
)
]
and is consistent. It can provide a valid lower bound and guarantee convergence.


## 3.2. Reduction Operations

Clearly, the smaller the rectangleX is, the tighter the lower bound LB
(
X
) of P
(
X
) will be, and therefore the closer the feasible solution of (
P
) will be to the optimal solution of (
P
). To show this, the next results give two reduction operations (i.e., reduction rules A and B) to reduce the size of this partitioned rectangle without losing any feasible solution currently still of interest.


### 3.2.1. Reduction Rule A

Rule A is based on the monotonic structure of the problem(
P
). At a given stage of the BRB algorithm for (
P
), for a rectangle X
=
[
a
,
b
] generated during the partitioning procedure and still of interest, let UB be the object function value of the best so far feasible solution to problem (
P
). Given an ε
>
0, we want to find a feasible solution x
∈
X of (
P
) such that F
0
(
x
)
≤
UB
-
ε or else establish that no such x exists. So the search for such x can then be restricted to the set H
∩
[
a
,
b
], where
(24)
H
:
=
{
x
∣
F
0
(
x
)
≤
UB
-
ε
,
F
m
(
x
)
≤
0
,
m
=
1
,
…
,
M
}
.The reduction rule aims at replacing the rectangle[
a
,
b
] with a smaller rectangle [
a
′
,
b
′
]
⊂
[
a
,
b
] without losing any point x
∈
H
∩
[
a
,
b
], that is, such that H
∩
[
a
′
,
b
′
]
=
H
∩
[
a
,
b
]. The rectangle [
a
′
,
b
′
] satisfying this condition is denoted by re
d
ν
[
a
,
b
] with
(25)
ν
=
UB
-
ε
.
To illustrate how re
d
ν
[
a
,
b
]
=
[
a
′
,
b
′
] is deduced by this rule, we first define the following functions.Definition 4.
Given two boxes[
a
,
b
] and [
a
′
,
b
′
] with [
a
′
,
b
′
]
⊆
[
a
,
b
], for i
=
1
,
…
,
n, m
=
1
,
…
,
M, the functions φ
m
i
(
α
), ψ
m
i
(
α
), and ψ
0
i
(
α
)
:
[
0,1
]
→
R are defined by
(26)
φ
m
i
(
α
)
=
F
m
-
(
b
-
α
(
b
i
-
a
i
)
e
i
)
-
F
m
+
(
a
)
,
ψ
m
i
(
α
)
=
F
m
+
(
a
′
+
α
(
b
i
-
a
i
′
)
e
i
)
-
F
m
-
(
b
)
,
ψ
0
i
(
α
)
=
F
0
(
a
′
+
α
(
b
i
-
a
i
′
)
e
i
)
-
ν
,
where e
i denotes the ith unit vector of R
n, that is, a vector such that e
i
i
=
1
,
e
j
i
=
0, ∀
j
≠
i, and the functions F
0
(
x
), F
m
+
(
x
), and F
m
-
(
x
) are given in problem (P), respectively.
Clearly, the functionsφ
m
i
(
α
), ψ
m
i
(
α
), and ψ
0
i
(
α
) are either constant or strictly monotonic over the interval [0,1) from the properties of F
m
-
(
x
), F
m
+
(
x
), and F
0
(
x
). By using these functions, re
d
ν
[
a
,
b
] can be given as follows.Theorem 5.
(
i
) If F
0
(
a
)
>
ν or F
m
+
(
a
)
-
F
m
-
(
b
)
>
0 for some m
=
1
,
…
,
M, then r
e
d
ν
[
a
,
b
]
=
[
a
′
,
b
′
]
=
∅.
(
i
i
) If F
0
(
a
)
≤
ν and F
m
+
(
a
)
-
F
m
-
(
b
)
≤
0 for each m
=
1
,
…
,
M, then r
e
d
ν
[
a
,
b
]
=
[
a
′
,
b
′
], where
(27)
a
′
=
b
-
∑
i
=
1
n
‍
min
⁡
m
=
1
,
…
,
M
{
α
m
i
}
(
b
i
-
a
i
)
e
i
,
b
′
=
a
′
+
∑
i
=
1
n
‍
min
⁡
m
=
0,1
,
…
,
M
{
β
m
i
}
(
b
i
-
a
i
′
)
e
i
are given by
(28)
α
m
i
=
{
1
,
i
f
φ
m
i
(
1
)
≥
0
α
w
i
t
h
φ
m
i
(
α
)
=
0
,
o
t
h
e
r
w
i
s
e
,
β
m
i
=
{
1
,
i
f
ψ
m
i
(
1
)
≤
0
α
w
i
t
h
ψ
m
i
(
α
)
=
0
,
o
t
h
e
r
w
i
s
e
.Proof.
(i) By the increasing property ofF
0
(
x
), F
m
+
(
x
), and F
m
-
(
x
), if F
0
(
a
)
>
ν, then F
0
(
x
)
≥
F
0
(
a
)
>
ν for every x
∈
[
a
,
b
]. If there exists m
∈
{
1
,
…
,
M
} such that F
m
+
(
a
)
-
F
m
-
(
b
)
>
0, then F
m
(
x
)
=
F
m
+
(
x
)
-
F
m
-
(
x
)
≥
F
m
+
(
a
)
-
F
m
-
(
b
)
>
0 for every x
∈
[
a
,
b
]. In both cases, H
∩
[
a
,
b
]
=
∅.
(ii) Given any pointx
∈
[
a
,
b
] satisfying
(29)
F
0
(
x
)
≤
ν
,
F
m
+
(
x
)
-
F
m
-
(
x
)
≤
0
,
m
=
1
,
…
,
M
,
we will show that x
∈
[
a
′
,
b
′
]. Let
(30)
α
m
′
i
=
min
⁡
{
α
m
i
∣
m
=
1
,
…
,
M
}
,
β
m
′
′
i
=
min
⁡
{
β
m
i
∣
m
=
0,1
,
…
,
M
}
.
Firstly, we will show thatx
≥
a
′. If x
≱
a
′, then there exists index i such that
(31)
x
i
<
a
i
′
=
b
i
-
α
m
′
i
(
b
i
-
a
i
)
,
i
.
e
.
,
x
i
=
b
i
-
α
(
b
i
-
a
i
)
with
α
m
′
i
<
α
≤
1
.
We consider the following two cases.
Case  1. If α
m
′
i
=
1, then from (31) we have x
i
<
a
i
′
=
b
i
-
α
m
′
i
(
b
i
-
a
i
)
=
a
i, conflicting with x
∈
[
a
,
b
]; that is, x
i
≥
a
i.
Case  2. If 0
≤
α
m
′
i
<
1, the function φ
m
′
i
(
α
) must be strictly decreasing in single variable α over the interval [0,1). If the function φ
m
′
i
(
α
) is not strictly decreasing in single variable α, we get φ
m
′
i
(
α
) must be a constant over the interval [0,1). In this case, we have
(32)
φ
m
′
i
(
1
)
=
φ
m
′
i
(
0
)
=
F
m
′
-
(
b
)
-
F
m
′
+
(
a
)
≥
0
.
It follows from the definition of α
m
′
i that α
m
′
i
=
1, contradicting with 0
≤
α
m
′
i
<
1.
Since the functionφ
m
′
i
(
α
) is strictly decreasing, it follows from (31) and the definition of α
m
′
i that
(33)
F
m
′
-
(
b
-
(
b
i
-
x
i
)
e
i
)
-
F
m
′
+
(
a
)
=
F
m
′
-
(
b
-
α
(
b
i
-
a
i
)
e
i
)
-
F
m
′
+
(
a
)
=
φ
m
′
i
(
α
)
<
φ
m
′
i
(
α
m
′
i
)
=
0
;
hence,
(34)
F
m
′
-
(
b
-
(
b
i
-
x
i
)
e
i
)
<
F
m
′
+
(
a
)
.
In addition, since F
m
′
-
(
x
) is an increasing function in n-dimension variable x and x
≤
b
-
(
b
i
-
x
i
)
e
i, we have
(35)
F
m
′
-
(
x
)
≤
F
m
′
-
(
b
-
(
b
i
-
x
i
)
e
i
)
<
F
m
′
+
(
a
)
,
conflicting with F
m
′
-
(
x
)
≥
F
m
′
+
(
x
)
≥
F
m
′
+
(
a
).
Based on the above discussion, we havex
≥
a
′; that is, x
∈
[
a
′
,
b
] in either case.
Secondly, we also can show fromx
∈
[
a
′
,
b
] that
(36)
x
≤
b
′
,
i
.
e
.
,
x
∈
[
a
′
,
b
′
]
.
Supposed that x
≰
b
′, then there exists some i such that
(37)
x
i
>
b
i
′
=
a
i
′
+
β
m
′′
i
(
b
i
-
a
i
′
)
;
that is, there exists α such that
(38)
x
i
=
a
i
′
+
α
(
b
i
-
a
i
′
)
,
β
m
′′
i
<
α
≤
1
.
By the definition of β
m
′′
i, there are the following two cases to consider.
Case  1. If β
m
′′
i
=
1, then from (38) we have x
i
>
b
i
′
=
a
i
′
+
(
b
i
-
a
i
′
)
=
b
i, conflicting with x
∈
[
a
′
,
b
]; that is, x
i
≤
b
i.
Case  2. If 0
≤
β
m
′′
i
<
1, the function ψ
m
′′
i
(
α
) is strictly increasing in single variable α. If the function ψ
m
′′
i
(
α
) is not strictly increasing in single variable α, we get ψ
m
′′
i
(
α
) must be a constant over the interval [0,1). In this case, we have
(39)
ψ
0
i
(
1
)
=
ψ
0
i
(
0
)
=
F
0
(
a
′
)
-
ν
≤
0
,
or
(40)
ψ
m
′′
i
(
1
)
=
ψ
m
′′
i
(
0
)
=
F
m
′
′
+
(
a
′
)
-
F
m
′′
-
(
b
)
≤
0
.
It follows from the definition of β
m
′′
i that β
m
′′
i
=
1, which is a contradiction with 0
≤
β
m
′′
i
<
1.
Since the functionψ
m
′′
i
(
α
) is strictly increasing, from (31) and the definition of β
m
′′
i, it implies that
(41)
F
0
(
a
′
+
α
(
b
i
-
a
i
′
)
e
i
)
-
ν
=
ψ
0
i
(
α
)
>
ψ
0
i
(
β
0
i
)
=
0
,
or
(42)
F
m
′′
+
(
a
′
+
α
(
b
i
-
a
i
′
)
e
i
)
-
F
m
′′
-
(
b
)
=
ψ
m
′′
i
(
α
)
>
ψ
m
′′
i
(
β
m
′′
i
)
=
0
.
Assume that (41) holds; we can derive from (38) that
(43)
F
0
(
a
′
+
(
x
i
-
a
i
′
)
e
i
)
=
F
0
(
a
′
+
α
(
b
i
-
a
i
′
)
e
i
)
>
ν
.
It follows from x
≥
a
′
+
(
x
i
-
a
i
′
)
e
i and F
0
(
x
) increasing that
(44)
F
0
(
x
)
≥
F
0
(
a
′
+
(
x
i
-
a
i
′
)
e
i
)
>
ν
,
conflicting with F
0
(
x
)
≤
ν.
If (42) holds, we obtain from (38) that
(45)
F
m
′′
+
(
a
′
+
(
x
i
-
a
i
′
)
e
i
)
=
F
m
′′
+
(
a
′
+
α
(
b
i
-
a
i
′
)
e
i
)
>
F
m
′′
-
(
b
)
;
since x
≥
a
′
+
(
x
i
-
a
i
′
)
e
i and F
m
′′
+
(
x
) is increasing, we have
(46)
F
m
′′
+
(
x
)
≥
F
m
′′
+
(
a
′
+
(
x
i
-
a
i
′
)
e
i
)
>
F
m
′′
-
(
b
)
.
It is a contradiction with F
m
′′
+
(
x
)
≤
F
m
′′
-
(
x
)
≤
F
m
′′
-
(
b
).
From the above results, we must havex
≤
b
′
;
that
is
,
x
∈
[
a
′
,
b
′
] in both cases, and this ends the proof.Remark 6.
Clearly, for anyi
=
1
,
…
,
n, α
m
i
(
m
=
1
,
…
,
M
) and β
m
i
(
m
=
0,1
,
…
,
M
) defined in Theorem 5 must exist and be unique, since the functions F
0
(
x
), F
m
+
(
x
), and F
m
-
(
x
) are all continuous and increasing.


### 3.2.2. Reduction Rule B

For anyx
∈
X
=
(
X
i
)
n
×
1 with X
i
=
[
a
i
,
b
i
]
(
i
=
1
,
…
,
n
), without loss of generality, we assume the above relaxation linear problem RLP
(
X
) can be rewritten as
(47)
RLP
(
X
)
:
{
min
⁡
∑
i
=
1
n
‍
λ
0
i
x
i
+
t
0
s
.
t
.
∑
i
=
1
n
‍
λ
j
i
x
i
+
t
j
≤
0
,
j
=
1
,
…
,
M
,
x
∈
X
⊆
X
0
.Let(48)
R
L
j
=
∑
i
=
1
n
‍
min
⁡
{
λ
j
i
a
i
,
λ
j
i
b
i
}
+
t
j
,
j
=
0,1
,
…
,
M
,
(49)
ρ
i
=
UB
-
R
L
0
+
min
⁡
{
λ
0
i
a
i
,
λ
0
i
b
i
}
λ
0
i
with
λ
0
i
≠
0
,
(50)
τ
j
i
=
-
R
L
j
+
min
⁡
{
λ
j
i
a
i
,
λ
j
i
b
i
}
λ
j
i
with
λ
j
i
≠
0
,
where j
=
1
,
…
,
M, i
=
1
,
…
,
n.Theorem 7.
For any rectangleX
=
(
X
i
)
n
×
1
⊆
X
0, if R
L
0
>
U
B, then there exists no optimal solution of R
L
P
(
X
0
) over X; otherwise, consider the following two cases: if there exists some h
∈
{
1
,
…
,
n
} satisfying λ
0
h
>
0 and ρ
h
<
b
h, then there is no optimal solution of R
L
P
(
X
0
) over X
a; conversely, if λ
0
h
<
0 and ρ
h
>
a
h for some h
∈
{
1
,
…
,
n
}, then there does not exist optimal solution of RLP
(
X
0
) over X
b, where
(51)
X
a
=
(
X
a
i
)
n
×
1
⊆
X
0
w
i
t
h
X
a
i
=
{
X
i
,
i
f
i
≠
h
,
(
ρ
h
,
b
h
]
⋂
‍
X
h
,
i
f
i
=
h
,
X
b
=
(
X
b
i
)
n
×
1
⊆
X
0
w
i
t
h
X
b
i
=
{
X
i
,
i
f
i
≠
h
,
[
a
h
,
ρ
h
)
⋂
‍
X
h
,
i
f
i
=
h
.Theorem 8.
For any rectangleX
=
(
X
i
)
n
×
1
⊆
X
0, if R
L
j
(
x
)
>
0 for some j
∈
{
1
,
…
,
M
}, then there exists no feasible solution of problem R
L
P
(
X
0
) over X, otherwise, consider the following two cases: if there exists some index h
∈
{
1
,
…
,
n
} and j
∈
{
1
,
…
,
M
} satisfying λ
j
h
>
0 and τ
j
h
<
b
h, then there is no feasible solution of the problem R
L
P
(
X
0
) over X
c; conversely, if λ
j
h
<
0 and τ
j
h
>
a
h for some j
∈
{
1
,
…
,
M
} and h
∈
{
1
,
…
,
n
}, then there exists no feasible solution of the problem R
L
P
(
X
0
) over X
d, where
(52)
X
c
=
(
X
c
i
)
n
×
1
⊆
X
0
w
i
t
h
X
c
i
=
{
X
i
,
i
f
i
≠
h
,
(
τ
j
h
,
b
h
]
⋂
‍
X
h
,
i
f
i
=
h
,
X
d
=
(
X
d
i
)
n
×
1
⊆
X
0
w
i
t
h
X
d
i
=
{
X
i
,
i
f
i
≠
h
,
[
a
h
,
τ
j
h
)
⋂
‍
X
h
,
i
f
i
=
h
.Proof.
The proof of the Theorems7 and 8 is similar to Theorems 2 and 3 in [27], respectively; therefore, it is omitted here.By Theorems7 and 8, we can give a new reduction rule B to reject some regions in which the globally optimal solution of RLP
(
X
0
) does not exist. The computation procedure of this rule is summarized as follows.Step 1.
ComputeR
L
0 in (48). If R
L
0
>
UB, let X
=
∅; otherwise, compute ρ
i
(
i
=
1
,
…
,
n
) in (49). If λ
0
h
>
0 and ρ
h
<
b
h for some h
∈
{
1
,
…
,
n
}, then let b
h
=
ρ
h and X
=
(
X
i
)
n
×
1 with X
i
=
[
a
i
,
b
i
]
(
i
=
1
,
…
,
n
). If λ
0
h
<
0 and ρ
h
>
a
h for some h
∈
{
1
,
…
,
n
}, then let a
h
=
ρ
h and X
=
(
X
i
)
n
×
1 with X
i
=
[
a
i
,
b
i
]
(
i
=
1
,
…
,
n
).Step 2.
For anyj
=
1
,
…
,
M, compute R
L
j in (48). If R
L
j
>
0 for some j
∈
{
1
,
…
,
M
}, then let X
=
∅; otherwise, compute τ
j
i in (50) (
j
=
1
,
…
,
M
,
i
=
1
,
…
,
n
). If λ
j
h
>
0 and τ
j
h
<
b
h for some j
∈
{
1
,
…
,
M
} and h
∈
{
1
,
…
,
n
}, then let b
h
=
τ
j
h and X
=
(
X
i
)
n
×
1 with X
i
=
[
a
i
,
b
i
]
(
i
=
1
,
…
,
n
). If λ
j
h
<
0 and τ
j
h
>
a
h for some j
∈
{
1
,
…
,
M
} and h
∈
{
1
,
…
,
n
}, then let a
h
=
τ
j
h and X
=
(
X
i
)
n
×
1 with X
i
=
[
a
i
,
b
i
]
(
i
=
1
,
…
,
n
).Rule B provides a possibility to cut away all or a large part of the rectangleX which is currently investigated by the algorithm procedure.


## 3.2.1. Reduction Rule A

Rule A is based on the monotonic structure of the problem(
P
). At a given stage of the BRB algorithm for (
P
), for a rectangle X
=
[
a
,
b
] generated during the partitioning procedure and still of interest, let UB be the object function value of the best so far feasible solution to problem (
P
). Given an ε
>
0, we want to find a feasible solution x
∈
X of (
P
) such that F
0
(
x
)
≤
UB
-
ε or else establish that no such x exists. So the search for such x can then be restricted to the set H
∩
[
a
,
b
], where
(24)
H
:
=
{
x
∣
F
0
(
x
)
≤
UB
-
ε
,
F
m
(
x
)
≤
0
,
m
=
1
,
…
,
M
}
.The reduction rule aims at replacing the rectangle[
a
,
b
] with a smaller rectangle [
a
′
,
b
′
]
⊂
[
a
,
b
] without losing any point x
∈
H
∩
[
a
,
b
], that is, such that H
∩
[
a
′
,
b
′
]
=
H
∩
[
a
,
b
]. The rectangle [
a
′
,
b
′
] satisfying this condition is denoted by re
d
ν
[
a
,
b
] with
(25)
ν
=
UB
-
ε
.
To illustrate how re
d
ν
[
a
,
b
]
=
[
a
′
,
b
′
] is deduced by this rule, we first define the following functions.Definition 4.
Given two boxes[
a
,
b
] and [
a
′
,
b
′
] with [
a
′
,
b
′
]
⊆
[
a
,
b
], for i
=
1
,
…
,
n, m
=
1
,
…
,
M, the functions φ
m
i
(
α
), ψ
m
i
(
α
), and ψ
0
i
(
α
)
:
[
0,1
]
→
R are defined by
(26)
φ
m
i
(
α
)
=
F
m
-
(
b
-
α
(
b
i
-
a
i
)
e
i
)
-
F
m
+
(
a
)
,
ψ
m
i
(
α
)
=
F
m
+
(
a
′
+
α
(
b
i
-
a
i
′
)
e
i
)
-
F
m
-
(
b
)
,
ψ
0
i
(
α
)
=
F
0
(
a
′
+
α
(
b
i
-
a
i
′
)
e
i
)
-
ν
,
where e
i denotes the ith unit vector of R
n, that is, a vector such that e
i
i
=
1
,
e
j
i
=
0, ∀
j
≠
i, and the functions F
0
(
x
), F
m
+
(
x
), and F
m
-
(
x
) are given in problem (P), respectively.
Clearly, the functionsφ
m
i
(
α
), ψ
m
i
(
α
), and ψ
0
i
(
α
) are either constant or strictly monotonic over the interval [0,1) from the properties of F
m
-
(
x
), F
m
+
(
x
), and F
0
(
x
). By using these functions, re
d
ν
[
a
,
b
] can be given as follows.Theorem 5.
(
i
) If F
0
(
a
)
>
ν or F
m
+
(
a
)
-
F
m
-
(
b
)
>
0 for some m
=
1
,
…
,
M, then r
e
d
ν
[
a
,
b
]
=
[
a
′
,
b
′
]
=
∅.
(
i
i
) If F
0
(
a
)
≤
ν and F
m
+
(
a
)
-
F
m
-
(
b
)
≤
0 for each m
=
1
,
…
,
M, then r
e
d
ν
[
a
,
b
]
=
[
a
′
,
b
′
], where
(27)
a
′
=
b
-
∑
i
=
1
n
‍
min
⁡
m
=
1
,
…
,
M
{
α
m
i
}
(
b
i
-
a
i
)
e
i
,
b
′
=
a
′
+
∑
i
=
1
n
‍
min
⁡
m
=
0,1
,
…
,
M
{
β
m
i
}
(
b
i
-
a
i
′
)
e
i
are given by
(28)
α
m
i
=
{
1
,
i
f
φ
m
i
(
1
)
≥
0
α
w
i
t
h
φ
m
i
(
α
)
=
0
,
o
t
h
e
r
w
i
s
e
,
β
m
i
=
{
1
,
i
f
ψ
m
i
(
1
)
≤
0
α
w
i
t
h
ψ
m
i
(
α
)
=
0
,
o
t
h
e
r
w
i
s
e
.Proof.
(i) By the increasing property ofF
0
(
x
), F
m
+
(
x
), and F
m
-
(
x
), if F
0
(
a
)
>
ν, then F
0
(
x
)
≥
F
0
(
a
)
>
ν for every x
∈
[
a
,
b
]. If there exists m
∈
{
1
,
…
,
M
} such that F
m
+
(
a
)
-
F
m
-
(
b
)
>
0, then F
m
(
x
)
=
F
m
+
(
x
)
-
F
m
-
(
x
)
≥
F
m
+
(
a
)
-
F
m
-
(
b
)
>
0 for every x
∈
[
a
,
b
]. In both cases, H
∩
[
a
,
b
]
=
∅.
(ii) Given any pointx
∈
[
a
,
b
] satisfying
(29)
F
0
(
x
)
≤
ν
,
F
m
+
(
x
)
-
F
m
-
(
x
)
≤
0
,
m
=
1
,
…
,
M
,
we will show that x
∈
[
a
′
,
b
′
]. Let
(30)
α
m
′
i
=
min
⁡
{
α
m
i
∣
m
=
1
,
…
,
M
}
,
β
m
′
′
i
=
min
⁡
{
β
m
i
∣
m
=
0,1
,
…
,
M
}
.
Firstly, we will show thatx
≥
a
′. If x
≱
a
′, then there exists index i such that
(31)
x
i
<
a
i
′
=
b
i
-
α
m
′
i
(
b
i
-
a
i
)
,
i
.
e
.
,
x
i
=
b
i
-
α
(
b
i
-
a
i
)
with
α
m
′
i
<
α
≤
1
.
We consider the following two cases.
Case  1. If α
m
′
i
=
1, then from (31) we have x
i
<
a
i
′
=
b
i
-
α
m
′
i
(
b
i
-
a
i
)
=
a
i, conflicting with x
∈
[
a
,
b
]; that is, x
i
≥
a
i.
Case  2. If 0
≤
α
m
′
i
<
1, the function φ
m
′
i
(
α
) must be strictly decreasing in single variable α over the interval [0,1). If the function φ
m
′
i
(
α
) is not strictly decreasing in single variable α, we get φ
m
′
i
(
α
) must be a constant over the interval [0,1). In this case, we have
(32)
φ
m
′
i
(
1
)
=
φ
m
′
i
(
0
)
=
F
m
′
-
(
b
)
-
F
m
′
+
(
a
)
≥
0
.
It follows from the definition of α
m
′
i that α
m
′
i
=
1, contradicting with 0
≤
α
m
′
i
<
1.
Since the functionφ
m
′
i
(
α
) is strictly decreasing, it follows from (31) and the definition of α
m
′
i that
(33)
F
m
′
-
(
b
-
(
b
i
-
x
i
)
e
i
)
-
F
m
′
+
(
a
)
=
F
m
′
-
(
b
-
α
(
b
i
-
a
i
)
e
i
)
-
F
m
′
+
(
a
)
=
φ
m
′
i
(
α
)
<
φ
m
′
i
(
α
m
′
i
)
=
0
;
hence,
(34)
F
m
′
-
(
b
-
(
b
i
-
x
i
)
e
i
)
<
F
m
′
+
(
a
)
.
In addition, since F
m
′
-
(
x
) is an increasing function in n-dimension variable x and x
≤
b
-
(
b
i
-
x
i
)
e
i, we have
(35)
F
m
′
-
(
x
)
≤
F
m
′
-
(
b
-
(
b
i
-
x
i
)
e
i
)
<
F
m
′
+
(
a
)
,
conflicting with F
m
′
-
(
x
)
≥
F
m
′
+
(
x
)
≥
F
m
′
+
(
a
).
Based on the above discussion, we havex
≥
a
′; that is, x
∈
[
a
′
,
b
] in either case.
Secondly, we also can show fromx
∈
[
a
′
,
b
] that
(36)
x
≤
b
′
,
i
.
e
.
,
x
∈
[
a
′
,
b
′
]
.
Supposed that x
≰
b
′, then there exists some i such that
(37)
x
i
>
b
i
′
=
a
i
′
+
β
m
′′
i
(
b
i
-
a
i
′
)
;
that is, there exists α such that
(38)
x
i
=
a
i
′
+
α
(
b
i
-
a
i
′
)
,
β
m
′′
i
<
α
≤
1
.
By the definition of β
m
′′
i, there are the following two cases to consider.
Case  1. If β
m
′′
i
=
1, then from (38) we have x
i
>
b
i
′
=
a
i
′
+
(
b
i
-
a
i
′
)
=
b
i, conflicting with x
∈
[
a
′
,
b
]; that is, x
i
≤
b
i.
Case  2. If 0
≤
β
m
′′
i
<
1, the function ψ
m
′′
i
(
α
) is strictly increasing in single variable α. If the function ψ
m
′′
i
(
α
) is not strictly increasing in single variable α, we get ψ
m
′′
i
(
α
) must be a constant over the interval [0,1). In this case, we have
(39)
ψ
0
i
(
1
)
=
ψ
0
i
(
0
)
=
F
0
(
a
′
)
-
ν
≤
0
,
or
(40)
ψ
m
′′
i
(
1
)
=
ψ
m
′′
i
(
0
)
=
F
m
′
′
+
(
a
′
)
-
F
m
′′
-
(
b
)
≤
0
.
It follows from the definition of β
m
′′
i that β
m
′′
i
=
1, which is a contradiction with 0
≤
β
m
′′
i
<
1.
Since the functionψ
m
′′
i
(
α
) is strictly increasing, from (31) and the definition of β
m
′′
i, it implies that
(41)
F
0
(
a
′
+
α
(
b
i
-
a
i
′
)
e
i
)
-
ν
=
ψ
0
i
(
α
)
>
ψ
0
i
(
β
0
i
)
=
0
,
or
(42)
F
m
′′
+
(
a
′
+
α
(
b
i
-
a
i
′
)
e
i
)
-
F
m
′′
-
(
b
)
=
ψ
m
′′
i
(
α
)
>
ψ
m
′′
i
(
β
m
′′
i
)
=
0
.
Assume that (41) holds; we can derive from (38) that
(43)
F
0
(
a
′
+
(
x
i
-
a
i
′
)
e
i
)
=
F
0
(
a
′
+
α
(
b
i
-
a
i
′
)
e
i
)
>
ν
.
It follows from x
≥
a
′
+
(
x
i
-
a
i
′
)
e
i and F
0
(
x
) increasing that
(44)
F
0
(
x
)
≥
F
0
(
a
′
+
(
x
i
-
a
i
′
)
e
i
)
>
ν
,
conflicting with F
0
(
x
)
≤
ν.
If (42) holds, we obtain from (38) that
(45)
F
m
′′
+
(
a
′
+
(
x
i
-
a
i
′
)
e
i
)
=
F
m
′′
+
(
a
′
+
α
(
b
i
-
a
i
′
)
e
i
)
>
F
m
′′
-
(
b
)
;
since x
≥
a
′
+
(
x
i
-
a
i
′
)
e
i and F
m
′′
+
(
x
) is increasing, we have
(46)
F
m
′′
+
(
x
)
≥
F
m
′′
+
(
a
′
+
(
x
i
-
a
i
′
)
e
i
)
>
F
m
′′
-
(
b
)
.
It is a contradiction with F
m
′′
+
(
x
)
≤
F
m
′′
-
(
x
)
≤
F
m
′′
-
(
b
).
From the above results, we must havex
≤
b
′
;
that
is
,
x
∈
[
a
′
,
b
′
] in both cases, and this ends the proof.Remark 6.
Clearly, for anyi
=
1
,
…
,
n, α
m
i
(
m
=
1
,
…
,
M
) and β
m
i
(
m
=
0,1
,
…
,
M
) defined in Theorem 5 must exist and be unique, since the functions F
0
(
x
), F
m
+
(
x
), and F
m
-
(
x
) are all continuous and increasing.


## 3.2.2. Reduction Rule B

For anyx
∈
X
=
(
X
i
)
n
×
1 with X
i
=
[
a
i
,
b
i
]
(
i
=
1
,
…
,
n
), without loss of generality, we assume the above relaxation linear problem RLP
(
X
) can be rewritten as
(47)
RLP
(
X
)
:
{
min
⁡
∑
i
=
1
n
‍
λ
0
i
x
i
+
t
0
s
.
t
.
∑
i
=
1
n
‍
λ
j
i
x
i
+
t
j
≤
0
,
j
=
1
,
…
,
M
,
x
∈
X
⊆
X
0
.Let(48)
R
L
j
=
∑
i
=
1
n
‍
min
⁡
{
λ
j
i
a
i
,
λ
j
i
b
i
}
+
t
j
,
j
=
0,1
,
…
,
M
,
(49)
ρ
i
=
UB
-
R
L
0
+
min
⁡
{
λ
0
i
a
i
,
λ
0
i
b
i
}
λ
0
i
with
λ
0
i
≠
0
,
(50)
τ
j
i
=
-
R
L
j
+
min
⁡
{
λ
j
i
a
i
,
λ
j
i
b
i
}
λ
j
i
with
λ
j
i
≠
0
,
where j
=
1
,
…
,
M, i
=
1
,
…
,
n.Theorem 7.
For any rectangleX
=
(
X
i
)
n
×
1
⊆
X
0, if R
L
0
>
U
B, then there exists no optimal solution of R
L
P
(
X
0
) over X; otherwise, consider the following two cases: if there exists some h
∈
{
1
,
…
,
n
} satisfying λ
0
h
>
0 and ρ
h
<
b
h, then there is no optimal solution of R
L
P
(
X
0
) over X
a; conversely, if λ
0
h
<
0 and ρ
h
>
a
h for some h
∈
{
1
,
…
,
n
}, then there does not exist optimal solution of RLP
(
X
0
) over X
b, where
(51)
X
a
=
(
X
a
i
)
n
×
1
⊆
X
0
w
i
t
h
X
a
i
=
{
X
i
,
i
f
i
≠
h
,
(
ρ
h
,
b
h
]
⋂
‍
X
h
,
i
f
i
=
h
,
X
b
=
(
X
b
i
)
n
×
1
⊆
X
0
w
i
t
h
X
b
i
=
{
X
i
,
i
f
i
≠
h
,
[
a
h
,
ρ
h
)
⋂
‍
X
h
,
i
f
i
=
h
.Theorem 8.
For any rectangleX
=
(
X
i
)
n
×
1
⊆
X
0, if R
L
j
(
x
)
>
0 for some j
∈
{
1
,
…
,
M
}, then there exists no feasible solution of problem R
L
P
(
X
0
) over X, otherwise, consider the following two cases: if there exists some index h
∈
{
1
,
…
,
n
} and j
∈
{
1
,
…
,
M
} satisfying λ
j
h
>
0 and τ
j
h
<
b
h, then there is no feasible solution of the problem R
L
P
(
X
0
) over X
c; conversely, if λ
j
h
<
0 and τ
j
h
>
a
h for some j
∈
{
1
,
…
,
M
} and h
∈
{
1
,
…
,
n
}, then there exists no feasible solution of the problem R
L
P
(
X
0
) over X
d, where
(52)
X
c
=
(
X
c
i
)
n
×
1
⊆
X
0
w
i
t
h
X
c
i
=
{
X
i
,
i
f
i
≠
h
,
(
τ
j
h
,
b
h
]
⋂
‍
X
h
,
i
f
i
=
h
,
X
d
=
(
X
d
i
)
n
×
1
⊆
X
0
w
i
t
h
X
d
i
=
{
X
i
,
i
f
i
≠
h
,
[
a
h
,
τ
j
h
)
⋂
‍
X
h
,
i
f
i
=
h
.Proof.
The proof of the Theorems7 and 8 is similar to Theorems 2 and 3 in [27], respectively; therefore, it is omitted here.By Theorems7 and 8, we can give a new reduction rule B to reject some regions in which the globally optimal solution of RLP
(
X
0
) does not exist. The computation procedure of this rule is summarized as follows.Step 1.
ComputeR
L
0 in (48). If R
L
0
>
UB, let X
=
∅; otherwise, compute ρ
i
(
i
=
1
,
…
,
n
) in (49). If λ
0
h
>
0 and ρ
h
<
b
h for some h
∈
{
1
,
…
,
n
}, then let b
h
=
ρ
h and X
=
(
X
i
)
n
×
1 with X
i
=
[
a
i
,
b
i
]
(
i
=
1
,
…
,
n
). If λ
0
h
<
0 and ρ
h
>
a
h for some h
∈
{
1
,
…
,
n
}, then let a
h
=
ρ
h and X
=
(
X
i
)
n
×
1 with X
i
=
[
a
i
,
b
i
]
(
i
=
1
,
…
,
n
).Step 2.
For anyj
=
1
,
…
,
M, compute R
L
j in (48). If R
L
j
>
0 for some j
∈
{
1
,
…
,
M
}, then let X
=
∅; otherwise, compute τ
j
i in (50) (
j
=
1
,
…
,
M
,
i
=
1
,
…
,
n
). If λ
j
h
>
0 and τ
j
h
<
b
h for some j
∈
{
1
,
…
,
M
} and h
∈
{
1
,
…
,
n
}, then let b
h
=
τ
j
h and X
=
(
X
i
)
n
×
1 with X
i
=
[
a
i
,
b
i
]
(
i
=
1
,
…
,
n
). If λ
j
h
<
0 and τ
j
h
>
a
h for some j
∈
{
1
,
…
,
M
} and h
∈
{
1
,
…
,
n
}, then let a
h
=
τ
j
h and X
=
(
X
i
)
n
×
1 with X
i
=
[
a
i
,
b
i
]
(
i
=
1
,
…
,
n
).Rule B provides a possibility to cut away all or a large part of the rectangleX which is currently investigated by the algorithm procedure.


## 4. Algorithm and Its Convergence

In this section, a branch-reduce-bound (BRB) algorithm is developed to solve the problem (P) based on the former discussion. This method needs to solve a sequence of (RLP) problems over partitioned subsets of X
0.The BRB algorithm is based on partitioning the rectangleX
0 into subrectangles, each concerned with a node of the branch and bound tree. Hence, at any stage k of the algorithm, suppose that we have a collection of active nodes denoted by 𝒯
k, that is, each associated with a rectangle X
⊆
X
0, for
all
X
∈
𝒯
k. For each such node X
=
[
a
,
b
], we will compute a lower bound LB
(
X
) of the optimal objective function value of (P) via the optimal value of the RLP(X) and F
0
(
a
), so the lower bound of the optimal value of (P) at stage k is given by min
⁡
{
LB
(
X
)
,
∀
X
∈
𝒯
k
}. We now select an active node to subdivide its associated rectangle into two subrectangles according to the standard branch rule for each new node, reducing it, and then compute the lower bound as before. At the same time, if necessary, we will update the upper bound U
B
k. Upon fathoming any nonimproving node, we obtain a collection of active nodes for the next stage, and this process is repeated until convergence is obtained.Algorithm 1.
Consider the following steps.
Step  0 (Initialization). Choose the convergence tolerance ε
>
0. Let 𝒫
0
=
{
X
0
} and 𝒯
0
=
{
X
0
}. If some feasible solutions are available, add them to H and let U
B
0
=
min
⁡
{
F
0
(
x
)
|
x
∈
H
}; otherwise, let H
=
∅ and U
B
0
=
+
∞. Set k
=
0.
Step  1 (Reduction). (i) Delete every box [
a
,
b
]
∈
𝒫
k such that F
0
(
a
)
>
U
B
k
-
ε or F
m
+
(
a
)
-
F
m
-
(
b
)
>
0 for some m
∈
{
1
,
…
,
M
}, and denote the remaining still as 𝒫
k. If 𝒫
k
≠
∅, apply the reduction rule A described in Theorem 5 in Section 3.2 to each box [
a
,
b
]
∈
𝒫
k. Let 𝒫
k
′
=
{
re
d
ν
[
a
,
b
]
∣
[
a
,
b
]
∈
𝒫
k
} with ν
=
U
B
k
-
ε.
(ii) If𝒫
k
′
≠
∅, for each box [
a
,
b
]
∈
𝒫
k
′ that is currently investigated, we use the reduction rule B in Sub section 3.2 to cut away X and denote the left still as 𝒫
k
′′.
Step  2 (Bounding). If 𝒫
k
′′
≠
∅, begin to do for each [
a
,
b
]
∈
𝒫
k
′′the following.
(i) Solve the problemRLP
(
X
) to obtain the optimal solution x
(
X
) and the optimal value V
[
RLP
(
X
)
]. Let LB
(
X
)
=
max
⁡
{
V
[
RLP
(
X
)
]
,
F
0
(
a
)
}.
(ii) IfF
m
(
a
)
≤
0 for every m
=
1
,
…
,
M, then set H
=
H
∪
{
a
}.
(iii) IfF
0
(
b
)
>
UB
-
ε, compute a point x
^
=
a
+
θ
(
b
-
a
) such that F
0
(
a
+
θ
(
b
-
a
)
)
=
UB
-
ε; otherwise, let x
^
=
b.
(iv) IfH
≠
∅, define the new upper bound U
B
k
=
min
⁡
{
F
0
(
x
)
∣
x
∈
H
}, and the best known feasible point is denoted by x
*
=
argmin
{
F
0
(
x
)
∣
x
∈
H
}. Set 𝒯
k
=
(
𝒯
k
∖
X
k
)
∪
𝒫
k
′′.
Step  3 (Convergence Checking). Set 𝒯
k
+
1
=
𝒯
k
∖
{
X
∣
LB
(
X
)
>
U
B
k
-
ε
,
X
∈
𝒯
k
}.
If𝒯
k
+
1
=
∅, then stop: if U
B
k
=
+
∞, the problem is infeasible; otherwise, U
B
k is the optimal value and x
* is the optimal solution. Otherwise, select an active node X
k
+
1
=
arg
min
⁡
{
LB
(
X
)
∣
X
∈
𝒯
k
+
1
} for further consideration.
Step  4 (Branching). Divide X
k
+
1 into two new subrectangles using the standard branch rule and let 𝒫
k
+
1 be the collection of these two subrectangles. Set k
=
k
+
1 and return to Step 1.Convergence Analysis. In this subsection, we give the convergence of the proposed algorithm. Assume that the number of globally optimal solutions of (SGP) is finite. Then the above proposed algorithm either terminates finitely at a globally optimal solution or generates an infinite sequence of iteration nodes. If the algorithm terminates at some iteration k, then obviously the point x
* is a globally optimal solution and UB is the optimal value of problem (P). If the algorithm is infinite, its convergence is discussed as follows.Theorem 9.
Assume that the above algorithm is infinite; then it generates an infinite sequence of iterations such that along any infinite branch-and-bound tree any accumulation point of the sequence{
L
B
k
} will be the global minimum of problem (P).Proof.
Since the algorithm is infinite, it generates an infinite sequence{
X
k
} such that a subsequence {
X
k
l
} of {
X
k
} satisfies X
k
l
+
1
⊂
X
k
l for l
=
1,2
,
…. In this case, for every iteration k
=
0,1
,
2
,
…, from [28, 29] there is at least an infinite subsequence {
L
B
k
l
} of {
L
B
k
} such that
(53)
L
B
k
l
⩽
min
⁡
x
∈
X
F
0
(
x
)
,
X
k
l
∈
arg
min
⁡
X
∈
𝒯
k
l
LB
(
X
)
,
x
k
l
=
x
(
X
k
l
)
∈
X
k
l
⊆
X
0
,
where X denotes the feasible region of problem (P). We see from [28–30] that {
L
B
k
l
} is a nondecreasing sequence bounded above by min
⁡
x
∈
X
F
0
(
x
), which guarantees the existence of the limit lim
⁡
l
→
∞
L
B
k
l
:
=
LB and LB
≤
min
⁡
x
∈
X
F
0
(
x
). Since {
x
k
l
} is an infinite sequence on a compact set, it follows that there exists a convergent subsequence {
x
q
} of {
x
k
l
} satisfying lim
⁡
q
→
∞
x
q
=
x
^
,
x
q
∈
X
q and L
B
q
=
LB
(
X
q
)
=
L
F
0
(
x
q
), where {
X
q
} is a subsequence of {
X
k
l
}. The linear functions L
F
j
(
j
=
0,1
,
…
,
M
) used in the problem RLP
(
X
) are strongly consistent on X
0. Thus, lim
⁡
q
→
∞
L
B
q
=
LB
=
F
0
(
x
^
). All that remains is to show that x
^
∈
X. Since X
0 is a closed set, it follows that x
^
∈
X
0. Suppose that x
^
∉
X. Then there exists some F
j, j
∈
{
1
,
…
,
M
}, such that F
j
(
x
^
)
=
δ
>
0. Since L
F
j
(
x
) is continuous, the sequence {
L
F
j
(
x
q
)
} converges to F
j
(
x
^
) as q
→
∞. By definition of convergence, ∃
q
δ such that |
L
F
j
(
x
q
)
-
F
j
(
x
^
)
|
<
δ as q
>
q
δ, and so when q
>
q
δ, L
F
j
(
x
q
)
>
0 implies that the problem RLP
(
X
) is infeasible. This contradicts the assumption of x
q
=
x
(
X
q
). Therefore, x
^
∈
X; that is, LB
=
F
0
(
x
^
)
=
min
⁡
x
∈
X
F
0
(
x
), and the proof is complete.


## 5. Numerical Results

To verify the performance of the proposed algorithm, we will give some computational results through ten test problems. The algorithm is coded in Compaq Visual Fortran. The simplex method is applied to solve the relaxation linear programming problems. All test problems are implemented in an Athlon(tm) CPU 2.31 GHz with 960 MB RAM microcomputer.Example 1 (see [22, 31, 32]).
Consider(54)
min
⁡
y
3
0.8
y
4
1.2
s
.
t
.
y
1
y
4
-
1
+
y
2
-
1
y
4
-
1
≤
1
,

-
y
1
-
2
y
3
-
1
-
y
2
y
3
-
1
≤
1
,
0.1
≤
y
1
≤
1
,
5
≤
y
2
≤
10
,
8
≤
y
3
≤
15
,
0.01
≤
y
4
≤
1
.Example 2 (see [22, 32]).
Consider(55)
min
⁡
y
0
s
.
t
.
3.7
y
0
-
1
y
1
0.85
+
1.985
y
0
-
1
y
1
+
700.3
y
0
-
1
y
2
-
0.75
≤
1
,
0.7673
y
2
0.05
-
0.05
y
1
≤
1
,
5
≤
y
0
≤
15
,
0.1
≤
y
1
≤
5
,
380
≤
y
2
≤
450
.Example 3 (see [21, 22, 31, 33]).
Consider(56)
min
⁡

0.5
y
1
y
2
-
1
-
y
1
-
5
y
2
-
1
s
.
t
.
0.01
y
2
y
3
-
1
+
0.01
y
2
+
0.0005
y
1
y
3
≤
1
,
70
≤
y
1
≤
150
,
1
≤
y
2
≤
30
,
0.5
≤
y
3
≤
21
.Example 4 (see [21, 22, 33]).
Consider(57)
min
⁡
168
y
1
y
2
+
3651.2
y
1
y
2
y
3
-
1
+
4
×
1
0
4
y
4
-
1
s
.
t
.
1.0425
y
1
y
2
-
1
≤
1
,
3.5
×
1
0
-
4
y
1
y
2
≤
1
,
1.25
y
1
-
1
y
4
+
41.63
y
1
-
1
≤
1
,
40
≤
y
1
≤
44
,
40
≤
y
2
≤
45
,
60
≤
y
3
≤
70
,
0.1
≤
y
4
≤
1.4
.Example 5 (see [21, 22, 33]).
Consider(58)
min
⁡
5.3578
y
3
2
+
0.8357
y
1
y
5
+
37.2392
y
1
s
.
t
.
0.00002584
y
3
y
5
-
0.00006663
y
2
y
5

-
0.0000734
y
1
y
4
≤
1
,
0.000853007
y
2
y
5
+
0.00009395
y
1
y
4
-
0.00033085
y
3
y
5
≤
1
,
1330.3294
y
2
-
1
y
5
-
1
-
0.42
y
1
y
5
-
1
-
0.30586
y
2
-
1
y
3
2
y
5
-
1
≤
1
,
0.00024186
y
2
y
5
+
0.00010159
y
1
y
2
+
0.00007379
y
3
2
≤
1
,
2275.1327
y
3
-
1
y
5
-
1
-
0.2668
y
1
y
5
-
1
-
0.40584
y
4
y
5
-
1
≤
1
,
0.00029955
y
3
y
5
+
0.00007992
y
1
y
3
+
0.00012157
y
3
y
4
≤
1
,
78.0
≤
y
1
≤
102.0
,
33.0
≤
y
2
≤
45.0
,
27.0
≤
y
3
≤
45.0
,
27.0
≤
y
4
≤
45.0
,
27.0
≤
y
5
≤
45.0
.Example 6 (see [21, 24, 34]).
Consider(59)
min
⁡
5
x
1
+
5
×
1
0
4
x
1
-
1
+
46.2
x
2
+
7.2
×
1
0
4
x
1
-
1

+
1.44
×
1
0
5
x
3
-
1
s
.
t
.
4
x
1
-
1
+
32
x
2
-
1
+
120
x
3
-
1
≤
1
,
1
≤
x
1
,
x
2
,
x
3
≤
220
.Example 7 (see [24]).
Consider(60)
min
⁡
-
4
x
2
+
(
x
1
-
1
)
2
+
x
2
2
-
10
x
3
2
s
.
t
.
x
1
2
+
x
2
2
+
x
3
2
≤
2
,
(
x
1
-
2
)
2
+
x
2
2
+
x
3
2
≤
2
,
2
-
2
≤
x
1
≤
2
,
-
2
≤
x
2
≤
2
,
-
2
≤
x
3
≤
2
.Example 8 (see [22]).
Consider(61)
min
⁡
x
12
(
12.62626
-
1.231059
y
1
)
+
x
13
(
12.62626
-
1.231059
x
2
)
+
x
14
(
12.62626
-
1.231059
y
3
)
+
x
15
(
12.62626
-
1.231059
x
4
)
+
x
16
(
12.62626
-
1.231059
x
5
)
s
.
t
.
x
12
-
x
11
≤
0
,
x
11
-
x
12
≤
50
,
x
10
-
x
4
≤
0
,
x
9
-
x
10
≤
0
,
x
8
-
x
9
≤
0
,
2
x
7
-
x
1
≤
1
,
x
3
-
x
4
≤
,
x
3
x
2
-
x
3
≤
0
,
x
1
-
x
2
≤
0
,
x
4
x
16
-
50
x
4
-
x
5
x
16
≤
-
450
,
50
x
4
+
x
5
x
16
+
x
10
x
15
-
50
x
10
-
x
4
x
15
-
x
4
x
16
≤
0
,
50
x
10
+
x
4
x
5
+
x
9
x
14
-
50
x
9
-
x
3
x
14
-
x
8
x
15
≤
0
,
50
x
8
+
50
x
9
+
x
3
x
14
+
x
8
x
13
-
x
2
x
13
-
x
9
x
14
≤
500
,
50
x
7
+
x
2
x
13
+
x
7
x
12
-
50
x
8
-
x
1
x
12
-
x
8
x
13
≤
0
,
50
x
8
+
x
1
x
12
+
x
8
x
13
-
50
x
7
-
x
2
x
13
-
x
7
x
12
≤
0
,
x
6
x
11
+
x
1
x
12
+
x
7
x
11
-
x
6
x
12
≤
0
,
100
x
6
+
0.0975
x
1
2
-
3.475
x
1
-
9.75
x
1
x
6
≤
0
,
100
x
7
+
0.0975
x
2
2
-
3.475
x
2
-
9.75
x
2
x
7
≤
0
,
100
x
8
+
0.0975
x
3
2
-
3.475
x
3
-
9.75
x
3
x
8
≤
0
,
100
x
9
+
0.0975
x
4
2
-
3.475
x
4
-
9.75
x
4
x
9
≤
0
,
100
x
10
+
0.0975
x
5
2
-
3.475
x
5
-
9.75
x
5
x
10
≤
0
,
x
≥
(
1,1
,
9,9
,
9,1
,
1,1
,
1,1
,
50,0
,
1,50,50,0
)
,
x
≤
(
8.037732,9
,
9,9
,
9,1
,
4.518866,9
,
9,9
,
100
,
50,50,50,50,0
)
.Example 9 (see [22]).
Consider(62)
min
⁡
(
3
+
x
1
x
3
)
(
x
1
x
2
x
3
x
4
+
2
x
1
x
3
+
2
)
2
/
3
s
.
t
.
-
3
(
2
x
1
x
2
+
3
x
1
x
2
x
4
)
(
2
x
1
x
3
+
4
x
1
x
4
-
x
2
)
-
(
x
1
x
3
+
3
x
1
x
2
x
4
)
×
(
4
x
3
x
4
+
4
x
1
x
3
x
4
+
x
1
x
3
-
4
x
1
x
2
x
4
)
1
/
3
+
3
(
x
4
+
3
x
1
x
3
x
4
)
×
(
3
x
1
x
2
x
3
+
3
x
1
x
4
+
2
x
3
x
4
-
3
x
1
x
2
x
4
)
1
/
4
≤
-
309.219315
,
-
2
(
3
x
3
+
3
x
1
x
2
x
3
)
(
x
1
x
2
x
3
+
4
x
2
x
4
-
x
3
x
4
)
2
+
(
3
x
1
x
2
x
3
)
(
3
x
3
+
2
x
1
x
2
x
3
+
3
x
4
)
4
-
(
x
2
x
3
x
4
+
x
1
x
3
x
4
)
(
4
x
1
-
1
)
3
/
4
-
3
(
3
x
3
x
4
+
2
x
1
x
3
x
4
)
×
(
x
1
x
2
x
3
x
4
+
x
3
x
4
-
4
x
1
x
2
x
3
-
2
x
1
)
4
≤
-
78243.910551
,
-
3
(
4
x
1
x
3
x
4
)
(
2
x
4
+
2
x
1
x
2
-
x
2
-
x
3
)
2
+
2
(
x
1
x
2
x
4
+
3
x
1
x
3
x
4
)
×
(
x
1
x
2
+
2
x
2
x
3
+
4
x
2
-
x
2
x
3
x
4
-
x
1
x
3
)
4
≤
9618
,
0
≤
x
i
≤
5
,
i
=
1
,
…
,
4
.Example 10 (see [22]).
Consider(63)
min
⁡
4
(
x
1
2
x
3
+
2
x
1
2
x
2
x
3
2
x
5
+
2
x
1
2
x
2
x
3
)
×
(
5
x
1
2
x
3
x
4
2
x
5
+
3
x
2
)
3
/
5
+
3
(
2
x
4
2
x
5
2
)
(
4
x
1
2
x
4
+
4
x
2
x
5
)
5
/
3
s
.
t
.
-
2
(
2
x
1
x
5
+
5
x
1
2
x
2
x
4
2
x
5
)
(
3
x
1
x
4
x
5
2
+
5
+
4
x
3
x
5
2
)
1
/
2
≤
-
7684.470329
,
2
(
2
x
1
x
2
2
x
3
x
4
2
)
(
2
x
1
x
2
x
3
x
4
2
+
2
x
2
x
4
2
x
5
-
x
1
2
x
5
2
)
3
/
2
≤
1286590.314422
,
0
≤
x
i
≤
5
,
i
=
1
,
…
,
5
.
Tables1 and 2 summarize the computational results on the above examples, where Iter denotes the number of algorithm iteration.Table 1
The numerical results for Examples1–4.
Example
Optimal solution
Optimal value
Iter
ε
1
Ours
(0.1, 9.9999, 8.0, 0.2)
0.7651
58
1
0
-
5
[22]
(0.1, 9.9999, 8.0, 0.2)
0.7651
132
1
0
-
5
[31]
(0.1015, 7.331972, 8.0169, 0.2395)
0.9514
175
1
0
-
5
[32]
(0.1358, 9.9324, 8.6973, 0.2365)
1.0000
171
1
0
-
5
2
Ours
(7.8922, 0.1002, 450.0000)
7.8922
14
1
0
-
2
[22]
(12.0475, 0.8167, 444.9416)
12.0475
6472
1
0
-
2
[32]
(11.9538, 0.8150, 445.1249)
11.9538
67
1
0
-
2
3
Ours
(149.99608, 29.9530, 3.9456)
−147.6591
156
1
0
-
2
[22]
(150, 30, 4.9620)
−147.6667
328
1
0
-
2
[21]
(88.724706796, 7.672652781, 1.317862596)
−83.2497…
1829
1
0
-
2
[31]
(88.6274, 7.9621, 1.3215)
−83.6898
1754
1
0
-
2
[33]
−83.2497,
…
1809
1
0
-
2
[24]
(88.875643887, 7.5637589, 1.3124563877)
−83.661573642
754
1
0
-
8
4
Ours
(43.1601, 44.9944, 69.9968, 1.2241)
460224.676188
23
1
0
-
1
[22]
(43.0473, 44.9317, 69.9359, 1.1338)
461200.00
968
1
0
-
1
[21]
(43.0137
,
…
,
44.8148
,
…
,
66.4239
,
…
,
1.1070
,
…)
623249.876,
…
2100
1
0
-
1
[33]
623249.8752,
…
1717
1
0
-
1
[24]
(43.0899785, 44.9997852, 66.419945664, 1.1069987564)
468479.996875421
1987
1
0
-
8Table 2
The numerical results for Examples5–10.
Example
Optimal solution
Optimal value
Iter
ε
5
Ours
(78.0, 33.0, 29.9957, 44.9999, 36.7753)
10122.4932
92
1
0
-
1
[22]
(78.2135, 33.2135, 29.6588, 44.757, 37.6808)
10088.51
122
1
0
-
1
[21]
(78, 32.9999,
…
,
29.9957
,
…
,
45, 36.7753,
…)
10122.4931,
…
341
1
0
-
1
[33]
10122.3811,
…
204
1
0
-
1
[24]
(78, 32.99998, 29.99737, 45, 36.77533)
10122.85643
324
1
0
-
4
6
Ours
(175.3433, 74.119872, 219.9999)
5651.37804758
2319
1
0
-
6
[24]
(109.32546781, 84.04821454, 214.32459429)
6217.46548921
612
1
0
-
8
[21]
(108.734706796, 85.126214158, 204.32459429)
6299.842427922
550
[34]
(107.4, 84.9, 204.5)
6300.00
7
Ours
(0.9999, 0.18181812, 0.98333213)
−10.363636
837
1
0
-
6
[24]
(0.99712235, 0.18184214, 0.98034321)
−10.305022,
…
3
1
0
-
8
8
Ours
(8.037732, 8.9999, 9, 9, 9, 1, 1, 1.15686, 1.15686, 1.15686, 50, 0, 1, 50, 50, 0)
156.2196
67
1
0
-
5
[22]
(8.03772, 9, 9, 9, 9, 1, 1, 1.1568, 1.1568, 1.1568, 50, 0, 1, 50, 50, 0)
156.2196
3
1
0
-
5
9
Ours
(5.0, 0.021584, 0.044603, 5.0)
5.8894162
3
1
0
-
1
[22]
(4.99671, 0.02158, 0.044603, 4.99584)
5.888618
12097
1
0
-
1
10
Ours
(5.0, 5.0, 0.13996, 1.177798, 0.94773)
28660.8648
2831
1
0
-
1
[22]
(4.992904, 4.99136, 0.1460728, 1.173758, 0.95455)
28745.107539
12014
1
0
-
1From the computational results, we can see that the proposed BRB algorithm can solve the problem (SGP) effectively. This illustrates the potential advantage of the proposed algorithm: not only is a feasible optimal solution obtained, but also less computational effort may be required for finding a better objective function value.


## 6. Conclusion

To globally solve the problem (SGP), a new branch-reduce-bound algorithm is proposed, based on an equivalent monotonic optimization problem and a linear relaxation method. The algorithm can attain the global minimum through the successive refinement of a linear relaxation and the subsequent solutions of a series of linear programming problems. To improve the convergence speed, two range reduction operations are proposed, which can cut away a large part of the region in which the global optimal solution of (SGP) does not exist. The convergence of the algorithm is proved and numerical results are reported to vindicate the feasibility and effectiveness of the proposed algorithm.



---

*Source: 163263-2014-03-30.xml*