# An Effective Branch and Bound Algorithm for Minimax Linear Fractional Programming

Authors: Hong-Wei Jiao; Feng-Hui Wang; Yong-Qiang Chen
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

An effective branch and bound algorithm is proposed for globally solving minimax linear fractional programming problem (MLFP). In this algorithm, the lower bounds are computed during the branch and bound search by solving a sequence of linear relaxation programming problems (LRP) of the problem (MLFP), which can be derived by using a new linear relaxation bounding technique, and which can be effectively solved by the simplex method. The proposed branch and bound algorithm is convergent to the global optimal solution of the problem (MLFP) through the successive refinement of the feasible region and solutions of a series of the LRP. Numerical results for several test problems are reported to show the feasibility and effectiveness of the proposed algorithm.


---

## Body

## 1. Introduction

Minimax linear fractional programming problem (MLFP) has become a subject of wide interest for practitioners and scientists [1–3], which has broad applications in various disciplines, for examples, system engineering [3], electronic science [4], and management science [5], and whose mathematical modeling can be formulated as follows:
(1)
(
MLFP
)
:
min
⁡
x
max
⁡
{
Ψ
1
(
x
)
,
Ψ
2
(
x
)
,
…
,
Ψ
p
(
x
)
}
s
.
t
.
x
∈
D
=
{
x
∈
R
n
∣
A
x
≤
b
,
x
≥
0
}
,
where
(2)
Ψ
j
(
x
)
=
∑
i
=
1
n
‍
c
j
i
x
i
+
d
j
∑
i
=
1
n
‍
e
j
i
x
i
+
f
j
,
j
=
1,2
,
…
,
p
,
∑
i
=
1
n
c
j
i
x
i
+
d
j and ∑
i
=
1
n
e
j
i
x
i
+
f
j are all affine functions such that ∑
i
=
1
n
c
j
i
x
i
+
d
j
>
0 and ∑
i
=
1
n
e
j
i
x
i
+
f
j
>
0, A
∈
R
m
×
n, b
∈
R
m, and D is a nonempty compact set.The minimax linear fractional programming problems (MLFP) pose significant theoretical and computational challenges. This is mainly because the problems (MLFP) possess multiple local optima that are not globally optimal. Therefore, it is necessary to put forward an effective global optimization algorithm for solving the minimax linear fractional programming problem (MLFP). During the past years, some algorithms have been proposed for solving the minimax linear fractional programming problem (MLFP), for instance, dual methods [2, 6, 7], parametric programming methods [8, 9], interior-point algorithms [10, 11], monotonic optimization approach [12], exact method [13], approximation algorithm [14], cutting plane algorithm [15], method of centers [16], inexact proximal point method [17], interval-type algorithm [18], and so on. Recently, based on the linear relaxation and branch and bound scheme, a solution algorithm has been developed for solving globally the minimax linear fractional programming problem (MLFP) [19]. Up to now, although there has been significant progress in the development of algorithms for solving the minimax linear fractional programming, to our knowledge, less work has been still done for globally solving the minimax linear fractional programming problem (MLFP).The purpose of this paper is to present a new global optimization algorithm for solving the minimax linear fractional programming problem (MLFP), and the goals of this research are threefold. First, we present a transformation of the problem; thus, the original problem (MLFP) is reformulated as an equivalent problem (EP). Second, in order to design an effective branch and bound algorithm for the equivalent problem (EP), a new linear relaxation bounding technique is presented, and, by utilizing this technique, the nonconvex programming problem (EP) is reduced to a sequence of linear relaxation programming problems, which can provide reliable lower bounds for the optimal value of the problem (EP) and are embedded into the branch and bound framework. The main computational operation in the algorithm only involves solving a sequence of linear relaxation programming subproblems that do not grow in size from iteration to iteration. Third, compare our algorithm (using new linear relaxation bounding technique) with the known algorithms (recent literatures) with respect to robustness (finding the optimum) and efficiencies (number of function evaluations), and the numerical experimental results show that the proposed algorithm is robust and effective.This paper is organized as follows. The next section firstly converts the problem (MLFP) into an equivalent problem (EP); a new linear relaxation bound method is presented, and then the linear relaxation programming of the problem (EP) is established. Section3 a branch and bound algorithm is proposed for globally solving the problem (MLFP), and the convergence property of the algorithm is given. In Section 4, we report the numerical results for solving some examples with the proposed algorithm. Finally, a few concluding remarks are given in Section 5.


## 2. Linear Relaxation Programming

In order to globally solve the problem (MLFP), we first compute the initial lower boundx
_
i
=
min
⁡
x
∈
D
x
i and upper bound x
¯
i
=
max
⁡
x
∈
D
x
i of each variable x
i and denote the initial rectangle by
(3)
X
0
=
{
x
∣
x
_
i
≤
x
i
≤
x
-
i
,
i
=
1
,
…
,
n
}
.Next, we can convert the problem (MLFP) into the following equivalent problem (EP), which has the same global optimal solution and optimal value as the problem (MLFP):(4)
(
EP
⁡
)
:
min
⁡
x
,
t
t
s
.
t
.
Ψ
j
(
x
)
-
t
≤
0
,
j
=
1
,
…
,
p
,
c
c
c
c
c
A
x
≤
b
,
x
≥
0
,
c
c
c
c
c
x
∈
X
0
.In the following, we only consider solving the equivalent problem (EP); the important step in the construction of a solution procedure for globally solving the problem (EP) is the establishment of a linear relaxation programming for computing the lower bounds of the optimal value for this problem. Here, we only need to construct linear lower bounding function ofΨ
j
(
x
) in constraint function. For each j
∈
{
1
,
…
,
p
}, we can let
(5)
h
j
(
x
)
=
ln
⁡
(
∑
i
=
1
n
‍
c
j
i
x
i
+
d
j
)
,
g
j
(
x
)
=
ln
⁡
(
∑
i
=
1
n
‍
e
j
i
x
i
+
f
j
)
,
Ψ
j
(
x
)
=
exp
⁡
[
h
j
(
x
)
-
g
j
(
x
)
]
.The detailed new linear relaxation bounding technique can be given as follows.First, we consider the functionh
j
(
x
)  (
j
=
1
,
…
,
p
). For convenience in expression, for ∀
x
∈
X
k
=
[
x
_
k
,
x
-
k
]
⊆
X
0, some notations are introduced as follows:
(6)
X
j
=
∑
i
=
1
n
‍
c
j
i
x
i
+
d
j
,
X
_
j
=
∑
i
=
1
n
‍
min
⁡
{
c
j
i
x
_
i
k
,
c
j
i
x
¯
i
k
}
+
d
j
,
X
¯
j
=
∑
i
=
1
n
‍
max
⁡
{
c
j
i
x
_
i
k
,
c
j
i
x
¯
i
k
}
+
d
j
,
K
j
=
ln
⁡
X
¯
j
-
ln
⁡
X
_
j
X
¯
j
-
X
_
j
,
h
j
l
(
x
)
=
ln
⁡
(
X
_
j
)
+
K
j
(
∑
i
=
1
n
‍
c
j
i
x
i
+
d
j
-
X
_
j
)
.
Obviously, by the characteristic of the concave function, we have
(7)
h
j
l
(
x
)
≤
h
j
(
x
)
.
Second, we consider the concave function g
j
(
x
)
=
ln
⁡
(
∑
i
=
1
n
e
j
i
x
i
+
f
j
)  (
j
=
1
,
…
,
p
) about the whole variable (
∑
i
=
1
n
e
j
i
x
i
+
f
j
); by the property of the concave function, we have
(8)
g
j
(
x
)
≤
g
j
(
x
mid
)
+
∇
g
j
(
x
mid
)
T
(
x
-
x
mid
)
=
g
j
u
(
x
)
,
where
(9)
x
mid
=
1
2
(
x
_
k
+
x
¯
k
)
,
∇
g
j
(
x
)
=
[
e
j
1
∑
i
=
1
n
‍
e
j
i
x
i
+
f
j
⋮
e
j
p
∑
i
=
1
n
‍
e
j
i
x
i
+
f
j
]
.
From (7) and (8), for all x
∈
X
k, we have
(10)
h
j
(
x
)
-
g
j
(
x
)
≥
h
j
l
(
x
)
-
g
j
u
(
x
)
.
Let
(11)
H
j
(
x
)
=
h
j
l
(
x
)
-
g
j
u
(
x
)
,
G
j
(
x
)
=
exp
⁡
(
H
j
(
x
)
)
.
By (5), (10), and (11), we have
(12)
G
j
(
x
)
=
exp
⁡
(
H
j
(
x
)
)
=
exp
⁡
(
h
j
l
(
x
)
-
g
j
u
(
x
)
)
≤
exp
⁡
(
h
j
(
x
)
-
g
j
(
x
)
)
=
Ψ
j
(
x
)
.Third, we consider the functionG
j
(
x
)
(
j
=
1
,
…
,
p
). By the property of the convex function, we have
(13)
G
j
(
x
)
≥
G
j
(
x
mid
)
+
∇
G
j
(
x
mid
)
T
(
x
-
x
mid
)
,
where
(14)
∇
G
j
(
x
mid
)
=
(
K
j
[
c
j
1
⋮
c
j
n
]
-
∇
g
j
(
x
mid
)
)
exp
⁡
(
H
j
(
x
mid
)
)
.
Let
(15)
G
j
l
(
x
)
=
G
j
(
x
mid
)
+
∇
G
j
(
x
mid
)
T
(
x
-
x
mid
)
,
and, by (12) and (13), we have
(16)
G
j
l
(
x
)
≤
G
j
(
x
)
≤
Ψ
j
(
x
)
.
Therefore, we can follow the linear lower bounding function G
j
l
(
x
) of Ψ
j
(
x
) for each j
∈
{
1
,
…
,
p
}, which underestimates the function Ψ
j
(
x
) as follows:
(17)
G
j
l
(
x
)
=
G
j
(
x
mid
)
+
∇
G
j
(
x
mid
)
T
(
x
-
x
mid
)
.According to the above discussion, for∀
X
k
⊆
X
0, we can construct the linear relaxation programming (LRP) of the problem (EP) in X
k as follows:
(18)
(
LRP
)
:
min
⁡
t
s
.
t
.
G
j
l
(
x
)
-
t
≤
0
,
j
=
1
,
…
,
p
,
s
.
t
.
A
x
≤
b
,
s
.
t
.
x
∈
X
k
.Based on the above construction method of the linear relaxation programming problem, for∀
X
k
⊆
X
0, LRP
(
X
k
) provides a valid lower bound for the optimal value of EP
⁡
(
X
k
).The following theorem will ensure that eachG
j
l
(
x
) will approximate the corresponding function Ψ
j
(
x
) as ∥
x
-
k
-
x
_
k
∥
→
0; that is, the optimal solution of the LRP
(
X
k
) will approximate the optimal solution of EP
⁡
(
X
k
).Theorem 1.
For∀
x
∈
X
k
=
[
x
_
k
,
x
-
k
]
⊆
X
0, for each j
=
1
,
…
,
p, and then the error Θ
j
=
Ψ
j
(
x
)
-
G
j
l
(
x
)
→
0 as ∥
x
-
k
-
x
_
k
∥
→
0.Proof.
Let(19)
Θ
j
=
[
Ψ
j
(
x
)
-
G
j
(
x
)
]
+
[
G
j
(
x
)
-
G
j
l
(
x
)
]
=
Θ
j
1
+
Θ
j
2
,
and then it is obvious that Θ
j
1
≥
0 and Θ
j
2
≥
0.
First, we consider the differenceΘ
j
1. Let
(20)
Ψ
^
j
(
x
)
=
ln
⁡
(
h
j
(
x
)
)
-
ln
⁡
(
g
j
(
x
)
)
=
ln
⁡
(
∑
i
=
1
n
‍
c
j
i
x
i
+
d
j
)
-
ln
⁡
(
∑
i
=
1
n
‍
e
j
i
x
i
+
f
j
)
,
and it follows that
(21)
|
Θ
j
1
|
=
|
exp
⁡
(
ln
⁡
(
∑
i
=
1
n
‍
c
j
i
x
i
+
d
j
)
-
ln
⁡
(
∑
i
=
1
n
‍
e
j
i
x
i
+
f
j
)
)
-
exp
⁡
(
H
j
(
x
)
)
∑
i
=
1
n
‍
|
=
|
exp
⁡
(
Ψ
^
j
(
x
)
)
-
exp
⁡
(
H
j
(
x
)
)
|
≤
∥
Ψ
^
j
(
x
)
-
H
j
(
x
)
∥
sup
⁡
σ
j
∈
L
(
Ψ
^
j
(
x
)
,
H
j
(
x
)
)
exp
⁡
(
σ
j
)
,
where
(22)
L
(
Ψ
^
j
(
x
)
,
H
j
(
x
)
)
=
α
Ψ
^
j
(
x
)
+
(
1
-
α
)
H
j
(
x
)
,
2222222222222222222222
for
∀
α
∈
[
0,1
]
.
Let(23)
Θ
j
1.1
=
ln
⁡
(
∑
i
=
1
n
‍
c
j
i
x
i
+
d
j
)
-
[
ln
⁡
(
X
_
j
)
+
K
j
(
∑
i
=
1
n
‍
c
j
i
x
i
+
d
j
-
X
_
j
)
]
,
Θ
j
1.2
=
g
j
(
x
mid
)
+
∇
g
j
(
x
mid
)
T
(
x
-
x
mid
)
-
g
j
(
x
)
,
We have
(24)
Ψ
^
j
(
x
)
-
H
j
(
x
)
=
{
ln
⁡
(
∑
i
=
1
n
‍
c
j
i
x
i
+
d
j
)
-
ln
⁡
(
∑
i
=
1
n
‍
e
j
i
x
i
+
f
j
)
}
=
-
{
ln
⁡
(
X
_
j
)
+
K
j
(
∑
i
=
1
n
‍
c
j
i
x
i
+
d
j
-
X
_
j
)
-
g
j
(
x
mid
)
-
∇
g
j
(
x
mid
)
T
(
x
-
x
mid
)
∑
i
=
1
n
‍
}
=
Θ
j
1.1
+
Θ
j
1.2
.
Since Θ
j
1.1 is a concave function about (
∑
i
=
1
n
c
j
i
x
i
+
d
j
), we can know that Θ
j
1.1 can attain the maximum Θ
j
1.1
max
⁡ at the point ∑
i
=
1
n
c
j
i
x
i
+
d
j
=
1
/
K
j. Let u
j
=
X
¯
j
/
X
_
j. Then, through computing, we derive
(25)
Θ
j
1.1
max
⁡
=
ln
⁡
u
j
u
j
-
1
-
1
-
ln
⁡
ln
⁡
u
j
u
j
-
1
.
Since u
j
→
1 as ∥
x
-
k
-
x
_
k
∥
→
0, we have Θ
j
1.1
max
⁡
→
0 as ∥
x
-
k
-
x
_
k
∥
→
0.
One has(26)
Θ
j
1.2
=
g
j
(
x
mid
)
+
∇
g
j
(
x
mid
)
T
(
x
-
x
mid
)
-
g
j
(
x
)
=
∇
g
j
(
x
mid
)
T
(
x
-
x
mid
)
-
∇
g
j
(
η
)
T
(
x
-
x
mid
)
≤
∥
∇
2
g
j
(
ρ
)
∥
∥
η
-
x
mid
∥
∥
x
-
x
mid
∥
,
where η and ρ are constant vectors, which satisfy
(27)
g
j
(
x
)
-
g
j
(
x
mid
)
=
∇
g
j
(
η
)
T
(
x
-
x
mid
)
,
∇
g
j
(
x
mid
)
-
∇
g
j
(
η
)
=
∇
2
g
j
(
ρ
)
(
η
-
x
mid
)
.
Since ∇
2
g
j
(
x
) is continuous, and X is a compact set, there exists some M
>
0 such that
(28)
∥
∇
2
g
j
(
x
)
∥
≤
M
.
By (26), we have
(29)
Θ
j
1.2
≤
M
∥
x
-
k
-
x
_
k
∥
2
,
Furthermore, we have Θ
j
1.2
→
0 as ∥
x
-
k
-
x
_
k
∥
→
0.
Therefore, we have(30)
Ψ
^
j
(
x
)
-
H
j
(
x
)
=
Θ
j
1.1
+
Θ
j
1.2
⟶
0
as
∥
x
-
k
-
x
_
k
∥
⟶
0
.
Sinceexp
⁡
(
σ
j
) is a continuous and bounded function about x, there exists some M
-
>
0 such that |
exp
⁡
(
σ
j
)
|
≤
M
-. Therefore, by (30), we have
(31)
Θ
j
1
≤
M
-
|
Ψ
^
j
(
x
)
-
H
j
(
x
)
|
⟶
0
as
∥
x
-
k
-
x
_
k
∥
⟶
0
.
Second, we consider the difference Θ
j
2, and it follows that
(32)
Θ
j
2
=
G
j
(
x
)
-
G
j
l
(
x
)
=
G
j
(
x
)
-
[
G
j
(
x
mid
)
+
∇
G
j
(
x
mid
)
T
(
x
-
x
mid
)
]
=
∇
G
j
(
γ
)
T
(
x
-
x
mid
)
-
∇
G
j
(
x
mid
)
T
(
x
-
x
mid
)
≤
∥
∇
2
G
j
(
β
)
∥
∥
γ
-
x
mid
∥
∥
x
-
x
mid
∥
,
where γ and β are constant vectors, which satisfy
(33)
G
j
(
x
)
-
G
j
(
x
mid
)
=
∇
G
j
(
γ
)
T
(
x
-
x
mid
)
,
∇
G
j
(
γ
)
-
∇
G
j
(
x
mid
)
=
∇
2
G
j
(
β
)
(
γ
-
x
mid
)
.
Since ∇
2
G
j
(
x
) is a continuous function, and X is a compact set, there exists some M
^
>
0 such that
(34)
∥
∇
2
G
j
(
x
)
∥
≤
M
^
.
By (32), we have
(35)
Θ
j
2
≤
M
^
∥
x
-
k
-
x
_
k
∥
2
.
Furthermore, we have
(36)
Θ
j
2
⟶
0
as
∥
x
-
k
-
x
_
k
∥
⟶
0
.
By (19), (31), and (36), we can derive that
(37)
Θ
j
=
[
Ψ
j
(
x
)
-
G
j
(
x
)
]
+
[
G
j
(
x
)
-
G
j
l
(
x
)
]
=
Θ
j
1
+
Θ
j
2
⟶
0
as
∥
x
-
k
-
x
_
k
∥
⟶
0
.
By the above discussion, it is obvious that the conclusion is followed.


## 3. Algorithm and Its Convergence

In this section, based on the former linear relaxation method, we will present a branch and bound algorithm for globally solving problem (EP). There are three fundamental operations in the proposed algorithm: a branching operation, an updating upper bounds operation, and an updating lower bounds operation.The first fundamental operation iteratively subdivides the investigated rectangleX into two subrectangles. During the process of iteration of the algorithm, the branching operation produces a more refined partition that cannot yet be excluded from further consideration in finding the global optimum for the problem (EP). In this paper, we choose a simple and standard branching rule. This branching rule is enough to ensure the convergence of the algorithm since it drives the intervals shrinking to a singleton for all variables along any infinite branch of the branch and bound tree. Consider any node subproblem identified by the hyperrectangle X
=
[
x
_
,
x
¯
]
⊆
X
0. This branching rule is as follows.(a)
Letq
=
arg
max
⁡
{
x
¯
i
-
x
_
i
:
i
=
1
,
…
,
n
}.
(b)
Let(38)
X
^
1
=
{
x
_
q
+
x
¯
q
2
x
∈
R
n
∣
x
_
i
≤
x
i
≤
x
¯
i
,
i
≠
q
,
x
_
q
≤
x
q
≤
x
_
q
+
x
¯
q
2
}
,
X
^
2
=
{
x
_
q
+
x
¯
q
2
x
∈
R
n
∣
x
_
i
≤
x
i
≤
x
¯
i
,
i
≠
q
,
x
_
q
+
x
¯
q
2
≤
x
q
≤
x
¯
q
}
.By this branching rule, the rectangle X is subdivided into two subrectangles X
^
1 and X
^
2.The second fundamental operation is to update the lower bounds of the optimal value of the problem (EP). This main computation needs to solve a sequence of linear relaxation programming problems, which can be easily solved by using the simplex method.The third fundamental operation is to update the upper bounds of the optimal value of the problem (EP). The upper bounds can be updated by computing the objective function values of the original problem (MLFP) and the equivalent problem (EP) which corresponds to optimal solution of each linear relaxation programming problem, respectively.The setF in the algorithm is the set of fathomed subrectangles X of X
0. Let LB
(
X
k
) refer to the optimal objective function value of the problem (LRP) on the sub-hyper-rectangles X
k and x
k
=
x
(
X
k
) refer to an element of corresponding argmin. The basic steps of the proposed algorithm are summarized as follows.Algorithm Statement. Consider the followingStep0. Choose ϵ
≥
0. Let X
0
=
{
x
∣
x
_
i
≤
x
i
≤
x
-
i
,
i
=
1
,
…
,
n
}
,
U
B
0
=
+
∞. Find an optimal solution (
x
0
,
t
0
) and the optimal value υ
(
X
0
) of the LRP
(
X
0
). Set
(39)
L
B
0
:
=
LB
(
X
0
)
=
υ
(
X
0
)
,
(
x
c
,
t
c
)
=
(
x
0
,
t
0
)
.
For the given feasible tolerance ϵ
1, if (
x
c
,
t
c
) is feasible to the problem EP(
X
0
), update U
B
0
=
t
c, if necessary. Set
(40)
U
B
0
=
min
⁡
{
U
B
0
,
max
⁡
{
Ψ
1
(
x
c
)
,
Ψ
2
(
x
c
)
,
…
,
Ψ
p
(
x
c
)
}
}
.
If U
B
0
-
L
B
0
≤
ϵ, stop; x
c is a global ϵ-optimal solution for the problem (MLFP). Otherwise, let the set of active node Ω
0
=
X
0 and F
:
=
∅,  k
=
1, and go to Step k.Step  k. k
≥
1.Step  k
1. Set
(41)
U
B
k
=
U
B
k
-
1
.
Subdivide X
k
-
1 into two n-dimensional rectangles X
k
,
1, X
k
,
2 via the rectangular bisection process. Denote the set of new partitioned rectangles by X
¯
k. Set F
=
F
∪
X
k
-
1.Step  k
2. For each j
=
1,2, compute υ
(
X
k
,
j
), and if υ
(
X
k
,
j
)
≠
+
∞, find an optimal solution (
x
k
,
j
,
t
k
,
j
) for the problem EQ(X) with X
=
X
k
,
j. For each j
=
1,2, set
(42)
LB
(
X
k
,
j
)
=
υ
(
X
k
,
j
)
.
Set s
=
0.Step  k
3. Set s
=
s
+
1. If s
>
2, go to Step k
7. Otherwise, continue.Step  k
4. If LB
(
X
k
,
s
)
≥
U
B
k, set F
=
F
∪
X
k
,
s and go to Step k
6. Otherwise, continue.Step  k
5. For the given feasible tolerance ϵ
1, if (
x
k
,
s
,
t
k
,
s
) is feasible to the EP(
X
0
), update U
B
k
=
t
k
,
s, if necessary. Let
(43)
U
B
k
=
min
⁡
{
U
B
k
,
max
⁡
{
Ψ
1
(
x
k
,
s
)
,
Ψ
2
(
x
k
,
s
)
,
…
,
Ψ
p
(
x
k
,
s
)
}
}
.
If
(44)
U
B
k
<
max
⁡
{
Ψ
1
(
x
k
,
s
)
,
Ψ
2
(
x
k
,
s
)
,
…
,
Ψ
p
(
x
k
,
s
)
}
,
go to Step k
6. If
(45)
U
B
k
=
max
⁡
{
Ψ
1
(
x
k
,
s
)
,
Ψ
2
(
x
k
,
s
)
,
…
,
Ψ
p
(
x
k
,
s
)
}
,
set
(46)
x
c
=
x
k
,
s
,
F
=
F
∪
{
X
∈
Ω
k
-
1
∣
LB
(
X
)
≥
U
B
k
}
,
and continue.Step  k
6. Go to Step k
3.Step  k
7. Set
(47)
Ω
k
=
{
X
∣
X
∈
(
Ω
k
-
1
∪
{
X
k
,
1
,
X
k
,
2
}
)
,
X
∉
F
}
.Step  k
8. Set L
B
k
=
min
⁡
{
LB
(
X
)
∣
X
∈
Ω
k
}, and let X
k
∈
Ω
k satisfying L
B
k
=
LB
(
X
k
). If U
B
k
-
L
B
k
≤
ϵ, stop; x
c is a global ϵ-optimal solution for the problem (MLFP), and v
=
max
⁡
{
Ψ
1
(
x
c
)
,
Ψ
2
(
x
c
)
,
…
,
Ψ
p
(
x
c
)
} is global optimal value for the problem EP(
X
0
). Otherwise, set k
=
k
+
1 and go to Step k.The convergence properties of the proposed algorithm are given as follows.Theorem 2.
If the proposed algorithm terminates in finite steps, then a global optimal solution of the problem (MLFP) is obtained when the algorithm is terminated.Proof.
Assume that the algorithm is terminated finitely atx
k. Obviously, L
B
k
=
U
B
k when it is terminated at the k
t
h iteration; therefore, x
k is a global optimal solution of the problem (MLFP).Theorem 3.
If the algorithm generates an infinite sequence{
x
k
}, then every accumulation point x
* of this sequence is a global optimal solution of the problem (MLFP).Proof.
Letx
* be an accumulation point of the sequence {
x
k
}, and let {
x
k
q
} be a subsequence {
x
k
q
} of the sequence {
x
k
} which is convergent to x
*. Obviously, in the proposed algorithm, the lower bound sequence {
L
B
k
} is monotonic increasing and the upper bound sequence {
U
B
k
} is monotonic decreasing, so that {
L
B
k
} and {
U
B
k
} are convergent and
(48)
lim
⁡
k
→
∞
U
B
k
=
lim
⁡
q
→
∞
U
B
k
q
=
lim
⁡
q
→
∞
max
⁡
{
Ψ
1
(
x
k
q
)
,
Ψ
2
(
x
k
q
)
,
…
,
Ψ
p
(
x
k
q
)
}
=
max
⁡
{
Ψ
1
(
x
*
)
,
Ψ
2
(
x
*
)
,
…
,
Ψ
p
(
x
*
)
}
.
Without loss of generality, we assume thatx
k
q is the solution of the problem (LRP) on X
k
q which satisfies X
k
q
+
1
⊆
X
k
q,  q
=
1,2
,
…. Because the proposed rectangle partition is exhaustive; that is, lim
⁡
q
→
∞
X
k
q
=
x
*, and, from Theorem 1, we have
(49)
0
≤
U
B
k
q
-
L
B
k
q
≤
max
⁡
{
|
Ψ
1
(
x
k
q
)
-
G
1
l
(
x
k
q
)
|
,
…
,
|
Ψ
p
(
x
k
q
)
-
G
p
l
(
x
k
q
)
|
}
⟶
0
as
q
⟶
∞
.
Thus,
(50)
lim
⁡
q
→
∞
(
U
B
k
q
-
L
B
k
q
)
=
0
.
Hence,
(51)
lim
⁡
k
→
∞
L
B
k
=
lim
⁡
q
→
∞
(
U
B
k
q
-
(
U
B
k
q
-
L
B
k
q
)
)
=
lim
⁡
q
→
∞
U
B
k
q
=
max
⁡
{
Ψ
1
(
x
*
)
,
Ψ
2
(
x
*
)
,
…
,
Ψ
p
(
x
*
)
}
.
Therefore, x
* is a global optimal solution of the problem (MLFP).


## 4. Numerical Experiments

To verify the performance of our algorithm, several test examples in recent literatures are implemented on on a Intel(R) Core(TM)2 Duo CPU (1.58 GHZ) microcompute; the algorithm program is coded in C++, and each linear relaxation programming problem is solved by using simplex method, and the convergence tolerance is set toϵ
=
5
×
1
0
-
8 in our experiment. For the test problems, numerical results are illustrated in Table 1. For Examples 1–5, feasible errors ϵ
1 are set by 0.005, 0.005, 0,0.005, and 0.001, respectively.Table 1
Computational results for test Examples1–4.
Example
References
Optimal solution
Iter
L
max
⁡
Time (s)
Example1
ours
(1.015569395,  0.591850539,  1.401565828)
1
2
0.00332836
[12]
(1.015695,  0.590494,  1.403675)
1
—
0.06
[19]
(1.015678086,  0.590676676,  1.403391837)
6
5
0.01533491
Example2
ours
(1.5,  1.5)
3
2
0.0025344
[12]
(1.5,  1.5)
1
—
0.00
[19]
(1.5,  1.5)
6
7
0.00579627
Example3
ours
(1.016666667,  0.55,  1.45)
5
2
0.0110939
[19]
(1.016666667,  0.55,  1.45)
8
8
0.02143792
Example4
ours
(1.008333333,  0.5,  1.45)
3
2
0.00856142
[19]
(1.008333333,  0.5,  1.45)
7
8
0.02374296In Tables1 and 2, the notations have been used for column headers: Iter: number of algorithm iteration; L
max
⁡: the maximal number of algorithm active nodes necessary; time: execution time of algorithm in seconds.Table 2
Numerical results for Example5.
Example5
Our algorithm
Algorithm of [19]
(
p
,
M
,
N
)
Iter
L
max
⁡
Time (s)
Iter
L
max
⁡
Time (s)
(
3,4
,
5
)
59
16
0.18905
90
88
0.308533
(
5,5
,
5
)
173
40
0.560235
440
438
2.070590
(
5,5
,
6
)
211
46
0.996647
328
314
1.954055
(
6,6
,
5
)
88
18
0.382545
348
348
2.012132
(
7,5
,
6
)
88
16
0.545829
174
159
1.315186
(
30,6
,
6
)
74
13
2.21828
151
148
6.439019
(
50,6
,
6
)
29
2
2.08805
95
81
9.848997
(
10,7
,
6
)
454
131
3.79913
685
659
7.590868
(
7,7
,
7
)
154
30
1.30391
242
235
2.713118
(
7,7
,
8
)
733
175
7.4577
8913
8901
157.815951
(
20,9
,
8
)
55
6
1.65562
125
123
4.672965
(
9,7
,
10
)
2243
570
42.8553
3581
3400
79.042373
(
10,10,10
)
258
20
5.69239
450
200
11.414042In Table1, optimal value is denoted by objective function value of the optimal solution in computational procedure of [19] and this paper, respectively.Example 1 (see [12, 19]).
Consider(52)
min
⁡
max
⁡
{
3
x
1
+
x
2
-
2
x
3
+
0.8
2
x
1
-
x
2
+
x
3
,
4
x
1
-
2
x
2
+
x
3
7
x
1
+
3
x
2
-
x
3
}
s
.
t
.
x
1
+
x
2
-
x
3
≤
1
,
s
.
t
.
-
x
1
+
x
2
-
x
3
≤
-
1
,
s
.
t
.
12
x
1
+
5
x
2
+
12
x
3
≤
34.8
,
s
.
t
.
12
x
1
+
12
x
2
+
7
x
3
≤
29.1
,
s
.
t
.
-
6
x
1
+
x
2
+
x
3
≤
-
4.1
,
s
.
t
.
1.0
≤
x
1
≤
1.1
,
s
.
t
.
0.55
≤
x
2
≤
0.65
,
s
.
t
.
1.35
≤
x
3
≤
1.45
.Example 2 (see [12, 19]).
Consider(53)
max
⁡
min
⁡
{
37
x
1
+
73
x
2
+
13
13
x
1
+
13
x
2
+
13
,
63
x
1
-
18
x
2
+
39
13
x
1
+
26
x
2
+
13
}
s
.
t
.
5
x
1
-
3
x
2
=
3
,
s
.
t
.
0
≤
x
1
≤
3
.
This example is originally presented in Phuong and Tuy [12], which has the same global optimal solution as the following problem 2
′′:
(54)
min
⁡
max
⁡
{
13
x
1
+
13
x
2
+
13
37
x
1
+
73
x
2
+
13
,
13
x
1
+
26
x
2
+
13
63
x
1
-
18
x
2
+
39
}
s
.
t
.
5
x
1
-
3
x
2
=
3
,
s
.
t
.
0
≤
x
1
≤
3
.
Therefore, we can use the proposed algorithm to globally solve Example 2 by solving the problem 2
′′.Example 3 (see [19]).
Consider(55)
min
⁡
max
⁡
{
2
x
1
+
2
x
2
-
x
3
+
0.9
x
1
-
x
2
+
x
3
,
3
x
1
-
x
2
+
x
3
8
x
1
+
4
x
2
-
x
3
}
s
.
t
.
x
1
+
x
2
-
x
3
≤
1
,
s
.
t
.
-
x
1
+
x
2
-
x
3
≤
-
1
,
s
.
t
.
12
x
1
+
5
x
2
+
12
x
3
≤
34.8
,
s
.
t
.
12
x
1
+
12
x
2
+
7
x
3
≤
29.1
,
s
.
t
.
-
6
x
1
+
x
2
+
x
3
≤
-
4.1
,
s
.
t
.
1.0
≤
x
1
≤
1.2
,
s
.
t
.
0.55
≤
x
2
≤
0.65
,
s
.
t
.
1.35
≤
x
3
≤
1.45
.Example 4 (see [19]).
Consider(56)
min
⁡
max
⁡
{
3
x
1
+
x
2
-
2
x
3
+
0.8
2
x
1
-
x
2
+
x
3
,
4
x
1
-
2
x
2
+
x
3
7
x
1
+
3
x
2
-
x
3
,
3
x
1
+
2
x
2
-
x
3
+
1.9
x
1
-
x
2
+
x
3
,
4
x
1
-
x
2
+
x
3
8
x
1
+
4
x
2
-
x
3
}
s
.
t
.
x
1
+
x
2
-
x
3
≤
1
,
s
.
t
.
-
x
1
+
x
2
-
x
3
≤
-
1
,
s
.
t
.
12
x
1
+
5
x
2
+
12
x
3
≤
34.8
,
s
.
t
.
12
x
1
+
12
x
2
+
7
x
3
≤
29.1
,
s
.
t
.
-
6
x
1
+
x
2
+
x
3
≤
-
4.1
,
s
.
t
.
1.0
≤
x
1
≤
1.2
,
s
.
t
.
0.55
≤
x
2
≤
0.65
,
s
.
t
.
1.35
≤
x
3
≤
1.45
.Example 5.
Consider(57)
min
⁡
max
⁡
{
∑
i
=
1
n
‍
c
1
i
x
i
+
d
1
∑
i
=
1
n
‍
e
1
i
x
i
+
f
1
,
∑
i
=
1
n
‍
c
2
i
x
i
+
d
2
∑
i
=
1
n
‍
e
2
i
x
i
+
f
2
,
…
,
∑
i
=
1
n
‍
c
p
i
x
i
+
d
p
∑
i
=
1
n
‍
e
p
i
x
i
+
f
p
}
s
.
t
.
A
x
≤
b
,
s
.
t
.
0
≤
x
i
≤
3
,
i
=
1
,
…
,
n
,
where A is an m
×
n matrix, b is an m dimension vector, all elements of c
j
i, e
j
i, j
=
1
,
…
,
p, i
=
1
,
…
,
n, are randomly generated between 0 and 1; all elements of d
j, f
j, j
=
1
,
…
,
p are randomly generated between 0 and p; all elements of A are randomly generated between 0 and 1; all elements of b are randomly generated between 0 and 16.In Table2, the notations have been also used for column headers: p: the number of linear fractional functions in the objective function; m: represents the number of rows for A; n: stands for the dimension of considered problem. From the experimental results in Table 2, it is seen that our algorithm can effectively solve the minimax linear fractional programming problem (MLFP) with large scale number of fractional functions.


## 5. Concluding Remarks

In this paper, an effective branch and bound algorithm is proposed for globally solving the minimax linear fractional programming problem (MLFP). In this algorithm, the lower bound is computed during the branch and bound search by solving linear relaxation programming (LRP) of the problem (MLFP), which can be derived by using the new linear relaxation bounding technique and can be effectively solved by using the simplex method or interior point algorithm. The proposed algorithm is convergent to the global minimum of the problem (MLFP) through the successive refinement of the feasible region and solutions of a series of the LRP. Numerical results for several test problems have been reported to show the feasibility and effectiveness of the proposed algorithm. It is hoped that the ideas and methods used to construct the algorithm will offer useful tools for solving the minimax linear fractional programming problem.



---

*Source: 160262-2014-06-15.xml*