# An Efficient Branch-and-Bound Algorithm for Globally Solving Minimax Linear Fractional Programming Problem

Authors: Pujun Jia; Hongwei Jiao; Dongwei Shi; Jingben Yin
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

This paper presents an efficient outer space branch-and-bound algorithm for globally solving a minimax linear fractional programming problem (MLFP), which has a wide range of applications in data envelopment analysis, engineering optimization, management optimization, and so on. In this algorithm, by introducing auxiliary variables, we first equivalently transform the problem (MLFP) into the problem (EP). By using a new linear relaxation technique, the problem (EP) is reduced to a sequence of linear relaxation problems over the outer space rectangle, which provides the valid lower bound for the optimal value of the problem (EP). Based on the outer space branch-and-bound search and the linear relaxation problem, an outer space branch-and-bound algorithm is constructed for globally solving the problem (MLFP). In addition, the convergence and complexity of the presented algorithm are given. Finally, numerical experimental results demonstrate the feasibility and efficiency of the proposed algorithm.


---

## Body

## 1. Introduction

This paper considers the following minimax linear fractional programming problem:(1)MLFP:minmaxφ1xψ1x,φ2xψ2x,…,φpxψpxs.t.x∈D=x∈Rn|Ax≤b,where p≥2, A∈Rm×n, b∈Rm, D is a nonempty bounded polyhedral set, and φix=∑j=1ncijxj+di and ψix=∑j=1neijxj+fi are all bounded affine functions over D, and for ∀x∈D, we have that φix≥0 and ψix>0,i=1,…,p.The problem (MLFP) has aroused the interest of many practitioners and researchers. On the one hand, it has a wide range of applications, such as electronic circuit design [1], system identification [2–4], and finance and investment [5]. On the other hand, because it has multiple local optimal solutions that are not globally optimal, it is still challenging to solve the problem (MLFP). So, it is necessary to come up with an efficient algorithm to globally solve the problem (MLFP).In the past few decades, many algorithms have been proposed for solving some special forms of the problem (MLFP). In general, these algorithms can be classified into the following categories: interior-point algorithm [6], parameter programming method [7], partial linearization algorithm [8], monotonic optimization method [9], cutting plane algorithm [10], and branch-and-bound algorithm [11–19]. In addition to the above algorithms, in recent years, Chen et al. [20] proposed a unified framework to study various versions of Dinkelbach-type algorithms for solving the generalized fractional programming problem; based on a proximal bundle method, Boualam and Roubi [21] designed a dual algorithm for solving the convex minimax fractional programming problem; by analyzing the dual method of centers, Boufi and Roubi [22] presented an algorithm for solving the generalized fractional programs; Lai and Huang [23] presented a duality programming problem for solving a complex nondifferentiable minimax fractional programming with complex variables. However, the above algorithms can only deal with some specific cases of the problem (MLFP). Therefore, it is necessary to propose an efficient algorithm for globally solving the general form of the problem (MLFP).In this paper, we present an efficient outer space branch-and-bound algorithm for globally solving the minimax linear fractional programming problem (MLFP). In this algorithm, we first transform the problem (MLFP) into an outer space equivalent problem (EP) by introducing auxiliary variables. Then, in order to obtain the lower bound of the optimal value of the problem (EP), a new linear relaxation technique is proposed to construct the linear relaxation problem (LRP) of the problem (EP) over the outer space rectangle. And we can solve the problem (EP) by solving a sequence of linear relaxation problems over the outer space rectangle. Based on the outer space branch-and-bound search and the new linear relaxation problem over the outer space rectangle, we present an outer space branch-and-bound algorithm for globally solving the problem (MLFP). In addition, the global convergence and the computational complexity of the proposed algorithm are given. The numerical results demonstrate that the proposed algorithm can effectively find the global optimal solutions for all tested instances. The numerical comparisons among our algorithm and the algorithms of Feng et al. [8], Jiao and Liu [12], and Wang et al. [24] indicate that our algorithm outperforms the algorithms presented in Feng et al. [8], Jiao and Liu [12], and Wang et al. [24].This paper is organized as follows. In Section2, the equivalent problem (EP) of the problem (MFLP) is obtained, and by utilizing the new linear relaxation technique, the linear relaxation problem (LRP) of the problem (EP) over the outer space rectangle is constructed. In Section 3, an efficient outer space branch-and-bound algorithm is described, and the global convergence and the computational complexity of the proposed algorithm are given. Numerical results are reported to show the feasibility and efficiency of the proposed algorithm in Section 4. Finally, some conclusions are presented in Section 5.


## 2. Equivalent Problem and Its Linear Relaxation

For globally solving the problem (MLFP), we need to establish its equivalent problem (EP). For this purpose, we first compute the initial lower boundβ¯i0=minx∈Dψix and the upper bound β¯i0=maxx∈Dψix of the function ψix over D so that we can obtain the initial outer space rectangle:(2)Ω0=ψix∈Rp|β¯i0≤ψix≤β¯i0,i=1,2,…,p.By introducing a new variabler, we can establish the outer space equivalent problem (EP) of the problem (MLFP) as follows:(3)EP:minrs.t.φixψix≤r,i=1,2,…,p,β¯i0≤ψix≤β¯i0,i=1,2,…,p,Ax≤b.Theorem 1.
x∗,r∗ is a global optimal solution of the problem (EP) if and only if x∗ is a global optimal solution of the problem (MLFP).Proof.
The conclusion of the theorem is obvious; therefore, the proof is omitted.
From Theorem1, for globally solving the problem (MLFP), we can globally solve its equivalence problem (EP) instead; they have the same optimal solutions and optimal value. In order to globally solve the problem (EP), we need to construct its linear relaxation problem of the problem (EP) over the outer space rectangle, which can provide a reliable lower bound for the optimal value of the problem (EP). And the next main task is to construct the linear relaxation problem of the problem (EP).
First of all, letΩ=ψix∈Rp|β¯i≤ψix≤β¯i,i=1,2,…,p denote the initial rectangle Ω0 or a subrectangle of Ω0 that is generated by the branching operation. Then, for convenience in expression, some notations are introduced as follows:(4)α¯i0=minx∈Dφix,α¯i0=maxx∈Dφix.
From the above formulas, it is easy to see that0≤α¯i0≤φix≤α¯i0,0<β¯i≤ψix≤β¯i,i=1,2,…,p. And we consider the term φix/ψix,i=1,2,…,p, and it follows that α¯i0ψix−β¯iφix≥0, ψix−β¯i≥0, so that we have(5)α¯i0ψix−β¯iφixψix−β¯i≥0.
Expanding the above formula, we have that(6)α¯i0ψi2x−α¯i0β¯iψix−β¯iφixψix+β¯i2φix≥0.
Sinceβ¯i2ψix>0, we divide both ends of the above inequality by β¯i2ψix at the same time, and we can obtain that(7)φixψix≥φixβ¯i−α¯i0β¯i2ψix+α¯i0β¯i.
LetΨix,r=φix/ψix−r; we have the following relation:(8)Ψix,r=φixψix−r≥φixβ¯i−α¯i0β¯i2ψix+α¯i0β¯i−r=Ψilx,r.
Through the above discussions, the linear relaxation problem of the problem (EP) over the outer space rectangleΩ is constructed as follows:(9)LRP:minrs.t.Ψilx,r≤0,i=1,2,…,p,β¯i≤ψix≤β¯i,i=1,2,…,p,Ax≤b.
From the above results, the optimal value of the problem (LRP) is less than or equal to that of the problem (EP) overΩ. Therefore, the problem (LRP) can provide a valid lower bound for the optimal value of the problem (EP) over Ω. Theorem 2 will show that the problem (LRP) will infinitely approximate the problem (EP) over Ω as β¯−β¯⟶0.Theorem 2.
For anyψix∈Ω=β¯,β¯, we consider the functions Ψilx,r and Ψix,r. Then, we have that(10)limβ¯−β¯⟶0Ψix,r−Ψilx,r⟶0.Proof.
From the definitionsΨix,r and Ψilx,r, we have(11)Ψix,r−Ψilx,r=φixψix−φixβ¯i−α¯i0β¯i2ψix+α¯i0β¯i=φixψix−φixβ¯i+α¯i0β¯i2ψix−α¯i0β¯i≤φix1ψix−1β¯i+α¯i0β¯iψixβ¯i−1=φixβ¯i−ψixψixβ¯i+α¯i0β¯iψix−β¯iβ¯i≤α¯i0β¯i−β¯iβ¯i2+α¯i0β¯iβ¯i−β¯iβ¯i=2α¯i02β¯i2β¯i−β¯i.
Therefore, we have that(12)limβ¯−β¯⟶0Ψix,r−Ψilx,r⟶0,and the proof of the theorem is completed.
From Theorem2, we can know that the linear relaxation function Ψilx,r will infinitely approximate the function Ψix,r as β¯−β¯⟶0, which guarantees the global convergence of the proposed algorithm.


## 3. Algorithm, Global Convergence, and Complexity Analysis

In this section, we first describe the outer space branching rule. Then, based on the outer space partitioning search and the linear relaxation problem, an efficient outer space branch-and-bound algorithm is developed to globally solve the problem (MLFP). Finally, the global convergence and the computational complexity of the presented algorithm are derived.


### 3.1. Outer Space Partitioning Rule

The important factor to ensure that the proposed algorithm in this paper can converge to the global minimum of the problem (MLFP) is to choose a suitable outer space partitioning strategy. In this paper, we choose an outer space rectangle bisection method, which can ensure the global convergence of the proposed outer space branch-and-bound algorithm. The proposed outer space partitioning rule is given as follows.Consider any node subproblem identified by the subrectangleΩ=ψix∈Rp|β¯i≤ψix≤β¯i,i=1,2,…,p⊆Ω0; the branching rule is described as follows:(i)
Letτ=argmaxβ¯i−β¯i|i=1,2,…,p.(ii)
Let(13)Ω′=ψix∈Rp|β¯i≤ψix≤β¯i,i=1,2,…,p,i≠τ,β¯τ≤ψτx≤β¯τ+β¯τ2,Ω″=ψix∈Rp|β¯i≤ψix≤β¯i,i=1,2,…,p,i≠τ,β¯τ+β¯τ2≤ψτx≤β¯τ.From the outer space partitioning rule, it can be seen that the outer space rectangleΩ is partitioned into two outer space subrectangles Ω′ and Ω″.


### 3.2. Algorithm Statement

By the above discussions, the basic steps of the proposed algorithm are given as follows. LetLBΩk and xΩk,rΩk be the optimal objective functional value of the problem (LRP) and an element of the corresponding argmin over the subrectangle Ωk, respectively.Step 1: given the convergence toleranceε≥0, the set of feasible points F=∅ and the upper bound UB0=+∞.Solve the problem LRPΩ0 for obtaining its optimal solution xΩ0,rΩ0 and optimal value LBΩ0. Let x0,r0=xΩ0,rΩ0 and LB0=LBΩ0.Ifx0,r0 is feasible to the problem (EP), then we update F and UB0.IfUB0−LB0≤ε, then the algorithm stops with that x0,r0 is an ε-global optimal solution for the problem (EP); otherwise, set Θ0=Ω0 be the set of all active notes, k=1, and go to step 2.Step 2: letUBk=UBk−1, select and subdivide Ωk−1 into two subrectangles Ωk,1 and Ωk,2 based on the branching rule. Set Ω¯=Ωk,1,Ωk,2.Step 3: for eachΩk,s∈Ω¯s=1,2, solve the problem LRP Ωk,s to get the lower bound LBΩk,s and xΩk,s,rΩk,s.IfLBΩk,s>UBk, let Ω¯=Ω¯\Ωk,s; otherwise, set(14)F=F∪xΩ,rΩ.Update the upper bound:(15)UBk=minUBk,rΩk,s.IfUBk=rΩk,s, let xk,rk=xΩk,s,rΩk,s, and it is obvious that xk,rk is the best feasible solution for the problem (EP). Let Θk=Θk−1\Ωk−1∪Ω¯ and LBk=minLBΩ|Ω∈Θk.Step 4: setΘk+1=Θk\Ω:UBk−LBΩ>ε,Ω∈Θk.IfΘk+1=∅, then the algorithm stops, and xk,rk is an ϵ-global optimal solution of the problem (EP).Otherwise, select the new subrectangleΩk such that Ωk+1=argminΩ∈ΘkLBΩ; let k=k+1, and return to step 2.


### 3.3. Convergence Analysis

The following theorem gives the proof of the convergence of the above algorithm.Theorem 3.
The proposed algorithm either terminates finitely with the solutionxk which is a global ϵ-optimal solution for the problem (MLFP) or generates an infinite sequence xk of iterations such that any infinite branch of the branch-and-bound tree and any accumulation point will be a global optimal solution of the problem (MLFP).Proof.
When the algorithm is finitely terminated, the conclusion is obvious. When the algorithm is not finitely terminated, Horst and Tuy [25] point out that a sufficient condition for the algorithm to be convergent to the global minimum is that the bounding operation must be consistent and the selection operation is bound improving.
LetLBk be a lower bound computed in stage k, and let UBk be the best upper bound at iteration k not necessarily occurring inside the same subrectangle with LBk. A bounding operation is called consistent if, at every step, any unfathomed partition can be further refined, and since our subdivision process is the bisection, the branching process is exhaustive. Therefore, from Theorem 2, we have that(16)limk⟶∞UBk−LBk=0.
Then, this implies that the employed bounding operation is consistent.
A selection operation is called bound improving if at least one partition element where the actual upper bound is attained is selected for further partition after a finite number of refinements. Obviously, since the partition element where the actual upper bound is attained is selected for further partition in the immediately following iteration, the employed selection operation is bound improving.
In general, it can show that the bounding operation is consistent and that selection operation is bound improving. Therefore, the proposed algorithm is convergent to the global minimum of the problem (MFLP), and the proof of the theorem is completed.


### 3.4. Computational Complexity Analysis

In this section, we will analyze the complexity of the algorithm. To this end, we define the sizeΔΩ of a rectangle Ω=ψix∈Rp|β¯i≤ψix≤β¯i,i=1,2,…,p⊆Ω0, given by(17)ΔΩ≔maxβ¯i−β¯i|i=1,2,…,p.Additionally, for convenience, we denote by(18)μ=max2α¯i02β¯i02,i=1,2,…,p.Theorem 4.
Given the convergence toleranceε>0, if there exists a rectangle Ωk generated by the algorithm at kth iteration, such that ΔΩk≤ε/μ, then we have(19)UB−LBΩk≤ε,where LBΩk is the optimal value to the problem (LRP Ωk) and UB is the best current known upper bound of the optimum value to the problem (EP).Proof.
From Theorem2, ΔΩk≤ε/μ, and the definition of α¯i0, β¯i, and β¯i, we have(20)UB−LBΩk≤max2α¯i02β¯i2β¯i−β¯i,i=1,2,…,p≤max≤ε,2α¯i02β¯i02β¯i−β¯i,i=1,2,…,p≤μΔΩ,and the proof of the theorem is completed.Remark 1.
Given the convergence toleranceε>0, the proposed algorithm finds a global ε-optimal solution to the problem (MFLP) in at most iterations:(21)N=2∑i=1plog2μβ¯i0−β¯i0/ε−1.
Based on the above discussions, the maximum iterations of the algorithm can be obtained by analyzing the computational complexity of the proposed algorithm.


## 3.1. Outer Space Partitioning Rule

The important factor to ensure that the proposed algorithm in this paper can converge to the global minimum of the problem (MLFP) is to choose a suitable outer space partitioning strategy. In this paper, we choose an outer space rectangle bisection method, which can ensure the global convergence of the proposed outer space branch-and-bound algorithm. The proposed outer space partitioning rule is given as follows.Consider any node subproblem identified by the subrectangleΩ=ψix∈Rp|β¯i≤ψix≤β¯i,i=1,2,…,p⊆Ω0; the branching rule is described as follows:(i)
Letτ=argmaxβ¯i−β¯i|i=1,2,…,p.(ii)
Let(13)Ω′=ψix∈Rp|β¯i≤ψix≤β¯i,i=1,2,…,p,i≠τ,β¯τ≤ψτx≤β¯τ+β¯τ2,Ω″=ψix∈Rp|β¯i≤ψix≤β¯i,i=1,2,…,p,i≠τ,β¯τ+β¯τ2≤ψτx≤β¯τ.From the outer space partitioning rule, it can be seen that the outer space rectangleΩ is partitioned into two outer space subrectangles Ω′ and Ω″.


## 3.2. Algorithm Statement

By the above discussions, the basic steps of the proposed algorithm are given as follows. LetLBΩk and xΩk,rΩk be the optimal objective functional value of the problem (LRP) and an element of the corresponding argmin over the subrectangle Ωk, respectively.Step 1: given the convergence toleranceε≥0, the set of feasible points F=∅ and the upper bound UB0=+∞.Solve the problem LRPΩ0 for obtaining its optimal solution xΩ0,rΩ0 and optimal value LBΩ0. Let x0,r0=xΩ0,rΩ0 and LB0=LBΩ0.Ifx0,r0 is feasible to the problem (EP), then we update F and UB0.IfUB0−LB0≤ε, then the algorithm stops with that x0,r0 is an ε-global optimal solution for the problem (EP); otherwise, set Θ0=Ω0 be the set of all active notes, k=1, and go to step 2.Step 2: letUBk=UBk−1, select and subdivide Ωk−1 into two subrectangles Ωk,1 and Ωk,2 based on the branching rule. Set Ω¯=Ωk,1,Ωk,2.Step 3: for eachΩk,s∈Ω¯s=1,2, solve the problem LRP Ωk,s to get the lower bound LBΩk,s and xΩk,s,rΩk,s.IfLBΩk,s>UBk, let Ω¯=Ω¯\Ωk,s; otherwise, set(14)F=F∪xΩ,rΩ.Update the upper bound:(15)UBk=minUBk,rΩk,s.IfUBk=rΩk,s, let xk,rk=xΩk,s,rΩk,s, and it is obvious that xk,rk is the best feasible solution for the problem (EP). Let Θk=Θk−1\Ωk−1∪Ω¯ and LBk=minLBΩ|Ω∈Θk.Step 4: setΘk+1=Θk\Ω:UBk−LBΩ>ε,Ω∈Θk.IfΘk+1=∅, then the algorithm stops, and xk,rk is an ϵ-global optimal solution of the problem (EP).Otherwise, select the new subrectangleΩk such that Ωk+1=argminΩ∈ΘkLBΩ; let k=k+1, and return to step 2.


## 3.3. Convergence Analysis

The following theorem gives the proof of the convergence of the above algorithm.Theorem 3.
The proposed algorithm either terminates finitely with the solutionxk which is a global ϵ-optimal solution for the problem (MLFP) or generates an infinite sequence xk of iterations such that any infinite branch of the branch-and-bound tree and any accumulation point will be a global optimal solution of the problem (MLFP).Proof.
When the algorithm is finitely terminated, the conclusion is obvious. When the algorithm is not finitely terminated, Horst and Tuy [25] point out that a sufficient condition for the algorithm to be convergent to the global minimum is that the bounding operation must be consistent and the selection operation is bound improving.
LetLBk be a lower bound computed in stage k, and let UBk be the best upper bound at iteration k not necessarily occurring inside the same subrectangle with LBk. A bounding operation is called consistent if, at every step, any unfathomed partition can be further refined, and since our subdivision process is the bisection, the branching process is exhaustive. Therefore, from Theorem 2, we have that(16)limk⟶∞UBk−LBk=0.
Then, this implies that the employed bounding operation is consistent.
A selection operation is called bound improving if at least one partition element where the actual upper bound is attained is selected for further partition after a finite number of refinements. Obviously, since the partition element where the actual upper bound is attained is selected for further partition in the immediately following iteration, the employed selection operation is bound improving.
In general, it can show that the bounding operation is consistent and that selection operation is bound improving. Therefore, the proposed algorithm is convergent to the global minimum of the problem (MFLP), and the proof of the theorem is completed.


## 3.4. Computational Complexity Analysis

In this section, we will analyze the complexity of the algorithm. To this end, we define the sizeΔΩ of a rectangle Ω=ψix∈Rp|β¯i≤ψix≤β¯i,i=1,2,…,p⊆Ω0, given by(17)ΔΩ≔maxβ¯i−β¯i|i=1,2,…,p.Additionally, for convenience, we denote by(18)μ=max2α¯i02β¯i02,i=1,2,…,p.Theorem 4.
Given the convergence toleranceε>0, if there exists a rectangle Ωk generated by the algorithm at kth iteration, such that ΔΩk≤ε/μ, then we have(19)UB−LBΩk≤ε,where LBΩk is the optimal value to the problem (LRP Ωk) and UB is the best current known upper bound of the optimum value to the problem (EP).Proof.
From Theorem2, ΔΩk≤ε/μ, and the definition of α¯i0, β¯i, and β¯i, we have(20)UB−LBΩk≤max2α¯i02β¯i2β¯i−β¯i,i=1,2,…,p≤max≤ε,2α¯i02β¯i02β¯i−β¯i,i=1,2,…,p≤μΔΩ,and the proof of the theorem is completed.Remark 1.
Given the convergence toleranceε>0, the proposed algorithm finds a global ε-optimal solution to the problem (MFLP) in at most iterations:(21)N=2∑i=1plog2μβ¯i0−β¯i0/ε−1.
Based on the above discussions, the maximum iterations of the algorithm can be obtained by analyzing the computational complexity of the proposed algorithm.


## 4. Numerical Experiments

In this section, we numerically compare our algorithm with the existing branch-and-bound-algorithms presented in the works of Feng et al. [8], Jiao and Liu [12], and Wang et al. [24]. All algorithms are coded in MATLAB R2014a; our algorithm is executed on the microcomputer with Intel(R) Core(TM) i7-10700K CPU @3.80 GHz processor and 32 GB RAM. All test examples and their numerical results are listed as follows.First of all, for Examples1–8, when n is smaller, with the given approximation error ε=10−6, numerical comparisons among our algorithm and the algorithms presented in works of Feng et al. [8], Jiao and Liu [12], and Wang et al. [24] are given in Table 1. Next, for randomly generated large-scale Example 9, when n≥1000, with the given approximation error ε=10−4, numerical computational results of our algorithm are given in Table 2. When n≥1000, since the algorithms presented in works of Feng et al. [8], Jiao and Liu [12], and Wang et al. [24] all failed to solve the randomly generated large-scale Example 9 in 3600s, we only present the numerical computational results of our algorithm in Table 2. For all numerical tests of randomly generated Example 9, we solved arbitrary ten independently generated test problems and recorded their average numerical results among these ten test problems.Table 1
Numerical comparisons among the algorithm presented in the works of Feng et al. [8], Jiao et al. [12], Wang et al. [24], and our algorithm on Examples 1–8.
ExampleRefs.Optimal valueOptimal solutionIterCPU time1Feng et al. [8]0.57310(1.0157, 0.5905, 1.4037)189788.40531Jiao and Liu [12]0.57310(1.0157, 0.5905, 1.4037)221.05172Wang et al. [24]0.57310(1.0157, 0.5905, 1.4037)221.38462Ours0.57335(1.0157, 0.5902, 1.4041)10.203352Feng et al. [8]0.67136(1.5000, 1.5000)1233.69388Jiao and Liu [12]0.67136(1.5000, 1.5000)160.52438Wang et al. [24]0.67136(1.5000, 1.5000)201.11778Ours0.67136(1.5000, 1.5000)10.057563Feng et al. [8]1.34783(1.0167, 0.5500, 1.4500)42814.23580Jiao and Liu [12]1.34783(1.0167, 0.5500, 1.4500)221.01556Wang et al. [24]1.34783(1.0167, 0.5500, 1.4500)191.26376Ours1.34783(1.0167, 0.5500, 1.4500)170.897394Feng et al. [8]2.40000(1.0167, 0.5500, 1.4500)49417.10538Jiao and Liu [12]2.40000(1.0167, 0.5500, 1.4500)230.93779Wang et al. [24]2.40000(1.0167, 0.5500, 1.4500)191.33390Ours2.40000(1.0167, 0.5500, 1.4500)432.135185Feng et al. [8]1.16157(1.0000, 0.5500, 1.4500)31310.15298Jiao and Liu [12]1.16157(1.0000, 0.5500, 1.4500)210.85291Wang et al. [24]1.16157(1.0000, 0.5500, 1.4500)171.18794Ours1.16157(1.0000, 0.5500, 1.4500)190.882016Feng et al. [8]0.98971(1.3452, 0.5000, 1.9464)2272113.77662Jiao and Liu [12]0.98971(1.3452, 0.5000, 1.9465)401.84189Wang et al. [24]0.98971(1.3452, 0.5000, 1.9465)392.04739Ours0.99279(1.3500, 0.5000, 1.9417)914.068227Feng et al. [8]1.11789(1.5054, 0.3500, 1.5500)207696.72385Jiao and Liu [12]1.11789(1.5054, 0.3500, 1.5500)391.58835Wang et al. [24]1.11789(1.5054, 0.3500, 1.5500)412.08152Ours1.12533(1.4844, 0.3500, 1.5500)984.679478Feng et al. [8]1.11838(1.7538, 0.3500, 1.5500)10326477.60639Jiao and Liu [12]1.11838(1.7538, 0.3500, 1.5500)461.77758Wang et al. [24]1.11838(1.7538, 0.3500, 1.5500)602.60233Ours1.13750(1.4546, 0.3500, 1.3967)1496.75431Table 2
Numerical results of our algorithm on Example9 with the large-size variables.
p,m,nAvg.NAvg.T(2, 100, 1000)84.425.780946(2, 100, 2000)150.6197.582295(2, 100, 3000)136.6385.307614(2, 100, 4000)171.4837.706223(2, 100, 5000)77.8476.919714(2, 100, 6000)137.11418.259703(2, 100, 7000)140.72077.776716(2, 100, 8000)193.64235.722436(2, 100, 10000)80.22002.843398(3, 100, 1000)536.8164.539888(3, 100, 2000)598.1687.34879(3, 100, 3000)535.31249.842719(3, 100, 4000)760.73928.820802(3, 100, 5000)486.42941.007123(3, 100, 6000)558.15126.950975From the numerical results for Examples1–8 in Table 1, first of all, we can observe that our algorithm can obtain the almost same optimal solution and optimal value as the algorithms presented in the works of Feng et al. [8], Jiao and Liu [12], and Wang et al. [24]. Secondly, in terms of computational efficiency, in all cases, our algorithm outperforms the algorithms presented in the works of Feng et al. [8], Jiao and Liu [12], and Wang et al. [24].From the numerical results for the randomly generated large-scale Example9 in Table 2, it is obvious that the proposed algorithm can solve randomly generated large-scale Example 9 with the large-size variables n≥1000. However, the algorithms of Feng et al. [8], Jiao and Liu [12], and Wang et al. [24] all failed to solve the randomly generated large-scale Example 9. Therefore, this demonstrates the robustness and stability of our algorithm.Example 1.
(see [12, 14]).(22)minmax3x1+x2−2x3+0.82x1−x2+x3,4x1−2x2+x37x1+3x2−x3s.t.x1+x2−x3≤1,−x1+x2−x3≤−1,12x1+5x2+12x3≤34.8,12x1+12x2+7x3≤29.1,−6x1+x2+x3≤−4.1,1.0≤x1≤1.1,0.55≤x2≤0.65,1.35≤x3≤1.45.Example 2.
(see [12, 14]).(23)maxmin37x1+73x2+1313x1+13x2+13,63x1−18x2+3913x1+26x2+13s.t.5x1−3x2=3,1.5≤x1≤3.Example 3.
(see [12, 14]).(24)minmax2x1+2x2−x3+0.9x1−x2+x3,3x1−x2+x38x1+4x2−x3s.t.x1+x2−x3≤1,−x1+x2−x3≤−1,12x1+5x2+12x3≤34.8,12x1+12x2+7x3≤29.1,−6x1+x2+x3≤−4.1,1.0≤x1≤1.2,0.55≤x2≤0.65,1.35≤x3≤1.45.Example 4.
(see [12, 14]).(25)minmax3x1+x2−2x3+0.82x1−x2+x3,4x1−2x2+x37x1+3x2−x3,3x1+2x2−x3+1.9x1−x2+x3,4x1−x2+x38x1+4x2−x3s.t.x1+x2−x3≤1,−x1+x2−x3≤−1,12x1+5x2+12x3≤34.8,12x1+12x2+7x3≤29.1,−6x1+x2+x3≤−4.1,1.0≤x1≤1.2,0.55≤x2≤0.65,1.35≤x3≤1.45.Example 5.
(see [12, 14]).(26)minmax2.1x1+2.2x2−x3+0.81.1x1−x2+1.2x3,3.1x1−x2+1.3x38.2x1+4.1x2−x3s.t.x1+x2−x3≤1,−x1+x2−x3≤−1,12x1+5x2+12x3≤40,12x1+12x2+7x3≤50,−6x1+x2+x3≤−2,1.0≤x1≤1.2,0.55≤x2≤0.65,1.35≤x3≤1.45.Example 6.
(see [12, 14]).(27)minmax3x1+4x2−x3+0.52x1−x2+x3+0.5,3x1−x2+3x3+0.59x1+5x2−x3+0.5,4x1−x2+5x3+0.511x1+6x2−x3,5x1−x2+6x3+0.512x1+7x2−x3+0.9s.t.x1+x2−x3≤1,−x1+x2−x3≤−1,12x1+5x2+12x3≤42,12x1+12x2+7x3≤55,−6x1+x2+x3≤−3,1.0≤x1≤2.0,0.50≤x2≤2.0,0.50≤x3≤2.0.Example 7.
(see [12, 14]).(28)minmax3x1+4x2−x3+0.92x1−x2+x3+0.5,3x1−x2+3x3+0.59x1+5x2−x3+0.5,4x1−x2+5x3+0.511x1+6x2−x3+0.9,5x1−x2+6x3+0.512x1+7x2−x3+0.9,6x1−x2+7x3+0.611x1+6x2−x3+0.9s.t.2x1+x2−x3≤2,−2x1+x2−2x3≤−1,11x1+6x2+12x3≤45,11x1+13x2+6x3≤52,−7x1+x2+x3≤−2,1.0≤x1≤2.0,0.35≤x2≤0.9,1.0≤x3≤1.55.Example 8.
(see [12, 14]).(29)minmax5x1+4x2−x3+0.93x1−x2+2x3+0.5,3x1−x2+4x3+0.59x1+3x2−x3+0.5,4x1−x2+6x3+0.512x1+7x2−x3+0.9,7x1−x2+7x3+0.511x1+9x2−x3+0.9,7x1−x2+7x3+0.711x1+7x2−x3+0.8s.t.2x1+2x2−x3≤3,−2x1+x2−3x3≤−1,11x1+7x2+12x3≤47,13x1+13x2+6x3≤56,−6x1+2x2+3x3≤−1,1.0≤x1≤2.0,0.35≤x2≤0.9,1.0≤x3≤1.55.Example 9.
(30)minmax∑j=1nd1jxj+g1∑j=1ne1jxj+h1,∑j=1nd2jxj+g2∑j=1ne2jxj+h2,…,∑j=1ndpjxj+gp∑j=1nepjxj+hps.t.∑j=1nakjxj≤bk,k=1,2,…,m,xj≥0,j=1,2,…,n,where all dijandeij,i=1,2,…,pandj=1,2,…,n,andbkandakj,k=1,2,…,mandj=1,2,…,n, are randomly generated in 0,10; all gi and hi,i=1,2,…,p, are randomly generated in 0,1.
From the numerical results in Tables1 and 2, it is seen that the proposed algorithm has higher computational efficiency than the algorithms presented in the works of Feng et al. [8], Jiao and Liu [12], and Wang et al. [24], which can be used to globally solve the problem (MLFP) with the large-size variables.


## 5. Concluding Remarks

In this paper, based on the outer space partitioning search and the new linear relaxation problem, we present an outer space branch-and-bound algorithm for globally solving the problem (MLFP). The proposed algorithm is convergent to the global optimal value by the successive refinement of the outer space region and the subsequent solutions of a series of linear relaxation programming problems over the outer space region. The main work of the proposed algorithm involves solving a series of linear relaxation programming problems over the outer space region which does not grow in size for each iteration and which can be efficiently solved by the simplex method. Compared with the algorithms presented in the works of Feng et al. [8], Jiao and Liu [12], and Wang et al. [24], numerical results for some test examples are given to illustrate the feasibility and effectiveness of our new algorithm. It is also hoped that the ideas and methods used to create the algorithm will offer a useful tool for globally solving the problem (MLFP).



---

*Source: 3584494-2021-11-27.xml*