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

• Applicant: Professor Dr. Marc Goerigk
• Subject Area: Accounting and Finance ; Theoretical Computer Science
• Term: since 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 448792059

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.

• DFG Programme: Research Grants