The Improvement of Optimality Test over Possible Reaction Set in Bilevel Linear Optimization with Ambiguous Objective Function of the Follower

Verifying a rational response is the most crucial step in searching for an optimal solution in bilevel linear programming. Such verification is even difficult in a model with ambiguous objective function of the follower who reacts rationally to a leader’s decision. In our model, we assume that the ambiguous coefficient vector of follower lies in a convex polytope and we formulate bilevel linear programming with the ambiguous objective function of the follower as a special three-level programming problem. We use the k -th best method that sequentially enumerates a solution and examine whether it is the best of all possible reactions. The optimality test process over possible reactions in lower-level problems usually encounters degenerate bases that become obstacles to verifying the optimality of an enumerated solution efficiently. To accelerate optimality verification, we propose search strategies and the evaluation of basic possible reactions adjacent to a degenerate basic solution. We introduce these methods in both local and global optimality testing, confirming the effectiveness of our proposed methods in numerical experiments.