OWA Regret – Decision Making beyond Ordered Weighted Averaging and Min-Max Regret

决策无处不在，但很少有保证最佳解决方案所需的所有信息可用。在不确定情况下的决策中，我们考虑多个结果的情况，其中概率分布是未知的。当使用历史数据时，自然会出现这样的问题。如果不是所有的备选方案都以明确的列表给出，而是用一组隐含的约束来描述，那么决策过程就会变得更加困难。例如，在路线规划中，可能有许多潜在的指数级路径需要考虑。对所有这些问题进行评估需要太长时间。在这个项目中，我们考虑了这类所谓的组合问题，其中所有的决策变量都是二进制的，在研究文献中已经提出并分析了许多选择方案的准则。不幸的是，事实证明，从公理的角度来看，不可能存在单一的最佳决策标准。两个常用的标准是最小-最大遗憾和有序加权平均(OWA)方法。在第一个设置中，我们确定每个场景下的最优目标值。然后选择一个备选方案，其中对应的目标值与最佳值的最大差异在所有情况下都尽可能小。在第二种方法中，我们使用一个权重向量来控制保守性的程度。对于每个备选方案，我们计算所有方案的目标值向量，对该向量进行排序，并计算带有权重向量的标量积。这包括仅针对最坏情况(稳健优化)、平均情况甚至最好情况进行优化的极端方法。在本项目中，我们考虑了这两种方法的一种新的组合，其中OWA算子被应用于目标值差异的向量。这意味着，不只是最大限度地减少遗憾，而是各种不那么保守的OWA后悔方法成为可能。此设置尚未针对组合问题进行分析。我们对这种方法进行建模，了解其复杂性和逼近性，开发启发式和精确求解算法，并使用真实世界的数据对其进行评估。由于最小-最大遗憾和OWA组合优化都是当前研究的热点，本课题的研究成果将对不确定性社区下的优化问题产生重大影响，并为在实践中寻找更好的决策打开了新的大门。

Decision making is ubiquitous, but only seldom is all information available that is required to guarantee an optimal solution. In decision making under uncertainty, we consider the case of multiple outcomes, where no probability distribution is known. Such problems naturally arise when using historical data.The decision making process is made more difficult if not all alternatives are given in an explicit list, but instead described by an implicit set of constraints. In route planning, for example, there are potentially exponentially many paths that would need consideration. To evaluate all of them takes too long. In this project we consider so-called combinatorial problems of this type, where all decision variables are binary.Many criteria which alternative to choose have been proposed and analyzed in the research literature. Unfortunately it turns out that there cannot be a single best decision criterion from an axiomatic point of view. Two criteria frequently used are the min-max regret and the ordered weighted averaging (OWA) approaches. In the first setting, we determine an optimal objective value under every scenario. When then choose an alternative where the largest difference of the corresponding objective value to the optimal value is as small as possible over all scenarios. In the second approach, we use a weight vector that controls the degree of conservatism. For each alternative, we calculate the vector of objective values over all scenarios, sort this vector, and calculate the scalar product with the weight vector. This includes the extreme approaches of only optimizing with respect to the worst case (robust optimization), the average case, or even the best case.In this project we consider a novel combination of these two approaches, where the OWA operator is applied to the vector of objective value differences. This means that instead of minimizing only the maximum regret, a variety of less conservative OWA regret approaches become possible. This setting has not been analyzed for combinatorial problems. We model this approach, understand its complexity and approximability, develop heuristic and exact solution algorithms, and evaluate it using real-world data. Additionally, we extend this approach from discrete uncertainty sets to interval-based uncertainty.As both min-max regret and OWA combinatorial optimization are active fields of research, the results developed in this project will have a major impact in the optimization under uncertainty community, and open new doors to finding good decisions in practice.