Adjustable Robust Optimization Reformulations of Two-Stage Worst-Case Regret Minimization Problems

Although the stochastic optimization paradigm exploits probability theory to optimize the tradeoff between risk and returns, robust optimization has gained significant popularity by reducing computation requirements through the optimization of the worst-case scenario in a set. An appealing alternative to stochastic and robust optimization consists in optimizing decisions using the notion of regret. Although regret minimization models are generally perceived as leading to less conservative decisions than those produced by robust optimization, their numerical optimization is a real challenge in general. In “Adjustable Robust Optimization Reformulations of Two-Stage Worst-case Regret Minimization Problems,” M. Poursoltani and E. Delage show how to reduce a two-stage worst-case absolute/relative regret minimization problem to a two-stage robust optimization one. This opens the way for taking advantage of recent advanced approximate and exact solution schemes for these hard problems. Their experiments corroborate the high-quality performance of affine decision rules as a popular polynomial-time approximation scheme, from which, under mild conditions, one can even expect exact regret-averse decisions.