represent the inequality constraint functions at the upper and lower levels respectively.
However, it is usually worthwhile to treat equality constraints separately, to deal with them more efficiently in a dedicated way; in the representation above, they have been omitted for brevity.
Bilevel optimization was first realized in the field of game theory by a German economist Heinrich Freiherr von Stackelberg who published Market Structure and Equilibrium (Marktform und Gleichgewicht) in 1934 that described this hierarchical problem.
This kind of a hierarchical game is asymmetric in nature, where the leader and the follower cannot be interchanged.
The leader knows ex ante that the follower observes its actions before responding in an optimal manner.
Some of the practical bilevel problems studied in the literature are briefly discussed.
[4] In the field of transportation, bilevel optimization commonly appears in the toll-setting problem.
The government wants to maximize its revenues by choosing the optimal toll setting for the highways.
However, the government can maximize its revenues only by taking the highway users' problem into account.
The upper level consists of the government’s objectives and constraints, and the lower level consists of the highway users' objectives and constraints for a given tax structure.
It is noteworthy that the government will be able to identify the revenue generated by a particular tax structure only by solving the lower level problem that determines to what extent the highways are used.
However, for any given set of upper level variables, the state variables (displacement, stresses and contact forces) can only be figured out by solving the potential energy minimization problem that appears as an equilibrium satisfaction constraint or lower level minimization task to the upper level problem.
Bilevel optimization has a number of applications in defense, like strategic offensive and defensive force structure design, strategic bomber force structure, and allocation of tactical aircraft to missions.
The second level reflects employees goal to minimize the gap between desired salary and a preferred work plan.
The bilevel model provides an exact solution based on a mixed integer formulation and present a computational analysis based on changing employees behaviors in response to the firm’s strategy, thus demonstrate how the problem’s parameters influence the decision policy.
These annotations facilitate the automatic reformulation to Mathematical Programs with Equilibrium Constraints (MPECs) for which mature solver technology exists.
This yields a single-level mathematical program with complementarity constraints, i.e., MPECs.
[6] For complex bilevel problems, classical methods may fail due to difficulties like non-linearity, discreteness, non-differentiability, non-convexity etc.
Among them, evolutionary methods, though computationally demanding, often constitute an alternative tool to offset some of these difficulties encountered by exact methods, albeit without offering any optimality guarantee on the solutions they produce.
represent the inequality constraint functions at the upper and lower levels respectively.
Equality constraints may also be present in a bilevel program, but they have been omitted for brevity.