An improved three-Step method for solving the interval linear programming problems

Yugoslav Journal of Operations Research 28 (2018), Number 4, 435-451 DOI: https://doi.org/10.2298/YJOR180117020A AN IMPROVED THREE-STEP METHOD FOR SOLVING THE INTERVAL LINEAR PROGRAMMING PROBLEMS Mehdi ALLAHDADI Mathematics Faculty, University of Sistan and Baluchestan, Zahedan, Iran m allahdadi@math.usb.ac.ir Chongyang DENG School of Science, Hangzhou Dianzi University, Hangzhou, PR China dcy@hdu.edu.cn Received: January 2018 / Accepted: July 2018 Abstract: Feasibility condition, which ensures that the solution space does not violate any constraints, and optimality condition, which guarantees that all points of the solu- tion space are optimal, are very significant conditions for the solution space of interval linear programming (ILP) problems. Among the existing methods for ILP problems, the best-worst cases (BWC) method and two-step method (TSM) do not ensure feasi- bility condition, while the modified ILP (MILP), robust TSM (RTSM), improved TSM (ITSM), and three-step method (ThSM) guarantee feasibility condition, whose solution spaces may not be completely optimal. We propose an improved ThSM (IThSM) for ILP problems, which ensures both feasibility and optimality conditions, i.e., we introduce an extra step to optimality. Keywords: Feasibility, Interval Linear Programming, Optimality, Robust two-step Method, Three-step Method. MSC: 65G40, 80M50, 90C05. 1. INTRODUCTION Interval linear programming (ILP) is used to deal with uncertainties of many real-world problems, where parameters may be specified as lying between lower and upper bounds. There are several methods for solving ILP models, which are divided into two sub-models to obtain the solution set [2, 3, 4, 10, 12, 14, 24, 26, 27, 28]. 436 M. Allahdadi and C. Deng / An improved ThSM for solving the ILP problems Also, there are some methods for ILP models. Tong [26] proposed the best and worst cases (BWC) method by converting the ILP model into two sub-models, the best and worst sub-models which have the largest and the smallest feasible regions, respectively. This method has been extended by Chinneck and Ramadan to ILP models with equality constraints [6]. A novel ILP method was proposed by Huang and Moore [14]. Huang et al. proposed a two-step method (TSM) through analyzing relations between variables and coefficients [11]. For ILP model, a given point is feasible if it satisfies the constraints of the best problem. The solutions given by the BWC, ILP, and TSM may stray into infeasible spaces. The solutions of BWC may appear in an infeasible area though it introduces exact bounds for the values of the objective function. To achieve the feasibility, the modified ILP method (MILP) [28], three-step method (ThSM) [13], robust TSM (RTSM) [7] and improved TSM (ITSM) [27] were proposed. However, the solutions resulting from the above methods may not be optimal. To our best knowledge, only the solutions of IILP and IMILP methods proposed by Allahdadi et al. are completely feasible and optimal [3]. Some researchers also focused on basis stability [9, 17, 20, 25], with which it is possible to obtain the optimal solution set of ILP. Some have used interval arithmetic and extensions of the simplex algorithm [5, 15, 16, 19]. In the ThSM, only the feasibility condition is considered. In such a way, the solution might not be optimal in a part of the solution space. So, although the basis stability condition can be disregarded, it is crucial to obtain a feasible and optimal solution set of ILP problems for the whole space of solution. 1.1. Background knowledge An interval number x± is represented as [x−, x+], where x− ≤ x+. If x− = x+, then x± is degenerate. x± ≥ 0 if and only if x− ≥ 0. In addition, x± ≤ 0 if and only if x+ ≤ 0. If A− and A+ are two matrices in Rm×n such that A− ≤ A+, then the set of matrices A± = [A−, A+] = {A| A− ≤ A ≤ A+} is called an interval matrix, and the matrices A− and A+ are called its bounds. Center and radius matrices are defined as Ac = 1 2 (A+ +A−) , ∆A± = 1 2 (A+ −A−). A square interval matrix A± is said to be regular if each A ∈ A± is non-singular. A special case of an interval matrix is an interval vector x± = {x| x− ≤ x ≤ x+}, where x−,x+ ∈ Rn. Interval arithmetic has been studied in [1]. Consider the following ILP: max z± = ∑n j=1 c ± j x ± j s.t. ∑n j=1 a ± ijx ± j ≤ b±i , i = 1, 2, ...,m x±j ≥ 0, j = 1, 2, ..., n. (1) M. Allahdadi and C. Deng / An improved ThSM for solving the ILP problems 437 A characteristic model of ILP problem (1) is max z = ∑n j=1 cjxj s.t. ∑n j=1 aijxj ≤ bi, i = 1, 2, ...,m xj ≥ 0, j = 1, 2, ..., n, (2) where aij ∈ a±ij , cj ∈ c±j , and bi ∈ b±i . The magnitude and mignitude of an interval number x± are defined as follows[8]: mig(x±) = { x− x± ≥ 0 −x+ x± < 0 , mag(x ±) = { x+ x± ≥ 0 −x− x± < 0, and sign(x±) is defined as follows: sign(x±) = { 1 x± ≥ 0 −1 x± < 0. We use the notation |x±|− and |x±|+ to denote mig(x±) and mag(x±), respec- tively. The feasible solution set of the ILP is defined as {x ∈ Rn : ∑nj=1 a−ijxj ≤ b+i , xj ≥ 0, i = 1, ...,m, j = 1, ..., n}. Moreover, the optimal solution set of the ILP is defined as the set of all optimal solutions over all characteristic models. We first review some methods for solving ILP problems, and then discuss the concept of stability. In the following, by considering the basis stability, we propose a new method to obtain solution space that is both feasible and optimal. 1.2. Related works There are only a few solution methods for solving the general ILP problems. The fundamental idea of these methods is to divide an ILP model into two extreme LP sub-models to obtain interval solutions. One LP sub-model is solved to obtain the best optimal value, and the other is for the worst optimal value of the objective function. In this section, we review some methods for solving ILP model (1), see [3, 7, 11, 26, 27]. Suppose that c±j ≥ 0 for j = 1, ..., k, and c±j ≤ 0 for j = k+ 1, ..., n. Also, a±ij ≥ 0 for j = 1, ..., li1; j = li2 + 1, ..., n and a±ij ≤ 0 for j = li1 + 1, ..., li2, where li1 ≤ k, and li2 ≥ k. In the ITSM, we have x′j =  x−j sign(a ± ij) 6= sign(c±j ), j = 1, 2, ..., k x+j opt sign(a ± ij) = sign(c ± j ), j = 1, 2, ..., k x+j sign(a ± ij) 6= sign(c±j ), j = k + 1, ..., n x−j opt sign(a ± ij) = sign(c ± j ), j = k + 1, ..., n The results are given in Table 1. Note that in each method, x+j opt for j = 1, 2, ..., k and x−j opt for j = k + 1, ..., n are the optimal solutions of sub-model 1 of that method. 438 M. Allahdadi and C. Deng / An improved ThSM for solving the ILP problems In the IILP and IMILP methods, δ is the number of active constraints in sub- model 1 for the optimal solution, as well as a±δj ≤ 0 for j = k − p + 1, ..., k and a±δj ≥ 0 for j = n− q + 1, ..., n. Since we want to improve the three-step method (ThSM), then let us first review the ThSM. According to [13], the ThSM is based on the TSM solutions. The steps of this method are as follows [13]: Step 1. Obtain the solutions by the TSM to be x±opt. Step 2. Test feasibility condition to analyze whether the TSM solutions can satisfy the constraints of the best problem in the BWC method. Step 3. Constrict the solutions to eliminate the infeasible solutions. Let y±j = [x c j − q∆x±j , x c j + q∆x±j ] for j = 1, ..., n be the ThSM solutions. Two constricting approaches are as follows: • ThSM-I max q s.t. ∑ j∈B1 a − ijq∆x±j −∑j∈B2 a−ijq∆x±j ≤ b+i −∑nj=1 a−ijxcj , i = 1, ...,m 0 ≤ q ≤ 1 (3) • ThSM-II max q1 × q2 × ...× qn0 s.t. ∑ j∈B1 a − ijqj∆x±j −∑j∈B2 a−ijqj∆x±j ≤ b+i −∑nj=1 a−ijxcj , i = 1, ...,m 0 ≤ q ≤ 1, (4) where n0 is the number of interval solutions obtained by the sub-models of the TSM and B1 = {j : a±ij ≥ 0} and B2 = {j : a±ij < 0}. y±j is the shrunk interval of x ± j opt, and the constricting rate depends on the value of qj . 2. BASIS STABILITY (B-STABILITY) In this section, we define the concept of basis stability (B-stability), which can be used to obtain the optimal solution set of the ILP model [9, 17]. Definition 1. The problem max{cTx : Ax = b , x ≥ 0}, where c ∈ c± ⊆ Rn, A ∈ A± ⊆ Rm×n, and b ∈ b± ⊆ Rm, is called B-stable with basis B if B is an optimal basis for each characteristic problem. The ILP problem is called [unique] non-degenerate B-stable if each characteristic model has a [unique] non-degenerate optimal basic solution with the basis B. M. Allahdadi and C. Deng / An improved ThSM for solving the ILP problems 439 Table 1: Sub-models of the methods for ILP model (1) Method Sub-models Sub-model 1 (the best problem) max z+ = ∑n j=1 c + j xj s.t. ∑n j=1 a − ijxj ≤ b+i , i = 1, ...,m, xj ≥ 0, j = 1, ..., n. BWC Sub-model 2 (the worst problem) max z− = ∑n j=1 c − j xj s.t. ∑n j=1 a + ijxj ≤ b−i , i = 1, ...,m, xj ≥ 0, j = 1, ..., n. Sub-model 1 max z+ = ∑k j=1 c + j x + j + ∑n j=k+1 c + j x − j s.t. ∑k j=1 sign(a ± ij)|a±ij |−x+j + ∑n j=k+1 sign(a ± ij)|a±ij |+x−j ≤ b+i , i = 1, ...,m, x±j ≥ 0, j = 1, ..., n. TSM Sub-model 2 max z− = ∑k j=1 c − j x − j + ∑n j=k+1 c − j x + j s.t. ∑k j=1 sign(a ± ij)|a±ij |+x−j + ∑n j=k+1 sign(a ± ij)|a±ij |−x+j ≤ b−i , i = 1, ...,m, x−j ≤ x+j opt, j = 1, ..., k, x+j ≥ x−j opt, j = k + 1, ..., n, x±j ≥ 0, j = 1, ..., n. Sub-model 1 same as that of the TSM Sub-model 2 max z− = ∑k j=1 c − j x − j + ∑n j=k+1 c − j x + j s.t. ∑k j=1 sign(a ± ij)|a±ij |+x−j + ∑n j=k+1 sign(a ± ij)|a±ij |−x+j ≤ b−i , i = 1, ...,m, ITSM ∑n j=1 a − ijx ′ j ≤ b+i x−j ≤ x+j opt, j = 1, ..., k, x+j ≥ x−j opt, j = k + 1, ..., n, x±j ≥ 0, j = 1, ..., n. Sub-model 1 max z− = ∑k j=1 c − j x − j + ∑n j=k+1 c − j x + j s.t. ∑k j=1 sign(a ± ij)|a±ij |+x−j + ∑n j=k+1 sign(a ± ij)|a±ij |−x+j ≤ b−i , i = 1, ...,m, x±j ≥ 0, j = 1, ..., n. RTSM Sub-model 2 max z+ = ∑k j=1 c + j x + j + ∑n j=k+1 c + j x − j s.t. ∑k j=1 sign(a ± ij)|a±ij |−x+j + ∑n j=k+1 sign(a ± ij)|a±ij |+x−j ≤ b+i , i = 1, ...,m,∑li1 j=1 a − ijx + j + ∑k j=li1+1 a−ijx − j opt + ∑li2 j=k+1 a − ijx − j + ∑n j=li2+1 a−ijx + j opt ≤ b+i x+j ≥ x−j opt, j = 1, .., k, x−j ≤ x+j opt, j = k + 1, ..., n, x±j ≥ 0, j = 1, ..., n. Sub-model 1 max z− = ∑k j=1 c − j x − j + ∑n j=k+1 c − j x + j s.t. ∑k j=1 sign(a ± ij)|a±ij |+x−j + ∑n j=k+1 sign(a ± ij)|a±ij |−x+j ≤ b−i , i = 1, ...,m, x±j ≥ 0, j = 1, ..., n. IILP Sub-model 2 max z+ = ∑k j=1 c + j x + j + ∑n j=k+1 c + j x − j s.t. ∑k j=1 sign(a ± ij)|a±ij |−x+j + ∑n j=k+1 sign(a ± ij)|a±ij |+x−j ≤ b+i , i = 1, ...,m, x+j ≥ x−j opt, j = 1, ..., k, x−j ≤ x+j opt, j = k + 1, ..., n, x±j ≥ 0, j = 1, ..., n,∑k j=k−p+1−(|a±δj |−x+j − |a±δj |+x−j opt) + ∑n j=n−q+1(|a±δj |+x−j − |a±δj |−x+j opt) ≥ 0. Sub-model 1 same as that of the TSM Sub-model 2 min z− = ∑k j=1 c − j x − j + ∑n j=k+1 c − j x + j IMILP s.t. ∑k j=1 sign(a ± ij)|a±ij |+x−j + ∑n j=k+1 sign(a ± ij)|a±ij |−x+j ≥ b−i , i = 1, ...,m, x−j ≤ x+j opt, j = 1, ..., k, x+j ≥ x−j opt, j = k + 1, ..., n, x±j ≥ 0, j = 1, ..., n,∑k j=k−p+1−(|a±δj |+x−j − |a±δj |−x+j opt) + ∑n j=n−q+1(|a±δj |−x+j − |a±δj |+x−j opt) ≤ 0. 440 M. Allahdadi and C. Deng / An improved ThSM for solving the ILP problems Let B ⊆ {1, 2, ..., n} be an index set such that AB (the restriction of A to the columns indexed by B) is regular, (i.e., each real matrix in AB is non-singular). Similarly, N = {1, 2, ..., n} \ B denotes the set of non-basic variables and AN is its restriction to non-basic indices. B can be computed by solving an arbitrary characteristic model of the ILP. We now review the conditions for B-stability[9]. • Regularity: AB is regular. • Feasibility: The solution set of the interval system ABxB = b is non- negative. • Optimality: AB is optimal, i.e., cTBA−1B AN − cTN ≥ 0T . Theorem 2. [21] If ρ(|(AcB)−1|∆AB ) < 1, then AB is regular, where ρ(.) denotes the spectral radius. Theorem 3. [21] If max1≤i≤n(|(AcB)−1|∆AB )ii ≥ 1, then AB is not regular. Some conditions for the regularity of interval matrices have been proposed in[23]. Theorem 4. [22] The interval vector r is an enclosure to the solution set of a system ABxB = b, where: r−i = min{−x∗i + (xci + |xci |)Mii, 1 2Mii − 1(−x ∗ i + (x c i + |xci |)Mii)}, r+i = max{x∗i + (xci − |xci |)Mii, 1 2Mii − 1(x ∗ i + (x c i − |xci |)Mii)}, M = (I − |(AcB)−1|∆AB )−1, xc = (AcB)−1bc, x∗ = M(|xc|+ |(AcB)−1|∆b), AcB is non-singular, and ρ(|(AcB)−1|∆AB ) < 1. Theorem 5. [9] Let y be an enclosure to the solution set of ATBy = cB. If ((ATN )y) − ≥ c+N , then the optimality condition is valid. Theorem 6. [9] Let diag(q) denote the diagonal matrix with entries q1, ..., qm. For each q ∈ {±1}m, if the solution set of the system ((A c B) T − (∆AB )T diag(q))y ≤ c+B −((AcB)T + (∆AB )T diag(q))y ≤ −c−B diag(q)y ≥ 0 lies in the solution set of the system{ ((AcN ) T − (∆AN )T diag(q))y ≥ c+N diag(q)y ≥ 0, then, the optimality condition is valid. M. Allahdadi and C. Deng / An improved ThSM for solving the ILP problems 441 Remark 6.1. Since there are no dependencies, the set of constraints Ax ≤ b,x ≥ 0 is equivalent to Ax + Iy = b,x,y ≥ 0. Theorem 7. [9] Let ILP model (1) be unique non-degenerate B-stable where B = (1, 2, ...,m). The optimal solution set of the ILP model is equal to the solution set of the interval system ABxB = b,xB ≥ 0,xN = 0, or A−BxB ≤ b+, A+BxB ≥ b−,xB ≥ 0,xN = 0. Consider the model, i.e. an example given by [13]: max z± = [2, 2.4]x±1 − [1, 1.3]x±2 + [1.5, 1.8]x±3 s.t. [2.6, 3.5]x±1 + [2, 2.4]x ± 2 + [3.2, 3.8]x ± 3 ≤ [18, 22] [4.6, 5.5]x±1 + [3, 3.6]x ± 2 − [1.3, 1.6]x±3 ≤ [8, 9] [1, 1.3]x±1 − [6, 6.5]x±2 + [2, 2.5]x±3 ≤ [2.2, 2.6] x±1 , x ± 2 , x ± 3 ≥ 0. (5) To obtain the optimal solution set, we first check the basis stability conditions. Based on Remark 6.1, model (5) is equivalent to the following model: max z± = [2, 2.4]x±1 − [1, 1.3]x±2 + [1.5, 1.8]x±3 s.t. [2.6, 3.5]x±1 + [2, 2.4]x ± 2 + [3.2, 3.8]x ± 3 + x ± 4 = [18, 22] [4.6, 5.5]x±1 + [3, 3.6]x ± 2 − [1.3, 1.6]x±3 + x±5 = [8, 9] [1, 1.3]x±1 − [6, 6.5]x±2 + [2, 2.5]x±3 + x±6 = [2.2, 2.6] x±1 , x ± 2 , x ± 3 , x ± 4 , x ± 5 , x ± 6 ≥ 0. A candidate basis for B-stability is B = (1, 2, 3), since this is optimal for the characteristic model with center values. 1. According to Theorem 2, the spectral radius is equal to 0.24, so AB is regular: AB =  [2.6, 3.5] [2, 2.4] [3.2, 3.8][4.6, 5.5] [3, 3.6] −[1.3, 1.6] [1, 1.3] −[6, 6.5] [2, 2.5]  . 2. According to Theorem 4, we can compute the enclosure of the solution set of ABxB = b to be xB = ( [1.32, 2.57], [0.94, 1.40], [2.72, 4.03] )t , which is non- negative. 3. Using Theorem 4 again, we can compute the enclosure of the solution set of ATBy = cB to be y = ( [0.19, 0.43], [0.13, 0.21], [0.36, 0.39] )t . According to Theorem 5, since ((ATN )y) − ≥ c+N , the optimality condition holds. Thus the problem is B-stable. Therefore in view of Theorem 7, the optimal solution set of ILP model (5) is the solution set of the following inequalities: 2.6x1 + 2x2 + 3.2x3 ≤ 22, (6) 4.6x1 + 3x2 − 1.6x3 ≤ 9, (7) x1 − 6.5x2 + 2x3 ≤ 2.6, (8) 3.5x1 + 2.4x2 + 3.8x3 ≥ 18, (9) 5.5x1 + 3.6x2 − 1.3x3 ≥ 8, (10) 1.3x1 − 6x2 + 2.5x3 ≥ 2.2 (11) 442 M. Allahdadi and C. Deng / An improved ThSM for solving the ILP problems Note that the inequalities (6)-(8) and (9)-(11) are the feasibility and optimality conditions, respectively. 3. THE IThSM Suppose that x±opt is the solution obtained by the TSM. To guarantee that the given solutions are completely feasible, we use the ThSM approach proposed by Huang et al. [13] (Models (3) and (4)). To ensure that all points of the ThSM solutions are optimal, the following approach of optimality test is developed. In view of Theorem 7, if ∑n j=1 a + ijxj opt ≥ b−i is tenable, then all solutions are optimal, which means that x±opt pass the optimality test. Otherwise, we eliminate the non- optimal solutions by the following approach. Assume that y±opt is the IThSM solution, where y ± j = [x c j opt − qj∆x±j , x c j opt + qj∆x±j ] for j = 1, ..., n. To optimality, Theorem 7 implies that it is sufficient that n∑ j=1 a+ijyj ≥ b−i , or ∑ j∈B1 a+ijy − j + ∑ j∈B2 a+ijy + j ≥ b−i , where B1 = {j : a±ij ≥ 0} and B2 = {j : a±ij < 0}. Therefore, we have:∑ j∈B1 a+ij(x c j opt − qj∆x±j ) + ∑ j∈B2 a+ij(x c j opt + qj∆x±j ) ≥ b−i . Thus, to optimality, it is sufficient that − ∑ j∈B1 a+ijqj∆x±j opt + ∑ j∈B2 a+ijqj∆x±j opt ≥ b−i − n∑ j=1 a+ijx c j opt. Suppose that for each j = 1, 2, ..., n0, qj = q. Then, we have: − ∑ j∈B1 a+ijq∆x±j opt + ∑ j∈B2 a+ijq∆x±j opt ≥ b−i − n∑ j=1 a+ijx c j opt. Hence, the models for solving q and qj(j = 1, 2, ..., n), which are named IThSM-I and IThSM-II, can be presented as follows: • IThSM-I max q s.t.∑pi j=1 a − ijq∆x±j opt −∑n0j=pi+1 a−ijq∆x±j opt ≤ b+i −∑nj=1 a−ijxcj opt, i = 1, ...,m −∑j∈B1 a+ijq∆x±j opt +∑j∈B2 a+ijq∆x±j opt ≥ b−i −∑nj=1 a+ijxcj opt, i = 1, ...,m 0 ≤ q ≤ 1, (12) M. Allahdadi and C. Deng / An improved ThSM for solving the ILP problems 443 • IThSM-II max q1 × q2 × ...× qn0 s.t.∑pi j=1 a − ijqj∆x±j opt −∑n0j=pi+1 a−ijqj∆x±j opt ≤ b+i −∑nj=1 a−ijxcj opt, i = 1, ...,m −∑j∈B1 a+ijqj∆x±j opt +∑j∈B2 a+ijqj∆x±j opt ≥ b−i −∑nj=1 a+ijxcj opt, i = 1, ...,m 0 ≤ q ≤ 1. (13) Remark 8. The IThSM consisted of the following steps: Step 1. Obtain solutions of ILP model (1) by the TSM to be x±opt. Step 2. If ∑n j=1 a − ijxj opt ≤ b+i is tenable, then x±opt pass the feasibility test; oth- erwise, it means that a part of solutions will be infeasible. Suppose that the ILP model is B-stable. If ∑n j=1 a + ijxj opt ≥ b−i is tenable, then x±opt pass the optimality test; otherwise, it means that a part of solutions will not be optimal. Step 3. Eliminate the infeasible and non-optimal solutions by models (12) or (13). Therefore, the IThSM-I and IThSM-II solutions are y±j opt = [x c j opt−q∆x±j opt , x c j opt+ q∆x±j opt ] and y±j opt = [x c j opt − qj∆x±j opt , x c j opt + qj∆x±j opt ], respectively. The optimal value of the objective function can be obtained as follows: z−opt = k∑ j=1 c−j y − j opt + n∑ j=k+1 c−j y + j opt, z+opt = k∑ j=1 c+j y + j opt + n∑ j=k+1 c+j y − j opt. Note that similar to the IILP and IMILP, the IThSM obtains a solution space that is both feasible and optimal. In fact, the IThSM gives a new feasible and optimal solution space. Therefore, the union of the solution spaces obtained by which of the mentioned methods will be closer to the exact optimal solution space of the ILP model. 4. PROPERTIES OF IThSM Let us first analyze the solving methods based on feasibility and optimality conditions. Consider ILP model (5). Since the ILP model is B-stable, in view of Theorem 7, then the optimal solution set of the ILP model is equal to the solution set of the system A−BxB ≤ b+, A+BxB ≥ b−,xB ≥ 0,xN = 0, where AB =  [2.6, 3.5] [2, 2.4] [3.2, 3.8][4.6, 5.5] [3, 3.6] −[1.3, 1.6] [1, 1.3] −[6, 6.5] [2, 2.5]  , 444 M. Allahdadi and C. Deng / An improved ThSM for solving the ILP problems Table 2: Results for ILP model (5) Method x±opt z ± BWC ([1.40, 2.55], [1.09, 1.23], [2.76, 4.03])t [5.52, 12.15] TSM ([1.56, 2.18], 1.22, [2.66, 4.18])t [5.51, 11.55] ITSM ([1.26, 2.18], 1.22, [2.94, 4.18])t [5.33, 11.55] RTSM ([1.63, 2.17], 1.09, [2.66, 3.76])t [5.83, 10.88] ThSM − I ([1.61, 2.13], 1.22, [2.78, 4.06])t [5.80, 11.20] ThSM − II ([1.63, 2.11], 1.22, [2.73, 4.11])t [5.77, 11.24] IILP ([1.63, 2.17], 1.09, [2.66, 3.76])t [5.83, 10.88] IMILP ([1.65, 2.18], 1.22, [2.95, 4.18])t [6.14, 11.55] Table 3: Feasibility and optimality of the methods for ILP model (5) Method Feasibility Optimality BWC × × TSM × × ITSM X × RTSM X X ThSM − I X × ThSM − II X × IILP X X IMILP X X or the solution set of inequalities (6)-(11). We now solve ILP model (5). The results are given in Table 2. Some points given by the BWC are either infeasible or non-optimal. For exam- ple, point (2.55, 1.23, 2.76)t which does not satisfy (7), is not feasible, and point (1.4, 1.09, 4.03)t which does not satisfy (10), is not optimal. In the TSM, since points (2.18, 1.22, 4.18)t and (1.56, 1.22, 4.18)t do not satisfy (8) and (10), respec- tively, then these points are infeasible and non-optimal, respectively. The solutions obtained by ITSM are completely feasible, but are not completely optimal. For example, point (1.26, 1.22, 4.18)t is non-optimal because it does not satisfy (10). The solutions given by the RTSM, IILP, and IMILP are both feasible and optimal. Some solutions obtained through ThSM-I and ThSM-II are non-optimal, too. For example, point (1.61, 1.22, 2.78)t of ThSM-I and (1.63, 1.22, 2.73)t of ThSM-II do not satisfy (11), therefore these points are non-optimal. The feasibility and opti- mality for the methods are summarized in Table 3. In the following, we propose an improved ThSM by considering the feasibility and optimality conditions. In the ThSM, only the feasibility condition is considered [13]. In such a way, a part of the solution space may not be optimal. To remove this non-optimal part, by considering an optimality test, we propose an improved ThSM, namely IThSM. M. Allahdadi and C. Deng / An improved ThSM for solving the ILP problems 445 5. NUMERICAL ANALYSIS AND COMPARISONS In this section, two ILP models are solved by using the mentioned methods and the results are then compared. Example 9. Consider ILP model (5), again. We solve the ILP model by the IThSM. Step 1. The TSM solution is x±opt = ([1.56, 2.18], 1.22, [2.66, 4.18]) t. Step 2. The ILP model is B-stable, therefore based on inequalities (6)-(11) the following inequalities should be tested: 2.6x+1 opt + 2x + 2 opt + 3.2x + 3 opt ≤ 22, (14) 4.6x1 opt + 3x2 opt − 1.6x−3 opt ≤ 9, (15) x+1 opt − 6.5x−2 opt + 2x+3 opt ≤ 2.6, (16) 3.5x−1 opt + 2.4x − 2 opt + 3.8x − 3 opt ≥ 18, (17) 5.5x−1 opt + 3.6x − 2 opt − 1.3x+3 opt ≥ 8, (18) 1.3x−1 opt − 6x+2 opt + 2.5x−3 opt ≥ 2.2. (19) Since the TSM solutions do not satisfy inequalities (15) and (18), then a part of the solution space obtained by the TSM is not feasible and optimal. Step 3. For the TSM solutions, we have: ∆x±opt = (1.87, 1.22, 3.42)t and x± c opt = (0.31, 0, 0.76)t. Suppose that y± is the solution of the IThSM, where y± = ([1.87− 0.31q1, 1.87 + 0.31q1], 1.22, [3.42− 0.76q3, 3.42 + 0.76q3])t. According to model (12), we have: max q s.t. 2.6× 0.31q + 3.2× 0.76q ≤ 22− (2.6× 1.87 + 2× 1.22 + 3.2× 3.42) 4.6× 0.31q − (−1.6)× 0.76q ≤ 9− (4.6× 1.87 + 3× 1.22− 1.6× 3.42) 1× 0.31q + 2× 0.76q ≤ 2.6− (1× 1.87− 6.5× 1.22 + 2× 3.42) −3.5× 0.31q − 3.8× 0.76q ≥ 18− (3.5× 1.87 + 2.4× 3.8 + 3.8× 3.42) −5.5× 0.31q − 1.3× 0.76q ≥ 8− (5.5× 1.87 + 3.6× 3.8− 1.3× 3.42) −1.3× 0.31q − 2.5× 0.76q ≥ 2.2− (1.3× 1.87− 6× 2.5 + 3.8× 3.42) 0 ≤ q ≤ 1 The solution is q = 0.63, and hence y±opt = ([1.67, 2.07], 1.22, [2.94, 3.90]) t and z±opt = [6.16, 10.77]. 446 M. Allahdadi and C. Deng / An improved ThSM for solving the ILP problems According to model (13), we have: max q1q3 s.t. 2.6× 0.31q1 + 3.2× 0.76q3 ≤ 22− (2.6× 1.87 + 2× 1.22 + 3.2× 3.42) 4.6× 0.31q1 − (−1.6)× 0.76q3 ≤ 9− (4.6× 1.87 + 3× 1.22− 1.6× 3.42) 1× 0.31q1 + 2× 0.76q3 ≤ 2.6− (1× 1.87− 6.5× 1.22 + 2× 3.42) −3.5× 0.31q1 − 3.8× 0.76q3 ≥ 18− (3.5× 1.87 + 2.4× 3.8 + 3.8× 3.42) −5.5× 0.31q1 − 1.3× 0.76q3 ≥ 8− (5.5× 1.87 + 3.6× 3.8− 1.3× 3.42) −1.3× 0.31q1 − 2.5× 0.76q3 ≥ 2.2− (1.3× 1.87− 6× 2.5 + 3.8× 3.42) 0 ≤ q ≤ 1 The solutions are q1 = 0.98, q3 = 0.56, and hence y±opt = ([1.57, 2.17], 1.22, [2.99, 3.85]) t, and z±opt = [6.04, 10.92]. The interval value of the objective function obtained by IThSM-II (i.e. [6.04, 10.92]) is wider than that of IThSM-I (i.e. [6.16, 10.77]). Since the value of z+opt given by IThSM-II is larger than that of IThSM-I, then IThSM-II is preferred (Note that the objective is to maximize the objective function). Based on the constraints of models (12) and (13), the solutions obtained by IThSM are both feasible and optimal. The interval width of x±1 opt given by IThSM-II is larger than that of IThSM-I, whereas that of x±3 opt is converse. Example 10. Consider the model, i.e., an example given by [13]: max z± = [3, 3.5]x±1 − [1, 1.2]x±2 s.t. [1, 1.1]x±1 + [1.6, 1.8]x ± 2 ≤ [11.6, 12] [3, 4]x±1 − [2, 3]x±2 ≤ [5, 7] x±1 , x ± 2 ≥ 0. (20) Before using the IThSM, we first check the basis stability of ILP model (20). Based on Remark 6.1, model (20) is equivalent to the following model: max z± = [3, 3.5]x±1 − [1, 1.2]x±2 s.t. [1, 1.1]x±1 + [1.6, 1.8]x ± 2 + x ± 3 = [11.6, 12] [3, 4]x±1 − [2, 3]x±2 + x±4 = [5, 7] x±1 , x ± 2 , x ± 3 , x ± 4 ≥ 0. A candidate basis for B-stability is B = (1, 2), since this is optimal for the char- acteristic model with center values. 1. According to Theorem 2, the spectral radius is equal to 0.21, so AB is regular: AB = ( [1, 1.1] [1.6, 1.8] [3, 4] [−3,−2] ) . M. Allahdadi and C. Deng / An improved ThSM for solving the ILP problems 447 Figure 1: Exact solution space of ILP model (20) Figure 2: Solution spaces obtained by BWC, TSM, ITSM, RTSM, IILP, and IMILP for ILP model (20) 2. According to Theorem 4, we can compute the enclosure of the solution set of ABxB = b to be xB = ( [3.42, 6.16], [3.72, 4.46] )T , which is non-negative. 3. Using Theorem 4 again, we can compute the enclosure of the solution set of ATBy = cB to be y = ( [0.19, 1.16], [0.81, 0.95] )T . According to Theorem 5, since ((ATN )y) − ≥ c+N , the optimality condition holds. Thus the problem is B-stable, and hence in view of Theorem 7, the optimal solution set of ILP model (20) is the solution set of the following inequalities system, which has been shown in Fig. 1. { x1 + 1.6x2 ≤ 12 , 1.1x1 + 1.8x2 ≥ 11.6 3x1 − 3x2 ≤ 7 , 4x1 − 2x2 ≥ 5. We solve model (20) by using the BWC, TSM, ITSM, RTSM, IILP, IMILP, ThSM, and IThSM. The results are given in Table 4 and Fig. 2. The feasibility and optimality for the methods are summarized in Table 5. The solution space obtained through BWC and TSM is not completely feasible and optimal. The ITSM and RTSM solutions are completely feasible, but a part of solution spaces is non-optimal 448 M. Allahdadi and C. Deng / An improved ThSM for solving the ILP problems Figure 3: Non-optimal space of ITSM for ILP model (20) Figure 4: Non-optimal space of RTSM for ILP model (20) Figure 5: Solution space obtained by ThSM for ILP model (20) Figure 6: Solution space obtained by IThSM for ILP model (20) M. Allahdadi and C. Deng / An improved ThSM for solving the ILP problems 449 Table 4: Results for ILP model (20) Method z±opt x ± opt BWC [5.06, 17.46] ( [3.43, 6.05], [3.72, 4.35] )t TSM [5.18, 16.80] ( [3.63, 5.79], [3.45, 4.76] )t ITSM [4.91, 16.80] ( [3.19, 5.79], [3.45, 3.88] )t RTSM [5.18, 13.31] ( [3.63, 4.39], [2.06, 4.76] )t ThSM-I [7.86, 13.86] ( [4.35, 5.07], [3.89, 4.32] )t ThSM-II [7.87, 13.85] ( [4.35, 5.07], [3.88, 4.33] )t IILP [5.18, 11.11] ( [3.63, 4.38], [4.23, 4.76] )t IMILP [10.04, 16.80] ( [4.90, 5.79], [3.45, 3.88] )t IThSM-I [7.84, 13.89] ( [4.34, 5.08], [3.88, 4.33] )t IThSM-II [7.88, 13.85] ( [4.35, 5.07], [3.88, 4.33] )t Table 5: Feasibility and optimality of the methods for ILP model (20) Method Feasibility Optimality BWC × × TSM × × ITSM X × RTSM X × ThSM-I X X ThSM-II X X IILP X X IMILP X X IThSM-I X X IThSM-II X X as shown in Fig. 3 and Fig. 4. The solution spaces obtained through the ThSM and IThSM are completely feasible and optimal as shown in Fig. 5 and Fig. 6. 6. CONCLUSIONS Some methods for solving interval linear programming (ILP) problems have been reviewed based on feasibility and optimality conditions. Feasibility condition is used to avoid violation of the constraints of the best problem, which has the largest feasible space, and optimality condition to ensure that each point of the solution space is optimal for at least one characteristic problem. In some methods, the best and worst cases (BWC) and two-step method (TSM), the feasibility condition was not been considered. Therefore, solution spaces given by the BWC and TSM may be infeasible. Solutions obtained through improved TSM (ITSM), robust TSM (RTSM), modified ILP (MILP), and three-step method (ThSM) are completely feasible, but are not completely optimal. In these methods, the optimality condition has not been considered. The solutions of improved MILP 450 M. Allahdadi and C. Deng / An improved ThSM for solving the ILP problems (IILP and IMILP) are feasible and optimal. To ensure that solutions given by ThSM are optimal, optimality test is needed. By considering basis stability, and hence adding the optimality condition to ThSM, we propose an improved ThSM (IThSM) which gives both feasible and optimal solution space. Acknowledgments: The authors would like to thank to the Editor-in-Chief and the anonymous referees for their constructive comments and suggestions that have helped to improve this paper. REFERENCES [1] Alefeld, G., Herzberger, J., Introduction to Interval Computations, Academic Press, New York, 1983. [2] Allahdadi, M., Mishmast Nehi, H., “The optimal solutions set of the interval linear pro- gramming problems”, Optimization Letters, 7 (2013) 893-1911. [3] Allahdadi, M., Mishmast Nehi, H., Ashayerinasab, H. A., Javanmard, M., “Improving the modified interval linear programming method by new techniques”, Information Sciences, 339 (2016) 224-236. [4] Ashayerinasab, H. A., Mishmast Nehi, H., Allahdadi, M., “Solving the interval linear pro- gramming problem: A new algorithm for a general case”, Expert Systems With Applications, 93 (2018) 39-49. [5] Beeck, H., “Linear programming with inexact data”, Technical report TUM-ISU-7830, Tech- nical University of Munich, Munich, 1978. [6] Chinneck, J.W., Ramadan, K., “Linear programming with interval coefficients”, Journal of the Operational Research Society, 51 (2000) 209-220. [7] Fan, Y.R., Huang, G.H., “A robust two-step method for solving interval linear program- ming problems within an environmental management context”, Journal of Environmental Informatics, 19 (1) (2012) 1-9. [8] Hansen, H., Walster, G. W., Global Optimization Using Interval Analysis, Second Edition, Revised and Expanded, Dekker, New York, 1992. [9] Hladik, M., “How to determine basis stability in interval linear programming”, Optim. Lett., 8 (2014) 375-389. [10] Hladik, M., “Interval linear programming: A survey”, in: Z. A. Mann, editor, Linear Pro- gramming, New Frontiers in Theory and Applications, Nova Science Publishers, New York, 2012 (2) 85-120. [11] Huang, G.H., Baetz, B.W., Patry, G.G., “A grey linear programming approach for municipal solid waste management planning under uncertainty”, Civ. Eng. Environ. Syst., 9 (1992) 319-335. [12] Huang, G.H., Baetz, B.W., Patry, G.G., “Grey integer programming: an application to waste management planning under uncertainty”, Eur. J. Oper. Res., 83 (1995) 594-620. [13] Huang, G.H., Cao, M.F., “Analysis of solution methods for interval linear programming”, Journal of Environmental Informatics, 17 (2) (2011) 54-64. [14] Huang, G.H., Moore, R.D., “Grey linear programming, its solving approach, and its appli- cation”, International Journal of Systems Science, 24 (1993) 159-172. [15] Jansson, C., “A self-validating method for solving linear programming problems with inter- val input data”, in: Kulisch, U., Stetter, H.J. (eds.) Scientific computation with automatic result verification, Computing Suppl., 6 (1988) 33-45. [16] Jansson, C., Rump, S. M., “Rigorous solution of linear programming problems with uncer- tain data”,Oper. Res., 35 (2) (1991) 87-111. [17] Konickova, J., “Sufficient condition of basis stability of an interval linear programming problem”, ZAMM. Z. Angew. Math. Mech., 81 (3) (2001) 677-678. [18] Li, Y.P., Huang, G. H., Guo, p., Yang, Z. F., and Nie, S. L., “A dual-interval vertex analysis method and its application to environmental decision making under uncertainty”, Eur. J. Oper. Res., 200 (2010) 536-550. M. Allahdadi and C. Deng / An improved ThSM for solving the ILP problems 451 [19] Machost, B., “Numerische Behandlung des Simplexverfahrens mit intervallanalytischen Methoden”, Tech. Rep. 30, Berichte der Gesellschaft fr Mathematik und Datenverarbeitung, 54 pages, Bonn, 1970. [20] Mraz, F., “On infimum of optimal objective function values in interval linear programming”, Technical report KAM Series, Department of Applied Mathematics, Charles University, Prague, 96-337,1996. [21] Rex, J., Rohn, J., “Sufficient conditions for regularity and singularity of interval matrices”, SIAM J. Matrix Anal. Appl., 20 (2) (1998) 437-445. [22] Rohn, J., “Cheap and tight bound: The recent result by E. Hansen can be made more efficient”, Interval comput., 4 (1993) 13-21. [23] Rohn, J., “Forty necessary and sufficient conditions for regularity of interval matrices: A survey”, J. Linear Algebra, 18 (2009) 500-512. [24] Rohn, J.,“Interval linear programming”, in M. Fiedler et al., editor, Linear optimization problems with inexact data, chapter 3, pages 79-100, Springer, New York, 2006. [25] Rohn, J., “Stability of the optimal basis of a linear program under uncertainty”, Oper. Res. Lett., 13 (1) (1993) 9-12. [26] Tong, S.C., “Interval number, fuzzy number linear programming”, Fuzzy Sets and Systems, 66 (1994) 301-306. [27] Wang, X., Huang, G., “Violation analysis on two-step method for interval linear program- ming”, Information Sciences, 281 (2014) 85-96. [28] Zhou, F., Huang, G. H., Chen, G., Guo, H., “Enhanced-interval linear programming”, European Journal of Operational Research, 199 (2009) 323-333.