General approximation methods for multicriteria optimization problems

点击翻译按钮获取中文摘要

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, our proposal aims at developing approximation methods for multicriteria optimization problems that (1) are applicable under weak assumptions, (2) yield a provably good approximation quality, and (3) possess a provable worst-case running time. The applicants contribute to this goal with their complementary skills in multicriteria optimization and approximation algorithms and are able to build on joint previous work. 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 our proposal 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.