Approximation Methods for Multiobjective Optimization Problems: A Survey

Arne Herzel (), Stefan Ruzika () and Clemens Thielen ()
Additional contact information
Arne Herzel: Department of Mathematics, University of Kaiserslautern, D-67663 Kaiserslautern, Germany
Stefan Ruzika: Department of Mathematics, University of Kaiserslautern, D-67663 Kaiserslautern, Germany
Clemens Thielen: TUM Campus Straubing, Technical University of Munich, D-94315 Straubing, Germany

INFORMS Journal on Computing, 2021, vol. 33, issue 4, 1284-1299

Abstract: Algorithms for approximating the nondominated set of multiobjective optimization problems are reviewed. The approaches are categorized into general methods that are applicable under mild assumptions and, thus, to a wide range of problems, and into algorithms that are specifically tailored to structured problems. All in all, this survey covers 52 articles published within the last 41 years, that is, between 1979 and 2020. Summary of Contribution: In many problems in operations research, several conflicting objective functions have to be optimized simultaneously, and one is interested in finding Pareto optimal solutions. Because of the high complexity of finding Pareto optimal solutions and their usually very large number, however, the exact solution of such multiobjective problems is often very difficult, which motivates the study of approximation algorithms for multiobjective optimization problems. This research area uses techniques and methods from algorithmics and computing in order to efficiently determine approximate solutions to many well-known multiobjective problems from operations research. Even though approximation algorithms for multiobjective optimization problems have been investigated for more than 40 years and more than 50 research articles have been published on this topic, this paper provides the first survey of this important area at the intersection of computing and operations research.

Keywords: multiobjective optimization; approximation algorithm; approximate Pareto set; survey (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2020.1028 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:33:y:2021:i:4:p:1284-1299

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().