Back to Search
Start Over
Inner approximation algorithm for solving linear multiobjective optimization problems.
- Source :
-
Optimization . Jul2021, Vol. 70 Issue 7, p1487-1511. 25p. - Publication Year :
- 2021
-
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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *APPROXIMATION algorithms
*ALGORITHMS
*LINEAR programming
Subjects
Details
- Language :
- English
- ISSN :
- 02331934
- Volume :
- 70
- Issue :
- 7
- Database :
- Academic Search Index
- Journal :
- Optimization
- Publication Type :
- Academic Journal
- Accession number :
- 151190605
- Full Text :
- https://doi.org/10.1080/02331934.2020.1737692