International Journal of Management, Accounting and Economics

Monthly Publication

Current Issue

By Issue

By Author

By Subject

Author Index

Keyword Index

About Journal

Aims and Scope

Editorial Board

Publication Ethics

Indexing and Abstracting

Related Links

FAQ

Peer Review Process

Journal Metrics

News

Line Search and Genetic Approaches for Solving Linear Tri-level Programming Problem

Document Type : Original Research

Authors

1 Department of Mathematics, Payam Noor University of Tehran, Tehran, Iran

2 Department of Industry, University of Kurdistan, Sanandaj, Iran

Abstract

In the recent years, the multi-level programming problems specially the bi-level and tri-level programming problems (TLPP) are interested by many researchers and these problems, particularly TLPP, are known as an appropriate tool to solve the real problems in several areas of optimization such as economic, traffic, finance, management, transportation, computer science and so on. Also, it has been proven that the general bi-level and TLPP are NP-hard problems. The literature shows it has been proposed a few attempts for solving using TLPP. In this paper, we attempt to propose a new function for smoothing the tri-level programming problem after using Karush-Kuhn-Tucker condition, also we develop two effective approaches, one based on Genetic algorithm, which it is an approximate approach, and the other based on the hybrid algorithm by combining the proposed method based on penalty function and the line search algorithm for solving the linear TLPP. In both of these approaches, by using the Karush-Kuhn-Tucker condition the TLPP is converted to a non-smooth single problem, and then it is smoothed by proposed functions. Finally, the smoothed problem is solved using both of the proposed approaches. The presented approaches achieve an efficient and feasible solution in an appropriate time which has been evaluated by comparing to references and test problems.

Keywords

References
Allende, G, & B. G. Still. (2012).  Solving bi-level programs with the KKT-approach, Springer and Mathematical Programming Society 1 31:37 – 48.
Arora, S.R,  & R. Gupta. (2007). Interactive fuzzy goal programming approach for bi-level programming problem, European Journal of Operational Research 176  1151–1166.
Bard, J.F. (1991). Some properties of the bi-level linear programming, Journal of Optimization Theory and Applications 68  371–378.
Bard, J.F. (1998). Practical bi-level optimization: Algorithms and applications, Kluwer Academic Publishers, Dordrecht.
Dempe, S, & A.B. Zemkoho.(2012). On the Karush–Kuhn–Tucker reformulation of the bi-level optimization problem, Nonlinear Analy sis 75 1202–1218.
Facchinei, F, H. Jiang, & L. Qi. (1999). A smoothing method for mathematical programming with  equilibrium constraints, Mathematical Programming 85 107-134. 
He, X, & C. Li, T. Huang, C. Li. (2014).Neural network for solving convex quadratic bilevel programming problems, Neural Networks, Volume 51, March, Pages 17-25.
Hosseini, E, & I.Nakhai Kamalabadi. (2013).A Genetic Approach for Solving Bi-Level Programming Problems, Advanced Modeling and Optimization, Volume 15, Number 3.
Hosseini, E , & I.Nakhai Kamalabadi. (2013).Solving Linear-Quadratic Bi-Level Programming and Linear-Fractional Bi-Level Programming Problems Using Genetic Based Algorithm, Applied Mathematics and Computational Intellegenc, Volume 2.
Hosseini, E & I.Nakhai Kamalabadi. (2014). Taylor Approach for Solving Non-Linear Bi-level Programming Problem ACSIJ Advances in Computer Science: an International Journal, Vol. 3, Issue 5, No.11 , September.
Hejazi, S.R, A. Memariani, & G. Jahanshahloo. (2002). Linear bi-level programming solution by genetic algorithm, Computers & Operations Research 29  1913–1925.
Hu, T. X, Guo, X. Fu, & Y. Lv, (2010). A neural network approach for solving linear bi-level programming problem, Knowledge-Based Systems 23  239–242.
Khayyal, A.AL. (1985). Minimizing a Quasi-concave Function Over a Convex Set: A Case Solvable by Lagrangian Duality, proceedings, I.E.E.E. International Conference on Systems, Man,and Cybemeties, Tucson AZ  661-663.
Kuen-Ming, L, Ue-Pyng.W, & Hsu-Shih.S. (2007). A hybrid neural network approach to bi-level programming problems, Applied Mathematics Letters 20 880–884
Luce, B, Saïd.H, & Raïd.M. (2013).One-level reformulation of the bi-level Knapsack problem using dynamic programming, Discrete Optimization 10 1–10.
Masatoshi, S, & Takeshi.M. (2012).Stackelberg solutions for random fuzzy two-level linear programming through possibility-based probability model, Expert Systems with Applications 39 10898–10903.
Mathieu, R, L. Pittard, & G. Anandalingam. (1994). Genetic algorithm based approach to bi-level Linear  Programming, Operations Research 28  1–21.
Nocedal, J, & S.J. Wright. (2005). Numerical Optimization, Springer-Verlag, , New York.
Pramanik, S, & T.K. Ro. (2009). Fuzzy goal programming approach to multilevel programming problems, European Journal of Operational Research 194  368–376.
Sakava, M, I. Nishizaki, & Y. Uemura. (1997).  Interactive fuzzy programming for multilevel linear programming problem, Computers & Mathematics with Applications 36 71–86.
Sinha, S. (2003). Fuzzy programming approach to multi-level programming problems, Fuzzy Sets And Systems 136  189–202.
Thoai,  N. V, Y. Yamamoto, & A. Yoshise. (2002). Global optimization method for solving mathematical programs with linear complementary constraints, Institute of Policy and Planning Sciences, University of Tsukuba, Japan 978.
Vicente, L, G. Savard, & J. Judice. (1994). Descent approaches for quadratic bi-level  programming, Journal of Optimization Theory and Applications 81  379–399.
Wend, W. T, & U. P. Wen. (2000).  A primal-dual interior point algorithm for solving bi-level programming problems, Asia-Pacific J. of Operational Research, 17.
Wang, G. Z, Wan, X. Wang, & Y.Lv. (2008).Genetic algorithm based on simplex method for solving Linear-quadratic bi-level programming problem, Computers and Mathematics with  Applications 56  2550–2555.
Wan, Z. G,  Wang, & B. Sun. ( 2012). A hybrid intelligent algorithm by combining particle Swarm optimization with chaos searching technique for solving nonlinear bi-level programming Problems, Swarm and Evolutionary Computation.
Wan, Z,  L. Mao, & G. Wang. (2014). Estimation of distribution algorithm for a class of nonlinear bilevel programming problems, Information Sciences, Volume 256, 20 January, Pages 184-196.
Xu, P, & L. Wang. (2014). An exact algorithm for the bilevel mixed integer linear programming problem under three simplifying assumptions, Computers & Operations Research, Volume 41, January, Pages 309-318.
Yan, J, Xuyong.L, Chongchao.H, & Xianing.W. (2013). Application of particle swarm optimization based on CHKS smoothing function for solving nonlinear bi-level programming problem, Applied Mathematics and Computation 219 4332–4339.
Yibing, Lv, Hu. Tiesong, & Wang. Guangmin. (2007). A penalty function method Based on Kuhn–Tucker condition for solving linear bilevel programming, Applied  Mathematics and Computation  1 88  808–813.
Zhang , G, J. Lu , J. Montero , & Y. Zeng , Model. (2010). solution concept, and Kth-best algorithm for linear tri-level, programming Information Sciences 180 481–492
Zhongping, W, & Guangmin.W. (2008).An Interactive Fuzzy Decision Making Method for a Class of Bi-level Programming, Fifth International Conference on Fuzzy Systems and Knowledge Discovery.
Zheng, Y,  J. Liu, & Z. Wan. (2014). Interactive fuzzy decision making method for solving bi-level programming problem, Applied Mathematical Modelling, Volume 38, Issue 13, 1 July, Pages 3136-3141. 
International Journal of Management, Accounting and Economics
Volume 1, Issue 4 - Serial Number 4
November 2014
Pages 264-283
Files
Share
How to cite
Statistics