Bilevel Optimization: Applications, Models and Solution Approaches

Bilevel optimization is a difficult class of optimization problems, which contain an inner optimization problem as a constraint to an outer optimization problem. Such optimization problems are commonly referred to as Stackelberg games in the area of game theory, where a hierarchical interaction between a leader and a follower is modeled. This chapter presents several examples of bilevel optimization problems arising in various contexts, e.g., the product line selection problem and the shortest path interdiction problem. Depending on the context of the problem, the leader and the follower may have the same objective function but with conflicting objectives (max-min in the shortest path interdiction), or may have different objective functions (as in the product line selection problem). Under this hierarchical setting, the leader tries to optimize its own decision by taking into account the rational response of the follower. A bilevel optimization problem is NP-hard even in the simplest case in which the problems of the leader and the follower are both simple linear programs. This chapter discuses classical solution approaches that are based on the reformulation of the bilevel problem into a single level. It also discusses several alternate single-level reformulations for the application problems considered in this chapter.