# An Effective Computational Algorithm for the Global Solution of a Class of Linear Fractional Programming

Authors: XiaoLi Huang; YueLin Gao; Bo Zhang; Xia Liu
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

For the minimization of the sum of linear fractions on polyhedra, it is likewise a class of linear fractional programming (LFP). In this paper, we mainly propose a new linear relaxation technique and combine the branch-and-bound algorithm framework to solve the LFP globally. It is worthwhile to mention that the branching operation of the algorithm occurs in the relatively small output space of the dimension rather than the space where the decision variable is located. When the number of linear fractions in the objective function is much lower than the dimension of the decision variable, the performance of the algorithm is better. After that, we also explain the effectiveness, feasibility, and other performances of the algorithm through numerical experiments.


---

## Body

## 1. Introduction

Consider the linear fractional programming (LFP):(1)LFP≔minfx=∑i=1pciTx+dieiTx+fis.t.x∈X=x∈ℝn|Ax≤b,x≥0,where ci∈ℝn, di∈ℝ, ei∈ℝn, and fi∈ℝ. X is a nonempty polyhedron-feasible set, with A∈ℝm×n and b∈ℝm, in a decision (or variable) space ℝn. Note that throughout the paper, T represents the transpose of vectors, such as the previous ciT representing the transpose of vector ci. Furthermore, for each i=1,2,…,p, we let gix=ciTx+di and hix=eiTx+fi, which are in favour of the following narrative. For the single linear fraction gix/hix in the objective function, we assume that gix≥0 and hix>0; at the same time, by [1], our hypothesis has not lost generality, that is, as long as the denominator hix of gix/hix is not 0, we can convert it into gix≥0 and hix>0 by means of the method in [1].The problem (LFP) has many important applications in laminated manufacturing [2, 3], material layout [4], MIMO networks [5], and economics [6], among others. From [7–9], it can be seen that the computational efficiency of the algorithm is very sensitive to the number p of linear fractions in the problem (LFP). When p=1, Charnes and Cooper [10] indirectly solved the linear fractional programming by transforming the original linear fractional programming into an equivalent linear programming problem. Charnes and Novaes [11] proposed an updated objective function method to solve linear fractional programs by resolving a series of linear programs, while Dinkelbach [12] used a parametric approach to solving linear fractional programming problems. Through the transformation of the objective function and constraint, Das and Mandal [13] simplified the linear fractional programming into an equivalent linear program and then used the simplex method to solve this linear program. Indeed, when p=2, Matsui [14] proved that the problem (LFP) is an NP-hard problem. Therefore, its solution method has caught the attention of numerous scholars. So far, many methods have been proposed and used to solve the LFP and its special forms, such as the image space method [15], outer approximation method [16], unifying monotone method [17], cutting plane method [18], branch-and-bound algorithm [7, 8, 19, 20], interval-split algorithm [21], internal point method [22], heuristic method [23], and concave minimization method [24]. Besides, based on [25], by introducing strategies such as bound-lift and cone-compression, Shen et al. [26] proposed a new branch-reduction-bound algorithm. According to Jiao and Liu [9], the original problem is transformed into a bilinear programming problem, and then the lower bound of the original problem is constructed by using the technique of linearization of convex envelope and concave envelope of the bivariate product function and then solved by the branch-and-bound algorithm. By utilising the linearization technique, Jiao et al. [27] constructed the linear relaxation lower bound of the original problem and then proposed a new algorithm by pruning strategy and gave the convergence of the algorithm. When p is a fixed number, an approximate solution algorithm is given in [1, 28, 29], and its complexity analysis shows that it is a complete polynomial-time approximation algorithm. Xia et al. [30] extended the conclusion in [28] to the problem of linear-ratio-sum with the linear matrix inequality. Moreover, relevant scholars have also studied linear fractional programming problems in uncertain environments, such as fuzzy linear fractional programming [31, 32], linear fractional programming with absolute value variables [33], and interval linear fractional programming [34]. Das et al. [31] proposed the concept of a simple sorting method between the fuzzy numbers of two triangles and gave an equivalent three-objective linear fractional programming problem to calculate the upper, middle, and lower bounds of the fuzzy linear fraction programming problem, thus numerically constructing and solving the optimal value. In [32], the authors used the Charnes–Cooper scheme and the multiobjective linear programming problem to obtain an effective algorithm for solving the fully fuzzy linear fractional programming problem, and in [33], they also proposed a new model of linear fractional programming problems with absolute value functions and then transformed the linear fractional programming problems into independent linear programming problems with some theorems. Then, popular algorithms (such as the simplex algorithm) are utilized to solve these problems. Recently, in [34], Abad et al. proposed two new approaches to interval linear fractional programming, and in each method, two submodels were used to obtain the range of the objective function.In this paper, a branch-and-bound algorithm based on the branch of thep-dimensional output space is presented for solving the LFP. The literature studies [7–9] all report that the branching operation of the branch-and-bound algorithm occurring in the p-dimensional space may save more computation than in the 2p-dimensional or n-dimensional space, especially in [8], which, by Theorem 5 and its corollary, shows that the branching operation occurring in the p-dimensional space, in the case of p≪n, is the most advantageous. Therefore, the algorithm set forth in the present paper can greatly save the computational cost compared with the branching operation for the 2p- or n-dimensional space. In addition, another advantage of our algorithm is the fact that we only need to solve linear programming in the iterative process of the algorithm, which is easier to solve than the general nonlinear programming algorithm.This paper is organized as follows. In Section2, we give the equivalence problem (EP) of the problem (LFP) as well as some preparatory work. Section 3 mainly discusses the relevant theories of the proposed algorithm based on the equivalence problem (EP), including the bounding, branching, pruning, detailed steps, and the convergence analysis of the proposed algorithm. In Section 4, numerical experiments are performed, which are utilized to illustrate the effectiveness and feasibility of the algorithm and other performances. Finally, the conclusion part mainly makes a simple summary and prospect of the algorithm in this paper.


## 2. Equivalent Problem of Problem (LFP)

To get the equivalent problem of the LFP, we first solve the following4p-linear programming problems using the existing linear programming method:(2)y¯i0=minx∈Xgix=minx∈XciTx+di,i=1,2,…,p,y¯i0=maxx∈Xgix=maxx∈XciTx+di,i=1,2,…,p,z¯i0=minx∈Xhix=minx∈XeiTx+fi,i=1,2,…,p,z¯i0=maxx∈Xhix=maxx∈XeiTx+fi,i=1,2,…,p.Obviously, the optimal values of the above4p-linear programming problems determine the initial upper and lower bounds of the numerator and denominator in each linear fraction function, that is, y¯i0, y¯i0, z¯i0, and y¯i0, respectively.Next, we define the initial rectangle(3)R≔y,z∈ℝ2p:y¯i0≤yi≤y¯i0,z¯i0≤zi≤z¯i0,i=1,2,…,pand the subrectangle(4)Rk≔y,z∈ℝ2p:y¯i0≤yi≤y¯i0,z¯ik≤zi≤z¯ik,i=1,2,…,p⊆Rat the current iteration kk≥1.Consider the following equivalent problem (EP):(5)EP≔minφy,z≔∑i=1pyizi,s.t.gix−yi=0,i=1,2,…,phix−zi=0,i=1,2,…,px∈X,y,z∈R.The following Theorem1 creates the equivalent relationship between the problem (EP) and the original problem (LFP).Theorem 1.
Ifx∗,y∗,z∗ is a global optimal solution for problem (EP), then x∗ is a global optimal solution for problem (LFP). Conversely, if x∗ is an optimal solution for problem (LFP), then x∗,y∗,z∗ is a global optimal solution for problem (EP), where y∗≔gx∗ and z∗≔hx∗.Proof.
The conclusion of the theorem is obvious and omitted here.
Theorem1 shows that the solution of problem (LFP) can be obtained indirectly by addressing problem (EP).
In addition, if the rectangleR in problem (EP) is replaced by its subrectangle Rk, this will generate subproblem EPRk of problem (EP) over the rectangle Rk.


## 3. Branch-and-Bound Algorithm

In this section, we will consider the three components of the branch-and-bound algorithm, namely, branching, bounding, and pruning, respectively, by studying problem (EP).


### 3.1. Bounding

Note that the objective function of the problemEPRk(or (EP)) is separable and still nonconvex. And then, we can propose a new underestimation method for yi/zii=1,2,…,p and give it through the following Theorem 2.Theorem 2.
Consider the rectangleLR≔y,z∈ℝ×ℝ:y¯≤y≤y¯,z¯≤z≤z¯, where y¯, y¯, z¯, and z¯ are all constants satisfying 0≤y¯≤y≤y¯ and 0<z¯≤z≤z¯. For any y,z∈LR, define the functions ψy,z and ψ¯y,z as follows:(6)ψy,z≔yz,ϕ1y,z≔−y¯zz¯z¯+yz¯+y¯2z¯−z¯z¯z¯z¯z¯,ϕ2y,z≔−y¯zz¯z¯+2z¯−z¯z¯yz¯z¯z¯+y¯z¯,ψ¯y,z≔maxϕ1y,z,ϕ2y,z.
Then, the following conclusions hold:(i)
For anyy,z∈LR, the functions ψy,z and ψ¯y,z satisfy(7)ψy,z≥ψ¯y,z.(ii)
Let∇=2y¯z¯/z¯z¯z¯+z¯ and Δ=z¯−z¯; then, limΔ⟶0ψy,z−ψ¯y,z=0.Proof.
(i)
For anyy,z∈LR, we have(8)ψy,z−ψ¯y,z=ψy,z−max−y¯zz¯z¯+yz¯+y¯2z¯−z¯z¯z¯z¯z¯,−y¯zz¯z¯+2z¯−z¯z¯yz¯z¯z¯+y¯z¯,=yz−maxyz¯+y¯2z¯z¯−zz¯z¯−y¯z¯,−1z¯z¯y¯z+yz¯−y¯z¯+2yz¯z¯,≥minyz−yz¯+y¯z−y¯z¯,yz−−yzz¯z¯+2yz¯z¯,=miny−y¯1z−1z¯,y1z−2z¯z¯−zz¯z¯,≥0.The establishment of the first inequality in formula (8) takes advantage of the convexity of the univariate function 1/z in the case of z>0, i.e., 1/z≥2/z¯z¯−z/z¯z¯. Moreover, the establishment of the first inequality of formula (8) also takes advantage of the fact that y−y¯z−z¯≤0. As a result, according to formula (8), it is easy to know ψy,z≥ψ¯y,z. Conclusion (i) holds.(ii)
By the definition ofψy,z and ψ¯y,z, we have(9)ψy,z−ϕ1y,z=yz−yz¯+y¯1z¯−2z¯z¯+zz¯z¯,≤y¯z¯−z¯z¯z¯+y¯z¯z¯z¯−2z¯z¯+z¯z¯z¯,=y¯z¯−z¯z¯z¯+y¯z¯z¯z¯−z¯2,≤y¯z¯z¯1+z¯−z¯z¯+z¯z¯−z¯,=2y¯z¯z¯−z¯z¯z¯z¯+z¯,=∇Δ,(10)ψy,z−ϕ2y,z=y1z−−zz¯z¯+2z¯z¯+1z¯z¯y¯−yz−z¯,≤y1z−zz¯z¯2+1z¯z¯y¯−y¯z¯−z¯,≤y¯z¯z¯z¯−z¯2+y¯z¯z¯z¯−z¯,=y¯z¯z¯1+z¯−z¯z¯+z¯z¯−z¯,=∇Δ.
According to formulae (9) and (10) and conclusion (i), we have(11)0≤limΔ⟶0ψy,z−ψ¯y,z≤limΔ⟶0∇Δ.
Since∇ is a bounded value, this implies that ∇Δ⟶0 as Δ⟶0. Thus, combined with (11), we have limΔ⟶0ψy,z−ψ¯y,z=0, and the proof is completed.
In the following, by using Theorem2, we will construct the lower bounding function of the objective function for problem EPRk(or (EP)). Assume that R^ denotes R or a subrectangle Rk of R that is generated by the branching process, where R^=∏i=1pR^i, with R^i=y¯i0,y¯i0×z¯i,z¯i,i=1,2,…,p. Obviously, y¯i0,y¯i0,z¯i,andz¯i satisfy 0≤y¯i0≤yi≤y¯i0and0<z¯i≤zi≤z¯i. For each i∈1,2,…,p and for each yi,zi∈R^i, define(12)ψiyi,zi≔yizi,ϕi1yi,zi≔−y¯i0ziz¯iz¯i+yiz¯i+y¯i02z¯i−z¯iz¯iz¯iz¯iz¯i,ϕi2yi,zi≔−y¯i0ziz¯iz¯i+2z¯i−z¯iz¯iyiz¯iz¯iz¯i+y¯i0z¯i,ψ¯iyi,zi≔maxϕi1yi,zi,ϕi2yi,zi.
Then, by Theorem2, we have(13)ψiyi,zi≥ψ¯iyi,zi,i∈1,2,…,p.
Thus, for anyy,z∈R^, let ψ¯y,z=∑i=1pψ¯iyi,zi, and we have(14)φy,z≥ψ¯y,z,∀y,z∈R^.
Furthermore, by using formulae (13) and (14), we can construct the following linear relaxation programming problem LRPR^ of EPR^:(15)LRPR^:ψ¯y,z=min∑i=1pri,s.t.ϕi1yi,zi≤ri,i=1,2,…,p,ϕi2yi,zi≤ri,i=1,2,…,p,gix−yi=0,i=1,2,…,p,hix−zi=0,i=1,2,…,p,x∈X,y,z∈R^.
Based on the construction method of the linear relaxation programming problemLRPR^, obviously, the optimal value for problem NLRPR^ is less than or equal to that of EPR^, i.e., vNLRPR^≤vEPR^. Then, we have vLRPR^=vNLRPR^≤vEPR^. Therefore, the linear relaxation programming problem LRPR^ provides a valid lower bound for the optimal value of EPR^.
It is noted that the solutionx^,y^,z^ obtained from the above linear relaxation programming problem LRPR^, which is used to progressively update the upper bound of the optimal value of problem (EP), is a feasible solution to problem (EP).


### 3.2. Branching

For the selected rectangleR^, we use the dichotomization as a branching process, which subdivides a 2p-dimensional rectangle(16)R^=∏i=1pR^i=∏i=1py¯i0,y¯i0×z¯i,z¯i⊆Rinto two 2p-dimensional subrectangles R^1 and R^2 of the same volume along the midpoint of its longest edge. The specific rectangle-branch method is as follows:(i)
Letj∈argmaxz¯i−z¯i,i=1,2,…,p.(ii)
R^j is divided into R^j1 and R^j2, i.e.,(17)R^j1=y¯j0,y¯j0×z¯j,z¯j+z¯j2,R^j2=y¯j0,y¯j0×z¯j+z¯j2,z¯j.(iii)
LetR^1=∏i=1j−1R^i×R^j1×∏i=j+1pR^iandR^2=∏i=1j−1R^i×R^j2×∏i=j+1pR^i.Be sure to note that the intervaly¯i0,y¯i0i=1,2,…,p is never subdivided during the branching process. Thus, the branching process occurs only in the p-dimensional space, which greatly saves this computational cost.


### 3.3. Pruning

SupposeLR^ is the lower bound of problem EPR^ over the rectangle R^ and U represents the best upper bound that the algorithm has known so far. And let ε∈0,1 represent the tolerance of the algorithm. Then, the pruning process is the transversion of deleting the node information on the branch-and-bound tree corresponding to the rectangle R^ that satisfies LR^>U−ε.


### 3.4. Output-Space Branch-and-Bound Algorithm

Now, we present an output-space branch-and-bound algorithm for solving (LFP). For thek-th iteration, we give the following notation in advance: Rk is the rectangle to be subdivided, Q represents a set that produces a new solution after each iteration (note that the number of elements in the set Q does not exceed 2), and Ξ is a collection of rectangles left after pruning. xk,yk,zk and LRk represent the optimal solution and optimal value of problem LRPRk over the rectangle Rk, respectively. Lk represents the current lower bound of the global optimal value of problem (EP), and Uk represents the current upper bound of the global optimal value of problem (EP). U′ represents the best function value of all new feasible solutions to the resulting problem (EP) after each iteration is completed.Combined with the above content, the proposed algorithm is as follows:Step 0 (initialization):y¯0,y¯0,z¯0, and z¯0 are obtained by (2), and then the initial rectangle R0=R is constructed. Set tolerance ε∈0,1. Then, the initial linear relaxation programming problem LRPR0 is solved, and its optimal solution x0,y0,z0 and optimal value LR0 are obtained. And then, let(18)U1=φy0,z0,L1=LR0,R1=R0,Ξ=R1,Q=∅,k=1.Step 1 (termination):IfUk−Lk≤ε, then terminate the algorithm. Then, xk,yk,zk is the global ε-optimal solution of problem (EP), and the global optimal solution of problem (LFP) can be obtained according to Theorem 1 which is xk. Otherwise, go to Step 2.Step 2 (branching):LetRk=R^∈Ξ:Lk=LR^ and Ξ=Ξ∖Rk. Then, using the rectangle-branching method in Section 3.2, Rk is divided into two subrectangles Rk1 and Rk2.Step 3 (pruning):For eachs∈1,2, solve LRPRks to obtain LRks and xks,yks,zks for Rks⊆Rk. If LRks≥Uk−ε, then delete the rectangle Rks. Otherwise, let Ξ=Ξ∪Rks and Q=Q∪xks,yks,zks.Step 4 (bounding):Step 4.1 (upper bounding):IfQ is not empty, let U′=minx,y,z∈Qφy,z. If U′<Uk, set Uk=U′ and xk,yk,zk=argminx,y,z∈Qφy,z.IfQ is empty, both Uk and xk,yk,zk remain the same.Step 4.2 (lower bounding):(19)Lk=Uk,ifΞ=∅,minLR^:R^∈Ξ,else.Setk=k+1 and Q=∅, and go to Step 1.


### 3.5. Convergence of the Algorithm

The global convergence of the algorithm is reproduced as follows.Theorem 3.
The above algorithm either terminates in a finite iteration and is accompanied by the generation of optimal values of problem (LFP) or produces an infinite sequencexk composed of feasible solutions and makes any convergence point of xk global optimal solutions for (LFP).Proof.
If this algorithm is terminated at iterationkk≥1, then according to Step 1 of the algorithm, we have(20)Uk−Lk≤ε.
So, ifx∗,y∗,z∗ is the global optimal solution of problem (EP), there is(21)Uk=φyk,zk≥φy∗,z∗≥Lk.
By integrating (20) and (21),(22)fx∗=φy∗,z∗≤fxk=φyk,zk≤φy∗,z∗+ε=fx∗+εcan be obtained. Thus, when the algorithm terminates in the k−th iteration, the corresponding solution fxk is a global optimal value of problem (LFP).
The algorithm produces an infinite sequencexk,yk,zk by solving a series of linear programs LRPRk. And each point of this sequence is a feasible point for problem (EP), respectively. From the algorithm, there will be an infinite sequence Rkk=1∞ of rectangles corresponding to this series of linear programs. By the branching process of Step 2, we have(23)limk⟶∞Rk=∏i=1py¯i0,y¯i0×limk⟶∞∏i=1pz¯ik,z¯ik=∏i=1py¯i0,y¯i0×∏i=1pzi∗.
Therefore, we have(24)limk⟶∞z¯ik=zi∗=limk⟶∞z¯ik,i=1,2,…,p.
Also, sincezik=hixk,i=1,2,…,p, we have(25)z¯ik≤zik=hixk≤z¯ik,i=1,2,…,p.
By (24) and (25), we have(26)hix∗=limk⟶∞hixk=limk⟶∞zik=zi∗.
Thus,x∗,y∗,z∗ is also a viable solution to problem (EP). Moreover, according to the properties of the branch-and-bound algorithm, the sequence Lk is an increasing sequence bounded by φy∗,z∗, and then we have(27)φy∗,z∗≥limk⟶∞Lk.
Through the update process of the lower bound in Step 4 of the algorithm, we have(28)limk⟶∞Lk=limk⟶∞ψ¯yk,zk.
Through Theorem2 and the continuity of function ψy,z, we have(29)limk⟶∞ψ¯yk,zk=limk⟶∞∑i=1pψ¯iyk,zk=φy∗,z∗.
By using the previous formulae (27), (28), and (29), we have(30)limk⟶∞Lk=φy∗,z∗.
Ultimately,x∗,y∗,z∗ is a global optimal solution to problem (EP), and then using equivalence Theorem 2, we can know that x∗ is a global optimal solution to problem (LFP) immediately. The proof is completed.


## 3.1. Bounding

Note that the objective function of the problemEPRk(or (EP)) is separable and still nonconvex. And then, we can propose a new underestimation method for yi/zii=1,2,…,p and give it through the following Theorem 2.Theorem 2.
Consider the rectangleLR≔y,z∈ℝ×ℝ:y¯≤y≤y¯,z¯≤z≤z¯, where y¯, y¯, z¯, and z¯ are all constants satisfying 0≤y¯≤y≤y¯ and 0<z¯≤z≤z¯. For any y,z∈LR, define the functions ψy,z and ψ¯y,z as follows:(6)ψy,z≔yz,ϕ1y,z≔−y¯zz¯z¯+yz¯+y¯2z¯−z¯z¯z¯z¯z¯,ϕ2y,z≔−y¯zz¯z¯+2z¯−z¯z¯yz¯z¯z¯+y¯z¯,ψ¯y,z≔maxϕ1y,z,ϕ2y,z.
Then, the following conclusions hold:(i)
For anyy,z∈LR, the functions ψy,z and ψ¯y,z satisfy(7)ψy,z≥ψ¯y,z.(ii)
Let∇=2y¯z¯/z¯z¯z¯+z¯ and Δ=z¯−z¯; then, limΔ⟶0ψy,z−ψ¯y,z=0.Proof.
(i)
For anyy,z∈LR, we have(8)ψy,z−ψ¯y,z=ψy,z−max−y¯zz¯z¯+yz¯+y¯2z¯−z¯z¯z¯z¯z¯,−y¯zz¯z¯+2z¯−z¯z¯yz¯z¯z¯+y¯z¯,=yz−maxyz¯+y¯2z¯z¯−zz¯z¯−y¯z¯,−1z¯z¯y¯z+yz¯−y¯z¯+2yz¯z¯,≥minyz−yz¯+y¯z−y¯z¯,yz−−yzz¯z¯+2yz¯z¯,=miny−y¯1z−1z¯,y1z−2z¯z¯−zz¯z¯,≥0.The establishment of the first inequality in formula (8) takes advantage of the convexity of the univariate function 1/z in the case of z>0, i.e., 1/z≥2/z¯z¯−z/z¯z¯. Moreover, the establishment of the first inequality of formula (8) also takes advantage of the fact that y−y¯z−z¯≤0. As a result, according to formula (8), it is easy to know ψy,z≥ψ¯y,z. Conclusion (i) holds.(ii)
By the definition ofψy,z and ψ¯y,z, we have(9)ψy,z−ϕ1y,z=yz−yz¯+y¯1z¯−2z¯z¯+zz¯z¯,≤y¯z¯−z¯z¯z¯+y¯z¯z¯z¯−2z¯z¯+z¯z¯z¯,=y¯z¯−z¯z¯z¯+y¯z¯z¯z¯−z¯2,≤y¯z¯z¯1+z¯−z¯z¯+z¯z¯−z¯,=2y¯z¯z¯−z¯z¯z¯z¯+z¯,=∇Δ,(10)ψy,z−ϕ2y,z=y1z−−zz¯z¯+2z¯z¯+1z¯z¯y¯−yz−z¯,≤y1z−zz¯z¯2+1z¯z¯y¯−y¯z¯−z¯,≤y¯z¯z¯z¯−z¯2+y¯z¯z¯z¯−z¯,=y¯z¯z¯1+z¯−z¯z¯+z¯z¯−z¯,=∇Δ.
According to formulae (9) and (10) and conclusion (i), we have(11)0≤limΔ⟶0ψy,z−ψ¯y,z≤limΔ⟶0∇Δ.
Since∇ is a bounded value, this implies that ∇Δ⟶0 as Δ⟶0. Thus, combined with (11), we have limΔ⟶0ψy,z−ψ¯y,z=0, and the proof is completed.
In the following, by using Theorem2, we will construct the lower bounding function of the objective function for problem EPRk(or (EP)). Assume that R^ denotes R or a subrectangle Rk of R that is generated by the branching process, where R^=∏i=1pR^i, with R^i=y¯i0,y¯i0×z¯i,z¯i,i=1,2,…,p. Obviously, y¯i0,y¯i0,z¯i,andz¯i satisfy 0≤y¯i0≤yi≤y¯i0and0<z¯i≤zi≤z¯i. For each i∈1,2,…,p and for each yi,zi∈R^i, define(12)ψiyi,zi≔yizi,ϕi1yi,zi≔−y¯i0ziz¯iz¯i+yiz¯i+y¯i02z¯i−z¯iz¯iz¯iz¯iz¯i,ϕi2yi,zi≔−y¯i0ziz¯iz¯i+2z¯i−z¯iz¯iyiz¯iz¯iz¯i+y¯i0z¯i,ψ¯iyi,zi≔maxϕi1yi,zi,ϕi2yi,zi.
Then, by Theorem2, we have(13)ψiyi,zi≥ψ¯iyi,zi,i∈1,2,…,p.
Thus, for anyy,z∈R^, let ψ¯y,z=∑i=1pψ¯iyi,zi, and we have(14)φy,z≥ψ¯y,z,∀y,z∈R^.
Furthermore, by using formulae (13) and (14), we can construct the following linear relaxation programming problem LRPR^ of EPR^:(15)LRPR^:ψ¯y,z=min∑i=1pri,s.t.ϕi1yi,zi≤ri,i=1,2,…,p,ϕi2yi,zi≤ri,i=1,2,…,p,gix−yi=0,i=1,2,…,p,hix−zi=0,i=1,2,…,p,x∈X,y,z∈R^.
Based on the construction method of the linear relaxation programming problemLRPR^, obviously, the optimal value for problem NLRPR^ is less than or equal to that of EPR^, i.e., vNLRPR^≤vEPR^. Then, we have vLRPR^=vNLRPR^≤vEPR^. Therefore, the linear relaxation programming problem LRPR^ provides a valid lower bound for the optimal value of EPR^.
It is noted that the solutionx^,y^,z^ obtained from the above linear relaxation programming problem LRPR^, which is used to progressively update the upper bound of the optimal value of problem (EP), is a feasible solution to problem (EP).


## 3.2. Branching

For the selected rectangleR^, we use the dichotomization as a branching process, which subdivides a 2p-dimensional rectangle(16)R^=∏i=1pR^i=∏i=1py¯i0,y¯i0×z¯i,z¯i⊆Rinto two 2p-dimensional subrectangles R^1 and R^2 of the same volume along the midpoint of its longest edge. The specific rectangle-branch method is as follows:(i)
Letj∈argmaxz¯i−z¯i,i=1,2,…,p.(ii)
R^j is divided into R^j1 and R^j2, i.e.,(17)R^j1=y¯j0,y¯j0×z¯j,z¯j+z¯j2,R^j2=y¯j0,y¯j0×z¯j+z¯j2,z¯j.(iii)
LetR^1=∏i=1j−1R^i×R^j1×∏i=j+1pR^iandR^2=∏i=1j−1R^i×R^j2×∏i=j+1pR^i.Be sure to note that the intervaly¯i0,y¯i0i=1,2,…,p is never subdivided during the branching process. Thus, the branching process occurs only in the p-dimensional space, which greatly saves this computational cost.


## 3.3. Pruning

SupposeLR^ is the lower bound of problem EPR^ over the rectangle R^ and U represents the best upper bound that the algorithm has known so far. And let ε∈0,1 represent the tolerance of the algorithm. Then, the pruning process is the transversion of deleting the node information on the branch-and-bound tree corresponding to the rectangle R^ that satisfies LR^>U−ε.


## 3.4. Output-Space Branch-and-Bound Algorithm

Now, we present an output-space branch-and-bound algorithm for solving (LFP). For thek-th iteration, we give the following notation in advance: Rk is the rectangle to be subdivided, Q represents a set that produces a new solution after each iteration (note that the number of elements in the set Q does not exceed 2), and Ξ is a collection of rectangles left after pruning. xk,yk,zk and LRk represent the optimal solution and optimal value of problem LRPRk over the rectangle Rk, respectively. Lk represents the current lower bound of the global optimal value of problem (EP), and Uk represents the current upper bound of the global optimal value of problem (EP). U′ represents the best function value of all new feasible solutions to the resulting problem (EP) after each iteration is completed.Combined with the above content, the proposed algorithm is as follows:Step 0 (initialization):y¯0,y¯0,z¯0, and z¯0 are obtained by (2), and then the initial rectangle R0=R is constructed. Set tolerance ε∈0,1. Then, the initial linear relaxation programming problem LRPR0 is solved, and its optimal solution x0,y0,z0 and optimal value LR0 are obtained. And then, let(18)U1=φy0,z0,L1=LR0,R1=R0,Ξ=R1,Q=∅,k=1.Step 1 (termination):IfUk−Lk≤ε, then terminate the algorithm. Then, xk,yk,zk is the global ε-optimal solution of problem (EP), and the global optimal solution of problem (LFP) can be obtained according to Theorem 1 which is xk. Otherwise, go to Step 2.Step 2 (branching):LetRk=R^∈Ξ:Lk=LR^ and Ξ=Ξ∖Rk. Then, using the rectangle-branching method in Section 3.2, Rk is divided into two subrectangles Rk1 and Rk2.Step 3 (pruning):For eachs∈1,2, solve LRPRks to obtain LRks and xks,yks,zks for Rks⊆Rk. If LRks≥Uk−ε, then delete the rectangle Rks. Otherwise, let Ξ=Ξ∪Rks and Q=Q∪xks,yks,zks.Step 4 (bounding):Step 4.1 (upper bounding):IfQ is not empty, let U′=minx,y,z∈Qφy,z. If U′<Uk, set Uk=U′ and xk,yk,zk=argminx,y,z∈Qφy,z.IfQ is empty, both Uk and xk,yk,zk remain the same.Step 4.2 (lower bounding):(19)Lk=Uk,ifΞ=∅,minLR^:R^∈Ξ,else.Setk=k+1 and Q=∅, and go to Step 1.


## 3.5. Convergence of the Algorithm

The global convergence of the algorithm is reproduced as follows.Theorem 3.
The above algorithm either terminates in a finite iteration and is accompanied by the generation of optimal values of problem (LFP) or produces an infinite sequencexk composed of feasible solutions and makes any convergence point of xk global optimal solutions for (LFP).Proof.
If this algorithm is terminated at iterationkk≥1, then according to Step 1 of the algorithm, we have(20)Uk−Lk≤ε.
So, ifx∗,y∗,z∗ is the global optimal solution of problem (EP), there is(21)Uk=φyk,zk≥φy∗,z∗≥Lk.
By integrating (20) and (21),(22)fx∗=φy∗,z∗≤fxk=φyk,zk≤φy∗,z∗+ε=fx∗+εcan be obtained. Thus, when the algorithm terminates in the k−th iteration, the corresponding solution fxk is a global optimal value of problem (LFP).
The algorithm produces an infinite sequencexk,yk,zk by solving a series of linear programs LRPRk. And each point of this sequence is a feasible point for problem (EP), respectively. From the algorithm, there will be an infinite sequence Rkk=1∞ of rectangles corresponding to this series of linear programs. By the branching process of Step 2, we have(23)limk⟶∞Rk=∏i=1py¯i0,y¯i0×limk⟶∞∏i=1pz¯ik,z¯ik=∏i=1py¯i0,y¯i0×∏i=1pzi∗.
Therefore, we have(24)limk⟶∞z¯ik=zi∗=limk⟶∞z¯ik,i=1,2,…,p.
Also, sincezik=hixk,i=1,2,…,p, we have(25)z¯ik≤zik=hixk≤z¯ik,i=1,2,…,p.
By (24) and (25), we have(26)hix∗=limk⟶∞hixk=limk⟶∞zik=zi∗.
Thus,x∗,y∗,z∗ is also a viable solution to problem (EP). Moreover, according to the properties of the branch-and-bound algorithm, the sequence Lk is an increasing sequence bounded by φy∗,z∗, and then we have(27)φy∗,z∗≥limk⟶∞Lk.
Through the update process of the lower bound in Step 4 of the algorithm, we have(28)limk⟶∞Lk=limk⟶∞ψ¯yk,zk.
Through Theorem2 and the continuity of function ψy,z, we have(29)limk⟶∞ψ¯yk,zk=limk⟶∞∑i=1pψ¯iyk,zk=φy∗,z∗.
By using the previous formulae (27), (28), and (29), we have(30)limk⟶∞Lk=φy∗,z∗.
Ultimately,x∗,y∗,z∗ is a global optimal solution to problem (EP), and then using equivalence Theorem 2, we can know that x∗ is a global optimal solution to problem (LFP) immediately. The proof is completed.


## 4. Numerical Experiments

In this section, several test problems are given to illustrate the performance of the algorithm. All of our testing procedures were performed via MATLAB (2012a) on computers with Intel(R) Core(TM)i5-2320 3.00 GHz power processor 4.00 GB memory and Microsoft Win7 operating system.Problem 1.
(see [1]).(31)min−3.333x1−3.000x2−1.0001.666x1+x2+1.000+−4.000x1−3.000x2−1.000x1+x2+1.000s.t.5.000x1+4.000x2≤10.000,−x2≤−0.100−2.000x1−x2≤−2.000,−2.000x1−x2≤−2.000x1,x2≥0.000.
For test Problem1, we use the proposed algorithm to address the problem in detail, which can explain the feasibility of the algorithm. Then, the calculation results of the three test problems in other literature studies are also calculated and indicated in Table 1 together with the results of Problem 1. First, for convenience, we denote the feasible domain of Problem 1 by(32)X≔5.000x1+4.000x2≤10.000,−x2≤−0.100,−2.000x1−x2≤−2.000,−2.000x1−x2≤−2.000,x1,x2≥0.000.
We also let(33)g1x=−3.333x1−3.000x2−1.000,g2x=−4.000x1−3.000x2−1.000,h1x=1.666x1+x2+1.000,h2x=x1+x2+1.000.
It is easy to see that the molecules of Problem1 are negative (i.e., g1x<0andg2x<0,∀x∈X), and we need to convert these two molecules into nonnegative functions. Next, we solve the following four linear programming problems:(34)y¯10=minx∈Xg1x,y¯20=minx∈Xg2x,z¯10=minx∈Xh1x,z¯20=minx∈Xh2x.
Among them,y¯10=−8.4583, y¯20=−8.9800, z¯10=2.6827, and z¯20=2.0500 are obtained by solving the above four linear programming problems. Apparently, y¯10≤g1x<0,y¯20≤g2x<0,h1x≥z¯10>0,andh2x≥z¯20>0, and we let(35)M1=−y¯10z¯10=3.1529>0,M2=−y¯20z¯20=4.3804>0.
Well, for anyx∈X, we have(36)g¯ix≔gix+Mihix=gix+−y¯i0z¯i0hix=z¯i0gix−y¯i0hixz¯i0=z¯i0gix−z¯i0y¯i0+z¯i0y¯i0−y¯i0hixz¯i0=z¯i0gix−y¯i0+y¯i0z¯i0−hixz¯i0≥0,i=1,2.
According to the above data, we can get(37)g¯1x=1.9197x1+0.1529x2+2.1529,g¯2x=0.3804x1+1.3804x2+3.3804.
As a result, Problem1 can be reconstructed as follows:(38)ming¯1xh1x+g¯2xh2x−M1+M2s.t.x∈X.
Therefore, the optimal solution of Problem1 is the same as that of the following problem (P):(39)P:ming¯1xh1x+g¯2xh2x,s.t.x∈X.
Now, we convert problem (P) into the following initial equivalence problem (EP1):(40)EP1:miny1z1+y2z2,s.t.g¯ix−yi=0,i=1,2,h¯ix−zi=0,i=1,2,x∈X,y,z∈R1,where(41)R1=2.62015.85413.88006.69712.68274.29872.05003.4750,1of flowchart1represents rectangleR1.
By solving the linear relaxation programming problemLPRR1 constructed over the rectangle R1, we can obtain the initial lower bound 2.5843, the initial upper bound 2.6918 of problem (EP1), and the corresponding optimal solution x1,y1,z1=0.1000;2.2357;2.7080;6.6972;3.5416;3.4750; then, we select the rectangle R1 corresponding to the initial lower bound and then generate the subrectangle(42)R11=2.62015.85413.88006.69712.68273.49072.05003.4750,R12=2.62015.85413.88006.69713.49074.29872.05003.4750by the branching operation. 2 of flowchart 1 represents rectangle R11; 3 of flowchart 1 represents rectangle R12; through solving linear programming problem LPRR11, the corresponding optimal solution and the optimal value are x11,y11,z11=0.1000;2.3241;2.7003;6.6269;3.4907;3.4241 and 2.5916, respectively, and the objective function value of problem (EP1) is 2.7086>2.6918, so the current optimal solution and optimal value of problem (EP1) are not updated. Then, we continue to solve linear programming problem LPRR12 and obtain the corresponding optimal solution and optimal value which are x12,y12,z12=0.1000;2.3257;2.7080;6.6972;3.5416;3.4750 and 2.5844, respectively, and the objective function value of problem (EP1) is 2.6919; then, the current optimal solution and optimal value of the problem will not be updated. As a result, the lower bound of the current problem (EP1) is updated to 2.5844. Next, we select the rectangle R12 corresponding to the contemporary lower boundary to divide and then obtain two subrectangles:(43)R21=2.62015.85413.88006.69713.49074.29872.05002.7625,R22=2.62015.85413.88006.69713.49074.29872.76253.4750.
4 of flowchart 1 represents rectangleR21; 5 of flowchart 1 represents rectangle R22; through solving linear programming problem LPRR21, the corresponding optimal value and the optimal solution are 2.8388>2.6918 and x21,y21,z21=1.6625;0.1000;5.3598;4.1511;3.8697;2.7625, respectively. So, this node is deleted. Then, we continue to solve linear programming problem LPRR22 and obtain the corresponding optimal solution and optimal value which are x22,y22,z22=0.1000;2.3750;2.7080;6.6972;3.5416;3.4750 and 2.6655, respectively, and the objective function value of problem (EP1) is 2.6918; then, the current optimal solution and optimal value of the problem will not be updated. As a consequence, the lower bound of the current problem (EP1) is updated to 2.5916. We continue to select the rectangle R11 corresponding to the current lower bound and divide it to obtain two subrectangles:(44)R31=2.62015.85413.88006.69712.68273.49072.05002.7625,R32=2.62015.85413.88006.69712.68273.49072.76253.4750.
6 of flowchart 1 represents rectangleR31; 7 of flowchart 1 represents rectangle R32; through solving linear programming problem LPRR31, the corresponding optimal value and the optimal solution are 2.9048>2.6918 and x31,y31,z31=1.0934;0.6691;4.3543;4.7202;3.4907;2.76250, respectively. So, this node is deleted. Then, we continue to solve linear programming problem LPRR32 and obtain the corresponding optimal solution and optimal value which are x32,y32,z32=0.1000;2.3241;2.7003;6.6269;3.4907;3.4241 and 2.6697, respectively, and the objective function value of problem (EP1) is 2.7089>2.6918; then, the current optimal solution and optimal value of the problem will not be updated. As a result, the lower bound of the current problem (EP1) is updated to 2.6655. Continue to select and section the rectangle R22 corresponding to the current lower bound, resulting in two subrectangles:(45)R41=2.62015.85413.88006.69713.49073.89472.76253.4750,R42=2.62015.85413.88006.69713.89474.29872.76253.4750.
8 of flowchart 1 represents rectangleR41; 9 of flowchart 1 represents rectangle R42; through solving linear programming problem LPRR41, the corresponding optimal value and the optimal solution are 2.6719 and x41,y41,z41=0.1000;0.3750;2.7080;6.6972;3.5416;3.4750, and the objective function value of problem (EP1) is 2.6918, respectively. Then, we continue to solve linear programming problem LPRR42 and get the corresponding optimal solution and value which are x42,y42,z42=0.9488;1.3139;4.1753;5.5554;3.8947;3.2628 and 2.7375>2.6918, respectively. So, this node is deleted; then, the current optimal solution and optimal value of the problem will not be updated. As a result, the lower bound of the current problem (EP1) is updated to 2.6697. Continue to select and section the rectangle R32 corresponding to the current lower bound, resulting in two subrectangles:(46)R51=2.62015.85413.88006.69712.68273.08672.76253.4750,R52=2.62015.85413.88006.69713.08673.49072.76253.4750.
10 of flowchart 1 represents rectangleR51; 11 of flowchart 1 represents rectangle R52; through solving linear programming problem LPRR51, the corresponding optimal value and the optimal solution are 2.8417>2.6918 and x51,y51,z51=0.1000;1.9201;2.6385;6.0692;3.0867;3.0201, respectively. So, this node is deleted. Then, we continue to solve linear programming problem LPRR52 and obtain the corresponding optimal solution and optimal value which are x52,y52,z52=0.0999;2.3241;2.7002;6.6269;3.4907;3.4241 and 2.6816, and the objective function value of problem (EP1) is 2.7089>2.6918, respectively; then, the current optimal solution and optimal value of the problem will not be updated. As a result, the lower bound of the current problem (EP1) is updated to 2.6719. Continue to select and section the rectangle R41 corresponding to the current lower bound, resulting in two subrectangles:(47)R61=2.62015.85413.88006.69713.49073.89472.76253.1188,R62=2.62015.85413.88006.69713.49073.89473.11883.4750.
12 of flowchart 1 represents rectangleR61; 13 of flowchart 1 represents rectangle R62; through solving linear programming problem LPRR61, the corresponding optimal value and the optimal solution are 2.8039>2.6918 and x61,y61,z61=0.7855;1.3332;3.8649;5.5198;3.6420;3.1188, respectively. So, this node is removed. Then, we continue to solve linear programming problem LPRR62 and obtain the corresponding optimal solution and optimal value which are x62,y62,z62=0.1000;2.3750;2.7080;6.6972;3.5416;3.4750 and 2.6850, and the objective function value of problem (EP1) is 2.6918, respectively; then, the current optimal solution and optimal value of problem (EP1) will not be updated. As a result, the lower bound of the current problem (EP1) is updated to 2.6816. Continue to select and section the rectangle R52 corresponding to the current lower bound, resulting in two subrectangles:(48)R71=2.62015.85413.88006.69713.08673.49072.76253.1188,R72=2.62015.85413.88006.69713.08673.49073.11883.4750.
14 of flowchart 1 represents rectangleR71; 15 of flowchart 1 represents rectangle R72; through solving linear programming problem LPRR71, the corresponding optimal value and the optimal solution are 2.8162>2.6918 and x71,y71,z71=0.1000;2.0188;2.6536;6.2054;3.1854;3.1188, respectively. So, this node is removed. Then, we continue to solve linear programming problem LPRR72 and obtain the corresponding optimal solution and optimal value which are x72,y72,z72=0.1000;2.3241;2.7003;6.6269;3.4907;3.4241 and 2.7008>2.6918, respectively. So, this node is deleted; then, the current optimal solution and optimal value of problem (EP1) will not be updated. So far, there is one node 13 left on the branch-and-bound tree, and the current best optimal value and best solution for problem (EP1) are 2.6918 and [0.1000; 2.3750; 2.7080; 6.6972; 3.5416; 3.4750], respectively. As a result, the lower bound of the current problem (EP1) is updated to 2.6850. At this point, in the current iteration, the difference between the upper and lower bounds of problem (EP1) satisfies 2.6918−2.6850=0.0068<0.01, so the algorithm iteration stops. Then, the optimal solution of Problem 1 (or (P)) is [0.1000; 2.3750], and the optimal value is 2.6918−M1+M2=−4.84151. The specific steps are shown in Figure 1.Table 1
Comparison of results in Problems1– 5.
ProblemReferenceSolutionOptimumIterTimeε1[1](0.1000, 2.3750)−4.841512010−2Ours(0.1000, 2.3750)−4.8415180.318710−22[8](1.5000, 1.5000)4.91254608.794410−4[21](1.5, 1.5)4.9125874561.087010−3Ours(1.5, 1.5)4.9125874731.809110−43[8](0.0000, 1.66666667, 0.0000)3.71091694.242910−6[21](0.0000, 1.66666667, 0.0000)3.71091980.183010−3Ours(0, 1.6667, 0)3.71091323.521410−64[8](0, 0.333333, 0)−3.0029209050.822610−6[21](0, 0.333333, 0)−3.0029170.129010−3Ours(0, 0.333333, 0)−3.0029381.023710−65[9](6.24409, 20.0249, 3.79672, 5.93972, 0, 7.43852, 0, 23.2833, 0.515015, 40.9896, 0, 3.14363)16.2619927—10−3[17](6.223689, 20.060317, 3.774684, 5.947841, 0, 7.456686, 0, 23.312579, 0.000204, 41.031824, 0, 3.171106)16.07797862065.5810−2Ours(6.22369, 20.0603, 3.7746, 5.94784,0, 7.45668, 0,23.31257, 0, 41.03182, 0, 3.17111)16.0779784157.881510−3Figure 1
Algorithm flowchart 1.Note. (a, b), where “a” represents the object value of the relaxation problem and “b” represents the object value of the original problem. Spherical arrows represent the termination nodes. Node box represents a corresponding reduced rectangle, and it is finally removed.Problem 2.
(see [8, 21])(49)min37x1+73x2+1313x1+13x2+13+63x1−18x2+3913x1+26x2+13s.t.5x1−3x2=3,1.5≤x1≤3.Problem 3.
see [1, 8, 21])(50)min4x1+3x2+3x3+503x2+3x3+50+3x1+4x3+504x1+4x2+5x3+50+x1+2x2+4x3+50x1+5x2+5x3+50+x1+2x2+4x3+505x2+4x3+50s.t.2x1+x2+5x3≤10,x1+6x2+2x3≤109x1+7x2+3x3≥10,x1,x2,x3≥0.Problem 4.
(see [1, 8, 21])(51)min−3x1+5x2+3x3+503x1+4x2+5x3+50−3x1+4x2+504x1+3x2+2x3+50−4x1+2x2+4x3+505x1+4x2+3x3+50s.t.6x1+3x2+3x3≤10,10x1+3x2+8x3≤10,x1,x2,x3≥0.Problem 5.
(see [9, 17])(52)max∑i=15ciTx+dieiTx+fis.t.Ax≤b,x≥0,where(53)c1=0.0,−0.1,−0.3,0.3,0.5,0.5,−0.8,0.4,−0.4,0.2,0.2,−0.1T,d1=14.6,e1=−0.3,−0.1,−0.1,−0.1,0.1,0.4,0.2,−0.2,0.4,0.2,−0.4,0.3T,f1=14.2,c2=0.2,0.5,0.0,0.4,0.1,−0.6,−0.1,−0.2,−0.2,0.1,0.2,0.3T,d2=7.1,e2=0.0,0.1,−0.1,0.3,0.3,−0.2,0.3,0.0,−0.4,0.5,−0.3,0.1T,f2=1.7,c3=−0.1,0.3,0.0,0.1,−0.1,0.0,0.3,−0.2,0.0,0.3,0.5,0.3T,d3=1.7,e3=0.8,−0.4,0.7,−0.4,−0.4,0.5,−0.2,−0.8,0.5,0.6,−0.2,0.6T,f3=8.1,c4=−0.1,0.5,0.1,0.1,−0.2,−0.5,0.6,0.7,0.5,0.7,−0.1,0.1T,d4=4.0,e4=0.0,0.6,−0.3,0.3,0.0,0.2,0.3,−0.6,−0.2,−0.5,0.8,−0.5T,f4=26.9,c5=0.7,−0.5,0.1,0.2,−0.1,−0.3,0.0,−0.1,−0.2,0.6,0.5,−0.2T,d5=6.8,e5=0.4,0.2,−0.2,0.9,0.5,−0.1,0.3,−0.8,−0.2,0.6,−0.2,−0.4T,f5=3.7,A=−1.8−2.20.84.13.8−2.3−0.82.5−1.60.2−4.5−1.84.6−2.01.43.2−4.2−3.31.90.70.8−4.44.42.03.7−2.8−3.2−2.0−3.7−3.33.5−0.71.5−3.14.5−1.1−0.6−0.6−2.54.10.63.32.8−0.14.1−3.2−1.2−4.31.8−1.6−4.5−1.34.63.34.2−1.21.92.43.4−2.9−0.5−4.11.73.9−0.1−3.9−1.51.62.3−2.3−3.23.90.31.71.34.70.93.9−0.5−1.23.80.6−0.2−1.50.5−4.23.6−0.6−4.81.5−0.30.6−3.60.23.8−2.80.13.3−4.32.44.11.71.0−3.34.4−3.7−1.1−1.4−0.62.22.51.3−4.3−2.9−4.12.7−0.8−2.93.51.24.31.9−4.0−2.61.82.50.61.3−4.3−2.34.1−1.10.00.4−4.5−4.41.2−3.8−1.91.23.0−1.1−0.22.5−0.1−1.72.91.54.7−0.34.2−4.4−3.94.44.7−1.0−3.81.4−4.71.93.83.51.52.3−3.7−4.22.7−0.10.2−0.14.9−0.90.14.31.62.61.5−1.00.81.6,b=15.7,31.8,−36.4,38.5,40.3,10.0,89.8,5.8,2.7,−16.3,−14.6,−72.7,57.7,−34.5,69.1T.Problem 6.
(see [1])(54)min∑i=1p∑j=1najixj+bi∑j=1ncjixj+dis.t.∑j=1nQjlxj≤ql,l=1,2,…,m,x≥0,where both real numbers aji, cji and Qjl are randomly generated in the interval [0, 10], bi=di=10, and ql=10, which are the same as the data generation method in [1].
Besides, as can be seen from Table1, the algorithm in this paper can effectively solve the five test problems known in the literature. Through the description of the solving process of Problem 1, it can be seen that the proposed algorithm finds the optimal solution in the initial iteration, but the branch-and-bound algorithm needs to run again 7 times, which can make the upper and lower bounds meet the precision requirements. The results are not as good as the methods in [1]. However, Problem 1 is a small-scale example. In the relatively large-scale random experiments to Problem 6 in the following, the numerical results show that the proposed algorithm is better than that of [1]. At least, the algorithm is better than the algorithm in [8] when solving Problems 2– 4. And then, for Problem 5, we find that the solution obtained by the algorithm in [9] is not feasible, but the solution solved by the algorithm in [17] is feasible, and the results obtained by the proposed algorithm are the same as those obtained in [17], and the number of iterations used is less than the previous two.
Next, we also perform random tests on Problem6 to further explore the performance of the algorithm. We set the convergence accuracy of the algorithm to 0.01. For each set of the fixed parameter p,m,n, we run the algorithm 15 times to compare with the algorithm in [1] and give the numerical results in Table 2. In addition, we have done a series of large-scale numerical experiments, and the numerical results are also indicated in Table 3. In Tables 2 and 3, Avg.Time and Avg.Iter represent the average CPU run time and average number of iterations applied by the algorithm to run 15 times, and Std.Time and Std.Iter represent the standard deviation of the CPU run time and number of iterations used by the algorithm to run 15 times, respectively.
Table2 shows that the proposed algorithm is better than the one in [1] in terms of average CPU running time and average number of iterations. In addition, from the standard deviation of the number of iterations and CPU running time, it can be seen that our algorithm is more stable than the algorithm in [1]. Moreover, it can be seen from the data in Tables 2 and 3 that, under the premise of fixed parameter p,m, the CPU running time required by the algorithm is gradually increasing with the scale of Problem 6. On the premise of fixed parameter m,n, however, the CPU running time and iteration times of the algorithm are increasing with the increase of the number p of the linear fraction in the objective function of problem (LFP). Interestingly, the numerical results in Table 3 show that our algorithm has more advantages in solving large-scale (LFP) problems when p≪n, which is in agreement with the conclusions described in [8].Table 2
Comparison of numerical results by using Problem 6.
(p, m, n)The algorithm of the [1]Our algorithm in this paperAvg (Std).IterAvg (Std).TimeAvg (Std).IterAvg (Std).Time(2,100,100)48.3571 (17.2386)3.9248 (1.7489)16.8667(5.4267)2.2959 (0.7955)(2,100,500)67 (27.1833)20.0863 (10.6748)17.3333 (4.7703)8.9810 (2.6774)(2,100,800)78 (7.1614)42.3103 (19.5719)16.4000 (4.1091)14.3999 (4.2656)(2,100,1000)75.2308 (24.3145)57.3531 (35.5371)14.9333 (2.5157)16.1681 (3.2219)(2,100,1500)86.0769 (5.7076)107.0487 (37.6392)15.2667 (2.4891)27.3314 (5.2243)(2,100,2000)88.5333 (7.7724)152.7871 (62.4697)15 (1.1596)37.5513 (4.4475)(2,100,2500)92.8462 (5.9979)184.3362 (66.3833)16 (3.0984)54.4253 (12.8335)(2,100,3000)91.9000 (7.7810)296.6591 (32.0870)15.0667 (2.5157)63.8862 (13.5362)(3,50,50)230.5217 (74.0483)5.2437 (1.6432)64.9333 (36.3858)3.1009 (1.5003)(3,50,100)317.6522 (69.9140)10.0783 (2.5300)79.8000 (42.6555)4.8213 (2.4819)(3,50,200)329 (85.8534)15.6736 (4.0080)99.6667 (55.4997)9.3447 (3.8551)(3,50,500)367.9412 (85.5055)34.1162 (8.4457)89.7333 (37.3050)18.4939 (8.0485)(3,50,1000)387.6667 (80.9100)111.7268 (56.1365)86.8667 (27.7101)35.3195 (11.5188)(3,50,2000)462.6667 (112.0655)242.6109 (117.1050)86.2667 (22.8195)80.6322 (21.9889)(3,100,50)236.0714 (74.0088)11.4581 (7.0665)78.6000 (65.1356)8.1895 (6.8602)(3,100,100)252.8182 (74.0362)20.5326 (8.1031)89 (57.1116)12.8639 (8.5089)(3,100,200)290.8824 (54.0600)44.2078 (20.3639)78.8000 (33.2189)18.2206 (7.6801)(3,100,300)313.9167 (79.1483)62.4293 (29.0958)79.6667 (33.3500)26.5176 (12.0702)(3,100,400)326.5333 (72.9421)80.5609 (28.5460)83.0667 (23.9429)36.1708 (11.4116)(3,100,500)338.5833 (63.1278)91.9672 (36.7591)91.4667 (40.4242)50.8475 (24.0507)Table 3
Numerical results for Problem6 with large-scale variables.
p,m,nAvg (Std).IterAvg (Std).Time(2, 100, 4000)15.4000 (3.3025)96.5791 (25.2020)(2, 100, 5000)15.5333 (2.2171)133.1045 (24.0255)(3, 100, 1000)80.3333 (21.2781)93.9706 (25.2906)(3, 100, 2000)87.0667 (29.1330)243.9302 (87.2392)(3, 100, 3000)74.2667 (15.0309)350.9187 (75.8487)(3, 100, 4000)69.0667 (14.7036)484.1551 (110.7565)(3, 100, 5000)65.0667 (15.8513)606.5856 (154.7327)(4, 100, 1000)459.9333 (239.5927)577.2682 (322.2345)(4, 100, 2000)508.5333 (239.1791)1462.4441 (692.1418)(4, 100, 3000)403.8667 (161.4930)1997.0592 (825.9073)(5, 100, 1000)1908.4000 (1298.0444)1795.8044 (769.7409)(6, 100, 1000)4874.2000 (2968.7632)4714.3262 (936.0817)


## 5. Concluding Remarks

In this paper, we mainly propose an algorithm that can address problem (LFP) effectively. Based on the branching operation of thep-dimensional output space, a unique construction method of the linear lower-bound relaxation subproblem is given. A branch-and-bound algorithm is therefore proposed to find the global optimal solution of problem (LFP) by combining the pruning operation. Numerical experiments show that their algorithm is effective and feasible, its calculation effect is better than that in [1], and it is more suitable for solving large-scale (LFP) problems in the case of p≪n. Moreover, linear fractional programming problems in uncertain environments (such as [31–34]) have also been gradually studied by relevant scholars. In future studies, we will also try to gradually study the linear fractional programming problems in uncertain environments.



---

*Source: 3580419-2020-11-10.xml*