Bilevel linear programs: generalized models for the lower-level reaction set and related problems

Bilevel programming forms a class of optimization problems that model hierarchical relation between two independent decision-makers, namely, the leader and the follower, in a collaborative or conflicting setting. Decisions in this hierarchical structure are made sequentially where the leader decides first and then the follower responds by solving an optimization problem, which is parameterized by the leader's decisions. The follower's reaction, in return, affects the leader's decision, usually through shaping the leader's objective function. Thus, the leader should take into account the follower's response in the decision-making process. A key assumption in bilevel optimization is that both participants, the leader and the follower, solve their problems optimally. However, this assumption does not hold in many important application areas because: (i) there is no known efficient method to solve the lower-level formulation to optimality; (ii) the follower either is not sufficiently sophisticated or does not have the required computational resources to find an optimal solution to the lower-level problem in a timely manner; or (iii) the follower might be willing to give up a portion of his/her optimal objective function value in order to inflict more damage to the leader. This dissertation mainly focuses on developing approaches to model such situations in which the follower does not necessarily return an optimal solution of the lower-level problem as a response to the leader's action. That is, we assume that the follower's reaction set may include both exact and inexact solutions of the lower-level problem. Therefore, we study a generalized class of the follower's reaction sets. This is arguably the case in many application areas in practice, thus our approach contributes to closing the gap between the theory and practice in the bilevel optimization area. In addition, we develop a method to solve bilevel problems through single-level reformulations under the assumption that the lower-level problem is a linear program. The most common technique for such transformations is to replace the lower-level linear optimization problem by its KKT optimality conditions. We propose an alternative technique for a broad class of bilevel linear integer problems, based on the strong duality property of linear programs and compare its performance against the current methods. Finally, we explore bilevel models in an application setting of the pediatric vaccine pricing problem