Subscribe Now Subscribe Today
Abstract
Fulltext PDF
References
Research Article
 
Solving Linear Tri-level Programming Problem Using Heuristic Method Based on Bi-section Algorithm



Eghbal Hosseini
 
ABSTRACT
Background and Objective: In the recent decades several algorithms have been proposed to solve optimization problems. Among these algorithms, heuristics and meta-heuristics are much better than others. On the other hand, the multi-level programming problems are attractive for many researchers because of their application in several areas such as transportation, information technology, engineering and so on. The objective of this study was to solve tri-level programming problem, which was more important, by a heuristic approach. Materials and Methods: In this study, an approach based on bi-section algorithm would be proposed for solving the linear tri-level programming problem. Using Karush-Kuhn-Tucker conditions the tri-level programming problem was converted to a non-smooth single problem and then the problem would be smoothed by proposed smoothing function. Finally, bi-section algorithm was applied to solve the smoothed problem. Results: Main findings of this study were converted tri-level programming problem to a single problem, smoothing the converted problem, linearization the smoothed problem and solved the last problem by bi-section algorithm. It has been shown that, bi-section algorithm was efficient and feasible solution by solving some problems. Conclusion: Therefore, it is concluded that by comparing with the results of previous methods, this proposed algorithm has better numerical results and present better solutions. The best solutions produced by this algorithm were feasible unlike the previous best solutions. Solving large size of the problem would be significant for future works. Also extension of the problem to other kinds of multi-level programming problems would be interesting.
Services
Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

Eghbal Hosseini , 2017. Solving Linear Tri-level Programming Problem Using Heuristic Method Based on Bi-section Algorithm. Asian Journal of Scientific Research, 10: 227-235.

DOI: 10.3923/ajsr.2017.227.235

URL: http://scialert.net/abstract/?doi=ajsr.2017.227.235
 
Received: April 18, 2017; Accepted: May 17, 2017; Published: June 15, 2017

INTRODUCTION

Even to seek for the locally optimal solutions, the bi-level programming problem (BLPP) is an NP- Hard problem1,2. In fact the BLPP is an practical problem and a suitable tool for solving decision making problems. It is used in different areas such as information technology, transportation, computer science, engineering and so on. Therefore proposing the optimal solution is significant researchers.

There are different approaches to solve the BLPP3-8. These all algorithms would be divided into the following classes: Global techniques9,10, fuzzy methods11-13, meta heuristic approaches14-20, transformation methods21-27, enumeration methods28, However there is just an algorithm for solving TLPP29.

Linear bi-level and tri-level programming problems: The bi-level and tri-level programming problems would be introduced in this study.

The BLPP is defined as the following problem by Lv et al.1:

(1)

x,y > 0

where, and F(x, y) and g(x, y) are the objective functions of the leader and the follower, respectively.

Because a tri-level decision reflects the principle features of multi-level programming problems, the algorithms developed for tri-level decisions can be easily extended to multi-level programming problems which the number of levels is more than three. Hence, just tri-level programming is studied in this study.

In a TLPP, each decision entity at one level has its objective and its variables in part controlled by entities at other levels. To describe a TLPP, a basic model can be written as follows by Zhang et al.29:

(2)

x,y,z > 0

where, Ai∈Rq×k, Bi∈Rq×l, Ci∈Rq×p, ri∈Rq, x∈Rk, y∈Rl, z∈Rp, ai∈Rk, bi∈Rl, ci∈Rp, i = 1, 2, 3 and the variables x, y, z are called the top-level, middle-level and bottom-level variables respectively, F1(x, y, z), F2(x, y, z), F3(x, y, z), the top-level, middle-level and bottom-level objective functions, respectively. In this problem each level has individual control variables, but also takes account of other level’s variables in its optimization function.

To obtain an optimized solution to TLP problem based on the solution concept of bi-level programming6, here first introduce some definitions and notation.

Definition 1: The feasible region of the TLP problem when i = 1, 2, 3 is:

(3)

On the other hand, if x be fixed, the feasible region of the follower can be explained as:

(4)

Based on the above assumptions, the follower rational reaction set is:

(5)

Where the inducible region is as follows:

(6)

Finally, the tri-level programming problem can be written as:

(7)

If there is a finite solution for the TLP problem, we define feasibility and optimality for the TLP problem as:

(8)

Definition 2: Every point such as is a feasible solution to tri-level problem if (x, y, z) ∈IR.

Definition 3: Every point such as (x*, y*, z*) is an optimal solution to the tri-level problem if:

(9)

Smooth method for TLPP: Using KKT conditions for both of last levels in problem 2, the following problem is constructed:

(10)

x,y,z,μii > 0

Problem 10 is not convex and it is not differentiable. In this study, we proposed a smooth method for smoothing complementary constraints in problem 10. Using the following smooth method, problem 10 will be smoothed and then presented two algorithms based on Taylor theorem and hybrid algorithm to solve it.

Theorem 1: Let:

or:

where, m>0, n>0, then:

and:

Proof:

Also:

Using the proposed function:

in problem 10, we obtain the following problem:

(11)

x,y,z,μii > 0

Which in the first constraint m = μi>0, n = -gi (x, y)>0, gi (x, y) = aix+biy+ciz and ai, bi, ci are i-th row of A, B, C, respectively and in the second constraint m = βi>0, n = -hi (x, y)>0, hi (x, y) = aix+biy+ciz-r and ai, bi, ci are i-th row of A, B, C.

Let:

(12)

(13)

(14)

Problem 11 can be written as follows:

(15)

x,y,z,μ,β > 0

Where:

t = (x, y, μ)∈Rk+2l

Because problem 10 equal to 15, used the following method for solving problem 15.

Proposed algorithm based on bi-section method
Theoretical concepts:
Nonlinear equations are difficult to solve, therefore there are many algorithms to approximate of the root these equations. Bi-section algorithm is one of the most important methods to approximate the root. Necessary condition to use this method, is the uniqueness root of the nonlinear equation. The necessary definitions and theorems have been proposed by Hosseini and Kamalabadi21.

By applying the Taylor theorem to a feasible point such as tk for functions G’ and H’ taking only two linear part of them in problem 15, the following linear functions are constructed:

(16)

Let:

(17)

(18)

Let:

(19)

Using Taylor theorem for G’ and H’ at tk and 17, 19, in problem 15 obtained the following problem:

(20)

t, μ, β>0

Steps of the bi-section algorithm: The steps of the bi-section algorithm for f(x) = 0 as follows:

Step 1: Input a,b
Step 2: let x = (a+b)/2:print x
Step 3: If ABS(f(x))<ε then end
Step 4: If f(a)f(x)<0 then let b = x else let a = x
Step 5: GOTO 2
Step 6: End

ε is a positive small number

Steps of the proposed algorithm: The steps of the proposed algorithm are as follows:

Step 1
Initialization:
The feasible points a and b are created randomly and according to theorem 1, error ε is appropriate given error and finishing the algorithm depends on ε.

Step 2
Finding solution:
Using in step 1 and bi-section algorithm for in problem 15, two non-linear equations P(t) = 0 and Q(t) = 0 have been solved. Let t*1, t*2 are roots of P(t) = 0 and Q(t) = 0, if t*1 = t*2 let t* = t*1 = t*2 and go to the next step else go to step 4.

Step 3
Making the present best solution:
If t* solves the following problem go to the next step else go to step 1:

Step 4
Termination:
If d(F(t*1), F(t*2))<ε then the algorithm is finished and:

is the best solution by the proposed algorithm. Otherwise, go to the step 1. Which d is metric and:

Following theorems show that the proposed algorithm is convergent.

Theorem 2: Every Cauchy sequence in real line and complex plan is convergent.

Proof: Proof of this theorem was given by Rudin30.

Theorem 3: Sequence {Fk} which was proposed in above algorithm is convergent to the optimal solution, so that the algorithm is convergent.

Proof: Let:

According to step 4:

(21)

Therefore:

There is large number such as N which k+1>k>N and j = 1, 2,…, 2m+n we have:

Therefore:

Now let m = k+1, r = k then we have:

This shows that for each fixed j, (1<j<2m+n), the sequence (Fj(1), Fj(2),…) is Cauchy of real numbers, then it converges by theorem 2.

Say, Fj(m) → Fj asm → ∞. Using these 2m+n limits, we define F = (F1, F2,…, F2m+n). From 18 and m = k+1, r = k:

d(Fm, Fr)<ε1

Now if r → ∞, by Fr → F we have d (Fm, F)<ε1.

This shows that F is the limit of (Fm) and the sequence is convergent by definition 3 therefore proof of theorem is finished.

Theorem 4: If sequence {f(tk)} is converge to f(t) and f be linear function then {tk} is converge to t.

Proof: Proof of this theorem is given by Rudin30.

Theorem 5: Problem 15 and 23 are equal therefore they have same optimal solutions.

Proof: It is sufficient we prove that, ∣G’(t)-P(t)∣<ε and ∣H’(t)-Q(t)∣<ε for every arbitrary ε>0. According to the problem 19, 20 we have:

Now if n → ∞, from 18:

and let ∣∇2G’(tk)∣<m that m is an arbitrary large number, this is possible because ∇2G’(tk) is a number.

If k → ∞ because F is linear then by theorems 3 and 4 tk → t therefore ∣tk-t∣<ε2, say:

Now proved:

and let ∣∇2H’(tk)∣<m that m is an arbitrary large number, this is possible because ∇2H’(tk) is a number.

If k → ∞ because F is linear then by theorems 3 and 4 tk → t therefore ∣tk-t∣<ε2 , say:

This finished proof of theorem.

Computational results: To illustrate both algorithms, considered the following examples:

Example 1: Consider the following linear tri-level programming problem by Zhang et al.29:

Using KKT conditions, the following problem is obtained:

By the proposed function, the above problem becomes:



Fig. 1:Behavior of variables with ε = 0.001 in example 1

Fig. 2(a-d): Dimensionless distribution at different axial positions, y, z, t, for fix ε in example 1


Table 1:Comparison of optimal solutions by Taylor algorithm-example 1

Using the Taylor theorem, we obtain a problem in the form of problem 20 and solve it using the proposed algorithm. Optimal solution is presented according to Table 1. Behavior of the variables in example 1 has been show in Fig. 1. Dimensionless distribution at different axial positions has been shown in Fig. 2.

Example 2: Consider the following linear tri-level programming problem by Zhang et al.29:

Table 2:Comparison of optimal solutions by Taylor algorithm-example 2

Optimal solution for this example is presented according to Table 2. Behavior of the variables has been showed that variables x and y will be stable after 1000 and 4000 iterations respectively.

CONCLUSION AND FUTURE RECOMMENDATIONS

In this study, KKT conditions were used to convert the problem into a single level problem. Then, using the proposed function, the problem was made simpler and converted to a smooth programming problem. The smoothed problem was been solved, utilizing the first proposed algorithm based on Taylor theorem. Comparing with the results of previous methods, this algorithm has better numerical results and present better solutions. The best solutions produced by proposed algorithm were feasible unlike the previous best solutions by other researchers.

In the future works, the following would be researched:

Examples in larger sizes can be supplied to illustrate the efficiency of the proposed algorithms
Showing the efficiency of the proposed algorithms for solving other kinds of TLP such as quadratic and non-linear TLP

ACKNOWLEDGMENTS

The author would like to extend his thanks to the Faculty of Mathematics, University of Raparin. Special thanks also for Quality Assurance of the university which supported this study.

SIGNIFICANCE STATEMENTS

This study discovers an approach for solving the tri-level programming problem which is efficient not only for tri-level but also other kinds of multi-level programming problems. An efficient and feasible method based on bi-section algorithm is presented in this study. Most of the previous studies for BLPP have used approximate method which has high complexity order and has not efficient solution. The heuristic proposed algorithm in this study is based on an exact method which has never been proposed before. This study will help the researchers to solve other NP-Hard problems of optimization area.

REFERENCES
Allende, G.B. and G. Still, 2013. Solving bilevel programs with the KKT-approach. Math. Program., 138: 309-332.
CrossRef  |  Direct Link  |  

Arora, S.R. and R. Gupta, 2009. Interactive fuzzy goal programming approach for bilevel programming problem. Eur. J. Operat. Res., 194: 368-376.
CrossRef  |  Direct Link  |  

Brotcorne, L., S. Hanafi and R. Mansi, 2013. One-level reformulation of the bilevel Knapsack problem using dynamic programming. Discrete. Optim., 10: 1-10.
CrossRef  |  Direct Link  |  

Dempe, S. and A.B. Zemkoho, 2012. On the Karush-Kuhn-Tucker reformulation of the bilevel optimization problem. Nonlinear Anal.: Theory Methods Applic., 75: 1202-1218.
CrossRef  |  Direct Link  |  

He, X., C. Li, T. Huang and C. Li, 2014. Neural network for solving convex quadratic bilevel programming problems. Neural Networks, 51: 17-25.
CrossRef  |  Direct Link  |  

Hosseini, E. and I.N. Kamalabadi, 2013. A genetic approach for solving bi-level programming problems. Adv. Model. Optimizat., 15: 719-733.
Direct Link  |  

Hosseini, E. and I.N. Kamalabadi, 2014. Enhancing the Solution method of linear tri-level programming problem utilizing a new heuristic approach. Global J. Adv. Res., 1: 56-68.
Direct Link  |  

Hosseini, E. and I.N. Kamalabadi, 2015. Two approaches for solving non-linear Bi-level programming problem. Adv. Res., 4: 512-525.
CrossRef  |  Direct Link  |  

Hosseini, E. and I.N. Kamalabadi, 2015. Smoothing and solving linear quad-level programming problem using mathematical theorems. Int. J. Math. Comput. Sci., 1: 116-126.
Direct Link  |  

Hosseini, E. and I.N. Kamalabadi, 2015. Bi-section algorithm for solving linear Bi-level programming problem. Int. J. Sci. Eng., 1: 101-107.
Direct Link  |  

Hosseini, E., 2017. Laying chicken algorithm: A new meta-heuristic approach to solve continuous programming problems. J. Applied Comput. Math., Vol. 6. 10.4172/2168-9679.1000344

Hosseini, E., 2017. Presentation and solving non-linear quad-level programming problem utilizing a heuristic approach based on Taylor theorem. J. Optim. Ind. Eng., (In Press). 10.22094/joie.2017.282

Hosseini, E., I.N. Kamalabadi and F. Daneshfar, 2016. Solving Non-Linear Bi-Level Programming Problem Using Taylor Algorithm. In: Handbook of Research on Modern Optimization Algorithms and Applications in Engineering and Economics, Vasant, P., G.W. Weber and V.N. Dieu (Eds.). IGI Global Publisher, USA., ISBN-13: 978-1466696440, pp: 797-810.

Hu, T., X. Guo, X. Fu and Y. Lv, 2010. A neural network approach for solving linear bilevel programming problem. Knowledge-Based Syst., 23: 239-242.
CrossRef  |  Direct Link  |  

Jiang, Y., X. Li, C. Huang and X. Wu, 2013. Application of particle swarm optimization based on CHKS smoothing function for solving nonlinear bilevel programming problem. Applied Math. Comput., 219: 4332-4339.
CrossRef  |  Direct Link  |  

Jiang, Y., X. Li, C. Huang and X. Wu, 2014. An augmented Lagrangian multiplier method based on a CHKS smoothing function for solving nonlinear bilevel programming problems. Knowledge-Based Syst., 55: 9-14.
CrossRef  |  Direct Link  |  

Lan, K.M., U.P. Wen, H.S. Shih and E.S. Lee, 2007. A hybrid neural network approach to bilevel programming problems. Applied Math. Lett., 20: 880-884.
CrossRef  |  Direct Link  |  

Lv, Y., T. Hu, G. Wang and Z. Wan, 2007. A penalty function method based on Kuhn-Tucker condition for solving linear bilevel programming. Applied Math. Comput., 188: 808-813.
CrossRef  |  Direct Link  |  

Pal, B.B., D. Chakraborti and P. Biswas, 2010. A genetic algorithm approach to fuzzy quadratic bilevel programming. Proceedings of the International Conference on Computing Communication and Networking Technologies, July 29-31, 2010, Karur, India, pp: 1-7.

Pramanik, S. and T.K. Roy, 2007. Fuzzy goal programming approach to multilevel programming problems. Eur. J. Operat. Res., 176: 1151-1166.
CrossRef  |  Direct Link  |  

Rudin, W., 2008. Consequences of the Schwarz Lemma. In: Function Theory in the Unit Ball of Cn, Rudin, W. (Ed.). Springer-Verlag, Berlin, Heidelberg, ISBN: 978-3-540-68276-9, pp: 161-184.

Sakawa, M. and T. Matsui, 2012. Stackelberg solutions for random fuzzy two-level linear programming through possibility-based probability model. Expert Syst. Applic., 39: 10898-10903.
CrossRef  |  Direct Link  |  

Wan, Z., G. Wang and B. Sun, 2013. A hybrid intelligent algorithm by combining particle swarm optimization with chaos searching technique for solving nonlinear bilevel programming problems. Swarm Evol. Comput., 8: 26-32.
CrossRef  |  Direct Link  |  

Wan, Z., G. Wang and K. Hou, 2008. An interactive fuzzy decision making method for a class of bilevel programming. Proceedings of the 5th International Conference on Fuzzy Systems and Knowledge Discovery, Volume 1, October 18-20, 2008, Shandong, China, pp: 559-564.

Wan, Z., L. Mao and G. Wang, 2014. Estimation of distribution algorithm for a class of nonlinear bilevel programming problems. Inform. Sci., 256: 184-196.
CrossRef  |  Direct Link  |  

Wang, G., B. Jianq, K. Zhu and Z. Wan, 2010. Global convergent algorithm for the bilevel linear fractional-linear programming based on modified convex simplex method. J. Syst. Eng. Electron., 21: 239-243.
CrossRef  |  Direct Link  |  

Wang, G., Z. Wan, X. Wang and Y. Lv, 2008. Genetic algorithm based on simplex method for solving linear-quadratic bilevel programming problem. Comput. Math. Applic., 56: 2550-2555.
CrossRef  |  Direct Link  |  

Xu, P. and L. Wang, 2014. An exact algorithm for the bilevel mixed integer linear programming problem under three simplifying assumptions. Comput. Operat. Res., 41: 309-318.
CrossRef  |  Direct Link  |  

Zhang, G., J. Lu, J. Montero and Y. Zeng, 2010. Model, solution concept and Kth-best algorithm for linear trilevel programming. Inform. Sci., 180: 481-492.
CrossRef  |  Direct Link  |  

Zheng, Y., J. Liu and Z. Wan, 2014. Interactive fuzzy decision making method for solving bilevel programming problem. Applied Math. Modell., 38: 3136-3141.
CrossRef  |  Direct Link  |  

©  2017 Science Alert. All Rights Reserved
Fulltext PDF References Abstract