# An Effective Algorithm for Globally Solving Sum of Linear Ratios Problems

Authors: Hongwei Jiao; Lei Cai; Zhisong Hou; Chunyang Bai
Journal: Journal of Control Science and Engineering
 (2017)

---

## Abstract

In this study, we propose an effective algorithm for globally solving the sum of linear ratios problems. Firstly, by introducing new variables, we transform the initial problem into an equivalent nonconvex programming problem. Secondly, by utilizing direct relaxation, the linear relaxation programming problem of the equivalent problem can be constructed. Thirdly, in order to improve the computational efficiency of the algorithm, an out space pruning technique is derived, which offers a possibility of pruning a large part of the out space region which does not contain the optimal solution of the equivalent problem. Fourthly, based on out space partition, by combining bounding technique and pruning technique, a new out space branch-and-bound algorithm for globally solving the sum of linear ratios problems (SLRP) is designed. Finally, numerical experimental results are presented to demonstrate both computational efficiency and solution quality of the proposed algorithm.


---

## Body

## 1. Introduction

Sum of linear ratios problems (SLRP) have broad wide applications in information technology, control science and engineering, transportation design, government plan, economy and finance [1–5], and so on. In these applications, especially, the number of linear ratios is usually less than four or five. In addition, due to the fact that the sum of linear ratios problems (SLRP) possess generally multiple local optimal solutions that are not globally optimal, the kinds of problems pose significant theoretical difficulty and computational complexity. Therefore, they have attracted interest of many researchers and practitioners.In this paper, we will investigate the following sum of linear ratios problems:(1)SLRP:v=max⁡Gy=∑i=1pφiyϕiys.t.y∈Λ≜y∈Rn∣Ay≤b,y≥0,where A∈Rm×n,  b∈Rm,  φi(y), and ϕi(y) are all affine functions, Λ is a nonempty bounded constraint set, and for any y∈Λ,  ϕi(y)≠0,  i=1,2,…,p.During the past two decades, with the assumption that the denominatorφiy≥0 and the numerator ϕiy>0 for any y∈Λ, many optimization algorithms have been developed for globally solving the sum of linear ratios problems (SLRP), for example, simplex algorithms, image space algorithm, branch-and-bound algorithms, and monotonic algorithm (see [6–17]). Recently, Jiao et al. [18–20] presented three branch-and-bound algorithms for sum of linear ratios problem by constructing different linear relaxation technique; Jiao et al. [21] presented a new two-level relaxation algorithm for generalized linear multiplicative programming with generalized polynomial constraints, which can be also used to globally solve the sum of linear ratios problem (SLRP) investigated in this paper. In addition, several new algorithms [22–25] have been also proposed for solving linear sum-of-ratios and nonlinear sum-of-ratios problems.In this paper, we shall present a new out space branch-and-bound algorithm for the sum of linear ratios problems (SLRP) using out space pruning technique. Firstly, we transform the initial problem into the equivalent nonconvex programming problem by introducing new variables. Next, the linear relaxation programming problem of the equivalent problem can be constructed by utilizing direct relaxation. Secondly, by making full use of the special structure of the equivalent problem and the branch-and-bound algorithm, an out space pruning technique is derived to improve the computational efficiency of the proposed algorithm, which offers a possibility of pruning a large part of the investigated out space region which does not contain the global optimal solution of the equivalent problem. Thirdly, by combining bounding technique and pruning technique, a new out space branch-and-bound algorithm is designed for globally solving the sum of linear ratios problems (SLR). Finally, numerical experimental results are presented to demonstrate both computational efficiency and solution quality of the proposed algorithm.The remaining sections of this paper are organized as follows. At first, in Section2, by introducing new variables the equivalent nonconvex programming problem of the initial problem is introduced. Next, by utilizing direct relaxation the linear relaxation programming problem of the equivalent problem is constructed. Second, an out space pruning technique is derived by making full use of the special structure of the equivalent problem and the branch-and-bound algorithm in Section 3. Third, a new out space branch-and-bound algorithm and its global convergence are described in Section 4. Fourth, numerical experiments and their computational results are presented in Section 5. Finally, the concluding remarks of this paper are drawn.


## 2. Equivalent Problem and Its Linear Relaxation

In this section, to globally solve the problem (SLRP), by the continuity of the linear ratioφi(y)/ϕi(y), we know that ϕiy>0 or ϕiy<0. Here, without loss of generality, we can assume that (2)ϕiy>0,i=1,2,…,T;ϕiy<0,i=T+1,T+2,…,pexcept for the above assumptions, for each i∈1,2,…,p, since (3)φiyϕiy=φiy+Miϕiyϕiy-Mi,where Mi is an appropriate real number such that φi(y)+Miϕiy≥0. Thus, without loss of generality, by some proper transformation we can always guarantee that the numerator of each ratio is greater than or equal to 0.Let(4)Ui0=1miny∈Λ⁡ϕiy,i=1,2,…,T,1-maxy∈Λ⁡ϕiy,i=T+1,…,p;Li0=1maxy∈Λ⁡ϕiy,i=1,2,…,T,1-miny∈Λ⁡ϕiy,i=T+1,…,p. And construct the initial box (5)Z0=z∈Rp∣Li0≤zi≤Ui0,i=1,2,…,p; then the problem (SLRP) can be converted into the equivalent problem (EQ) as follows. (6)EQZ0:vZ0=max⁡H0y,z=∑i=1Tziφiy-∑i=T+1pziφiys.t.Hiy,z=ziϕiy≤1,i=1,2,…,T,Hiy,z=ziϕiy≤-1,i=T+1,T+2,…,p,y∈Λ,z∈Z0.The key equivalence theorem for the problem (SLRP) and the EQ(Z0) is described as follows.Theorem 1.
If(y∗,z1∗,…,zp∗) is a global optimum point of the problem EQ(Z0), then y∗ is a global optimum point of the problem (SLRP). On the contrary, if y∗ is a global optimum point of the problem (SLRP), then y∗,z1∗,…,zp∗ is a global optimum point of the problem EQ(Z0) with zi∗=1/ϕi(y∗),  i=1,2,…,T,  zi∗=1/-ϕi(y∗),  i=T+1,T+2,…,p.Proof.
The conclusion can be easily drawn, so the proof is omitted.From Theorem1, to solve the problem (SLRP), we may globally solve its equivalent nonconvex programming problem EQ(Z0) instead.For each boxZk=z∈Rp∣Lik≤zi≤Uik,i=1,2,…,p⊆Z0, some notations and functions of this paper are listed as follows: (7)H0Uy=∑i=1TUikφiy-∑i=T+1pLikφiy;H0Ly=∑i=1TLikφiy-∑i=T+1pUikφiy;HiUy=Uikϕiy,i=1,2,…,p;HiLy=Likϕiy,i=1,2,…,p.Theorem 2.
For the functionsHiU(y),  HiL(y),  Hi(y,z),  i=0,1,2,…,p, where y∈Λ,z∈Zk⊆Z0, we have the following two conclusions:(i)
HiU(y)≥Hi(y,z)≥HiL(y),i=0,1,2,…,p.(ii)
lim∥Uk-Lk∥→0[HiU(y)-Hi(y,z)]=lim∥Uk-Lk∥→0[Hi(y,z)-HiL(y)]=0.Proof.
The proof can be easily followed, therefore here it is omitted.From the above Theorem2, for any Zk⊆Z0, the corresponding linear relaxation programming problem LRPZk of the problem EQZk can be established as follows, which can offer a reliable upper bound for the global optimum of EQZk.(8)LRPZk:UBZk=max⁡H0Uy=∑i=1TUikφiy-∑i=T+1pLikφiys.t.HiLy=Likϕiy≤1,i=1,2,…,T,HiLy=Likϕiy≤-1,i=T+1,T+2,…,p,y∈Λ.


## 3. Out Space Pruning Technique

For any boxZk⊆Z0, we need to recognize whether or not Zk contains global optimum point of the problem (EQ). Thus, in this section, we shall construct an out space pruning technique for pruning a part of the investigated out space region which does not contain the global optimum point of the problem (SLRP) and use the technique to improve the computational efficiency of the proposed algorithm. The proposed new out space pruning technique aims at replacing the box Zk=Lk,Uk with a smaller box Z′=L′,U′ without pruning any global optimum point of the problem (EQ).We assume, without loss of generality, thatLB is a currently known lower bound of the global optimum value of the EQ(Z0) and that v(Zk) denote the maximum value of the problem H0(y,z) over Zk and D and set (9)li0=miny∈Λ⁡φiy,i=1,2,…,p,ui0=maxy∈Λ⁡φiy,i=1,2,…,p,RUBk=∑i=1TUikui0-∑i=T+1pLikli0,ρik=LB-RUBk+Uikui0ui0,i=1,2,…,T,ρik=-LB+RUBk+Likli0li0,i=T+1,T+2,…,p.Theorem 3.
For any subboxZk=(Zik)p×1=[Lik,Uik]p×1⊆Z0, we have the following two conclusions:(i)
Suppose thatRUBk<LB; then there does not exist any global optimum point of EQZk over Zk.(ii)
Suppose thatRUBk≥LB; then, when j∈1,2,…,T, there does not exist any global optimum point of EQZ0 over Zak; and when j∈T+1,T+2,…,p, there does not exist any global optimum point of EQZ0 over Zbk, where (10)Zak=Zaikp×1⊆Z0withZaik=Zik,i≠j,i=1,2,…,p,Lik,ρik∩Zik,i=j∈1,2,…,T.Zbk=Zbikp×1⊆Z0withZbik=Zik,i≠j,i=1,2,…,p,ρik,Uik∩Zik,i=j∈T+1,T+2,…,p,Proof.
(i) Suppose thatRUBk<LB; then we have (11)vZk=maxz∈Zk,y∈Λ⁡∑i=1pziφiy≤∑i=1pmaxz∈Zk,y∈Λ⁡ziφiy=∑i=1TUikui0-∑i=T+1pLikli0=RUBk<LB;therefore, there does not exist any global optimum point of the problem EQZk over Zk.
(ii) Suppose thatRUBk≥LB; then we can get the following several conclusions.
Whenj∈1,2,…,T, for any y∈Λ and z∈Zak, since (12)0≤li0≤φiy≤ui0,0≤Lik≤zi≤Uik,i=1,2,…,p,i≠j;0≤Ljk≤zj<ρjk,i=j,we can get (13)vZak=maxz∈Zak,y∈Λ⁡∑i=1Tziφiy-∑i=T+1pziziφiy≤maxz∈Zak,y∈Λ⁡∑i=1,i≠jTziφiy-minz∈Zak,y∈Λ⁡∑i=T+1pziφiy+maxz∈Zak,y∈Λ⁡ziφiy<∑i=1,i≠jTUikui0-∑i=T+1pLikli0+ρjkuj0=RUBk-Ujkuj0+ρjkuj0<LB.Therefore, there does not exist any global optimum point of EQ(Zk) over Zak.
Similarly, whenj∈{T+1,T+2,…,p}, and for any y∈Λ and z∈Zbk, since (14)0≤li0≤φiy≤ui0,0≤Lik≤zi≤Uik,i=1,2,…,p,i≠j,0≤ρjk<zj≤Ujk,i=j,we have(15)vZbk=maxz∈Zbk,y∈Λ⁡∑i=1Tziφiy-∑i=T+1pziφiy≤maxz∈Zbk,y∈Λ⁡∑i=1Tziφiy-minz∈Zbk,y∈Λ⁡∑i=T+1,i≠jpziφiy-minz∈Zbk,y∈Λ⁡ziφiy<∑i=1TUikui0-∑i=T+1,i≠jpLikli0-ρjklj0=RUBk+Ljklj0-ρjklj0<LB.Therefore, there does not exist any global optimum point of EQZk over Zbk.By the above Theorem3, we can construct an out space pruning technique to prune a part of the investigated out space region which does not contain the global optimum point of the problem (EQ). Assume that a subbox(16)Zk=Zikp×1⊆Z0withZik=Lik,Uikwill be pruned; then from the Theorem 3, the investigated box Zk can be renewed by a subbox (17)Z′=Zi′p×1withZi′=ρik,Uik∩Zik,i∈1,2,…,T,Lik,ρik∩Zik,i∈T+1,T+2,…,p.


## 4. Algorithm and Its Convergence

In this section, by utilizing the above new pruning technique, we will present a new out space branch-and-bound algorithm for globally solving the problem (SLRP). In the algorithm, the branching operation is performed in out spaceRp. Assume that Z=z∈Rp∣Li≤zi≤Ui,i=1,2,…,p is Z0 or a subbox of it, which will be partitioned, the branching rule is selected as follows.Set(18)q∈arg⁡max⁡Ui-Li∣i=1,2,…,p,Z1=z∈Rp∣Li≤zi≤Lq+Uq2,i=q,Li≤zi≤Ui,i=1,2,…,p,i≠q,Z2=z∈Rp∣Lq+Uq2≤zi≤Ui,i=q,Li≤zi≤Ui,i=1,2,…,p,i≠q.Obviously, from [26] we can get that this branching rule is exhaustive; that is, if {Zk} represents a nested subsequence of boxes (i.e., Zk+1⊆Zk, for all k) formed by partitioning process, then there exists a unique point z∗∈Rp satisfying ⋂kZk={z∗}.


### 4.1. Out Space Branch-and-Bound Algorithm

Based upon the above linear relaxation bounding problem, the new out space pruning technique, and bisection method, an out space branch-and-bound algorithm is proposed for globally solving the (SLRP) as follows.Step 1.
Letk=0, Δ0={Z0},ε≥0, li0=miny∈Λφi(y), and ui0=maxy∈Λφi(y),  i=1,2,…,p. And let (19)Ui0=1miny∈Λ⁡ϕiy,i=1,2,…,T,1-maxy∈Λ⁡ϕiy,i=T+1,…,p,Li0=1maxy∈Λ⁡ϕiy,i=1,2,…,T,1-miny∈Λ⁡ϕiy,i=T+1,…,p,and construct the initial box (20)Z0=z∈Rp∣Li0≤zi≤Ui0,i=1,2,…,p.Using simplex method to solve LRP(Z0), set its optimum solution y0 and optimum value UB(Z0), respectively. Let UB0=UB(Z0), zi0=ϕiy0  i=1,2,…,p,  LB0=H0y0,z0. If UB0-LB0≤ε, then y0,z0 and y0 are global optimum solutions of EQ(Z0) and the (SLRP), respectively. Otherwise, let F=∅, k=1 and continue to the following Step 2.Step 2.
SetLB=LBk-1. For each investigated subbox Zk-1, use the former out space pruning technique to prune the investigated subbox Zk-1, let the remaining box be Z′, and set Zk-1=Z′, LBk=LBk-1.Step 3.
PartitionZk-1 into two subboxes Zk,1,Zk,2⊆Zk-1 using the bisection technique. Let the new partitioned subboxes set be Z¯k. Set F=F∪{Zk-1}. For each Zk,t∈Z¯k, solve the (LRP) using simplex method to get UB(Zk,t) and yk,t, and set zik,t=ϕi(yk,t),  i=1,2,…,p. If UB(Zk,t)<LBk, then let Z¯k≔Z¯k∖Zk,t,  F=F∪Zk,t; otherwise, update LBk=min⁡LBk,H0yk,t,zk,t, if necessary.Step 4.
Let the remaining partitioned setΔk-1≔(Δk-1∖Zk-1)∪{Z¯k}, and let the new upper bound UBk=maxZ∈Δk-1⁡UB(Z). Let Δk=Z∣Z∈Δk-1∪Zk,1,Zk,2,Z∉F and UBk=min⁡UBZ∣Z∈Δk. If UBk-LBk≤ε, then we get that (yk,zk) and yk are global optimum points of the EQ(Z0) and the (SLRP), respectively. Otherwise, let k=k+1 and return to Step 2.


### 4.2. Convergence Analysis

In the following, we describe the global convergence of the above algorithm.Theorem 4.
The above algorithm either stops finitely to obtain the global optimum point of the (SLRP) or produces an infinite sequence{yk} whose accumulation point y∗ must be the global optimum point of the (SLRP).Proof.
If the proposed algorithm stops finitely atkth iteration, where k≥0, obviously, when the algorithm stops, we can get yk and yk,zk by solving the LRP(Zk), which are the feasible points of the (SLRP) and the (EQ), where (21)zik=1ϕiyk,i=1,2,…,T;zik=1-ϕiyk,i=T+1,T+2,…,p;and by terminating step of the algorithm, the updating operations of the lower bound and upper bound, and Theorems 1 and 2, we can easily follow that (22)H0yk,zk≥UBk-ε,UBk≥v,v≥H0yk,zk,Gyk=H0yk,zk.By combining the above all inequalities and equality, we can easily get that (23)v-ϵ≤Gyk≤v.Therefore, if the algorithm stops finitely at kth iteration, then yk is the global ϵ–optimal solution of the (SLRP).
If the above algorithm generates an infinite sequence{yk} of incumbent solutions by solving the LRP(Zk), let (24)zik=1ϕiyk,i=1,2,…,T,zik=1-ϕiyk,i=T+1,T+2,…,p;then we can get an infinite sequence {yk,zk} of incumbent solutions for EQ(Zk). By the continuity character of the function ϕi(yk) and 1/ϕi(yk)=zik∈Lik,Uiki=1,…,T and 1/-ϕi(yk)=zik∈Lik,Uiki=T+1,…,p, and the exhaustiveness of the bisection rule, we can get the following conclusions, for each i∈1,2,…,T:(25)1ϕiy∗=limk→∞1ϕiyk=limk→∞Lik=limk→∞Uik=limk→∞Lik,Uik=⋂kLik,Uik=zi∗;for each i∈T+1,T+2,…,p,(26)1-ϕiy∗=limk→∞1-ϕiyk=limk→∞Lik=limk→∞Uik=limk→∞Lik,Uik=⋂kLik,Uik=zi∗.Therefore, (y∗,z∗) is a feasible point of the EQ(Z0), also since {UB(Zk)} is a decreasing real number sequence bounded by v, we can follow that (27)H0y∗,z∗≤v≤limk→∞UBZk=limk→∞∑i=1TUikφiyk-∑i=T+1pLikφiyk=H0y∗,z∗.Thus, from the updating method of the lower bound and the continuity character of the G(y), we can get that (28)limk→∞LBZk=v=H0y∗,z∗=Gy∗=limk→∞Gyk=limk→∞UBZk.Hence, y∗ is the global optimum point of the (SLRP); the conclusion is proved.


### 4.3. Numerical Example

In this subsection, some well-known test problems are implemented on Intel(R) Core(TM)2 Duo CPU microcomputer to verify the performance of the proposed out space branch-and-bound algorithm. The proposed out space branch-and-bound algorithm is coded in C++ program, and the simplex method is used to solve each linear relaxation programming problem. Numerical problems and their computational results are summarized in Table1. Some notations have been also used for column headers in Table 1 as follows. Ave. Iter. represents the average number of iterations of the algorithm; Ave. L. represents the average number of the necessary maximum nodes of the algorithm; Ave. Time (s) stands for the execution time of algorithm in seconds.Table 1
Numerical results for test problem.
Number
(
m
,
n
,
p
,
c
)
Ref.
Ave. Iter.
Ave. L.
Ave. Time (s)
ϵ
(1)
(2, 3, 3, 2)
This paper
3.2
3.1
0.015
1
0
-
6
(2, 3, 3, 2)
[15]
38.3
7.8
0.05
1
0
-
6
(2, 3, 3, 2)
[16]
4.6
1.0
0
1
0
-
5
(2)
(4, 3, 4, 2)
This paper
5.2
4.6
0.05
1
0
-
6
(4, 3, 4, 2)
[15]
46
8.2
0.1
1
0
-
6
(4, 3, 4, 2)
[16]
5.6
1.1
0
1
0
-
5
(3)
(5, 10, 3, 2)
This paper
6.2
3.8
0.073
1
0
-
6
(5, 10, 3, 2)
[15]
414.3
60.2
1.9
1
0
-
6
(5, 10, 3, 2)
[16]
6.3
1.4
0
1
0
-
5
(4)
(10, 20, 3, 2)
This paper
7.3
4.4
0.087
1
0
-
6
(10, 20, 3, 2)
[15]
402.7
56.8
10.1
1
0
-
6
(10, 20, 3, 2)
[16]
7.4
2.0
0.023
1
0
-
5
(5)
(15, 30, 3, 2)
This paper
6.5
4.5
0.130
1
0
-
6
(15, 30, 3, 2)
[15]
424.3
61.6
35.1
1
0
-
6
(15, 30, 3, 2)
[16]
7.0
2.0
3.1
1
0
-
5Problem (see [15, 16]).
(29)
m
a
x
∑
j
=
1
p
∑
i
=
1
n
d
j
i
y
i
+
c
∑
i
=
1
n
σ
j
i
y
i
+
c
s.t.
∑
i
=
1
n
a
k
i
y
i
≤
b
k
,
k
=
1
,
…
,
m
,
y
i
≥
0.0
,
i
=
1,2
,
…
,
n
,wheredji,σji,aki,j=1,…,p, k=1,…,m, i=1,…,n, are randomly generated in 0.0,1.0; c are generated in [1.0,100.0]; bk=1.0, k=1,2,…,m. In the investigated problem, m denotes the number of the constraints, n denotes the dimension of the problem, and p denotes the number of ratios.From Table1, compared with the known algorithms, numerical results indicate that the proposed algorithm can be used to globally solve the problems (SLRP) with the higher computational efficiency.


## 4.1. Out Space Branch-and-Bound Algorithm

Based upon the above linear relaxation bounding problem, the new out space pruning technique, and bisection method, an out space branch-and-bound algorithm is proposed for globally solving the (SLRP) as follows.Step 1.
Letk=0, Δ0={Z0},ε≥0, li0=miny∈Λφi(y), and ui0=maxy∈Λφi(y),  i=1,2,…,p. And let (19)Ui0=1miny∈Λ⁡ϕiy,i=1,2,…,T,1-maxy∈Λ⁡ϕiy,i=T+1,…,p,Li0=1maxy∈Λ⁡ϕiy,i=1,2,…,T,1-miny∈Λ⁡ϕiy,i=T+1,…,p,and construct the initial box (20)Z0=z∈Rp∣Li0≤zi≤Ui0,i=1,2,…,p.Using simplex method to solve LRP(Z0), set its optimum solution y0 and optimum value UB(Z0), respectively. Let UB0=UB(Z0), zi0=ϕiy0  i=1,2,…,p,  LB0=H0y0,z0. If UB0-LB0≤ε, then y0,z0 and y0 are global optimum solutions of EQ(Z0) and the (SLRP), respectively. Otherwise, let F=∅, k=1 and continue to the following Step 2.Step 2.
SetLB=LBk-1. For each investigated subbox Zk-1, use the former out space pruning technique to prune the investigated subbox Zk-1, let the remaining box be Z′, and set Zk-1=Z′, LBk=LBk-1.Step 3.
PartitionZk-1 into two subboxes Zk,1,Zk,2⊆Zk-1 using the bisection technique. Let the new partitioned subboxes set be Z¯k. Set F=F∪{Zk-1}. For each Zk,t∈Z¯k, solve the (LRP) using simplex method to get UB(Zk,t) and yk,t, and set zik,t=ϕi(yk,t),  i=1,2,…,p. If UB(Zk,t)<LBk, then let Z¯k≔Z¯k∖Zk,t,  F=F∪Zk,t; otherwise, update LBk=min⁡LBk,H0yk,t,zk,t, if necessary.Step 4.
Let the remaining partitioned setΔk-1≔(Δk-1∖Zk-1)∪{Z¯k}, and let the new upper bound UBk=maxZ∈Δk-1⁡UB(Z). Let Δk=Z∣Z∈Δk-1∪Zk,1,Zk,2,Z∉F and UBk=min⁡UBZ∣Z∈Δk. If UBk-LBk≤ε, then we get that (yk,zk) and yk are global optimum points of the EQ(Z0) and the (SLRP), respectively. Otherwise, let k=k+1 and return to Step 2.


## 4.2. Convergence Analysis

In the following, we describe the global convergence of the above algorithm.Theorem 4.
The above algorithm either stops finitely to obtain the global optimum point of the (SLRP) or produces an infinite sequence{yk} whose accumulation point y∗ must be the global optimum point of the (SLRP).Proof.
If the proposed algorithm stops finitely atkth iteration, where k≥0, obviously, when the algorithm stops, we can get yk and yk,zk by solving the LRP(Zk), which are the feasible points of the (SLRP) and the (EQ), where (21)zik=1ϕiyk,i=1,2,…,T;zik=1-ϕiyk,i=T+1,T+2,…,p;and by terminating step of the algorithm, the updating operations of the lower bound and upper bound, and Theorems 1 and 2, we can easily follow that (22)H0yk,zk≥UBk-ε,UBk≥v,v≥H0yk,zk,Gyk=H0yk,zk.By combining the above all inequalities and equality, we can easily get that (23)v-ϵ≤Gyk≤v.Therefore, if the algorithm stops finitely at kth iteration, then yk is the global ϵ–optimal solution of the (SLRP).
If the above algorithm generates an infinite sequence{yk} of incumbent solutions by solving the LRP(Zk), let (24)zik=1ϕiyk,i=1,2,…,T,zik=1-ϕiyk,i=T+1,T+2,…,p;then we can get an infinite sequence {yk,zk} of incumbent solutions for EQ(Zk). By the continuity character of the function ϕi(yk) and 1/ϕi(yk)=zik∈Lik,Uiki=1,…,T and 1/-ϕi(yk)=zik∈Lik,Uiki=T+1,…,p, and the exhaustiveness of the bisection rule, we can get the following conclusions, for each i∈1,2,…,T:(25)1ϕiy∗=limk→∞1ϕiyk=limk→∞Lik=limk→∞Uik=limk→∞Lik,Uik=⋂kLik,Uik=zi∗;for each i∈T+1,T+2,…,p,(26)1-ϕiy∗=limk→∞1-ϕiyk=limk→∞Lik=limk→∞Uik=limk→∞Lik,Uik=⋂kLik,Uik=zi∗.Therefore, (y∗,z∗) is a feasible point of the EQ(Z0), also since {UB(Zk)} is a decreasing real number sequence bounded by v, we can follow that (27)H0y∗,z∗≤v≤limk→∞UBZk=limk→∞∑i=1TUikφiyk-∑i=T+1pLikφiyk=H0y∗,z∗.Thus, from the updating method of the lower bound and the continuity character of the G(y), we can get that (28)limk→∞LBZk=v=H0y∗,z∗=Gy∗=limk→∞Gyk=limk→∞UBZk.Hence, y∗ is the global optimum point of the (SLRP); the conclusion is proved.


## 4.3. Numerical Example

In this subsection, some well-known test problems are implemented on Intel(R) Core(TM)2 Duo CPU microcomputer to verify the performance of the proposed out space branch-and-bound algorithm. The proposed out space branch-and-bound algorithm is coded in C++ program, and the simplex method is used to solve each linear relaxation programming problem. Numerical problems and their computational results are summarized in Table1. Some notations have been also used for column headers in Table 1 as follows. Ave. Iter. represents the average number of iterations of the algorithm; Ave. L. represents the average number of the necessary maximum nodes of the algorithm; Ave. Time (s) stands for the execution time of algorithm in seconds.Table 1
Numerical results for test problem.
Number
(
m
,
n
,
p
,
c
)
Ref.
Ave. Iter.
Ave. L.
Ave. Time (s)
ϵ
(1)
(2, 3, 3, 2)
This paper
3.2
3.1
0.015
1
0
-
6
(2, 3, 3, 2)
[15]
38.3
7.8
0.05
1
0
-
6
(2, 3, 3, 2)
[16]
4.6
1.0
0
1
0
-
5
(2)
(4, 3, 4, 2)
This paper
5.2
4.6
0.05
1
0
-
6
(4, 3, 4, 2)
[15]
46
8.2
0.1
1
0
-
6
(4, 3, 4, 2)
[16]
5.6
1.1
0
1
0
-
5
(3)
(5, 10, 3, 2)
This paper
6.2
3.8
0.073
1
0
-
6
(5, 10, 3, 2)
[15]
414.3
60.2
1.9
1
0
-
6
(5, 10, 3, 2)
[16]
6.3
1.4
0
1
0
-
5
(4)
(10, 20, 3, 2)
This paper
7.3
4.4
0.087
1
0
-
6
(10, 20, 3, 2)
[15]
402.7
56.8
10.1
1
0
-
6
(10, 20, 3, 2)
[16]
7.4
2.0
0.023
1
0
-
5
(5)
(15, 30, 3, 2)
This paper
6.5
4.5
0.130
1
0
-
6
(15, 30, 3, 2)
[15]
424.3
61.6
35.1
1
0
-
6
(15, 30, 3, 2)
[16]
7.0
2.0
3.1
1
0
-
5Problem (see [15, 16]).
(29)
m
a
x
∑
j
=
1
p
∑
i
=
1
n
d
j
i
y
i
+
c
∑
i
=
1
n
σ
j
i
y
i
+
c
s.t.
∑
i
=
1
n
a
k
i
y
i
≤
b
k
,
k
=
1
,
…
,
m
,
y
i
≥
0.0
,
i
=
1,2
,
…
,
n
,wheredji,σji,aki,j=1,…,p, k=1,…,m, i=1,…,n, are randomly generated in 0.0,1.0; c are generated in [1.0,100.0]; bk=1.0, k=1,2,…,m. In the investigated problem, m denotes the number of the constraints, n denotes the dimension of the problem, and p denotes the number of ratios.From Table1, compared with the known algorithms, numerical results indicate that the proposed algorithm can be used to globally solve the problems (SLRP) with the higher computational efficiency.


## 5. Concluding Remarks

In this paper, we present an effective algorithm for globally solving the sum of linear ratios problem (SLRP). By introducing new variables, we transform the initial sum of linear ratios problems (SLRP) into the equivalent nonconvex programming problem. Next, the linear relaxation programming problem of the equivalent problem is established by utilizing direct relaxation. To improve the computational efficiency of the algorithm, an out space pruning technique is derived, which offers a possibility of pruning a large part of the investigated out space region which does not contain the optimal solution of the equivalent problem. Based on out space partition, by combining bounding technique and reduction technique, a new outcome space branch-and-bound algorithm for globally solving the sum of linear ratios problem (SLRP) is constructed. Finally, numerical problems and their computational results are presented to demonstrate both computational efficiency and solution quality of the proposed algorithm.In future research, we can extend the proposed algorithm and reduction technique to solve nonlinear fractional problems, like concave-convex sum-of-ratios problem, convex-convex sum-of-ratios problem, linear fractional multiplicative problem, generalized linear fractional programming problem, and so on.



---

*Source: 8138975-2017-06-05.xml*