General Approximation Methods for Multicriteria Optimization Problems
The project "General Approximation Methods for Multicriteria Optimization Problems" is funded by the Deutsche Forschungsgesellschaft (DFG) from 01st June 2018 to 31st May 2021
In many optimization problems, several incommensurable objective functions are to be optimized simultaneously. Such multicriteria optimization problems are based on optimality concepts that are induced by ordering relations. The predominant concept is the concept of Pareto optimality, which characterizes optimal solutions as minima (or maxima) with respect to the componentwise ordering. For many optimization problems, however, the set of Pareto-optimal solutions and the corresponding image set are very large and very difficult to compute exactly. Hence, this project aims at developing approximation methods for multicriteria optimization problems that
- are applicable under weak assumptions,
- yield a provably good approximation quality, and
- possess a provable worst-case running time.
It is known that several of the existing methods for approximating multicriteria minimization problems cannot be transferred to maximization problems. Minimization and maximization problems require substantially different techniques. Additionally, the concept of Pareto optimality implies a significant difference in the level of difficulty between bicriteria problems and general multicriteria optimization problems. The structure of the project takes these findings into account and distinguishes between minimization and maximization problems as well as between problems with two and problems with more than two objective functions.
Upon completion of this project, general approximation methods for these optimization problems will be ready to use. Moreover, the relationship among several single-criterion problems (belonging, e.g., to the fields of robust optimization, parametric optimization, or budget-constrained optimization) and related multicriteria problems will be studied and better understood. Thus, on the one hand, we aim at developing a “provably good” alternative to the current exact and heuristic methods for multicriteria optimization problems and, on the other hand, we intend to contribute significantly to the state-of-the-art in the theory of mathematical programming.