Bilevel linear programming with ambiguous objective function of the follower

Bilevel linear optimization problems are the linear optimization problems with two sequential decision steps of the leader and the follower. In this paper, we focus on the ambiguity of coefficients of the follower in his objective function that hinder the leader from exactly calculating the rational response of the follower. Under the assumption that the follower’s possible range of the ambiguous coefficient vector is known as a certain convex polytope, the leader can deduce the possible set of rational responses of the follower. The leader further assumes that the follower’s response is the worst-case scenario to his objective function, and then makes a decision according to the maximin criteria. We thus formulate the bilevel linear optimization problem with ambiguous objective function of the follower as a special kind of three-level programming problem. In our formulation, we show that the optimal solution locates on the extreme point and propose a solution method based on the enumeration of possible rational responses of the follower. A numerical example is used to illustrate our proposed computational method.