Bilevel Programs

Table of Contents

Bilevel programs are mathematical programs with optimization problems in their constraints. The main problem is called the upper-level problem or the leader and the nested problem is called the lower-level problem or the follower. A simple example is the bilevel programming problem that optimizes an upper-level objective over constraints that include a lower-level optimization problem. A famous example from economics is the Stackelberg game, where there is one leader and many followers. Bilevel programming is used in many areas, for example the design of optimal tax instruments: the tax instrument is modeled in the upper level and the clearing market is modeled in the lower level.

In this section we first present a mathematical formulation of a bilevel program with one follower and introduce the respective EMP annotations. Then we present three examples: a simple first example, an example with a variational inequality as the lower-level problem and an example with multiple followers that form a Nash equilibrium. We conclude the section with a short discussion of the general EMP syntax for bilevel programs.

Bilevel Programs: Mathematical Formulation

A bilevel program with one leader and one follower can be expressed as follows:

\begin{equation} \tag {23} \begin{array}{llll} \textrm{Min}_{x \in X, y} & f(x,y) \\ \textrm{s.t.} & h(x,y) \leq 0 \\ & y \quad \textrm{solves} & \textrm{Min}_y & g(x,y) \\ & & \textrm{s.t} & k(x,y) \leq 0,\\ \end{array} \end{equation}

where

  • \(x \in \mathbb{R}^n\) are the upper-level variables,
  • \(y \in \mathbb{R}^m\) are the lower-level variables,
  • \(f: \mathbb{R}^n \times \mathbb{R}^m \rightarrow \mathbb{R} \) is the upper-level objective function,
  • \(g: \mathbb{R}^n \times \mathbb{R}^m \rightarrow \mathbb{R} \) is the lower-level objective function,
  • \(h: \mathbb{R}^n \times \mathbb{R}^m \rightarrow \mathbb{R}^u \) are the upper-level constraints, and
  • \(k: \mathbb{R}^n \times \mathbb{R}^m \rightarrow \mathbb{R}^l \) are the lower-level constraints.

Note that the upper-level constraints do not bind the lower-level decision maker.

This problem can be implemented with EMP as follows:

Sets  i, j ;
Variables x(i), objout, y(i), objin;
Equations deff(x,y), defg(x,y), defh(x,y), defk(x,y);

* Definitions of equations are omitted

Model bilevel / deff, defg, defH, defw /;

$onecho > "%emp.info%"
bilevel x
min objin y defg defk
$offecho

solve bilevel using EMP minimizing objout ;

Note that the variables and equations of the program are defined in GAMS in the usual way. The special bilevel structure of the model is specified in the EMP annotations. The EMP keyword bilevel indicates that this is a bilevel problem. The name and direction of the leader's objective variable is taken from the solve statement, but the other variables owned by the leader are listed after the bilevel keyword. The lower-level problem is specified next via the EMP keyword min, followed by the follower's objective variable objin. The other variables and the equations of the lower-level problem are listed next. Observe that this is exactly the same syntax that we introduced above for specifying optimization problems in the context of equilibrium problems.

The EMP tool reformulates the bilevel problem as a Mathematical Program with Equilibrium Constraints (MPEC) and passes this on to a subsolver (e.g. NLPEC or KNITRO). The reformulation is obtained by replacing the lower-level optimization problem by its KKT conditions, resulting in the following problem:

\begin{equation} \tag {24} \begin{array}{llll} \textrm{Min}_{x \in X, y, \lambda} & f(x,y) \\ \textrm{s.t.} & h(x,y) \leq 0 \\ & k(x,y) \leq 0\\ & \lambda_i \leq 0, & i = 1, \dots, l \\ & \lambda_i k_i(x,y) =0, & i=1, \dots , l \\ & \bigtriangledown_y \mathcal{L}(x,y,\lambda) = 0, \\ \end{array} \end{equation}

where

\begin{equation} \mathcal{L}(x,y,\lambda) = g(x,y) + \sum_{i=1}^l \lambda_i k_i(x,y) \end{equation}

is the Lagrangian function associated with the lower-level problem.

Note, however, that this reformulation is potentially problematic. KKT conditions require theoretical assumptions (like convexity) to be necessary and sufficient for local optimality. There may be cases where the lower lovel problem has multiple local solutions, but the modeler is interested in the global solution. Hence the reformulation above may not lead to the global solution, even if a global subsolver is used within the solver NLPEC.

Observe that there are two variations to problem (23) that the EMP framework is equipped to handle: the lower-level problem may be a variational inequality instead of an optimization problem, and there may be multiple lower-level problems (optimizing and/or VI) each behaving in a Nash manner. Examples follow in sections Bilevel Programs with EMP: A VI as Follower and Bilevel Programs with EMP: Multiple Followers respectively.

Bilevel Programs with EMP: A Simple Example

To illustrate, we use model [BARD851] from the GAMS EMP Library. Mathematically, the problem is

\begin{equation} \tag {25} \begin{array}{lllll} \textrm{Min}_{x, y_1, y_2} & (x-1)^2 + 2y_1^2 - 2x \\ & x \geq 0\\ \textrm{s.t.} & (y_1, y_2) \quad \textrm{solve} & \textrm{Min}_{y_1,y_2} & (2y_1 - 4)^2 + (2y_2 -1 )^2 + xy_1 \\ & & \textrm{s.t} & \quad 4x + 5y_1 + 4x_2 \leq 12\\ & & & \, -4x + 5y_1 + 4x_2 \leq -4 \\ & & & \quad 4x - 4y_1 + 5x_2 \leq \; \; 4 \\ & & & \, -4x + 4y_1 + 4x_2 \leq -4 \\ & & & \quad y_1, y_2 \geq 0 \end{array} \end{equation}

Note that this problem does not have any upper-level constraints. The GAMS code follows.

Positive Variables x, y1, y2;
Variables          objout, objin;

Equations defout, defin, e1, e2, e3, e4;

defout..  objout =e= sqr(x-1) + 2*sqr(y1) - 2*x;
defin..   objin  =e= sqr(2*y1-4) + sqr(2*y2-1) + x*y1;

e1..      4*x + 5*y1 + 4*y2 =l= 12;
e2..    - 4*x - 5*y1 + 4*y2 =l= -4;
e3..      4*x - 4*y1 + 5*y2 =l=  4;
e4..    - 4*x + 4*y1 + 5*y2 =l=  4;

Model bard / all /;

$echo bilevel x min objin y1 y2 defin e1 e2 e3 e4 > "%emp.info%"

solve bard use emp min objout;

The leader minimizes the variable objout, as specified in the solve statement. The EMP annotations specify the rest of the bilevel structure: the variable x belongs to the upper-level problem, and there is one lower-level agent or problem with objin minimized over the variables y1 and y2 subject to the constraints or equations defin, e1, e2, e3 and e4.

Alternatively, we could write the EMP annotations as:

$echo bilevel x min objin * defin e1 e2 e3 e4 > "%emp.info%"

Here the lower-level variables are not listed: instead, the '*' indicates that all variables in the GAMS model not explicitly assigned to any agent are to be assigned to the follower.

The EMP Summary produced by JAMS gives the number of followers in the bilevel program:

--- EMP Summary
    Bilevel Followers   = 1

The GAMS EMP Library contains other bilevel examples, including several models bard*, the engineering models [CCMG74] and [CCMG153], and the simple nonconvex model [MIRRLESS]. The models [JOINTC1] and [JOINTC2] illustrate the interplay of the decision variables of the upper-level and lower-level problems.

Bilevel Programs with EMP: A VI as Follower

If the lower-level problem is a variational inequality, problem (23) will take the following form:

\begin{equation} \tag {26} \begin{array}{llll} \textrm{Min}_{x, y} & f(x,y) \\ \textrm{s.t.} & h(x,y) \leq 0 \\ & y \; \textrm{solves } \; \; VI(F,K(x)), \\ \end{array} \end{equation}

where

  • \(x \in \mathbb{R}^n\) are upper-level variables and \(y \in \mathbb{R}^m\) are lower-level variables, and
  • \( K(x) \subseteq \mathbb{R}^m\) is a closed convex set, parametrized by \(x\).

Consider the following simple example adapted from [MULTMPEC]:

\begin{equation} \tag {27} \begin{array}{llll} \textrm{Min}_{w, z} & z \\ \textrm{s.t.} & e^z + w = 2 \\ & z \geq 1 \\ & w \; \textrm{solves the} \; VI(F,K), \; \textrm{where} \; K = \mathbb{R} \; \textrm{and} \; F = w + z + 3 \\ \end{array} \end{equation}

This bilevel problem can be modeled with EMP as follows:

variables w, z;
equations h, F;

h..  exp(z) + w =e= 2;
F..  w + z =n= -3;

z.lo = 1;

model bpvi / h, F /;

$onecho > %emp.info%
bilevel z
vi F w
$offecho

solve bpvi using emp min z;

Note that in the EMP annotations the lower-level problem is specified as a VI with the VI function F and the corresponding variable w: for details see section EMP Syntax for Variational Inequalities. The count of VI functions is indicated in the EMP Summary:

--- EMP Summary
    ...
    VI Functions        = 1
    ...
    Bilevel Followers   = 1

Bilevel Programs with EMP: Multiple Followers

The EMP framework allows multiple followers in a bilevel program. Taking the leader decisions as fixed, these followers behave as the agents in a Nash equilibrium. Consider the engineering example [CCMG71] from the GAMS EMP Library. In this bilevel program there are two followers, both solving minimization problems, specified in the EMP annotations as follows:

...
$onecho > %emp.info%
bilevel x1 x2 x3 x4
 min h1 u1 u2 u3 u4 defh1 e1
 min h2 v1 v2 v3 v4 defh2 e2
$offecho
...

The variables x1, x2, x3 and x4 are owned or controlled by the leader. The first follower minimizes the variable h1 over the variables u1, u2, u3 and u4 subject to the constraint/equation e1. The second follower is defined in a similar way. More details on how to specify optimization subproblems in the EMP annotations are given in section EMP Syntax for Equilibrium Problems.

Observe that in the EMP annotations of the actual model [CCMG71] the following shorthand notation is used:

...
$onecho > %emp.info%
bilevel x1 x2 x3 x4
min h1 * defh1 e1
min h2 * defh2 e2
$offecho
...

The symbol '*' in the problem of the first follower indicates that this agent will optimize over all variables appearing in equations defh1 and e1 (i.e. the equations it controls) that are not claimed by another agent. In this case, the respective variables are u1, u2, u3 and u4. N.B.: in this example, if a variable appears in the equations for both followers the problem structure is not well defined and an error will result. To avoid confusion and promote clarity, we recommend that modelers explicitly list all the variables in each agent's problem, as shown in the first version of the EMP annotations above.

The number of followers is indicated in the EMP Summary:

--- EMP Summary
    ...
    Bilevel Followers   = 2

The GAMS EMP Library contains several bilevel problems with several followers, e.g. the well-known transportation model with a variable demand function cast as a bilevel problem with one optimization follower and one VI follower [TRANSBP], a simple example with two VI followers [MULTMPEC], and the spatial equilibrium Stackelberg model [HARK-STACK].

EMP Syntax for Bilevel Programs

The general syntax that EMP provides to specify bilevel programs in the EMP annotations file emp.info is as follows:

Bilevel {var}
{MAX|MIN obj {var|*} {[-] equ}}
{VI {var|*} {[-] equ var} {[-] equ}}
{Dualvar {var [-] equ}}

A bilevel program is declared with the EMP keyword bilevel, followed by the decision variables of the upper-level problem. The other specifications refer to the lower-level problems. These lower-level followers are optional, but at least one follower has to be specified. Optimization problems are defined using the EMP keyword max or min followed by the objective variable obj and the decision variables and the equations that implement the constraints of the problem. Variational inequalities are introduced with the EMP keyword vi: details of the specification are given in section EMP Syntax for Variational Inequalities. The dualvar keyword is used in the same way as it is for equilibrium problems.

Note
While the EMP framework allows the symbol '*' to be used to specify an automatically-created list of variables, we recommend against using the '*' in the annotations file. Instead, list all variables explicitly to make the structure of the model clear and unambiguous to both human and machine readers of the EMP info file.