Optimisation over the efficient set of a multi-objective optimisation problem

Add to your list(s) Download to your calendar using vCal

• Zhengliang Liu (School of Mathematics, University of Birmingham)
• Thursday 05 October 2017, 12:00-13:00
• G13, Arts Building.

If you have a question about this talk, please contact Sergey Sergeev.

Optimisation over the efficient set of a multi-objective optimisation problem is a mathematical model for the problem of selecting a most preferred solution that arises in multiple criteria decision making to account for trade-offs between objectives within the set of efficient solutions. In this study we consider a particular case of this problem, namely that of optimising a linear function over the image of the efficient set in objective space of a convex multi-objective optimisation problem. We present both primal and dual algorithms for this task. The algorithms are based on recent algorithms for solving convex multi-objective optimisation problems in objective space with suitable modifications to exploit specific properties of the problem of optimisation over the efficient set. We first present the algorithms for the case that the underlying problem is a multi-objective linear programme. We then extend them to be able to solve problems with an underlying convex multi-objective optimisation problem. We compare the new algorithms with several state of the art algorithms from the literature on a set of randomly generated instances to demonstrate that they are considerably faster than the competitors.

We then apply the primal and dual algorithms to compute the nadir point of a multi-objective linear programme. The nadir point is the vector consisting of the worst values the individual objective functions attain over the non-dominated set of the multi-objective linear programme. Its knowledge is important for multiple criteria decision making, but its exact determination is difficult, hence few exact algorithms to compute it exist. We compare the performance of the primal and dual algorithms to the two known exact methods from the literature, namely the algorithm of Ehrgott and Tenfelde-Podehl (2003) and the algorithm of Alves and Costa (2009). It turns out that the dimension reduction in the algorithm of Ehrgott and Tenfelde-Podehl is the decisive factor in this comparison and explains its superior performance.

This talk is part of the Optimisation and Numerical Analysis Seminars series.

This talk is included in these lists:

• G13, Arts Building
• Optimisation and Numerical Analysis Seminars
• School of Mathematics events

Note that ex-directory lists are not shown.