308
M. Antoniou and P. Korošec
The first formulation of bilevel problem was documented in 1973 by Bracken
and McGill [3], and the definition of bilevel and multilevel programming was
used for the first time some years later by Candler and Norton in [4]. Since
then, both classical and evolutionary optimisation communities have studied bilevel
optimisation problems. These problems are intrinsically difficult to solve, so it is no
surprise that most of the proposed solution methods are either computationally very
expensive or applicable only to the simplest cases of bilevel optimisation problems
that have some nice mathematical properties [5].
One can find in literature the usage of multilevel optimisation referring to an
optimisation approach. While multilevel optimisation problems present a hierarchy
in the way the decision-solutions are taken, the multilevel paradigm is used to
describe the approach in optimisation that presents a hierarchy in the procedure
of the optimisation. The most common practice of solving an optimisation problem
is computing/evaluating solutions in some iterative process. In many applications,
such as in engineering, FEM or CFD computations, this can become really
expensive in terms of computational time. With the multilevel approach, one targets
into the minimisation of the expensive evaluations, by allowing for less accurate
computing by using computationally cheaper models of the problem or by reducing
solutions search space that needs to be explored. Both approaches heavily depend on
managing the balance between accuracy and computational time, so the best results
are achieved in a shorter time. The general multilevel strategy can be found in the
literature with several names and definitions. Though there are some differences in a
couple of aspects of each word, the main idea of the hierarchical method is the same.
Therefore, we can say that multilevel can be also found as multi-fidelity, multi-scale,
multi-grid or multistage optimisation approaches. Much more on this topic a reader
can find in [6–12].
In the following sections, we will focus only on multilevel and bilevel problems
by giving definitions, presenting a simple example of a linear bilevel optimisation
and its comparison to biobjective optimisation. Also, special cases of bilevel
problems are shown, providing an idea to the reader on how multilevel problems can
be found and/or formulated in different applications. Moreover, the main solution
algorithms with a special reference to metaheuristic solution methods found in the
literature are presented. The chapter ends by giving some examples of applications
solved as bilevel optimisation problems.
9.2 Multilevel Optimisation Problem
In the following of the chapter, we will consider minimisation problems without the
loss of generality since min = −max. The general multilevel optimisation problem
(P ) can be formulated as follows:
(P 1 ) min
x 1 ∈X 1
f 1 (x 1 , x 2 , . . . , x k )
M. Antoniou and P. Korošec
The first formulation of bilevel problem was documented in 1973 by Bracken
and McGill [3], and the definition of bilevel and multilevel programming was
used for the first time some years later by Candler and Norton in [4]. Since
then, both classical and evolutionary optimisation communities have studied bilevel
optimisation problems. These problems are intrinsically difficult to solve, so it is no
surprise that most of the proposed solution methods are either computationally very
expensive or applicable only to the simplest cases of bilevel optimisation problems
that have some nice mathematical properties [5].
One can find in literature the usage of multilevel optimisation referring to an
optimisation approach. While multilevel optimisation problems present a hierarchy
in the way the decision-solutions are taken, the multilevel paradigm is used to
describe the approach in optimisation that presents a hierarchy in the procedure
of the optimisation. The most common practice of solving an optimisation problem
is computing/evaluating solutions in some iterative process. In many applications,
such as in engineering, FEM or CFD computations, this can become really
expensive in terms of computational time. With the multilevel approach, one targets
into the minimisation of the expensive evaluations, by allowing for less accurate
computing by using computationally cheaper models of the problem or by reducing
solutions search space that needs to be explored. Both approaches heavily depend on
managing the balance between accuracy and computational time, so the best results
are achieved in a shorter time. The general multilevel strategy can be found in the
literature with several names and definitions. Though there are some differences in a
couple of aspects of each word, the main idea of the hierarchical method is the same.
Therefore, we can say that multilevel can be also found as multi-fidelity, multi-scale,
multi-grid or multistage optimisation approaches. Much more on this topic a reader
can find in [6–12].
In the following sections, we will focus only on multilevel and bilevel problems
by giving definitions, presenting a simple example of a linear bilevel optimisation
and its comparison to biobjective optimisation. Also, special cases of bilevel
problems are shown, providing an idea to the reader on how multilevel problems can
be found and/or formulated in different applications. Moreover, the main solution
algorithms with a special reference to metaheuristic solution methods found in the
literature are presented. The chapter ends by giving some examples of applications
solved as bilevel optimisation problems.
9.2 Multilevel Optimisation Problem
In the following of the chapter, we will consider minimisation problems without the
loss of generality since min = −max. The general multilevel optimisation problem
(P ) can be formulated as follows:
(P 1 ) min
x 1 ∈X 1
f 1 (x 1 , x 2 , . . . , x k )