Efficient Algorithm For Solving Robust Counterparts Of LP Problems Under Budgeted Uncertainty

Abstract

We consider the case of an uncertain linear optimization problem subject to budgeted uncertainty, meaning the uncertain parameters are dependent. Such uncertainty occurs in many real-life scenarios. Moreover, it is used in a standard approximation of scalar chance constraints. To create a tractable robust counterpart for the case of budgeted uncertainty we need to introduce many additional variables and constraints to the original problem, which may render it too large. However, many of these are typically inactive at the optimal robust solution. We present a simplex based algorithm that finds an optimal robust solution with minimal number of additional variables and constraints.