Multiobjective combinatorial optimization in higher dimensions

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

When solving optimization problems arising in technical and economical applications, there is often a need to consider several conflicting objective functions, complicating constraints, and/or uncertainties. Multiobjective models can represent such complex decision making situations by providing trade-off information and compromising between different goals and constraints. Examples for multiobjective combinatorial optimization problems are multiobjective knapsack problems, multiobjective assignment problems, and multiobjective network optimization problems like, for example, shortest path and spanning tree problems.The complexity of multiobjective combinatorial optimization problems depends largely on the number of considered objective functions. While the Pareto front of biobjective problems can be completely ordered - when one objective increases, then the other decreases and vice versa - this is no longer possible starting from three objectives. As a consequence, not only the number of nondominated solutions explodes, but also the complexity of the Pareto set and of its description increases drastically. In this project, the geometrical and combinatorial structure of the Pareto set will be used to achieve a new level of understanding for higher-dimensional problems. This includes the determination of representative subsets as well as the development of multiobjective branch and bound algorithms and the analysis of different preference structures and quality indicators.