# Solving Linear Tri-level Programming Problem using Approaches Based on Line Search and an Approximate Algorithm

Author Affiliations

^{1}Candidate at Payamenur University of Tehran, Department of Mathematics, Tehran^{2}Industrial Engineering at University of Kurdistan, Sanandaj, IRAN

*Res. J. Management Sci.,* **Volume 3, Issue (12),** Pages 18-26, December,6 **(2014)**

## Abstract

In the recent years, the bi-level and tri-level programming problems (TLPP) are interested by many researchers and TLPP is known as an appropriate tool to solve the real problems in several areas such as economic, traffic, finance, management, and so on. Also, it has been proven that the general TLPP is an NP-hard problem. The literature shows a few attempts for solving using TLPP. In this paper, we attempt to develop two effective approaches, one based on Taylor theorem and the other based on the hybrid algorithm by combining the penalty function and the line search algorithm for solving the linear TLPP. In these approaches, by using Karush-Kuhn-Tucker conditions, TLP Pischanged to 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.

## References

- Bard J.F Some properties of the bi-level linear programming, Journal of OptimizationTheory and Applications 68, 371–378 (1991)
- Vicente L. et.al, Descent approaches for quadratic bi-level programming, Journal of Optimization Theory and Applications, 81, 379–399 (1994)
- Yibing Lv et.al, A penalty function method Based on Kuhn–Tucker condition for solving linear bilevel programming, Applied Mathematics and Computation, 1(88), 808–813 (2007)
- Allende G.B. et.al, Solving bi-level programs with the KKT-approach, Springer and Mathematical Programming Society, 1(31), 37– 48 (2012)
- Mathieu R. et.al, Genetic algorithm based approach to bi-level Linear Programming, Operations Research, 28, 1–21 (1994)
- Wang G. and Jiang B., Global convergent algorithm for the bi-level linear fractional-linear programming based on modified convex simplex method, Journal of Systems Engineering and Electronics. 239–243 (2010)
- Wend W.T and Wen U.P., A primal-dual interior point algorithm for solving bi-level programming problems, Asia-Pacific J. of Operational Research, 17 (2000)
- Hosseini E andNakhai Kamalabadi I., Line Search and Genetic Approaches for Solving Linear Tri-level Programming Problem, International Journal of Management, Accounting and Economics,1(4), (2014)
- Sanjay Bhaskaran and R. Jubi,Impact of Emotional Intelligence on Productivity of Software Professionals, Res. J. Management Sci., 3(3),10-13 (2014)
- Nocedal J. and Wright S.J., Numerical Optimization, Springer-Verlag, New York (2005)
- Khayyal A.A.L. et.al, 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 (1985)
- Wan Z and Mao L, Estimation of distribution algorithm for a class of nonlinear bilevel programming problems, Information Sciences, 256(20), 184-196 (2014)
- Wang P. et.al, An exact algorithm for the bilevel mixed integer linear programming problem under three simplifying assumptions, Computers & Operations Research, 41, 309-318 (2014)
- Thoai N.V. and Yamamoto Y., Global optimization method for solving mathematical programs with linear complementary constraints, Institute of Policy and Planning Sciences, University of Tsukuba, Japan 978 (2002)
- Luce B. and Saïd. H., One-level reformulation of the bi-level Knapsack problem using dynamic programming, Discrete Optimization, 10, 1–10 (2013)
- Dempe S and Zemkoho A.B, On the Karush–Kuhn–Tucker reformulation of the bi-level optimization problem, Nonlinear Analysis, 75, 1202–1218 (2012)
- Bazara M.S. and Sherali H.D., Non-Linear Programming, Theory and Algorithm, New York (2005)
- Jiang Y. et.al, An augmented Lagrangian multiplier method based on a CHKS smoothing function for solving nonlinear bi-level programming problems, Knowledge-Based Systems, 55, 9-14 (2014)
- Wang G.Z. and Wan X., Genetic algorithm based on simplex method for solving Linear-quadratic bi-level programming problem, Computers and Mathematics with Applications, 56, 2550–2555, (2008)
- GuoX and Fu Y Lv, A neural network approach for solving linear bi-level programming problem, Knowledge-Based Systems, 23, 239–242 (2010)
- Baran Pal B. and Chakraborti D., A Genetic Algorithm Approach to Fuzzy Quadratic Bi-level Programming, Second International Conference on Computing, Communication and Networking Technologies(2010)
- Wan ZG and Wang Sun, A hybrid intelligent algorithm by combining particle Swarm optimization with chaos searching technique for solving nonlinear bi-level programming Problems, Swarm and Evolutionary Computation (2012)
- Huang T,Neural network for solving convex quadratic bilevel programming problems, Neural Networks, 51, 17-25 (2014)
- Hosseini E. and Nakhai Kamalabadi I., A Genetic Approach for Solving Bi-Level Programming Problems, Advanced Modeling and Optimization, 15, 3, (2013)
- Hosseini E. and Nakhai KamalabadiI., Solving LinearQuadratic Bi-Level Programming and Linear-Fractional Bi-Level Programming Problems Using Genetic Based Algorithm, Applied Mathematics and Computational Intellegenc, 2, (2013)
- Hejazi S.R. and Memariani A., Linear bi-level programming solution by genetic algorithm, Computers & Operations Research, 29, 1913–1925 (2002)
- Sakava M et.al, Interactive fuzzy programming for multilevel linear programming problem, Computers & Mathematics with Applications, 36, 71–86 (1997)
- Sinha S., Fuzzy programming approach to multi-level programming problems, Fuzzy Sets And Systems, 136, 189–202 (2003)
- Pramanik S., Fuzzy goal programming approach to multilevel programming problems, European Journal of Operational Research, 194, 368–376 (2009)
- Arora S.R. and Gupta R., Interactive fuzzy goal programming approach for bi-level programming problem, European Journal of Operational Research, 176, 1151–1166 (2007)
- Mohan R. and Venkateswarlu R., Inventory Management Model with Quadratic Demand, Variable Holding Cost with Salvage value, Res. J. Management Sci.,3(1), 18-22 (2014)
- Zheng Y. et.al,Interactive fuzzy decision making method for solving bi-level programming problem, Applied Mathematical Modelling,38(13), 3136-3141 (2014)
- Tauseef Zia Siddiqui Pramod Pathakand Asif Akhtar, A Model in Recommender Systems for Disease Diagnosis Using Combined Method, Res. J. Recent Sci.,3(3), 72-77 (2014)
- Anaram Yaghoobi Notash, Behrouz Minaei and Afshin Salajegheh, L. Kuen-Ming, Ue-Pyng.W, Hsu-Shih.S, A hybrid neural network approach to bi-level programming problems, Res. J. Recent Sci., 20 (2014)
- Hadi Yasrebdoost, Saeid Sarbazy Moghadam and Salma Ghassem Bagloo, A Model for Suppliers' Assessment through fuzzy AHP Technique at Piece Making Firms, Res. J. Recent Sci., 3(9), 1-9 (2014)
- Bard J.F., Practical bi-level optimization: Algorithms and applications, Kluwer Academic Publishers, Dordrecht, (1998)
- Silverman. Richard A., Calculus with analytic geometry, ISBN:978-964-311-008-6, (2000)
- Zhang G and Montero J., Model, solution concept, and Kth-best algorithm for linear tri-level, ProgrammingInformation Sciences,180, 481–492, (2010)