Relative Robust and Adaptive Optimization

Robust optimization has emerged in the operations research literature as a tractable and practical way to model uncertainty in optimization problems. Early approaches focused on relative worst-case objective functions, where the value of a solution is measured versus the best-possible solution over an uncertainty set of scenarios. However, over the past ten years the focus has primarily been on absolute worst-case objective functions, which have generally been considered to be more tractable. In this paper, we demonstrate that for many problems of interest, including some adaptive robust optimization problems, that considering relative objective functions does not significantly increase the computational cost over absolute objective functions. We use combinations of absolute and relative worst-case objective functions to find Pareto-efficient solutions that combine aspects of both, which suggests an approach to distinguish between otherwise very similar robust solutions. We provide reformulation and cutting plane approaches for these problems and demonstrate their efficacy with experiments on minimum-cost flow, inventory control, and facility location problems. These case studies show that solutions corresponding to relative objective functions may be a better match for a decision maker’s risk preferences than absolute.