An overview of bilevel optimization

An overview of bilevel optimization

20 April 2007 | Benoît Colson · Patrice Marcotte · Gilles Savard
This paper provides an overview of bilevel optimization, a branch of mathematical programming with both practical and theoretical significance. It begins with a simple example of a toll-setting problem, where the goal is to maximize revenue from tolls on a transportation network while considering users' travel cost minimization. The problem is formulated as a bilevel optimization problem, where the upper-level problem involves setting tolls, and the lower-level problem involves users' travel decisions. The hierarchical relationship between the two levels is central to bilevel programming, which is closely related to Stackelberg games in economics. The general formulation of a bilevel programming problem (BLPP) is presented, with the upper-level objective function and constraints, and the lower-level objective function and constraints. The paper discusses the properties of bilevel programs, noting that they are generally non-convex and non-differentiable, making them computationally challenging. It also introduces the concepts of optimistic and pessimistic solutions, which reflect different assumptions about the follower's behavior. The paper reviews various applications of bilevel programming, including revenue management, congestion management, origin-destination matrix estimation, hazardous materials management, network design, energy sector, engineering problems, and the principal-agent problem. It also discusses the relationship between bilevel programming and mathematical programs with equilibrium constraints (MPECs), which are closely related and often used interchangeably. The paper surveys existing methods for solving bilevel programs, including extreme-point approaches, branch-and-bound, complementary pivoting, descent methods, penalty function methods, and trust-region methods. These methods are discussed in the context of their applicability to different types of bilevel programs, such as linear, nonlinear, and convex quadratic programs. Finally, the paper concludes with a discussion of perspectives and challenges in the field of bilevel programming, highlighting the need for further research on nonlinear bilevel problems and the development of efficient solution methods. It also notes the importance of developing suitable modeling languages and test problems to advance the numerical solution of bilevel programming problems.This paper provides an overview of bilevel optimization, a branch of mathematical programming with both practical and theoretical significance. It begins with a simple example of a toll-setting problem, where the goal is to maximize revenue from tolls on a transportation network while considering users' travel cost minimization. The problem is formulated as a bilevel optimization problem, where the upper-level problem involves setting tolls, and the lower-level problem involves users' travel decisions. The hierarchical relationship between the two levels is central to bilevel programming, which is closely related to Stackelberg games in economics. The general formulation of a bilevel programming problem (BLPP) is presented, with the upper-level objective function and constraints, and the lower-level objective function and constraints. The paper discusses the properties of bilevel programs, noting that they are generally non-convex and non-differentiable, making them computationally challenging. It also introduces the concepts of optimistic and pessimistic solutions, which reflect different assumptions about the follower's behavior. The paper reviews various applications of bilevel programming, including revenue management, congestion management, origin-destination matrix estimation, hazardous materials management, network design, energy sector, engineering problems, and the principal-agent problem. It also discusses the relationship between bilevel programming and mathematical programs with equilibrium constraints (MPECs), which are closely related and often used interchangeably. The paper surveys existing methods for solving bilevel programs, including extreme-point approaches, branch-and-bound, complementary pivoting, descent methods, penalty function methods, and trust-region methods. These methods are discussed in the context of their applicability to different types of bilevel programs, such as linear, nonlinear, and convex quadratic programs. Finally, the paper concludes with a discussion of perspectives and challenges in the field of bilevel programming, highlighting the need for further research on nonlinear bilevel problems and the development of efficient solution methods. It also notes the importance of developing suitable modeling languages and test problems to advance the numerical solution of bilevel programming problems.
Reach us at info@study.space
[slides] An overview of bilevel optimization | StudySpace