9 Multilevel Optimisation
323
9.6.1 Classical Approaches
Well-behaved bilevel optimisation problems are formulated in the literature in
order to be solved with classical approaches, due to their inherent complexity.
Assumptions about the nature of the equations, such as that they are linear, quadratic
or convex, are made. The main classical approaches are listed, along with some
references for the reader that wants to find out more about the topic, as a more
detailed report of them is out of the scope of this chapter.
• Single-level reduction [16]
• Smoothing methods [16]
• Descent algorithm [41]
• Penalty methods [42]
• A trust region method [43]
9.6.2 Metaheuristic Approaches
Many metaheuristics algorithms have been so far applied to bilevel optimisation,
with most of the approaches using nested strategies. Evolutionary algorithms
(EAs), a popular subset of metaheuristics, are an efficient way of solving bilevel
optimisation problems since no implementable mathematical optimality conditions
exist [44]. To use classical numerical optimisation methods, various simplifying
assumptions are made, such as continuity, differentiability and convexity of the
problem. These assumptions though do not represent most of the real-world
problems. EA’s population-based approach, along with the flexibility of its operators
and without the need for simplifying the objective functions, leads to acquiring
better solutions of the BOPs [45]. Most of the times, the solutions of the lower/upper
level are multimodal, making the use of surrogate modeling very promising, since
a simpler approximation of the problem is solved, making the procedure faster [5].
Last but not the least, many bilevel optimisation problems are multiobjective, where
both levels require to find and maintain multiple optimal solutions, and EAs are
known to be good for these cases [19]. According to the classification of Sinha et al.
[5] and Talbi [22], the metaheuristic approaches can be categorised as follows:
• Nested methods: the lower level optimisation problem is solved in a nested way,
meaning that for each upper level solution, a lower level solution is obtained
and evaluates the solutions generated at the upper level of the BOP. In nested
strategies for every upper level solution, a lower level optimisation task is
executed, as seen in Fig. 9.8. This usually means that they are computationally
expensive and not practical for large-scale bilevel optimisation problems. We
refer the reader to the following papers [46, 47] for more detailed information.
• Single-level reduction: the BOP is reduced into a single-level optimisation
problem, and then any traditional evolutionary algorithm can be used to solve the
323
9.6.1 Classical Approaches
Well-behaved bilevel optimisation problems are formulated in the literature in
order to be solved with classical approaches, due to their inherent complexity.
Assumptions about the nature of the equations, such as that they are linear, quadratic
or convex, are made. The main classical approaches are listed, along with some
references for the reader that wants to find out more about the topic, as a more
detailed report of them is out of the scope of this chapter.
• Single-level reduction [16]
• Smoothing methods [16]
• Descent algorithm [41]
• Penalty methods [42]
• A trust region method [43]
9.6.2 Metaheuristic Approaches
Many metaheuristics algorithms have been so far applied to bilevel optimisation,
with most of the approaches using nested strategies. Evolutionary algorithms
(EAs), a popular subset of metaheuristics, are an efficient way of solving bilevel
optimisation problems since no implementable mathematical optimality conditions
exist [44]. To use classical numerical optimisation methods, various simplifying
assumptions are made, such as continuity, differentiability and convexity of the
problem. These assumptions though do not represent most of the real-world
problems. EA’s population-based approach, along with the flexibility of its operators
and without the need for simplifying the objective functions, leads to acquiring
better solutions of the BOPs [45]. Most of the times, the solutions of the lower/upper
level are multimodal, making the use of surrogate modeling very promising, since
a simpler approximation of the problem is solved, making the procedure faster [5].
Last but not the least, many bilevel optimisation problems are multiobjective, where
both levels require to find and maintain multiple optimal solutions, and EAs are
known to be good for these cases [19]. According to the classification of Sinha et al.
[5] and Talbi [22], the metaheuristic approaches can be categorised as follows:
• Nested methods: the lower level optimisation problem is solved in a nested way,
meaning that for each upper level solution, a lower level solution is obtained
and evaluates the solutions generated at the upper level of the BOP. In nested
strategies for every upper level solution, a lower level optimisation task is
executed, as seen in Fig. 9.8. This usually means that they are computationally
expensive and not practical for large-scale bilevel optimisation problems. We
refer the reader to the following papers [46, 47] for more detailed information.
• Single-level reduction: the BOP is reduced into a single-level optimisation
problem, and then any traditional evolutionary algorithm can be used to solve the