论文标题
通过多目标重新构造的顺序优化
Ordinal Optimization Through Multi-objective Reformulation
论文作者
论文摘要
我们分析了与序数（即非加addive的目标函数）分析组合优化问题，这些功能将类别（如好，中和坏）分配给可行解决方案元素的成本系数。我们回顾了不同的最佳概念，以解决序数优化问题，并讨论其相似性和差异。然后，我们专注于两个普遍的最佳概念，这些概念被证明是等效的。我们的主要结果是一种双线性线性转化，将顺序优化问题转化为与二进制成本系数的相关标准多目标优化问题。由于这种转换保留了基本问题的所有属性，因此特定于问题的解决方案方法仍然适用。一个突出的例子是动态编程和Bellman的最佳原理，例如，可以应用于序数最短路径和序数背包问题。我们将结果扩展到结合了序数和实现目标函数的多目标优化问题。
We analyze combinatorial optimization problems with ordinal, i.e., non-additive, objective functions that assign categories (like good, medium and bad) rather than cost coefficients to the elements of feasible solutions. We review different optimality concepts for ordinal optimization problems and discuss their similarities and differences. We then focus on two prevalent optimality concepts that are shown to be equivalent. Our main result is a bijective linear transformation that transforms ordinal optimization problems to associated standard multi-objective optimization problems with binary cost coefficients. Since this transformation preserves all properties of the underlying problem, problem-specific solution methods remain applicable. A prominent example is dynamic programming and Bellman's principle of optimality, that can be applied, e.g., to ordinal shortest path and ordinal knapsack problems. We extend our results to multi-objective optimization problems that combine ordinal and real-valued objective functions.
