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.