Min-Max Regret Problems with Ellipsoidal Uncertainty Sets

Andre and me just completed a new paper, see this arXiv link.

We look at min-max regret problems, that is, computationally challenging robust counterparts of uncertain problems. Typically, these problems are solved using very simple descriptions of the parameter uncertainty. For example, using an interval of possible outcomes for every coefficient, there are some nice tricks to reformulate the problem and to solve it relatively quickly.

But interval uncertainty sets are note very flexible and do not offer much possibilities to capture real-life requirements of  optimisation models. In this paper, we consider the more complex case of ellipsoidal uncertainty sets. We give a thorough discussion of problem complexities for the robust counterparts of the unconstrained and the shortest path problem, and show how to solve these kinds of problems.

This is the abstract:

We consider robust counterparts of uncertain combinatorial optimizationproblems, where the difference to the best possible solution over all scenarios is to be minimized. Such minmax regret problems are typically harder to solve than their nominal, non-robust counterparts. While current literature almost exclusively focuses on simple uncertainty sets that are either finite or hyperboxes, we consider problems with more flexible and realistic ellipsoidal uncertainty sets. We present complexity results for the unconstrained combinatorial optimization problem and for the shortest path problem. To solve such problems, two types of cuts are introduced, and compared in a computational experiment.