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.