9 Multilevel Optimisation
311
• Objectives: F is the leader’s (upper level) objective functions. f is the follower’s
(lower level) objective functions.
• Constraints: G k , k = 1, . . . , K are the leader’s (upper level) constraint
functions. g j , j = 1, . . . , J are the follower’s (lower level) constraint functions.
• Lower level feasible region: Ω : X U ⇒ X L , Ω(x u ) = {x l : g j (x u , x l ) ≤
0 ∀ j } represents the lower level feasible region for any given upper level
decision vector.
• Constraint region (relaxed feasible set): Φ = {(x u , x l ) : G k (x u , x l ) ≤ 0 ∀ k,
g j (x u , x l ) ≤ 0 ∀ j } represents the region satisfying both upper and lower level
constraints.
• Lower level/rational reaction set: Ψ : X U ⇒ X L ,
Ψ (x u ) = {x l : x l ∈ arg min
x l ∈X L
f (x u , x l ) : x l ∈ Ω(x u )},
represents the lower level optimal solution(s) for an upper level decision vector.
• Inducible region (feasible set):
I = {(x u , x l ) : (x u , x l ) ∈ G k (x u , x l ) ≤ 0, x l ∈ Ψ (x u )}
represents the set of upper level decision vectors and corresponding lower level
optimal solution(s) belonging to feasible constraint region.
• Choice function: ψ : X U → X L , ψ(x u ) represents the solution chosen by the
follower for any upper level decision vector. It becomes important in case of
multiple lower level optimal solutions.
• Optimal solution: A solution (x ∗
u , x ∗
l ) ∈ I is an optimal solution if ∀(x u , x l ) ∈
I, F (x ∗
u , x ∗
l ) ≤ F (x u , x l ).
A general sketch of the bilevel problem, inspired by [2], can be seen in Fig. 9.1, in
which the variable spaces of upper and lower levels are illustrated. For one decision
variable of the upper level, one lower level optimal solution is represented.
Bilevel optimisation problems can be also interpreted as non-cooperative static
Stackelberg game, as was first introduced by von Stackelberg in 1934 in the context
of unbalanced economic markets [15]. A bilevel problem is considered a game
where two decision makers follow a hierarchy. The upper and the lower levels
are termed as the leader and the follower, respectively. The leader is the first to
perform an optimisation step (decision) for his/her objective function. The follower
reacts having full knowledge of the leader’s choice. The follower’s decision, though,
affects the leader’s decision in an implicit manner, since it changes some of the
variables used by the leader [16, 17].
The main characteristic of the bilevel optimisation problem is its nested nature.
Hansel et al. have proved that bilevel programming is strongly NP-hard [18]. Moreover, bilevel optimisation problems are typically non-convex and disconnected. In
general, solving an optimisation problem produces one or more feasible solutions.
In the case that at the lower level there are multiple global optimal solutions,
311
• Objectives: F is the leader’s (upper level) objective functions. f is the follower’s
(lower level) objective functions.
• Constraints: G k , k = 1, . . . , K are the leader’s (upper level) constraint
functions. g j , j = 1, . . . , J are the follower’s (lower level) constraint functions.
• Lower level feasible region: Ω : X U ⇒ X L , Ω(x u ) = {x l : g j (x u , x l ) ≤
0 ∀ j } represents the lower level feasible region for any given upper level
decision vector.
• Constraint region (relaxed feasible set): Φ = {(x u , x l ) : G k (x u , x l ) ≤ 0 ∀ k,
g j (x u , x l ) ≤ 0 ∀ j } represents the region satisfying both upper and lower level
constraints.
• Lower level/rational reaction set: Ψ : X U ⇒ X L ,
Ψ (x u ) = {x l : x l ∈ arg min
x l ∈X L
f (x u , x l ) : x l ∈ Ω(x u )},
represents the lower level optimal solution(s) for an upper level decision vector.
• Inducible region (feasible set):
I = {(x u , x l ) : (x u , x l ) ∈ G k (x u , x l ) ≤ 0, x l ∈ Ψ (x u )}
represents the set of upper level decision vectors and corresponding lower level
optimal solution(s) belonging to feasible constraint region.
• Choice function: ψ : X U → X L , ψ(x u ) represents the solution chosen by the
follower for any upper level decision vector. It becomes important in case of
multiple lower level optimal solutions.
• Optimal solution: A solution (x ∗
u , x ∗
l ) ∈ I is an optimal solution if ∀(x u , x l ) ∈
I, F (x ∗
u , x ∗
l ) ≤ F (x u , x l ).
A general sketch of the bilevel problem, inspired by [2], can be seen in Fig. 9.1, in
which the variable spaces of upper and lower levels are illustrated. For one decision
variable of the upper level, one lower level optimal solution is represented.
Bilevel optimisation problems can be also interpreted as non-cooperative static
Stackelberg game, as was first introduced by von Stackelberg in 1934 in the context
of unbalanced economic markets [15]. A bilevel problem is considered a game
where two decision makers follow a hierarchy. The upper and the lower levels
are termed as the leader and the follower, respectively. The leader is the first to
perform an optimisation step (decision) for his/her objective function. The follower
reacts having full knowledge of the leader’s choice. The follower’s decision, though,
affects the leader’s decision in an implicit manner, since it changes some of the
variables used by the leader [16, 17].
The main characteristic of the bilevel optimisation problem is its nested nature.
Hansel et al. have proved that bilevel programming is strongly NP-hard [18]. Moreover, bilevel optimisation problems are typically non-convex and disconnected. In
general, solving an optimisation problem produces one or more feasible solutions.
In the case that at the lower level there are multiple global optimal solutions,