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 set on a transportation network while considering the optimal travel paths chosen by users. The hierarchical relationship between the network manager (upper-level decision-maker) and the users (lower-level decision-makers) is highlighted, drawing parallels to Stackelberg games in economics. The paper then introduces the general formulation of bilevel programming problems (BLPPs), which involve two levels of optimization: the upper-level problem involves the choice of parameters, while the lower-level problem is a nonlinear program that depends on these parameters. Key concepts such as the induced region, rational response, and optimistic and pessimistic solutions are discussed. The paper also reviews various applications of bilevel programming, including revenue management, congestion management, origin-destination matrix estimation, hazardous materials management, network design, energy sector optimization, engineering problems, principal-agent problems, and Stackelberg-Nash games. A survey of existing methods for solving bilevel programming problems is provided, covering linear and nonlinear cases. Techniques discussed include extreme-point approaches, branch-and-bound, complementary pivoting, descent methods, penalty function methods, and trust-region methods. Each method is evaluated based on its effectiveness and computational complexity. Finally, the paper explores the connection between bilevel programming and Mathematical Programs with Equilibrium Constraints (MPECs), noting that MPECs can be seen as a special case of bilevel programming when the lower-level problem is a variational inequality. The relationship between the two classes of problems is illustrated through specific examples, and recent developments in MPECs are mentioned. The paper concludes by discussing future research perspectives, emphasizing the need for further development of tools that exploit the combinatorial structure of bilevel problems, particularly for nonlinear instances.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 set on a transportation network while considering the optimal travel paths chosen by users. The hierarchical relationship between the network manager (upper-level decision-maker) and the users (lower-level decision-makers) is highlighted, drawing parallels to Stackelberg games in economics. The paper then introduces the general formulation of bilevel programming problems (BLPPs), which involve two levels of optimization: the upper-level problem involves the choice of parameters, while the lower-level problem is a nonlinear program that depends on these parameters. Key concepts such as the induced region, rational response, and optimistic and pessimistic solutions are discussed. The paper also reviews various applications of bilevel programming, including revenue management, congestion management, origin-destination matrix estimation, hazardous materials management, network design, energy sector optimization, engineering problems, principal-agent problems, and Stackelberg-Nash games. A survey of existing methods for solving bilevel programming problems is provided, covering linear and nonlinear cases. Techniques discussed include extreme-point approaches, branch-and-bound, complementary pivoting, descent methods, penalty function methods, and trust-region methods. Each method is evaluated based on its effectiveness and computational complexity. Finally, the paper explores the connection between bilevel programming and Mathematical Programs with Equilibrium Constraints (MPECs), noting that MPECs can be seen as a special case of bilevel programming when the lower-level problem is a variational inequality. The relationship between the two classes of problems is illustrated through specific examples, and recent developments in MPECs are mentioned. The paper concludes by discussing future research perspectives, emphasizing the need for further development of tools that exploit the combinatorial structure of bilevel problems, particularly for nonlinear instances.
Reach us at info@study.space