Primal and dual algorithms for optimization over the efficient set. (3rd October 2018)

• Record Type: Journal Article
• Authors: Liu, Zhengliang; Ehrgott, Matthias
• Is Part Of: Optimization. Volume 67:Number 10(2018)
• Page Start: 1661
• Page End: 1686
• Publication Date: 2018-10-03
• Subjects: Multi-objective optimization -- optimization over the efficient set -- objective space algorithm -- duality; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2018.1484922
• Languages: English
• ISSNs: 0233-1934

Abstract

ABSTRACT: Optimization over the efficient set of a multi-objective optimization 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 paper, we consider a particular case of this problem, namely that of optimizing a linear function over the image of the efficient set in objective space of a convex multi-objective optimization problem. We present both primal and dual algorithms for this task. The algorithms are based on recent algorithms for solving convex multi-objective optimization problems in objective space with suitable modifications to exploit specific properties of the problem of optimization 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 optimization 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.