Wednesday, 13:20-14:50

“Interdiction Models for Robust Combinatorial Optimization” Mohammad Khosravi, Marc Goerigk

Uncertainty can affect a problem in many forms, be it as imprecise data or because the future is impossible to know. To capture what scenarios can possibly occur, robust optimization approaches require uncertainty sets as a main ingredient. In this study we consider a new type of uncertainty set, applicable to objectives or constraints that involve the L1 norm of the solution, for example to problems where the task is to maximize the size of a set or where this cardinality is not allowed to fall below a certain threshold. The uncertainty set that affects these cardinality terms is defined by a knapsack constraint. We refer to this setting as robust optimization with bounded interdiction. We consider both real-world applications and the theoretical complexity of this model. We introduce different models and solution algorithms using various techniques, including dynamic programming.

Wednesday, 13:20-14:50

“Towards Robust Interpretable Optimization” Sebastian Merten, Marc Goerigk, Michael Hartisch

An important factor in the practical implementation of optimization models is the acceptance by the intended users. This is influenced among other factors by the interpretability of the solution process. Decision rules that meet this requirement can be generated using the framework for inherently interpretable optimization models. Furthermore, in practice there is often uncertainty about the parameters of an optimization problem. An established way to deal with this adversity is the concept of robust optimization. The goal of our work is to combine both concepts to create decision trees for a given optimization problem that are more robust to perturbations and still inherently interpretable. For this purpose, we present a suitable model and solution methods. Furthermore, the applicability of heuristic methods to perform this task is evaluated. Both approaches are compared with the existing framework for inherently interpretable optimization models and tests on real-world data are performed.

Thursday, 8:30-10:00

“OWA Regret: A Novel Approach for Decision Making” Werner Baak, Marc Goerigk

In this talk, we introduce a novel approach for decision making called OWA Regret, which combines the well-known ordered weighted averaging (OWA) method with min-max regret. We demonstrate how this approach can be applied to discrete scenarios and show that it can be approximated using clustering algorithms. To evaluate the effectiveness of OWA Regret, we conduct two experiments: a selection problem with synthetic variables and a shortest path experiment based on real data from Chicago’s street network. Our results show that OWA Regret provides a balanced trade-off between regret and OWA criteria. Specifically, we observe that OWA Regret is equivalent to Regret for very conservative weights and equivalent to OWA for very risk-neutral weights.

Thursday, 12:50-14:20

“Robust optimization with belief functions” Marc Goerigk, Romain Guillaume, Adam Kasperski, Pawel Zielinski

We consider optimization problems with an uncertain objective function, where the uncertainty is specified by providing a discrete scenario set. In an alternative setting to classic distributionally robust approaches, the concept of belief functions in the traditional and possibilistic setting is applied to define a set of admissible probability distributions over the scenario set. The generalized Hurwicz criterion is then used to compute a solution. The complexity of the resulting problem is explored, and some exact and approximation methods of solving it are proposed.