PaperlayerView exact revision on arXiv

Source-linked AI summary

A Review on Bilevel Optimization: From Classical to Evolutionary Approaches and Applications

Ankur Sinha, Pekka Malo, Kalyanmoy Deb

arXiv:1705.06270v2math.OCcs.NE

TL;DR

Bilevel optimization addresses hierarchical problems in which an inner optimization constrains an outer one, but such problems are difficult and existing solution procedures are limited for complex cases. This paper reviews foundational concepts, classical and evolutionary methods, applications, and literature trends using automated text-analysis. The review reports that evolutionary methods grew to almost 10% of bilevel studies and highlights scalability challenges alongside opportunities for further development.

  • Problem

    Bilevel optimization is mathematically difficult, and established procedures are limited for complex nonlinear, discrete, and large-scale problems.

  • Method

    The paper comprehensively reviews bilevel theory, applications, classical and evolutionary solution strategies, and uses automated text-analysis of the literature.

  • Results

    Almost 10% of studies on bilevel optimization use evolutionary methods, with post-2000 growth fueled by application-oriented papers.

  • Takeaways & Limitations

    Evolutionary approaches offer scope for addressing bilevel difficulties such as discreteness and nondifferentiability, while coordinated research is needed for progress.

  • Takeaways & Limitations

    Evolutionary bilevel methods are often practically non-scalable because required lower-level optimization tasks can increase exponentially with upper-level variables.

Abstract

from arXiv · show

Bilevel optimization is defined as a mathematical program, where an optimization problem contains another optimization problem as a constraint. These problems have received significant attention from the mathematical programming community. Only limited work exists on bilevel problems using evolutionary computation techniques; however, recently there has been an increasing interest due to the proliferation of practical applications and the potential of evolutionary algorithms in tackling these problems. This paper provides a comprehensive review on bilevel optimization from the basic principles to solution strategies; both classical and evolutionary. A number of potential application problems are also discussed. To offer the readers insights on the prominent developments in the field of bilevel optimization, we have performed an automated text-analysis of an extended list of papers published on bilevel optimization to date. This paper should motivate evolutionary computation researchers to pay more attention to this practical yet challenging area.

I. INTRODUCTION

Bilevel optimization models hierarchical leader–follower decisions in which the lower-level optimization constrains the upper-level problem. This review surveys its theory, applications, classical and evolutionary solution methods, and literature trends.

  • Motivation: Bilevel problems represent hierarchical decisions where a leader’s outcome depends on a follower’s optimal response.Each level has its own objectives and constraints, and the follower responds to the leader’s decision.
  • Applications: These problems matter in public and private decision-making because conflicting objectives can produce large economic and environmental spillover effects.The paper illustrates this with fertilizer overuse that increases productivity but causes pollution.
  • Challenges: Bilevel optimization is difficult because hierarchical structure can create non-convexity and disconnectedness, while both solving and evaluating solutions are NP-hard.The paper states that bilevel programming is strongly NP-hard and that evaluating a solution for optimality is also NP-hard.
  • Solution approaches: Classical methods often fail on nonlinear or discrete real-world problems, motivating evolutionary approaches for this challenging optimization class.The review organizes prior work around theory, applications, and automated text-analysis of the bilevel literature.
  • General formulation: The lower-level optimization is a parametric constraint on the upper-level problem, so feasible solutions must be lower-level optimal and satisfy upper-level constraints.The upper-level decision acts as a parameter for the lower-level problem.

A. Optimistic Position

The optimistic formulation resolves multiple lower-level optima by assuming the follower selects the solution best for the leader. It is more tractable and has an existence guarantee under stated regularity conditions.

  • Optimistic position: In the optimistic position, the follower selects from multiple lower-level optima the solution that gives the leader the best upper-level objective value.This choice assumes some cooperation between the two players.
  • Tractability: The optimistic formulation is more tractable than the pessimistic formulation, so most studies address the optimistic version.The paper contrasts this tractability with the greater methodological difficulty of pessimistic bilevel programs.
  • Existence conditions: An optimistic bilevel optimum is guaranteed when the functions are sufficiently smooth, the feasible region is non-empty and compact, and Mangasarian-Fromowitz constraint qualification holds.The guarantee also requires the existence of a feasible solution.

B. Pessimistic Position

The pessimistic formulation models the leader’s worst-case response among multiple follower optima, making the problem less tractable and effectively three-level. Under stronger regularity assumptions, existence of a pessimistic optimum is guaranteed.

  • Pessimistic Position: In the pessimistic position, the leader selects the follower’s optimal response that gives the worst upper-level objective value.This formulation assumes no cooperation between the two levels.
  • Pessimistic Position: Pessimistic bilevel optimization is less tractable because each lower-level solution must be checked for the follower optimum worst for the leader.This tracking requirement effectively turns the problem into a three-level task.
  • Existence Conditions: The pessimistic formulation guarantees an optimum when the functions are sufficiently smooth, the constraint region is non-empty and compact, and the set-valued mapping Ψp is lower semi-continuous.These are stronger assumptions than those stated for the optimistic formulation.
  • Example: The Stackelberg competition example models firms choosing production levels sequentially, with the follower responding after observing the leader’s production.The firms maximize their respective profits under shared inverse-demand and convex quadratic cost assumptions.
  • Example: The two firms’ optimal production levels can be expressed analytically in terms of the model constants.The reduction uses lower-level first-order conditions followed by first-order conditions for the resulting reduced problem.

III. CLASSICAL APPROACHES

Classical bilevel approaches commonly rely on mathematically well-behaved problems and reduce convex lower-level programs using KKT conditions. The resulting single-level problems can nevertheless remain non-convex or mixed-integer and may require exponentially slow algorithms.

  • Classical Approaches: Classical bilevel research often assumes linear, quadratic, or convex functions together with continuous differentiability and lower semicontinuity.These assumptions reflect the difficulty of handling more general bilevel problems.
  • Single-level Reduction: When the lower-level problem is convex and regular, its KKT conditions replace the nested problem and produce a single-level constrained formulation.The reduction introduces Lagrangian and complementarity constraints.
  • Single-level Reduction: Lagrangian constraints can introduce non-convexity, while complementarity constraints make the single-level formulation a mixed integer program.These difficulties remain even when the original objectives and constraints satisfy suitable convexity assumptions.
  • Linear Problems: For linear bilevel problems, the single-level reduction becomes a mixed integer linear program solvable by methods including vertex enumeration and branch-and-bound.Branch-and-bound is exponentially slow in the number of integer variables but has also been applied to linear-quadratic and quadratic-quadratic cases.

B. Descent Methods

Descent methods seek upper-level improvement while preserving lower-level optimality, whereas evolutionary bilevel methods include nested and hybrid strategies. These approaches can handle difficult structures but often scale poorly because lower-level tasks multiply rapidly.

  • Descent Methods: A bilevel descent direction must reduce the upper-level objective while keeping the new point lower-level optimal.Because feasibility depends on lower-level optimality, finding such directions is challenging.
  • Descent Methods: Penalty methods replace the bilevel problem with a sequence of unconstrained problems by penalizing constraint violations.The penalty is zero at feasible points and positive for infeasible minimization points.
  • Nested Methods: Nested evolutionary algorithms solve a lower-level optimization problem for every upper-level candidate, making them computationally expensive for large-scale problems.Early approaches paired upper-level evolutionary algorithms with lower-level linear programming or Frank-Wolfe methods.
  • Nested Methods: Nested particle swarm optimization demonstrated effectiveness on small-variable test problems, but its computational expense was not reported.This limits assessment of its scalability from the cited study.
  • Nested Methods: A hybrid nested method reported generations and population sizes but did not explicitly report total lower-level function evaluations.The omitted evaluation count was presumably high.
  • Scalability: Most evolutionary bilevel approaches are practically non-scalable because increasing upper-level variables causes the number of lower-level tasks to grow exponentially.The difficulty is compounded when the lower-level problem itself is hard to solve repeatedly.

B. Single-level Reduction

Single-level reduction methods reformulate bilevel optimization through approximations or optimality conditions, but may require many evaluations and restrictive assumptions. Evolutionary approaches approximate reaction mappings or lower-level value functions to reduce lower-level optimization calls.

  • B. Single-level Reduction: KKT-based single-level reductions can handle some non-convex lower-level problems but may require about 100,000 function evaluations for 2 to 5 variable bilevel problems.These approaches depend on regularity conditions at the lower level.
  • B. Single-level Reduction: Metamodeling approximates expensive bilevel components using surrogate models trained from a small sample of actual evaluations.The review discusses approximating reaction sets, optimal value functions, or the bilevel problem itself.
  • B. Single-level Reduction: Approximating the reaction set Ψ can reduce bilevel optimization to a single-level problem when the mapping is known or estimated from selected upper-level members.The approximation is refined during evolutionary optimization, and poor approximations can trigger a nested approach.
  • B. Single-level Reduction: Approximating the single-valued optimal value function ϕ avoids the set-valued mapping complexities associated with reaction-set approximation.An approximate mapping is generated from evolutionary population members and refined every few generations.

3) Bypassing lower level problem:

Bypassing the lower-level problem constructs a single-level representation from the relationship between upper- and lower-level decisions, but the resulting landscape can be difficult. An additional auxiliary bilevel metamodel is proposed as a future direction, while discreteness can make inducible regions disconnected.

  • 3) Bypassing lower level problem:: A metamodel can bypass the lower-level problem by treating optimal lower-level decisions as a function of upper-level decisions.Training data can be obtained by solving a few lower-level problems for different upper-level decisions.
  • 3) Bypassing lower level problem:: The resulting single-level landscape may be highly non-convex, disconnected, and nondifferentiable, requiring advanced metamodeling for some bilevel problem classes.The lower-level problem is ignored only after constructing an approximation from sampled upper-level decisions.
  • 3) Bypassing lower level problem:: An auxiliary bilevel metamodel could formulate simpler subproblems around evolutionary population members and update them using faster specialized techniques.The review identifies this approach as an interesting direction for future research rather than an existing evolutionary algorithm.
  • 3) Bypassing lower level problem:: Discrete variables at either level can produce disconnected inducible regions across continuous-continuous, discrete-continuous, discrete-discrete, and continuous-discrete cases.The figure compares the four variable-type combinations.

A. Discrete Bilevel Optimization Survey

Discrete bilevel optimization spans linear, mixed-integer, combinatorial, and multiobjective settings with applications including network design, facility location, and supply chains. Existing methods face scalability and solution-existence challenges, especially under certain mixed continuous-discrete structures.

  • A. Discrete Bilevel Optimization Survey: Early discrete bilevel research analyzed optimal-solution properties and existence conditions for different discretizations of upper- and lower-level variables.The work focused on discrete linear bilevel programs.
  • A. Discrete Bilevel Optimization Survey: Compactness conditions guarantee optimal-solution existence for continuous-continuous, discrete-continuous, and discrete-discrete linear bilevel programs.These conditions are equivalent to the inducible region being non-empty in the cited cases.
  • A. Discrete Bilevel Optimization Survey: Continuous-discrete linear bilevel programs can have noncompact inducible regions and may lack an optimal solution even when the inducible region is non-empty.Existence conditions for this case are described as less straightforward.
  • A. Discrete Bilevel Optimization Survey: Mixed-integer and combinatorial bilevel programs arise in network design, facility location, hub-and-spoke networks, interdiction, protection, robust design, competition, and supply chain management.The survey also introduces multiobjective bilevel optimization for problems where either level may have multiple objectives.
  • A. Discrete Bilevel Optimization Survey: Existing discrete bilevel techniques do not scale well to larger variable counts, and evolutionary studies for mixed-integer bilevel problems remain limited.The review identifies evolutionary methods as potentially suitable for discreteness and nondifferentiability.

A. Optimistic vs Pessimistic

Multiobjective bilevel optimization distinguishes optimistic and pessimistic follower positions, producing different leader Pareto-optimal frontiers. A tax-policy example illustrates the trade-off between government revenue and environmental damage.

  • The follower’s Pareto-optimal solutions form a frontier for each leader decision, while the overall problem produces a leader Pareto-optimal frontier.Optimistic and pessimistic positions determine how follower solutions influence the leader’s frontier.
  • Optimistic positions allow the follower to select a Pareto-optimal solution most favorable to the leader, assuming indifference and cooperation.This assumption is considered less realistic when follower objectives are multiple.
  • Known follower value or choice functions define intermediate positions whose leader frontier lies between optimistic and pessimistic frontiers.Such knowledge can reduce the lower-level problem to a single-objective task.
  • Tax-policy example: In the tax-policy example, the government maximizes mining revenue while minimizing environmental harm caused by extraction.The mine responds at the lower level, making extraction a follower decision.
  • Tax-policy example: The mine’s profit combines price-based extraction revenue, extraction costs, and the tax imposed by the government.The model assumes a linear price function with a small slope and quadratic extraction costs.
  • Tax-policy example: With α = 100, β = 1, δ = 1, γ = 1, and φ = 0, varying government preference weight w generates the leader’s Pareto-optimal solutions.Weights 0.01 ≤ w ≤ 1 generate the plotted frontier, while w < 0.01 produces no lower-level production.

C. Multiobjective Bilevel Optimization Survey

Multiobjective bilevel optimization remains comparatively underdeveloped because its computational and decision-making structures are demanding. The reviewed applications span practical domains, while evolutionary methods use nested population-based strategies.

  • Multiobjective bilevel optimization has received limited attention because its computational and decision-making complexities are substantial.The literature is considerably larger for single-objective bilevel optimization.
  • Classical approaches: Classical methods have solved simple multiobjective bilevel problems but can require computationally demanding, non-scalable exhaustive search.Numerical optimization handles lower-level problems while adaptive exhaustive search handles the upper level.
  • Evolutionary approaches: Evolutionary studies have applied nested genetic algorithms and particle swarm optimization to transportation planning and chemical-system problems.These approaches place optimization procedures at both levels of the bilevel structure.
  • Decision making: Interactive optimistic methods can target the upper-level decision maker’s most preferred point instead of computing the entire Pareto frontier.The approach is motivated by the computational expense of multiobjective bilevel optimization.
  • Applications: Bilevel optimization appears in economics, transportation, engineering, and management, including toll setting and network design.Authorities act as leaders while network users act as followers in toll-setting problems.
  • Applications: Applications also include optimal design, defense, and machine-learning parameter tuning.Machine-learning parameter selection can be formulated bilevelly instead of using brute-force grid or random search.

VIII. INTEREST OVER TIME

Text analysis traces changing research interest in bilevel optimization from classical theory toward applications and evolutionary methods. Topic modeling identifies both established methodological themes and expanding application areas, while several unresolved directions remain.

  • The review analyzes SCOPUS publications over time and discovers themes using a non-parametric Bayesian topic-modeling approach.The analysis covers publication volume and thematic development.
  • Interest in bilevel programming grew slowly until the early 2000s before increasing significantly around the middle of the following decade.Evolutionary bilevel studies began in the mid-1990s and later approached 10% of bilevel studies.
  • Before 2000, publications focused mainly on solution methods and optimality conditions; after 2000, application-oriented research fueled growth.This marks a shift from methodological foundations toward practical uses.
  • Topic development: Classical methods and optimality conditions peaked during 1995–2000, while supply chain, electricity, telecommunications, facility location, railway, and machine-learning applications later expanded.Defense applications also became more prominent after 2000.
  • Topic development: Network design, optimal design, and business applications maintained high publication volumes without a clear temporal trend.The topic figures encode theme words, approximate paper volume, and publication counts over time.
  • Future directions: Future directions emphasize uncertainty handling, metamodeling, scalability, and distributed computing for large-scale bilevel problems.The review identifies these areas as insufficiently developed or promising for further work.
  • Future directions: Multiobjective bilevel decision interaction and uncertain preferences remain insufficiently studied, with existing approaches described as preliminary.Further theory and methods are needed for hierarchical decision behavior under preferential uncertainty.

C. Bilevel Optimization under Variable Uncertainty

Variable uncertainty makes bilevel optimization harder because nested tasks complicate the search for robust solutions. Existing ideas are preliminary, motivating algorithmic work on scalable and distributed solution methods.

  • Uncertain decision variables challenge deterministic optimization frameworks that may fail to find robust solutions near optimality.Nested optimization makes robust-solution search substantially harder than in single-level optimization.
  • Existing ideas for handling variable uncertainty remain preliminary, and algorithmic innovations needed for practitioner access are still missing.The paper identifies this as an unresolved research boundary.
  • Bilevel problems are already highly computationally intensive before uncertainty is introduced, motivating distributed computing for larger instances.Distributed platforms are presented as a possible direction for faster solution of large problems.
  • Evolutionary bilevel optimization remains a relatively young field with opportunities for computational and theoretical innovation.Growing algorithm availability is opening the field to more applied research.
Loading 1705.06270v2…