Inner approximation algorithm for solving linear multiobjective optimization problems. (3rd July 2021)

• Record Type: Journal Article
• Authors: Csirmaz, Laszlo
• Is Part Of: Optimization. Volume 70:Number 7(2021)
• Page Start: 1487
• Page End: 1511
• Publication Date: 2021-07-03
• Subjects: Multiobjective optimization -- duality -- vertex enumeration -- double description -- objective space; 90C29 -- 90C05; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2020.1737692
• Languages: English
• ISSNs: 0233-1934

Abstract

ABSTRACT: Benson's outer approximation algorithm and its variants are the most frequently used methods for solving linear multiobjective optimization problems. These algorithms have two intertwined parts: single-objective linear optimization on one hand, and a combinatorial part closely related to vertex enumeration on the other. Their separation provides a deeper insight into Benson's algorithm, and points toward a dual approach. Two skeletal algorithms are defined which focus on the combinatorial part. Using different single-objective optimization problems yields different algorithms, such as a sequential convex hull algorithm, another version of Benson's algorithm with the theoretically best possible iteration count, and the dual algorithm of Ehrgott et al. [A dual variant of Benson's 'outer approximation algorithm' for multiple objective linear programming. J Glob Optim. 2012;52:757–778]. The implemented version is well suited to handle highly degenerate problems where there are many linear dependencies among the constraints. On problems with 10 or more objectives, it shows a significant increase in efficiency compared to Bensolve – due to the reduced number of iterations and the improved combinatorial handling.