9 Multilevel Optimisation
315
where F and f are the two objectives to be optimised, x and y are the decision
variables, and G and g are the constraints of the first and second objectives,
respectively. In single-objective optimisation problems, relations between solutions
(better/worse) are easily determined through comparison of their objective values. In
biobjective optimisation, this is not so obvious. Here the superiority of the solutions
is determined by the dominance. According to [1], a solution x 1 is said to dominate
x 2 solution, if solution x 1 is no worse than x 2 in all objectives and solution x 1
is strictly better than x 2 in at least one objective. Given this definition, the nondominated set of solutions in the feasible region 1 is called the Pareto-optimal set,
and the boundary marked of the solution objectives values of this set is called Paretooptimal front.
Many researchers tried to investigate the relationship between the bilevel and
biobjective optimisation problem [20, 21]. It has been shown that, while in some
special cases and examples the BOP can be formulated as a biobjective optimisation
problem and results can be found that way, there are no conditions that an optimal
solution of a BOP is in the Pareto-optimal front of its equivalent biobjective
optimisation problem.
For better understanding the differences between the two problems a comparison
of the two different problems are made, inspired by Talbi in [22], using the
example from the previous section. We will show that a BOP does not necessarily
have an equivalent corresponding biobjective problem composed of the upper
level and the lower level objectives. Consequently, the optimal solution of the
BOP is not automatically a Pareto-optimal solution of the biobjective problem
and vice versa. For this reason, finding a solution by reformulating the bilevel as
biobjective optimisation problem and using the Pareto dominance will not work.
Let us reformulate the previous bilevel problem as a biobjective one as follows:
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩
min
x≥0
F (x, y) = x − 8y
min
y≥0
f (y) = y
subject to
− x − y ≤ −4
−x + y ≤ 0
3x + y ≤ 10
−3x + 2y ≥ −3
,
(9.3)
where F and f are the previous upper and lower level objectives, but now they are
optimised independently and on a single level.
In Fig. 9.4, a scatterplot of the feasible decision space of the biobjective problem
is shown. It is obvious that the feasible space is formulating a trapezium, identical
to the one in the bilevel example. Figure 9.5 is a scatterplot of the corresponding
1 Feasible region is consisting of the set of all solutions that satisfy all the constraints.
315
where F and f are the two objectives to be optimised, x and y are the decision
variables, and G and g are the constraints of the first and second objectives,
respectively. In single-objective optimisation problems, relations between solutions
(better/worse) are easily determined through comparison of their objective values. In
biobjective optimisation, this is not so obvious. Here the superiority of the solutions
is determined by the dominance. According to [1], a solution x 1 is said to dominate
x 2 solution, if solution x 1 is no worse than x 2 in all objectives and solution x 1
is strictly better than x 2 in at least one objective. Given this definition, the nondominated set of solutions in the feasible region 1 is called the Pareto-optimal set,
and the boundary marked of the solution objectives values of this set is called Paretooptimal front.
Many researchers tried to investigate the relationship between the bilevel and
biobjective optimisation problem [20, 21]. It has been shown that, while in some
special cases and examples the BOP can be formulated as a biobjective optimisation
problem and results can be found that way, there are no conditions that an optimal
solution of a BOP is in the Pareto-optimal front of its equivalent biobjective
optimisation problem.
For better understanding the differences between the two problems a comparison
of the two different problems are made, inspired by Talbi in [22], using the
example from the previous section. We will show that a BOP does not necessarily
have an equivalent corresponding biobjective problem composed of the upper
level and the lower level objectives. Consequently, the optimal solution of the
BOP is not automatically a Pareto-optimal solution of the biobjective problem
and vice versa. For this reason, finding a solution by reformulating the bilevel as
biobjective optimisation problem and using the Pareto dominance will not work.
Let us reformulate the previous bilevel problem as a biobjective one as follows:
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩
min
x≥0
F (x, y) = x − 8y
min
y≥0
f (y) = y
subject to
− x − y ≤ −4
−x + y ≤ 0
3x + y ≤ 10
−3x + 2y ≥ −3
,
(9.3)
where F and f are the previous upper and lower level objectives, but now they are
optimised independently and on a single level.
In Fig. 9.4, a scatterplot of the feasible decision space of the biobjective problem
is shown. It is obvious that the feasible space is formulating a trapezium, identical
to the one in the bilevel example. Figure 9.5 is a scatterplot of the corresponding
1 Feasible region is consisting of the set of all solutions that satisfy all the constraints.