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

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.

کلیدواژه ها:

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