Bilevel Optimization: Applications, Models and Solution Approaches

Bilevel optimization is a difficult class of optimization problems, which contains an inner optimization problem as a constraint in 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 their own decision by taking into account the rational response of the follower. Bilevel optimization problems are NP-hard even in the simplest case in which the problems of the leader and the follower are both linear programs. This chapter discusses classical solution approaches that are based on the reformulation of the bilevel problem into a single-level problem. It also discusses several alternate single-level reformulations for the application problems considered in this chapter.