9 Multilevel Optimisation
309
subject to
g 1 (x 1 , x 2 , . . . , x k ) ≤ 0
where P 2 solves
(P 2 ) min
x 2 ∈X 2
f 2 (x 1 , x 2 , . . . , x k )
subject to
g 2 (x 1 , x 2 , . . . , x k ) ≤ 0
. . .
. . .
where P k solves
(P k ) min
x k ∈X k
f k (x 1 , x 2 , . . . , x k )
subject to
g k (x 1 , x 2 , . . . , x k ) ≤ 0
where P 1 is called the first (upper) level problem and corresponds to the highest
level in the hierarchy; x 1 is the solution, composed of n 1 variables, of the first level
problem from the set of solutions X 1 ∈ R n 1 ; x 2 is the solution, composed of n 2
variables, of the second level problem from the set of solutions X 2 ∈ R n 2 ; and
x k is the solution, composed of n k variables, of the k-th level problem from set of
solutions X k ∈ R n k . At this level, the decision maker controls the decision variables
x 1 , and his/her objective is to minimise the function f 1 . Consequently, P k is the
k-th level problem, which corresponds to the lowest level in the hierarchy [13]. Let
us assume that each of the levels corresponds to a decision maker, which we call
player from now on. Each player has control over its own set of variables and aims
to optimise its own objective function f . Each objective function can also depend
on the variables of other players [14]. Variable value choices of each player should
be such that there exists a sequence of choices for the other, following players that
all satisfy their constraints. Players are playing in a hierarchical order, meaning the
first player (first level) chooses first and the k-th (last) player plays last.
Multilevel optimisation problem presents a nested formulation. Finding a polynomial algorithm, capable of obtaining the global optimum for even the simplest case
of linear optimisation problems with only two levels, is highly unlikely. For this
reason, we will refer to instances and solution algorithms of bilevel optimisation for
309
subject to
g 1 (x 1 , x 2 , . . . , x k ) ≤ 0
where P 2 solves
(P 2 ) min
x 2 ∈X 2
f 2 (x 1 , x 2 , . . . , x k )
subject to
g 2 (x 1 , x 2 , . . . , x k ) ≤ 0
. . .
. . .
where P k solves
(P k ) min
x k ∈X k
f k (x 1 , x 2 , . . . , x k )
subject to
g k (x 1 , x 2 , . . . , x k ) ≤ 0
where P 1 is called the first (upper) level problem and corresponds to the highest
level in the hierarchy; x 1 is the solution, composed of n 1 variables, of the first level
problem from the set of solutions X 1 ∈ R n 1 ; x 2 is the solution, composed of n 2
variables, of the second level problem from the set of solutions X 2 ∈ R n 2 ; and
x k is the solution, composed of n k variables, of the k-th level problem from set of
solutions X k ∈ R n k . At this level, the decision maker controls the decision variables
x 1 , and his/her objective is to minimise the function f 1 . Consequently, P k is the
k-th level problem, which corresponds to the lowest level in the hierarchy [13]. Let
us assume that each of the levels corresponds to a decision maker, which we call
player from now on. Each player has control over its own set of variables and aims
to optimise its own objective function f . Each objective function can also depend
on the variables of other players [14]. Variable value choices of each player should
be such that there exists a sequence of choices for the other, following players that
all satisfy their constraints. Players are playing in a hierarchical order, meaning the
first player (first level) chooses first and the k-th (last) player plays last.
Multilevel optimisation problem presents a nested formulation. Finding a polynomial algorithm, capable of obtaining the global optimum for even the simplest case
of linear optimisation problems with only two levels, is highly unlikely. For this
reason, we will refer to instances and solution algorithms of bilevel optimisation for