An Algorithm to solve linear fractional bi-level problems based on Taylor approximation.

Document Type : Research Paper

Authors

Faculty of Science, Urmia University of Technology, Urmia, Iran

Abstract

The linear fractional bi-level problems are strongly NP-hard and non-convex, which results in high computational complexity to find the optimal solution. In this paper, we propose an efficient algorithm for solving a class of non-linear bi-level optimization problems, where the upper and lower objectives are linear fractional. The main idea behind the proposed algorithm is to obtain a single objective optimization problem via Taylor approximation. The proposed algorithm is composed of four steps. In the first, the lower level of the problem is converted into the convex optimization problem by using auxiliary variables and approximation techniques. Next, a single objective optimization problem is obtained by adopting the dual Lagrange method and Karush-Kuhn-Tucker (KKT) conditions. The obtained problem is non-convex with high computational complexity challenging to solve. Hence, the Fischer-Burmeister function is applied to smooth the problem. Finally, the first-order Taylor approximation is adopted to transform the non-linear problem into the linear one. Numerical results confirm the effectiveness of the proposed algorithm in comparison with Estimation of Distribution Algorithm (EDA) in terms of convergence performance.

Keywords

Main Subjects

References

Aghapour, H., & Osgooei, E. (2022). A novel approach for solving the fully fuzzy bi-level linear programming problems. Journal of Industrial and Systems Engineering, 14(1), 221-237.
Alessa, N. A. (2021). Bi-Level linear programming of intuitionistic fuzzy. Soft Computing, 25(13), 8635-8641.
Angelo, J. S., Krempser, E., & Barbosa, H. J. (2013, June). Differential evolution for bilevel programming. In 2013 IEEE Congress on Evolutionary Computation (pp. 470-477). IEEE.
Beck, A., Ben-Tal, A., & Tetruashvili, L. (2010). A sequential parametric convex approximation method with applications to nonconvex truss topology design problems. Journal of Global Optimization, 47, 29-51.
Camacho-Vallejo, J. F., Muñoz-Sánchez, R., & González-Velarde, J. L. (2015). A heuristic algorithm for a supply chain׳ s production-distribution planning. Computers & Operations Research, 61, 110-121.
Chen, H. J. (2020). A two-level vertex-searching global algorithm framework for bilevel linear fractional programming problems. Systems Science & Control Engineering, 8(1), 488-499.
Chen, H. J. (2019). A new vertex enumeration-based approach for bilevel linear-linear fractional programming problems. Journal of Information and Optimization Sciences, 40(7), 1413-1427.
Chen, H., Li, H., & Huang, J. (2018, August). An EDA for Solving Linear Fractional Bilevel Programming Problems. In 2018 International Conference on Information Technology and Management Engineering (ICITME 2018) (pp. 196-200). Atlantis Press.
Colson, B., Marcotte, P., & Savard, G. (2007). An overview of bilevel optimization. Annals of operations research, 153, 235-256.
Colson, B., Marcotte, P., & Savard, G. (2005). A trust-region method for nonlinear bilevel programming: algorithm and computational experience. Computational Optimization and Applications, 30, 211-227.
Dempe, S. (2003). Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints.
Dempe, S. (2002). Foundations of bilevel programming. Springer Science & Business Media.
Hejazi, S. R., Memariani, A., Jahanshahloo, G., & Sepehri, M. M. (2002). Linear bilevel programming solution by genetic algorithm. Computers & Operations Research, 29(13), 1913-1925.
Hussein, E., & Kamalabadi, I. (2014). Taylor approach for solving nonlinear bilevel programming problem. Adv. Comput. Sci., Int. J, 3(5), 91-97.
Li, H. (2015). A genetic algorithm using a finite search space for solving nonlinear/linear fractional bilevel programming problems. Annals of Operations Research, 235(1), 543-558.
Li, H., & Wang, Y. (2007, August). A hybrid genetic algorithm for solving nonlinear bilevel programming problems based on the simplex method. In Third International Conference on Natural Computation (ICNC 2007) (Vol. 4, pp. 91-95). IEEE.
Lv, Y., Hu, T., Wang, G., & Wan, Z. (2007). A penalty function method based on Kuhn–Tucker condition for solving linear bilevel programming. Applied mathematics and computation, 188(1), 808-813.
Marcotte, P., Savard, G., & Zhu, D. L. (2001). A trust region algorithm for nonlinear bilevel programming. Operations research letters, 29(4), 171-179.
Mishra, S. (2007). Weighting method for bi-level linear fractional programming problems. European Journal of Operational Research, 183(1), 296-302.
Nayak, S., & Ojha, A. K. (2020). Solving Bi-Level Linear Fractional Programming Problem with Interval Coefficients. In Numerical Optimization in Engineering and Sciences: Select Proceedings of NOIEAS 2019 (pp. 265-273). Springer Singapore.
Roghanian, E., Aryanezhad, M. B., & Sadjadi, S. J. (2008). Integrating goal programming, Kuhn–Tucker conditions, and penalty function approaches to solve linear bi-level programming problems. Applied Mathematics and Computation, 195(2), 585-590.
Toksarı, M. D. (2010). Taylor series approach for bi-level linear fractional programming problem. Selçuk journal of applied mathematics, 11(1), 63-69.
Tran, L. N., Hanif, M. F., Tolli, A., & Juntti, M. (2012). Fast converging algorithm for weighted sum rate maximization in multicell MISO downlink. IEEE Signal Processing Letters, 19(12), 872-875.
Vicente, L. N., & Calamai, P. H. (1994). Bilevel and multilevel programming: A bibliography review. Journal of Global optimization, 5(3), 291-306.
Wan, Z., Wang, G., & Sun, B. (2013). A hybrid intelligent algorithm by combining particle swarm optimization with chaos searching technique for solving nonlinear bilevel programming problems. Swarm and Evolutionary Computation, 8, 26-32.
Wang, Y., Li, H., & Dang, C. (2011). A new evolutionary algorithm for a class of nonlinear bilevel programming problems and its global convergence. INFORMS Journal on Computing, 23(4), 618-629.
Watada, J., Roy, A., Wang, B., Tan, S. C., & Xu, B. (2020). An artificial bee colony-based double layered neural network approach for solving quadratic bi-level programming problems. IEEE Access, 8, 21549-21564.
White, D. J., & Anandalingam, G. (1993). A penalty function approach for solving bi-level linear programs. Journal of Global Optimization, 3, 397-419.
Zhang, G., Han, J., & Lu, J. (2016). Fuzzy bi-level decision-making techniques: a survey. International Journal of Computational Intelligence Systems, 9(sup1), 25-34.
Zhou, X., Tian, J., Wang, Z., Yang, C., Huang, T., & Xu, X. (2022). Nonlinear bilevel programming approach for decentralized supply chain using a hybrid state transition algorithm. Knowledge-Based Systems, 240, 108119. 
Journal of Industrial and Systems Engineering
Volume 14, Issue 4 - Serial Number 4
November 2022
Pages 279-292

Files

History

  • Receive Date: 08 March 2023
  • Revise Date: 08 April 2023
  • Accept Date: 11 April 2023

Share

How to cite

Statistics