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

Iranian Journal of Numerical Analysis and Optimization

مقالات آماده انتشار، اصلاح شده برای چاپ، انتشار آنلاین از تاریخ 23 مرداد 1404   

نوع مقاله: Research Article

شناسه دیجیتال (DOI): 10.22067/ijnao.2025.93619.1651

نویسندگان

Flagot Yohannes Feleke¹؛ Semu Mitiku Kassa^{* 2}

¹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.

چکیده

In many practical applications, some problems are being modeled as bi-level 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, however, 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 can not 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 k-th 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.

کلیدواژه‌ها

Bi-level programming problem؛ Bi-level linear fractional programming problem؛ Multi-valued rational reaction map؛ $k$-th best method؛ Branch-and-bound scheme