bilevel

Bilevel refers to a class of optimization problems that involve two levels of decision making arranged hierarchically. The upper-level problem (the leader) chooses decisions while anticipating the optimal response of a lower-level problem (the follower), whose feasible set and objectives depend on the upper-level decisions. The interaction is inherently hierarchical: the outcome of the upper level depends on how the lower level reacts, and the upper level optimizes with that reaction in mind.

A canonical form is min F(x,y) subject to x in X, y in argmin_y { f(x,y) : Ay ≤ b }. Here x denotes upper-level variables, y lower-level variables, F is the upper-level objective, and f is the lower-level objective. X and Y define feasibility for the respective levels. In some models the two levels share decision variables or there are multiple lower-level problems.

Bilevel optimization is generally nonconvex and computationally hard, often NP-hard. Even simple linear upper and lower problems can be transformed into large mixed-integer programs. Special cases with convex lower levels admit reformulations using the Karush-Kuhn-Tucker conditions, producing mathematical programs with complementarity constraints (MPCCs). Other approaches include value-function methods, decomposition, outer-approximation, and global optimization techniques.

Applications span economics, engineering, and management. Notable examples include Stackelberg competition in game theory, energy market and power systems planning, transportation and network design, facility location, and pricing or procurement problems where a leader’s decision shapes the follower’s optimal response.

Related concepts include mathematical programs with equilibrium constraints (MPEC), bilevel multiobjective optimization, and stochastic bilevel problems.