A new exact solution method for bi-level linear fractional problems with multi-valued optimal reaction maps

Document Type : Research Article

Authors

• F.Y. Feleke ¹
• S.M. Kassa ²

¹ Department of Mathematics, Addis Ababa University, P.O.Box 1176, Addis Ababa, Ethiopia.

² Department of Mathematics and Statistical Sciences, Botswana International University of Science and Technology (BIUST), P/Bag 016, Palapye, Botswana.

10.22067/ijnao.2025.93619.1651

Abstract

In many practical applications, some problems are being modeled as bilevel programming problems where the upper and lower level objectives are linear fractional functions with polyhedral constraints. If the rational reaction set of (or the set of optimal solutions to) the lower level is not a singleton, then it is known that an optimal solution to the linear fractional bi-level programming problem may not occur at a boundary feasible extreme point. Hence, existing methods cannot solve such problems in general. In this article, a novel method is introduced to find the set of all feasible leader’s variables that can induce multi-valued reaction map from the follower. The proposed algorithm combines the kth best procedure with a branch-and-bound method to find an exact global optimal solution for continuous optimistic bi-level linear fractional problems without assuming the lower level rational reaction map is single valued. The branching constraint is constructed depending on the coefficients of the objective function of the lower-level problem. The algorithm is shown to converge to the exact solution of the bi-level problem. The effectiveness of the algorithm is also demonstrated using some numerical examples.

Keywords

• Bi-level programming problem
• Bi-level linear fractional programming problem
• Multi-valued rational reaction map
• kth best method
• Branch-and-bound scheme

Main Subjects

• Optimization

---

References

[1] Adhami, A. and Kausar, H. bi-level Multi-Objective Stochastic Linear Fractional Programming with General Form of Distribution, Stat., Optim. Inf. Comput. 7 (2019), 407–416.
[2] Bajalinov, E.B. Linear-Fractional Programming: Theory, Methods, Aplications and Software, Springer New York, USA, 2003.
[3] Bialas, W.F. and Karwan, M.H. Mathematical Methods for Multilevel Planning, Technical report No. 79-2, Department of Industrial Engineering, State University of New York at Buffalo, New York, 1979.
[4] Calvete, H.I. and Galé, C. The bi-level linear/linear fractional programming problem, Eur. J. Oper. Res. 114 (1999), 188–197.
[5] Calvete, H.I. and Galé, C. Solving linear fractional bi-level programs, Oper. Res. Lett. 32 (2004), 143–151.
[6] Calvete, H.I., Galé, C. and Mateo, P.M. A genetic algorithm for solving linear fractional bi-level problems, Ann. Oper. Res. 166 (2009), 39–56.
[7] Chen, H.J. A two-level vertex-searching global algorithm framework for bi-level linear fractional programming problems, Syst. Sci. Control Eng. 8 (2020), 488–499.
[8] Dempe, S. Foundations of bi-level programming, Springer New York, NY, USA, 2002.
[9] Emmami, M. and Osgooei, E. An algorithm to solve linear fractional bilevel problems based on Taylor approximation, J. Ind. Syst. Eng. 14(4) (2022), 279–292.

[10] Mathur, K. and Puri, M.C. On bi-level fractional programming, Optim. 35 (1995) 215–226.
[11] Mishra, S. Weighting method for bi-level linear fractional programming problems, Eur. J. Oper. Res. 183 (2007), 296–302.
[12] Pollak, E.G., Novaes, G.N. and Frankel, E.G. On the optimization and integration of shipping ventures, Int. Shipbuild. Prog. 12 (131) (1965), 267–281.
[13] Pramanik, S. and Banerjee, D. Chance Constrained Multi-Objective Linear Plus Linear Fractional Programming Problem Based on Taylor’s Series Approximation, Int. J. Eng. Res. Develop. 1(3) (2012), 55–62.
[14] Stancu-Minasian, I.M. Fractional programming: theory, methods and applications, Vol. 409. Springer Science & Business Media, 2012.
[15] Toksari, D.M. Taylor series approach for bi-level linear fractional programming, Selçuk J Appl Math, 11 (2010), 63–69.
[16] Wang, G., Ziyou G. and Zhongping W. A global optimization algorithm for solving the bi-level linear fractional programming problem, Computers and Industrial Engineering, 63 (2012), 428–432.
[17] Wen, U.-P. and Bialas, W. F. The hybrid algorithm for solving the three-level linear programming problem, Comput. Oper. Res. 13 (1986), 367–377.
[18] White, D.J. Penalty function approach to linear trilevel programming, J. Optim. Theory Appl. 93 (1997), 183–197.